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

Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
From: joaquin_at_[hidden]
Date: 2010-03-18 03:12:29

Daniel James escribió:
> On 17 March 2010 22:06, Howard Hinnant <howard.hinnant_at_[hidden]> wrote:
>   
>> Just a few minutes ago I changed my implementation of unordered_map to use a "lazy increment" for the iterator and ran it against Brad's test:
>>
>> $ time a.out
>> Add 500000 elements...done!
>>
>> remove the elements...done!
>>
>> real    0m0.153s
>> user    0m0.127s
>> sys     0m0.020s
>>
>> This time is about the same as I got using an erase() that did not increment the iterator.  The "lazy increment" allows the iterator to walk off of the end of bucket, and does not try to find the next bucket until dereference, another increment, or comparison.  I do not claim this is "the solution" it is one of several I'm exploring.  I mention it here in case others want to try it and report their experience.
>>     
>
> I've attached a patch to do something similar for Boost.Unordered. I
> got a similar result, although I think it will make some other things
> slower. And I'm not keen on mutable variables.
>   

There's an additional problem, I think. Your patch does not 
check_increment() on
hash_iterator copy ctor, so that the following pathological situation 
can happen:

  auto it1=cont.erase(it),it2=it1; // it1 and it2 unchecked yet
  (void)(it1==it1); // it1 checked
  cont.insert(x); // x gets inserted between it and it1
  (void)(it2==it2); // it2 gets checked and points to the position of x.
  assert(it1==it2); // fails!

Now, if you add check_increment() to the copy ctor you get the quadratic 
behavior
back in compilers without RVO.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo