+3.0 microsecond for iterating empty vectors

[krbyxtrm]

hello i have this profile for iterating empty vectors:
+0.3us (microsecond) on intel pentium 2.4Ghz

can this added delay to my application be reduced?
i mean near zero delay, its very important.

BTW,
does anyone has another profile for this?

thanks.

[benben]

krbyxtrm wrote:

hello i have this profile for iterating empty vectors:
+0.3us (microsecond) on intel pentium 2.4Ghz

can this added delay to my application be reduced?
i mean near zero delay, its very important.

BTW,
does anyone has another profile for this?

thanks.

if (v.size() > 0)
{
// iterate v here
}

[Ivan Vecerina]

"krbyxtrm" <kr******@gmail.com> wrote in message
news:11*********************@j33g2000cwa.googlegro ups.com...
: hello i have this profile for iterating empty vectors:
: +0.3us (microsecond) on intel pentium 2.4Ghz
:
: can this added delay to my application be reduced?
: i mean near zero delay, its very important.

If timing is so important, you should look into your
implementation of std::vector. Some current platforms
come with a standard library that is debug-enabled
by default -- making a number of redundant checks on
all iterators, etc. Read your documentation and find
out how to switch this off (usually with a #define...).

Are you compiling your code with inlining and
optimizations on ?

: BTW,
: does anyone has another profile for this?

Rarely do people need to care. But when it actually
makes sense, yes.

Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
Brainbench MVP for C++ <> http://www.brainbench.com

[Phlip]

krbyxtrm wrote:

hello i have this profile for iterating empty vectors:
+0.3us (microsecond) on intel pentium 2.4Ghz

How did you measure the time? You might have accidentally detected the
quanta of your task scheduler.

Put the test code inside a loop statement that counts to a million, record
wall-clock time, subtract, and divide to get a better measurement.

More advanced systems to measure the time are off-topic...

--
Phlip
http://c2.com/cgi/wiki?ZeekLand <-- NOT a blog!!!

[Mathias Waack]

benben wrote:

krbyxtrm wrote:

hello i have this profile for iterating empty vectors:
+0.3us (microsecond) on intel pentium 2.4Ghz

can this added delay to my application be reduced?
i mean near zero delay, its very important.

BTW,
does anyone has another profile for this?

thanks.

if (v.size() > 0)
{
// iterate v here
}

v.size() needs to calculate the amount of records in v - which could
be very time consuming, depending on implementation and size of v.
Its better to use !v.empty() for this purpose.

Mathias

[peter koch]

Mathias Waack skrev:

benben wrote:

krbyxtrm wrote:

hello i have this profile for iterating empty vectors:
+0.3us (microsecond) on intel pentium 2.4Ghz

can this added delay to my application be reduced?
i mean near zero delay, its very important.

BTW,
does anyone has another profile for this?

thanks.

if (v.size() > 0)
{
// iterate v here
}

v.size() needs to calculate the amount of records in v - which could
be very time consuming, depending on implementation and size of v.
Its better to use !v.empty() for this purpose.

We are talking about std::vector here so O(1) is guaranteed. I also
believe that size() is amortized O(1) in the general case.

/Peter
Mathias

[peter koch]

krbyxtrm skrev:

hello i have this profile for iterating empty vectors:
+0.3us (microsecond) on intel pentium 2.4Ghz

can this added delay to my application be reduced?
i mean near zero delay, its very important.

BTW,
does anyone has another profile for this?

thanks.

First of all, I'd check the code and see what is going on. The overhead
of the loop is two calls (to begin and end), two assignments (to the
loopvariable and the endvariable) and one comparison. Roughly put, you
could at best reduce this with a factor of five (by calling size() or
empty()). In real life you will not get that speed-up as e.g. empty
most likely will be implemented like begin() == end(), thus only saving
two assignments.
In practical life, the by far most expensive operation is to get access
to the memory in the first place assuming that it is not already
cached.

/Peter

[krbyxtrm]

Ayon kay Mathias Waack:

benben wrote:

krbyxtrm wrote:

hello i have this profile for iterating empty vectors:
+0.3us (microsecond) on intel pentium 2.4Ghz

can this added delay to my application be reduced?
i mean near zero delay, its very important.

BTW,
does anyone has another profile for this?

thanks.

if (v.size() > 0)
{
// iterate v here
}

v.size() needs to calculate the amount of records in v - which could
be very time consuming, depending on implementation and size of v.
Its better to use !v.empty() for this purpose.

Mathias

yeah i think this saved some time, now the delay is +4e-2 ~ 5e-2 (from
previously 3e-1) for empty vectors.

[krbyxtrm]

hello people,
i have implemented my code this way

start = read_timer(); // for profiling
if ( !any_vec.empty() )
{

std::for_each(
any_vec.begin(),
any_vec.end(),
retrieve); // where retrieve is an empty function for now...
}
end = read_timer();
duration = end - start ; // minus counter error
with this code and having empty callback function,
it duration = 1.2e-1 us

maybe i will have to see some std::vector implemtation manual to check
whether i'm using a debug-enable version, as of now i have from
http://www.sgi.com/tech/stl/Vector.html
but it does not have what Ivan Vecerina is telling.

-k-

[krbyxtrm]

Ayon kay krbyxtrm:

hello people,
i have implemented my code this way

start = read_timer(); // for profiling
if ( !any_vec.empty() )
{

std::for_each(
any_vec.begin(),
any_vec.end(),
retrieve); // where retrieve is an empty function for now...
}
end = read_timer();
duration = end - start ; // minus counter error
with this code and having empty callback function,
it duration = 1.2e-1 us BTW, IS FOR VECTOR WITH 1 ELEMENT

maybe i will have to see some std::vector implemtation manual to check
whether i'm using a debug-enable version, as of now i have from
http://www.sgi.com/tech/stl/Vector.html
but it does not have what Ivan Vecerina is telling.

-k-

[Greg]

krbyxtrm wrote:

hello people,
i have implemented my code this way

start = read_timer(); // for profiling
if ( !any_vec.empty() )
{

std::for_each(
any_vec.begin(),
any_vec.end(),
retrieve); // where retrieve is an empty function for now...
}
end = read_timer();
duration = end - start ; // minus counter error
with this code and having empty callback function,
it duration = 1.2e-1 us

maybe i will have to see some std::vector implemtation manual to check
whether i'm using a debug-enable version, as of now i have from
http://www.sgi.com/tech/stl/Vector.html
but it does not have what Ivan Vecerina is telling.
How much time do you think these lines of code should reasonably take?
In other words, by what measure is the one-ten millionth of a second
being spent here too time-consuming?
From my own experience, optimizing any operation not measured in

milliseconds is probably not worthwhile. So unless the program intends
to execute this code 10,000 times in a row - and do so repeatedly -
then this kind of "bottom-up" optimization is unlikely to be
productive. What is needed is a "top-down" approach, in which the
entire program's execution is timed. It is necessary to account for all
of the time that a program spends executing, in order to know where
optimizations are likely to improve performance.

Greg

[Erik Wikström]

On 2006-05-26 02:55, krbyxtrm wrote:

Ayon kay krbyxtrm:

hello people,
i have implemented my code this way

start = read_timer(); // for profiling
if ( !any_vec.empty() )
{

std::for_each(
any_vec.begin(),
any_vec.end(),
retrieve); // where retrieve is an empty function for now...
}
end = read_timer();
duration = end - start ; // minus counter error
with this code and having empty callback function,
it duration = 1.2e-1 us

BTW, IS FOR VECTOR WITH 1 ELEMENT

It might be of interest to try with more elements, the increase in time
is not necessarily linear with the number of elements. Caches for
example can be a part of it, if you get a cache-miss on the first
element that will take some time, but the next element will be much
faster. To get good measures you should use more elements and run the
test many times and calculate the average.

Erik Wikström
--
"I have always wished for my computer to be as easy to use as my
telephone; my wish has come true because I can no longer figure
out how to use my telephone" -- Bjarne Stroustrup

[Markus Schoder]

peter koch wrote:

Mathias Waack skrev:

benben wrote:

krbyxtrm wrote:
> hello i have this profile for iterating empty vectors:
> +0.3us (microsecond) on intel pentium 2.4Ghz
>
> can this added delay to my application be reduced?
> i mean near zero delay, its very important.
>
> BTW,
> does anyone has another profile for this?
>
> thanks.
>

if (v.size() > 0)
{
// iterate v here
}

v.size() needs to calculate the amount of records in v - which could
be very time consuming, depending on implementation and size of v.
Its better to use !v.empty() for this purpose.

We are talking about std::vector here so O(1) is guaranteed. I also
believe that size() is amortized O(1) in the general case.

It is certainly not guaranteed for std::list. Actually gcc has an O(n)
implementation which is conforming.

[Jerry Coffin]

In article <1148555061.701178.51780@
38g2000cwa.googlegroups.com>, pe***************@gmail.com
says...

[ ... ]

v.size() needs to calculate the amount of records in v - which could
be very time consuming, depending on implementation and size of v.
Its better to use !v.empty() for this purpose.

We are talking about std::vector here so O(1) is guaranteed. I also
believe that size() is amortized O(1) in the general case.

For better or worse, this isn't quite true -- the
standard says that size() "should have constant
complexity" (Table 65, Note A), but I don't believe it
guarantees it for _any_ container.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[peter koch]

Jerry Coffin wrote:

In article <1148555061.701178.51780@
38g2000cwa.googlegroups.com>, pe***************@gmail.com
says...

[ ... ]

v.size() needs to calculate the amount of records in v - which could
be very time consuming, depending on implementation and size of v.
Its better to use !v.empty() for this purpose.

We are talking about std::vector here so O(1) is guaranteed. I also
believe that size() is amortized O(1) in the general case.

For better or worse, this isn't quite true -- the
standard says that size() "should have constant
complexity" (Table 65, Note A), but I don't believe it
guarantees it for _any_ container.

From a teoretical point, you are correct. But "should" is a strong

encouragement and combined with the other requirements for std::vector
you would have some difficulties finding an implementation where size()
is not O(1).
Apart from that using empty() is clearer for the reader of the code
(although the name should have been is_empty()).

/Peter

[Jerry Coffin]

In article <1148729865.862340.147700
@j33g2000cwa.googlegroups.com>,
pe***************@gmail.com says...

[ size() "should" be constant complexity ... ]

From a teoretical point, you are correct. But "should" is a strong

encouragement and combined with the other requirements for std::vector
you would have some difficulties finding an implementation where size()
is not O(1).

That is almost certainly true. OTOH, the table in
question applies equally to all containers. In some cases
(e.g. std::list) it's _possible_ to make it constant
complexity, but only at considerable expense in other
areas (e.g. splicing two lists together becomes linear
rather than constant complexity).

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Erik Wikström]

On 2006-05-27 15:17, Jerry Coffin wrote:

In article <1148729865.862340.147700
@j33g2000cwa.googlegroups.com>,
pe***************@gmail.com says...

[ size() "should" be constant complexity ... ]

>From a teoretical point, you are correct. But "should" is a strong

encouragement and combined with the other requirements for std::vector
you would have some difficulties finding an implementation where size()
is not O(1).

That is almost certainly true. OTOH, the table in
question applies equally to all containers. In some cases
(e.g. std::list) it's _possible_ to make it constant
complexity, but only at considerable expense in other
areas (e.g. splicing two lists together becomes linear
rather than constant complexity).

What is it I'm missing here? AFAIK size() returns the number of elements
stored in the container, thus one could easily implement it with a
variable containing the value which is updated whenever an element is
inserted/removed from the container. How does that affect the time it
takes to splice two lists, all you have to do is add the size of both of
them.

Erik Wikström
--
"I have always wished for my computer to be as easy to use as my
telephone; my wish has come true because I can no longer figure
out how to use my telephone" -- Bjarne Stroustrup

[Bo Persson]

"Erik Wikström" <Er***********@telia.com> skrev i meddelandet
news:rl****************@newsb.telia.net...

On 2006-05-27 15:17, Jerry Coffin wrote:

