This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
[Bug libstdc++/67922] std::unordered_map::clear should take time linear in the number of elements
- From: "yegor.derevenets at gmail dot com" <gcc-bugzilla at gcc dot gnu dot org>
- To: gcc-bugs at gcc dot gnu dot org
- Date: Mon, 02 Nov 2015 16:59:50 +0000
- Subject: [Bug libstdc++/67922] std::unordered_map::clear should take time linear in the number of elements
- Auto-submitted: auto-generated
- References: <bug-67922-4 at http dot gcc dot gnu dot org/bugzilla/>
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?