I don't think you need to worry about cache misses, cache friendly optimizations can definitely wait for the end of the project if you're running slow and you've run out of general algorithmic optimization wins.

I haven't done any work with hardware profilers, so take this with a pinch of salt, but I think using a list for a 'display list' isn't going to cause many cache misses, as your list additions aren't going to be interspersed with many other allocations, and as such the allocated list nodes will be fairly contiguous in memory. Though I am used to consoles were the game is the only thing accessing it's reserved block of ram, I have no idea how other processes interact with an applications ram allocations on a PC.

Now changing topic.

Using a std::string for a key value really depends on the usage. I'd say that if you're using std::string as a key in a std::map, it can be plenty fast enough for a main loop, but as legalize advises, let your profiling be the guide on this one.

Using std::string's for resource naming and resource lookups and things like that is perfectly fine however, I generally never use raw char*.

if the vector is not being appended to, then avoid the vector::insert( back, begin, end) and use instead vector::assign( begin, end). in either of these (insert/assign) operations i would avoid the call to reserve, since youve provided enough information upfront so that the container can determine using std::distance whether it might need to reallocate.

its a bit weird though,

what is the final capacity() that you get at the end of each method using insert() vs push_back() ? could it be that somehow there is an internal resizing going on (calling reserve upfront should avoid this - that's the point) - so that there is extra default/copy constructing going?t. calling capacity() would be an easy way to determine if the allocation(s) were behaving differntly.

if its 227 elements (very small) taking 20/60ms then 95% of the time must be being spent doing object copy constructing, which perhaps is done differently in push_back vs insert. [edit] maybe put a static int count = 0; ++count in the copy constructor and assignment operator to check if each approach is really doing the same number of copies

[edit] 2.

I was curious about this so tested by implementing a static count implmented in the default and copy constructors of an object an using a vector with n = 1000 elts.

$all these operations behave identically
v.resize( n),
v.assign( b,e),
insert( v.b, x.b, x.e)
copy( x.b, x.e, back_inserter v)

with or without a reserve( n) in all cases they do n = std::distance = 1000 default or copy constructs in all cases. ie they are algorithmically optimal.


$push_back() where n = 1000 with a pre reserve( 1000) does 2000 default or copy construts.

$push_back() where n = 1000 without a reserve( 1000) does 3023 copy of default constructs due to incremental reallocation.

the assignment operator is never invoked in any of these operations - although required to be a conforming containtainer candidate. am using gnu libstdc++.

so anything that avoids push_back ought to be faster !! weird




[Edited by - chairthrower on August 11, 2008 5:15:21 AM]