In article <1148729865.862340.147700
@j33g2000cwa.googlegroups.com>, pe***************@gmail.com says...

[ size() "should" be constant complexity ... ]

>From a teoretical point, you are correct. But "should" is a
>strong
encouragement and combined with the other requirements for
std::vector
you would have some difficulties finding an implementation where
size()
is not O(1).

That is almost certainly true. OTOH, the table in question applies
equally to all containers. In some cases (e.g. std::list) it's
_possible_ to make it constant complexity, but only at considerable
expense in other areas (e.g. splicing two lists together becomes
linear rather than constant complexity).

What is it I'm missing here? AFAIK size() returns the number of
elements stored in the container, thus one could easily implement it
with a variable containing the value which is updated whenever an
element is inserted/removed from the container. How does that affect
the time it takes to splice two lists, all you have to do is add the
size of both of them.

The problem is with the splice function that takes a sequence of
elements from one list to another. This can be done in O(1) time, by
just rearranging some pointers. If you want to update the size of the
lists, you would have to count the spliced elements by walking the
links. There might be millions of them!
Bo Persson

[Jerry Coffin]

In article <rl****************@newsb.telia.net>, Erik-
wi******@telia.com says...

[ ... ]

What is it I'm missing here? AFAIK size() returns the number of elements
stored in the container, thus one could easily implement it with a
variable containing the value which is updated whenever an element is
inserted/removed from the container. How does that affect the time it
takes to splice two lists, all you have to do is add the size of both of
them.

