Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
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
hash_iterator copy ctor, so that the following pathological situation
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
back in compilers without RVO.
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk