Re: [boost] [multi_index] hashed_index erase(iterator) performance issue

Subject: Re: [boost] [multi_index] hashed_index erase(iterator) performance issue
From: OvermindDL1 (overminddl1_at_[hidden])
Date: 2010-03-16 17:56:53

On Tue, Mar 16, 2010 at 8:46 AM, Brad Higgins <bhiggins_at_[hidden]> wrote:
> Hello,
> Â I have encountered a performance issue with multi_index's hashed_index
> erase(iterator) routine. Â The erase(iterator) call returns an iterator to
> the next element in the data structure. Â When using this routine in a
> sparsely populated, large sized hash, it takes a very long time to complete.
> Â For example, in my program, I have rehashed the hash table to 5 million
> buckets, and added 600,000 elements. Â Adding the elements takes a matter of
> seconds. Â Then, I delete the elements. Â Deleting the elements takes hours.
> Â I have profiled the code, and it looks to me like the performance hit is
> rooted in the increment of the iterator by the erase(iterator) call. Â Since
> the hash is sparsely populated, the increment must advance over many empty
> buckets for each erase(iterator) call, in order to advance to the next valid
> element.
> Â My question is, why does the erase(iterator) function return an iterator at
> all? Â (In comparison, sgi's stl::hash_map's erase() returns void.) Â The hash
> is unordered, so the returned iterator is a random value, which I think
> decreases its usefulness (I expect most clients will discard the returned
> iterator.) Â Additionally, the same behavior can be achieved by clients who
> desire this behavior if they post-increment their iterator argument
> themselves. Â That is:
>
> // After this line, cur_itr's initial element will be erased,
> // AND cur_itr will be updated to the next element in the hash table
> hash_table.erase(cur_itr++);
>
> Â Is there some way to remove elements from the hash without taking this
> iterator increment hit? Â Would it be possible to add an erase routine (of
> some other name) which accepts an iterator argument, but does not
> automatically increment the argument?

We all know about the performance hit, however that style is mandated
by the standard (which thankfully is still in flux, hopefully they
will remove the need for it to return the iterator).