Speeding up iterators

[wildfire99]

I've got a program that is storing gobs of pointers to objects, and I want to be able to check them in a linear fashion pretty fast.

To that end, I set up a trial using both vectors and multimaps to test lookup and sequential access speed. The issue I'm running into is iterator speed, actually a huge slowdown when iterators are incremented. I'm using MSVC 2005.

Here's some sample code. It's a simple function that does nothing more complex than insert a pointer so that all records in the vector are in sequential ID order.


void insertv( ObjectPointer* p, std::vector<ObjectPointer*>& vec )
{
int x, count = (int) vec.size();

for (x = 0; x < count; x++)
{
if ( p->idnumber < vec[x]->idnumber )
{
vec.insert( vec.begin() + x, p );
return;
}
}

vec.push_back(p); //id is largest so push to back
}

This takes a freaking long time once it gets over 50,000 entries in the vector. But it's not the linear search eating up time, not even the insertion, it's adding x to the vector iterator!

If I change the insert to remove the x, the code speeds up by a factor of more than 10.

vec.insert( vec.begin(), p ); //more than 10x faster than vec.begin + x
This is despite the fact that the vector now (presumably) has to bump over all of its contents every time it inserts.

You might ask why I don't just use a map? Same problem but later in the code. Incrementing the map's iterator to step through all records is over four times slower than simply using the array operator for the vector ( e.g. vector[x] ).

Stepping through the actual code shows the iterator increment is nothing more than a simple internal pointer increment, so why is it so slow? How can I fix this so incrementing an iterator is reasonably fast?

I did check by defining _SECURE_SCL to zero to ensure that was off... makes no difference. All times were from the optimized release build, so there should be no debug oddities.

[Paul McKenzie]

To that end, I set up a trial using both vectors and multimaps to test lookup and sequential access speed. The issue I'm running into is iterator speed, actually a huge slowdown when iterators are incremented. I'm using MSVC 2005.If you have an optimized build, there is no way you can determine what is slow unless you're looking at the assembly code. The source code will not match what is actually being run, so the claim that "the slowdown is on this line" cannot be valid, unless you are debugging in assembly mode.

Optimizations removes code, moves code around, etc. so what you see in the debugger in terms of the source code is not what you see when you run the program. Only non-optimized builds can be debugged where the debugger and the source are in sync.
Stepping through the actual code shows the iterator increment is nothing more than a simple internal pointer increment, so why is it so slow?If "stepping" means "I'm looking at the source code in the debugger", optimized builds cannot be debugged this way -- only by debugging the assembly code can you know for sure what you're actually running.

Regards,

Paul McKenzie

[GNiewerth]

Since your vector is already sorted you can use lower_bound and an appropriate predicate to determine the insertion position:


struct InsertionPredicate
{
bool operator()( const ObjectPointer* pObj1, const ObjectPointer* pObj2 ) const
{
return pObj1->idnumber < pObj2->idnumber;
}
};


void insertv( ObjectPointer* p, std::vector<ObjectPointer*>& vec )
{
std::vector<ObjectPointer*>::iterator pos =
std::lower_bound( vec.begin(), vec.end(), p, InsertionPredicate() );

if( vec.end() == pos )
{
// append element to the end
vec.push_back( p );
}
else
{
// insert p at first possible position without breaking sort order
vec.insert( pos, p );
}
}


Edit:
Code cleanup

[JohnW@Wessex]

In all of my tests I've found vector iterators to be identical in speed to pointers (defining _SECURE_SCL to zero).

[Lindley]

My guess: The for loop and if statement are being optimized out since they don't depend on x in the second case.

[wildfire99]

If you have an optimized build, there is no way you can determine what is slow unless you're looking at the assembly code. The source code will not match what is actually being run, so the claim that "the slowdown is on this line" cannot be valid, unless you are debugging in assembly mode.
I've looked at the code in both debug and release. The times in release mode are from a timer utility that measures the run time in milliseconds from start to finish using Windows' timeGetTime(). So no, I don't know what code exactly is being run in release, but I do know that simply changing it to add x to the iterator makes it nearly 10 times slower (right now, 24,594ms when I add 'x', 2,670ms when I don't).

Along the same lines, doing a simple increment of the map iterator later on in another function slows down that function by eight times (a simple ++iterator). I have a function that steps through all 'ObjectPointer' records in the multimap and checks a few values for each. At the end of the function I simply increment the map iterator by using the prefix increment operator (++iterator). In release, that function takes 8ms to step through all 80,000 records. If I simply delete or replace the one line that says ++iterator with nothing or with iterator = map.begin(), then the function takes 0ms to step through all records (the same amount of time the same function using the vector takes, which steps through all records by getting a pointer using the [] operator, such as ObjectPointer* p = vector[x].

So it's weird because there is a lot of other stuff going on in the function, and adding or removing that single line has a tremendous impact on performance, even more than taking the iterator using .begin() in the first place. Thus, I figured I must have stumbled onto some generic iterator "gotcha".

If "stepping" means "I'm looking at the source code in the debugger", optimized builds cannot be debugged this way -- only by debugging the assembly code can you know for sure what you're actually running.
Quite right, I don't know what's going on outside of the debug build, but I know that both debug and release build show the same inexplicable slowdown by looking at the overall elapsed runtime for that section of code on a simple iterator incrementing. The debug step-through doesn't show anything more complex than pointer arithmetic except for Microsoft's SCL stuff, which I tried to turn off but it had no effect on runtimes (in release, anyway). I even tried rewriting the code so that the iterator is taken before anything else and incremented in different ways, just to ensure it wasn't some optimization-related issue. The elapsed runtime never wavers that much, it's always roughly 10x slower than the same code that doesn't increment the iterator.

It's just so unusual because the [] operator on the vector is as fast as you'd expect, it's only the moment an iterator comes into play that the whole thing nosedives. As noted, it's not specific to vector, my multimap iterators in the same program have the same issue.

Since your vector is already sorted you can use lower_bound and an appropriate predicate to determine the insertion position:
I don't know exactly how that code works (I'm not fully familiar with the STL) but it seems to resolve the problem. In the release build, doing an 80,000 object insertions, the code I listed took 24,941ms to complete all insertions, yours with the lower_bound routine only took 1,512ms (only 6% of the iterator version). Whatever is going on, everything is dandy if I never touch an iterator. I'm still confused about the iterator slowdown, but at least your lower_bound method works as fast as I could want. Thanks!