If you splice one entire list onto another, it's no
problem at all. The problem arises when/if you grab only
_part_ of one list and splice it onto another. You can do
this by manipulating only the pointers in a couple of
nodes (the two that get spliced so they're next to each
other). Figuring out the size of the new list, however,
isn't quite so simple -- just about the only way to know
how many nodes you've added is to walk the list to count
the nodes.

You also run into a problem of how to maintain that
count. Consider (for example) two iterators into the list
that are both active at once. We insert some new nodes
into the list with one, but at the same time we're using
the other to splice part of the list onto a different
list. Now, if the code handling the first iterator
assumes it needs to update the count of items in the list
when it adds some nodes, it doesn't realize that the
nodes are now being added to a different list. It
attempts to update the count for the original list, and
now the counts for both the lists are wrong...

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Erik Wikström]

On 2006-05-27 19:50, Jerry Coffin wrote:

In article <rl****************@newsb.telia.net>, Erik-
wi******@telia.com says...

[ ... ]

What is it I'm missing here? AFAIK size() returns the number of elements
stored in the container, thus one could easily implement it with a
variable containing the value which is updated whenever an element is
inserted/removed from the container. How does that affect the time it
takes to splice two lists, all you have to do is add the size of both of
them.
If you splice one entire list onto another, it's no
problem at all. The problem arises when/if you grab only
_part_ of one list and splice it onto another. You can do
this by manipulating only the pointers in a couple of
nodes (the two that get spliced so they're next to each
other). Figuring out the size of the new list, however,
isn't quite so simple -- just about the only way to know
how many nodes you've added is to walk the list to count
the nodes.

I see what you're getting at, however I'm not sure that the splice-
operation is guaranteed to run faster than linear complexity. I've only
got a draft of the standard (to cheap to buy the real thing) and there
it says that it's linear unless the spliced elements already are in the
destination list. On the other hand it would be nice with a faster
implementation.
You also run into a problem of how to maintain that
count. Consider (for example) two iterators into the list
that are both active at once. We insert some new nodes
into the list with one, but at the same time we're using
the other to splice part of the list onto a different
list. Now, if the code handling the first iterator
assumes it needs to update the count of items in the list
when it adds some nodes, it doesn't realize that the
nodes are now being added to a different list. It
attempts to update the count for the original list, and
now the counts for both the lists are wrong...

This of course is a problem but shouldn't there be a requirement that
the iterator for the inserts are an iterator of the list on which the
method is called. Thus if we have two lists A and B and use an iterator
it and perform A.insert(it, elem) would the operation be legal if it
was an iterator in B? A quick search and I've not been able to find such
a provision, however as I said I've just a draft.

Erik Wikström
--
"I have always wished for my computer to be as easy to use as my
telephone; my wish has come true because I can no longer figure
out how to use my telephone" -- Bjarne Stroustrup

[Jerry Coffin]

In article <a7****************@newsb.telia.net>, Erik-
wi******@telia.com says...

[ ... ]

I see what you're getting at, however I'm not sure that the splice-
operation is guaranteed to run faster than linear complexity. I've only
got a draft of the standard (to cheap to buy the real thing) and there
it says that it's linear unless the spliced elements already are in the
destination list. On the other hand it would be nice with a faster
implementation.
Right -- in particular, it's (highly, IMO) questionable
whether it's a good idea to make splicing a lot slower on
the off chance that somebody might eventually call size()
and want it to run faster.

[ ... ]
This of course is a problem but shouldn't there be a requirement that
the iterator for the inserts are an iterator of the list on which the
method is called.
There probably should be, but I can't find any such
requirement. Assuming there was, then, yes, this
particular problem should disappear.
Thus if we have two lists A and B and use an iterator
it and perform A.insert(it, elem) would the operation be legal if it
was an iterator in B? A quick search and I've not been able to find such
a provision, however as I said I've just a draft.

I'm looking at the real standard (the 2003 version, to be
exact) and I don't see any such requirement with it
either.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Markus Schoder]

Jerry Coffin wrote:

In article <a7****************@newsb.telia.net>, Erik-
wi******@telia.com says...

This of course is a problem but shouldn't there be a requirement that
the iterator for the inserts are an iterator of the list on which the
method is called.

There probably should be, but I can't find any such
requirement. Assuming there was, then, yes, this
particular problem should disappear.

Thus if we have two lists A and B and use an iterator
it and perform A.insert(it, elem) would the operation be legal if it
was an iterator in B? A quick search and I've not been able to find such
a provision, however as I said I've just a draft.

I'm looking at the real standard (the 2003 version, to be
exact) and I don't see any such requirement with it
either.

For insert the requirement is in 23.1.1 paragraph 3 and table 67. For
splice I cannot find anything.

