🔒 Locked

Removing all items from stl container, what would be more efficient?

Started by skwee Jul 31, 2009 at 12:49 PM 24 replies 4.7k views

Original Post

Jul 31, 2009 at 12:49 PM

Assume I have the following container:


stdext::hash_map<String, SceneNode*> NodeList;
NodeList nodes;

//Here we add nodes to the list, a lot of nodes

//Here we want to remove the nodes (delete them of course)
NodeList::iterator it, endIt;
//Here is the delete Either Way1 or Way2


//WAY1
it = nodes.begin();
endIt =  = nodes.end();
while(it != endIt){
  delete it->second;
  it = nodes.erase(it);
}


//WAY2
it = nodes.begin();
endIt =  = nodes.end();
while(it != endIt){
  delete it->second;
  it++;
}
nodes.clear();

What would be more efficient? Erasing each node after I deleted it or removing them all at the end? Thanks a lot :)

Sneftel

Jul 31, 2009 at 12:52 PM

If either, it would be the second. If clear() could have been implemented more efficiently as erase() in a loop, why would the implementor not have done it that way?

skwee

Jul 31, 2009 at 12:59 PM

Quote:
Original post by Sneftel
If either, it would be the second. If clear() could have been implemented more efficiently as erase() in a loop, why would the implementor not have done it that way?

Thank you!
I suspected the same, but some why thought that clear() could be implemented as erase() in loop.

SiCrane

Jul 31, 2009 at 1:00 PM

It could be the first one if your container is huge and iterating over it in two passes causes a larger number of cache misses. As always, when in doubt, use a profiler. I'm guessing the answer will be "This isn't a bottleneck. Worry about optimizing somewhere else".

Washu

Jul 31, 2009 at 1:05 PM

Quote:
Original post by SiCrane
It could be the first one if your container is huge and iterating over it in two passes causes a larger number of cache misses. As always, when in doubt, use a profiler. I'm guessing the answer will be "This isn't a bottleneck. Worry about optimizing somewhere else".

I'm guessing that

stdext::hash_map<String, boost::shared_ptr<SceneNode> > NodeList;NodeList nodes;nodes = NodeList();

would be best. Hurray for memory management!

ScottMayo

Jul 31, 2009 at 1:08 PM

I'd be surprised if there was a measurable difference, unless perhaps the set was huge. Go with what you find clearer.

If speed matters that much, drop in a half million entries and time it.

SiCrane

Jul 31, 2009 at 1:33 PM

Quote:
Original post by Washu
I'm guessing that
*** Source Snippet Removed ***
would be best. Hurray for memory management!

I think that if the container was huge, that would probably be slower than 1 since the reference counts aren't held inline with the data meaning that the effective working set would be a bit larger due to that non-locality. If the compiler supports move constructors and the hash_map container is compatible, unique_ptr would give you automatic memory management without the need for spending extra memory on the reference counts. Otherwise, you could use intrusive_ptr, which could end up effectively free depending on the size, alignment and composition of the held objects.

skwee

Jul 31, 2009 at 1:44 PM

SiCrane
ScottMayo
Yes most likely this wont be the bottle neck, but anyway its a good way to learn small optimizations similar to this:

for(int i = 0; i != container.size(); i++){}//Compared toint size = container.size();for(int i = 0; i != size; i++){}

Of course Ill profile it later, to make sure its ok.

Washu
I knew such comment will come. Implementing reference counting and auto deletion of object is not necessary in this system and in addition it adds complexity for the system it self. I use shared_ptr where its needed, here its not, at least not for now, thanks anyway :)

Antheus

Jul 31, 2009 at 1:51 PM

Is SceneNode polymorphic?

skwee

Jul 31, 2009 at 2:01 PM

Quote:
Original post by Antheus
Is SceneNode polymorphic?

Not, and I think that in future it might be, for basic scene graph I don't need it to be polymorphic.

cache_hit

Jul 31, 2009 at 2:05 PM

Since we're on the subject of optimizations, you should pretty much never use postincrement (i.e. it++), and pretty much always use pre-increment (e.g. ++i) unless you have a really really good reason not to.

Antheus

Jul 31, 2009 at 2:18 PM

