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

Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
From: Stefan Strasser (strasser_at_[hidden])
Date: 2009-11-23 19:34:10

Am Tuesday 24 November 2009 00:14:55 schrieb Christopher Jefferson:
> On 23 Nov 2009, at 23:23, Stefan Strasser wrote:
> > I think there is something very wrong with boost's implementation of
> > unordered_set/map.
> >
> > 1	unordered_set<int> s;
> > 2	for(int c=0;c<nr;++c) s.insert(c);
> > 3	for(int c=nr-1;c>=0;--c) s.erase(s.find(c));
> >
> > results:
> >
> > nr: time
> > 20000: 0m0.244s
> > 40000: 0m0.940s
> > 60000: 0m5.584s
> > 80000: 0m4.232s
> > 100000:    0m34.814s
> > 120000:    0m33.486s
> >
> >
> > the function that's causing this is erase(), which is specified to be
> > O(1) average, O(n) worst.
> > I can't think of a reason why it should be O(n) in this case (perfect
> > hash, erase doesn't rehash).
> > but even if it was, the results should be at worst quadratic.
>
> I suspect the problem you are seeing is that erase returns an iterator to
> the next member of the unordered_set, which is a possibly O(n) search if

you're right, here is the culprit:

                void increment()
                {
                    BOOST_ASSERT(bucket_);
                    node_ = node_->next_;

                    while (!node_) {
                        ++bucket_;
                        node_ = bucket_->next_;
                    }
                }

however, my results show even worse than O(size()), which is the specificied 
worst case.
this TR1 draft from 2005:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1745.pdf

had a "void" result of erase(), but that changed a few month later:

http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1836.pdf

so I guess they had a good reason for changing it, since the complexity 
requirements stayed the same.

does anyone on this list happen to know what caused that change?

> , and in particular if, as you get here, you 
> erase the elements in a particularly bad order. I'm not sure why this
> doesn't occur with the intrusive containers.

"void" return type:
http://www.boost.org/doc/libs/1_38_0/doc/html/boost/intrusive/unordered_set.html#id3497860-bb

Am Tuesday 24 November 2009 00:40:57 schrieb Thorsten Ottosen:
> 2) also if this is a real problem in real code.

it happened in real code.