Re: [boost] [unordered] unordered_set::erase() complexity bug?

Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
From: John Zwinck (jzwinck_at_[hidden])
Date: 2009-11-25 14:36:27

Beman Dawes wrote:
> On Mon, Nov 23, 2009 at 6:40 PM, Thorsten Ottosen <
> thorsten.ottosen_at_[hidden]> wrote:
>> 2) also if this is a real problem in real code.

Unfortunately (for me), it is. Literally the day after you asked, and without
my having seen this thread, my teammate discovered this very issue in
production code. The sequence of events which led to the poorly-performing
program was:
   1) Write program using std::map.
   2) Switch to unordered_map, noting it reduced CPU utilization by ~30%.
   3) Discover that performance suffered when large rehashes occurred.
   4) Find the maximum bucket count (millions), and initialize with that.
   5) Rehashing slowdowns go away, but then we discover something we failed
      to notice before due to profiling with fewer buckets: the
      application's user-space CPU utilization is dominated by erase()!

We may end up switching to erase() by key, which is a shame since in our
case we always have the victim iterator already when we want to erase (so
now we must pay to find the key twice).

Our application could benefit from reducing the number of buckets in some
cases, but:
   1) It's not supported by GCC, even if one writes a custom rehashing policy.
   2) We would likely suffer from rehashing again, as given this issue with
      erase(), the optimum number of buckets varies throughout the program's
      lifetime (increasing then later decreasing).

> what do other implementations do, and how do they perform?

We use GCC 4.2.4.  It has code analogous to Boost's:

     _M_incr_bucket()
     {
       ++_M_cur_bucket;

       // This loop requires the bucket array to have a non-null sentinel.
       while (!*_M_cur_bucket)
         ++_M_cur_bucket;
       _M_cur_node = *_M_cur_bucket;
     }

I haven't tried Boost, but I can tell you that GCC does not do well here.

-JZ