Re: perfomance of clear vs swap
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.
IIRC the SGI versions I've seen did not have this behavior.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]