+3.0 microsecond for iterating empty vectors

[Jerry Coffin]

[ ... ]

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.

 

[Markus Schoder]

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


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]

@i40g2000cwc.googlegroups.com>, (e-mail address removed)
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.

 

[krbyxtrm]

Ayon kay Greg:

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?

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:

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

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

-k-

 

[scott urban]

38g2000cwa.googlegroups.com>, (e-mail address removed)
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.