This is the mail archive of the gcc-bugs@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[Bug libstdc++/67922] std::unordered_map::clear should take time linear in the number of elements


https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67922

--- Comment #3 from Yegor Derevenets <yegor.derevenets at gmail dot com> ---
A small correction. A colleague of mine bothered to read the source code of
libc++ and noticed that its implementation of clear() method also generally
takes time, linear in the number of buckets. This was not visible in the tests
I already presented, because libc++ has special handling of the empty container
case:

template <class _Tp, class _Hash, class _Equal, class _Alloc>
void
__hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT
{
    if (size() > 0)
    {
        __deallocate(__p1_.first().__next_);
        __p1_.first().__next_ = nullptr;
        size_type __bc = bucket_count();
        for (size_type __i = 0; __i < __bc; ++__i)
            __bucket_list_[__i] = nullptr;
        size() = 0;
    }
}

If we modify the test example slightly, we get:

$ cat test_clear.cpp
#include <unordered_map>

int main() {
        std::unordered_map<int, int> m;
        for (int i = 0; i < 1000000; ++i) {
                m[i] = i;
        }
        for (int i = 0; i < 1000; ++i) {
                m[i] = i;
                m.clear();
        }
}

$ clang++-3.7 -O2 -std=c++11 -stdlib=libstdc++ test_clear.cpp && time ./a.out

real    0m4.054s
user    0m4.000s
sys     0m0.036s

$ clang++-3.7 -O2 -std=c++11 -stdlib=libc++ test_clear.cpp && time ./a.out

real    0m6.114s
user    0m6.000s
sys     0m0.036s

$ cat test_erase.cpp
#include <unordered_map>

int main() {
        std::unordered_map<int, int> m;
        for (int i = 0; i < 1000000; ++i) {
                m[i] = i;
        }
        for (int i = 0; i < 1000; ++i) {
                m[i] = i;
                m.erase(m.begin(), m.end());
        }
}

$ clang++-3.7 -O2 -std=c++11 -stdlib=libstdc++ test_erase.cpp && time ./a.out

real    0m0.151s
user    0m0.116s
sys     0m0.036s

$ clang++-3.7 -O2 -std=c++11 -stdlib=libc++ test_erase.cpp && time ./a.out

real    0m0.187s
user    0m0.156s
sys     0m0.028s

I find it strange that both libraries implement clear() less efficiently than
erase(m.begin(), m.end()). Maybe there is a rationale for this which I do not
understand?

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]