+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]

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]

: 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

 

[Phlip]

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...

 

[Mathias Waack]

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:

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

 

[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:

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

 

[Greg]

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

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

Ayon kay krbyxtrm:
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

 

[Markus Schoder]

Mathias Waack skrev:

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]

38g2000cwa.googlegroups.com>, (e-mail address removed)
says...

[ ... ]

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.

 

[peter koch]

38g2000cwa.googlegroups.com>, (e-mail address removed)
says...

[ ... ]

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]

@j33g2000cwa.googlegroups.com>,
(e-mail address removed) says...

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

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).

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

@j33g2000cwa.googlegroups.com>,
(e-mail address removed) says...

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

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

 

[Bo Persson]

[ 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]

[ ... ]

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...

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

[ ... ]

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