[Jerry Coffin]

In article <1148852190.398238.140750
@i40g2000cwc.googlegroups.com>, a3*************@yahoo.de
says...

[ ... ]

For insert the requirement is in 23.1.1 paragraph 3 and table 67.

Ah, I'd missed that -- I had looked at table 67, which
says that i and j must _not_ be iterators into a, but
says nothing about the fact that p does have to be an
iterator into a.

That removes one of the problems, but still leaves the
original one, and also leaves the possibility of two
different splices happening, where one splices nodes into
a list while the other splices a superset of those nodes
into another list.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[krbyxtrm]

Ayon kay Greg:

krbyxtrm wrote:

hello people,
i have implemented my code this way

start = read_timer(); // for profiling
if ( !any_vec.empty() )
{

std::for_each(
any_vec.begin(),
any_vec.end(),
retrieve); // where retrieve is an empty function for now...
}
end = read_timer();
duration = end - start ; // minus counter error
with this code and having empty callback function,
it duration = 1.2e-1 us

maybe i will have to see some std::vector implemtation manual to check
whether i'm using a debug-enable version, as of now i have from
http://www.sgi.com/tech/stl/Vector.html
but it does not have what Ivan Vecerina is telling.

How much time do you think these lines of code should reasonably take?
In other words, by what measure is the one-ten millionth of a second
being spent here too time-consuming?

From my own experience, optimizing any operation not measured in

milliseconds is probably not worthwhile. So unless the program intends
to execute this code 10,000 times in a row - and do so repeatedly -
then this kind of "bottom-up" optimization is unlikely to be
productive. What is needed is a "top-down" approach, in which the
entire program's execution is timed. It is necessary to account for all
of the time that a program spends executing, in order to know where
optimizations are likely to improve performance.

Greg

Greg,
Entire application's performace for my application is not quite
applicable, i should say,
application's initialization, etc for me is good enough, but the real
bottleneck is that code i'd been posting, since its not just a simple
vector/stack to iterate, it would store thousands of data, vector data
would be added, subtracted, etc. It holds not only plain data, it holds
function pointers, buffers and another pointer and another buffer, i
just made it simple to illustrate this problem.

-k-

[krbyxtrm]

Ayon kay Erik Wikström:

On 2006-05-26 02:55, krbyxtrm wrote:

Ayon kay krbyxtrm:

hello people,
i have implemented my code this way

start = read_timer(); // for profiling
if ( !any_vec.empty() )
{

std::for_each(
any_vec.begin(),
any_vec.end(),
retrieve); // where retrieve is an empty function for now...
}
end = read_timer();
duration = end - start ; // minus counter error
with this code and having empty callback function,
it duration = 1.2e-1 us

BTW, IS FOR VECTOR WITH 1 ELEMENT

It might be of interest to try with more elements, the increase in time
is not necessarily linear with the number of elements. Caches for
example can be a part of it, if you get a cache-miss on the first
element that will take some time, but the next element will be much
faster. To get good measures you should use more elements and run the
test many times and calculate the average.

Erik Wikström
--
"I have always wished for my computer to be as easy to use as my
telephone; my wish has come true because I can no longer figure
out how to use my telephone" -- Bjarne Stroustrup

Yes I think you're right. Afterall, the program will be dealing with
hundred of thousands vectors elements (360K+), ;-)

-k-

[scott urban]

On 2006-05-27, peter koch <pe***************@gmail.comwrote:

>
Jerry Coffin wrote:

>In article <1148555061.701178.51780@
38g2000cwa.googlegroups.com>, pe***************@gmail.com
says...

[ ... ]

v.size() needs to calculate the amount of records in v - which could
be very time consuming, depending on implementation and size of v.
Its better to use !v.empty() for this purpose.
We are talking about std::vector here so O(1) is guaranteed. I also
believe that size() is amortized O(1) in the general case.

For better or worse, this isn't quite true -- the
standard says that size() "should have constant
complexity" (Table 65, Note A), but I don't believe it
guarantees it for _any_ container.

From a teoretical point, you are correct. But "should" is a strong

encouragement and combined with the other requirements for std::vector
you would have some difficulties finding an implementation where size()
is not O(1).
Apart from that using empty() is clearer for the reader of the code
(although the name should have been is_empty()).

Why do people see the verb in 'v.empty()' but not in 'v.size()', etc ?

Both are adjectives, both are verbs. Perhaps one is more clearly
ambiguous to you. I worked with an excellent c++ programmer who just
couldn't get over this (for 'emtpy'). English is not clean, nor are
useful languages, in general. Oh well.