Quote:
Original post by s.kwee
Not, and I think that in future it might be, for basic scene graph I don't need it to be polymorphic.

Why not use:

stdext::hash_map<String, SceneNode> NodeList;

skwee

Jul 31, 2009 at 2:48 PM

Quote:
Original post by Antheus
Quote:
Original post by s.kwee
Not, and I think that in future it might be, for basic scene graph I don't need it to be polymorphic.

Why not use:
stdext::hash_map<String, SceneNode> NodeList;

I don't know...
Ill think about it.

MaulingMonkey

Jul 31, 2009 at 5:18 PM

Quote:
Original post by s.kwee
SiCrane
ScottMayo
Yes most likely this wont be the bottle neck, but anyway its a good way to learn small optimizations similar to this:

The compiler already likely does this optimization for you.

Decrius

Jul 31, 2009 at 5:55 PM

Quote:
Original post by MaulingMonkey
Quote:
Original post by s.kwee
SiCrane
ScottMayo
Yes most likely this wont be the bottle neck, but anyway its a good way to learn small optimizations similar to this:

The compiler already likely does this optimization for you.

Most likely ^^, if you do it yourself the chances are much higher.

rip-off

Jul 31, 2009 at 5:57 PM

Quote:
Original post by Decrius
Quote:
Original post by MaulingMonkey
Quote:
Original post by s.kwee
SiCrane
ScottMayo
Yes most likely this wont be the bottle neck, but anyway its a good way to learn small optimizations similar to this:

The compiler already likely does this optimization for you.

Most likely ^^, if you do it yourself the chances are much higher.

Where do you draw the line with such an attitude though? And if it is really such a minor optimisation, is there any real benefit to it?

Antheus

Jul 31, 2009 at 6:12 PM

Quote:
Original post by rip-off

Where do you draw the line with such an attitude though? And if it is really such a minor optimisation, is there any real benefit to it?

When you have adequate experience in a certain platform, which has shown that such performance tweaks are beneficial.

It's common in constrained environments. Such tweaks in general do not age well, but they remain universally applicable.

For example, Sun's JVM doesn't optimize integer divisions even if dividing by power of two. Both, right shift and SAR tend to be faster than straight division (PC). This obviously doesn't mean to use right shifts instead of division, but it can come in handy from time to time. It is also something worth testing on embedded devices.

Washu

Jul 31, 2009 at 6:46 PM

Quote:
Original post by s.kwee
Washu
I knew such comment will come. Implementing reference counting and auto deletion of object is not necessary in this system and in addition it adds complexity for the system it self. I use shared_ptr where its needed, here its not, at least not for now, thanks anyway :)

The shared_ptr is already implemented for you, it adds no extra complexity and actually removes complexity by eliminating the entire problem you're having at the moment.

Re: ++it vs it++ ->
Any half decent compiler will eliminate the temporary from it++ except in the case where the iterator copy is non-trivial. Since iterator copies in the standard library are always trivial (in the case of standard containers with iterator debugging disabled for instance), it++ ==> ++it for all cases where you ignore the result.

Re: SiCrane ->
True, intrusive pointers would certainly be almost free if the container was huge and with the added benefit of eliminating the need for manual memory management except in implementing the reference counting. Which could also be trivially eliminated through the use of templates and inheritance (intrusive_ptr_host class, for instance). However, most of the time a huge hash table is a bad idea simply because it's more optimal for searching through small to medium sized datasets, which means that you've probably chosen the wrong container in the first place. Thus the optimization of an intrusive_ptr vs shared_ptr was probably entirely lost in your usage of the container for searching. Furthermore, due to the structure of hash-tables, you're not going to maintain any sort of cache locality except within the individual buckets.

SiCrane

Jul 31, 2009 at 8:35 PM

Quote:
Original post by Washu
Furthermore, due to the structure of hash-tables, you're not going to maintain any sort of cache locality except within the individual buckets.

No, of course, not, but for the performance characteristic that the OP asked about - clearing the data structure - the issue isn't maintaining cache locality, which is completely hosed by using a large hash table in the first place, the issue is that non-intrusive reference counts will cause probably around 50% to 100% extra cache misses in the already extremely cache unfriendly operation (depending on the structure of the hash table, if it uses open or closed addressing, etc).

