Re: perfomance of clear vs swap
<wade@stoner.com> wrote in message
news:1164808878.271502.79630@j44g2000cwa.googlegroups.com...
Krishanu Debnath wrote:
Hello,
I have a call to hash_map::clear() function which takes long time.
someClass::someFunction()
{
// typedef hash_map<name_id, uint> Mp;
// Mp p;
// assuming proper namespace, hash function for name_id obj.
p.clear();
}
Above p.clear() takes long time, profiling indicates 'number of bucket
of hash table is large'.
Now, just for sake of experiments, I replaced this 'clear' call with
swap. i.e.
[...]
Now runtime drops significantly, 10 fold less.
What's exactly cause this run time reduction?
Note that the in the Dinkum implementation (VC7.1, VC8) (if I am
reading it correctly), given a hash_map which currently has N elements,
but in the past had as many as M elements, the costs are
Destructor: O(N) (assumes compiler is smart enough to destroy
vector<iterator> in O(1))
clear(): O(M)
while(p.begin() != p.end()) erase(p.begin()); O(M*N) (quadratic)
So if you have an implementation that uses the Dinkum layout, but
implements clear() with the loop shown above, the swap/destruct
strategy would be much faster than clear(). Even with the Dinkum
clear() code, swap/destruct is a bit faster if the map was previously
much larger than it currently is.
You're confounding several things here. We implement hash_* as a
list of elements plus a vector of buckets, each characterized by
a list iterator. hash_*::clear() calls list_clear, which destroys
all the elements, then assigns the list end iterator to all elements
of the hash table, which empties all the buckets. So you're talking
O(N) destructor calls plus O(M) iterator assignments, each assignment
generally being small, simple, and hence fast.
The swap trick has the one advantage of destroying the vector
instead of reinitializing it -- at least that's an advantage if
the hash table has grown large. But if the clearing time is
dominated by calling nontrivial element destructors, you should
get about the same time either way.
IIRC the SGI versions I've seen did not have this behavior.
Our implementation is quite different from SGI's, and has a number
of advantages.
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]