And for smallish to medium data structures where the data can be reasonably assumed to be in the cache because of data access before the container is destroyed, there are two cases: either the shared_ptr touches the reference count memory in every access (via operator -> or other equivalent operations) or it doesn't. If it does, then you've got a nice extra dereference on every operation, which would louse up the cache for every access, which at the very least means that you've cut the effective size of the cache for determining what will fit in the cache when the whole thing is destroyed. If it doesn't, shared_ptr still loses out in the cache miss category during destruction, because touching the reference count data will need to load in fresh cache lines when the shared_ptrs are destroyed. (boost's shared_ptr implementation falls in the latter category, which makes sense for a general purpose smart pointer implementation.)

Yes, for data access with a standard populate/use with minimal modifying/destroy life cycle for a hash table, shared_ptr, instrusive_ptr and even dumb pointers would probably have close to equal performance (presuming the shared_ptr implementation doesn't access the reference count block every access). However, for the case that creation and destruction performance matters (which I admit I already said is unlikely), shared_ptr isn't a winner here.

Washu

Jul 31, 2009 at 10:22 PM

Quote:
Original post by SiCrane
Quote:
Original post by Washu
Furthermore, due to the structure of hash-tables, you're not going to maintain any sort of cache locality except within the individual buckets.

No, of course, not, but for the performance characteristic that the OP asked about - clearing the data structure - the issue isn't maintaining cache locality, which is completely hosed by using a large hash table in the first place, the issue is that non-intrusive reference counts will cause probably around 50% to 100% extra cache misses in the already extremely cache unfriendly operation (depending on the structure of the hash table, if it uses open or closed addressing, etc).

And for smallish to medium data structures where the data can be reasonably assumed to be in the cache because of data access before the container is destroyed, there are two cases: either the shared_ptr touches the reference count memory in every access (via operator -> or other equivalent operations) or it doesn't. If it does, then you've got a nice extra dereference on every operation, which would louse up the cache for every access, which at the very least means that you've cut the effective size of the cache for determining what will fit in the cache when the whole thing is destroyed. If it doesn't, shared_ptr still loses out in the cache miss category during destruction, because touching the reference count data will need to load in fresh cache lines when the shared_ptrs are destroyed. (boost's shared_ptr implementation falls in the latter category, which makes sense for a general purpose smart pointer implementation.)

Yes, for data access with a standard populate/use with minimal modifying/destroy life cycle for a hash table, shared_ptr, instrusive_ptr and even dumb pointers would probably have close to equal performance (presuming the shared_ptr implementation doesn't access the reference count block every access). However, for the case that creation and destruction performance matters (which I admit I already said is unlikely), shared_ptr isn't a winner here.

Couple more things: stdext::hash_map is implemented using an std::list containing the elements, and a vector containing iterators into the list, so cache locality isn't going to be maintained even within the buckets (my mistake), obviously adding in the smart pointer there will add more misses. The real question though is: Will those additional misses increase the cost above that of his methods, which I don't believe to be so, and here's why:

His second method will be the slowest, with the dual loop (one explicit, one in clear), no matter how you get around it, clear ends up requiring a call to Alloc::destruct once per item in the hash_map.

The first method uses erase, which has a loop within it as well, to adjust the bucket iterators to avoid having buckets with invalidated iterators in them, it's not as bad as it sounds though. But you're already hitting the cache a bunch of times, once for the iterator, the vector of buckets, the linked list (in the erase method), and also the actual SceneNode*.

My method, with the simple destructor call ends up being slightly better, in my opinion, since it involves only the destruction of the vector, and not the erasure and then .assign of the vector that clear invokes. It also involves the destruction of the list, which will accomplish the requested operation of cleaning up the allocated items (SceneNode's in this case). The destruction of the vector elements will most likely be trivially elided, since list iterators are trivial (again, assuming iterator debugging is disabled).

Although, the best option (if the map was to be used again), would be to call clear with a smart pointer of some kind. This has almost the same behavior as calling the destructor of the hash map, but without certain deallocations in the vector (although it does call .assign on it with the minimum number of buckets).

Note to kiddies: This is why algorithms and data structures are such fun to play with.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.