[libc++] Optimize __hash_table::erase(iterator, iterator) #152471

philnik777 · 2025-08-07T09:45:21Z

Instead of just calling the single element erase on every element of the range, we can combine some of the operations in a custom implementation. Specifically, we don't need to search for the previous node or re-link the list every iteration. Removing this unnecessary work results in some nice performance improvements:

-----------------------------------------------------------------------------------------------------------------------
Benchmark                                                                                             old           new
-----------------------------------------------------------------------------------------------------------------------
std::unordered_set<int>::erase(iterator, iterator) (erase half the container)/0                    457 ns        459 ns
std::unordered_set<int>::erase(iterator, iterator) (erase half the container)/32                   995 ns        626 ns
std::unordered_set<int>::erase(iterator, iterator) (erase half the container)/1024               18196 ns       7995 ns
std::unordered_set<int>::erase(iterator, iterator) (erase half the container)/8192              124722 ns      70125 ns
std::unordered_set<std::string>::erase(iterator, iterator) (erase half the container)/0            456 ns        461 ns
std::unordered_set<std::string>::erase(iterator, iterator) (erase half the container)/32          1183 ns        769 ns
std::unordered_set<std::string>::erase(iterator, iterator) (erase half the container)/1024       27827 ns      18614 ns
std::unordered_set<std::string>::erase(iterator, iterator) (erase half the container)/8192      266681 ns     226107 ns
std::unordered_map<int, int>::erase(iterator, iterator) (erase half the container)/0               455 ns        462 ns
std::unordered_map<int, int>::erase(iterator, iterator) (erase half the container)/32              996 ns        659 ns
std::unordered_map<int, int>::erase(iterator, iterator) (erase half the container)/1024          15963 ns       8108 ns
std::unordered_map<int, int>::erase(iterator, iterator) (erase half the container)/8192         136493 ns      71848 ns
std::unordered_multiset<int>::erase(iterator, iterator) (erase half the container)/0               454 ns        455 ns
std::unordered_multiset<int>::erase(iterator, iterator) (erase half the container)/32              985 ns        703 ns
std::unordered_multiset<int>::erase(iterator, iterator) (erase half the container)/1024          16277 ns       9085 ns
std::unordered_multiset<int>::erase(iterator, iterator) (erase half the container)/8192         125736 ns      82710 ns
std::unordered_multimap<int, int>::erase(iterator, iterator) (erase half the container)/0          457 ns        454 ns
std::unordered_multimap<int, int>::erase(iterator, iterator) (erase half the container)/32        1091 ns        646 ns
std::unordered_multimap<int, int>::erase(iterator, iterator) (erase half the container)/1024     17784 ns       7664 ns
std::unordered_multimap<int, int>::erase(iterator, iterator) (erase half the container)/8192    127098 ns      72806 ns

github-actions · 2025-08-07T09:48:59Z

✅ With the latest revision this PR passed the C/C++ code formatter.

llvmbot · 2025-08-11T19:53:43Z

@llvm/pr-subscribers-libcxx

Author: Nikolas Klauser (philnik777)

Changes

----------------------------------------------------------------------------------------------------------------
Benchmark                                                                                        old         new
----------------------------------------------------------------------------------------------------------------
std::unordered_map&lt;int, int&gt;::erase(iterator, iterator) (erase half the container)/0          450 ns      446 ns
std::unordered_map&lt;int, int&gt;::erase(iterator, iterator) (erase half the container)/32        1017 ns      614 ns
std::unordered_map&lt;int, int&gt;::erase(iterator, iterator) (erase half the container)/1024     16035 ns     7747 ns
std::unordered_map&lt;int, int&gt;::erase(iterator, iterator) (erase half the container)/8192    122107 ns    73020 ns

Full diff: https://github.com/llvm/llvm-project/pull/152471.diff

1 Files Affected:

(modified) libcxx/include/__hash_table (+49-5)

diff --git a/libcxx/include/__hash_table b/libcxx/include/__hash_table
index dacc152030e14..2f0f9457f1416 100644
--- a/libcxx/include/__hash_table
+++ b/libcxx/include/__hash_table
@@ -1848,12 +1848,56 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) {
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, const_iterator __last) {
-  for (const_iterator __p = __first; __first != __last; __p = __first) {
-    ++__first;
-    erase(__p);
+  if (__first == __last)
+    return iterator(__last.__node_);
+
+  // current node
+  __next_pointer __current = __first.__node_;
+  size_type __bucket_count = bucket_count();
+  size_t __chash = std::__constrain_hash(__current->__hash(), __bucket_count);
+  // find previous node
+  __next_pointer __before_first = __bucket_list_[__chash];
+  for (; __before_first->__next_ != __current; __before_first = __before_first->__next_)
+    ;
+
+  __next_pointer __end = __last.__node_;
+
+  // If __before_first is in the same bucket, clear this bucket first without re-linking it
+  if (__before_first != __first_node_.__ptr() &&
+      std::__constrain_hash(__before_first->__hash(), __bucket_count) == __chash) {
+    while (__current != __end) {
+      if (auto __next_chash = std::__constrain_hash(__current->__hash(), __bucket_count); __next_chash != __chash) {
+        __chash = __next_chash;
+        break;
+      }
+      auto __next = __current->__next_;
+      __node_traits::deallocate(__node_alloc(), __current->__upcast(), 1);
+      __current = __next;
+      --__size_;
+    }
   }
-  __next_pointer __np = __last.__node_;
-  return iterator(__np);
+
+  while (__current != __end) {
+    auto __next = __current->__next_;
+    __node_traits::deallocate(__node_alloc(), __current->__upcast(), 1);
+    __current = __next;
+    --__size_;
+
+    // When switching buckets, set the old bucket to be empty and update the next bucket to have __before_first as its
+    // before-first element
+    if (__next) {
+      if (auto __next_chash = std::__constrain_hash(__next->__hash(), __bucket_count); __next_chash != __chash) {
+        __bucket_list_[__chash] = nullptr;
+        __chash                 = __next_chash;
+        __bucket_list_[__chash] = __before_first;
+      }
+    }
+  }
+
+  // re-link __before_start with __last
+  __before_first->__next_ = __current;
+
+  return iterator(__last.__node_);
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>

libcxx/include/__hash_table

boomanaiden154 · 2025-09-16T00:05:37Z

@philnik777 I'm seeing a regression under ASan (use after free after this patch). The following code snippet throws a use-after-free for me in final call to equal_range:

#include <unordered_map>
#include <utility>

typedef std::unordered_multimap<void*, void*> mapType;
typedef std::pair<mapType::iterator, mapType::iterator> erasePair;

int main(int argc, char** argv) {
  mapType map;
  map.insert(mapType::value_type((void*)0x7e4df9645ab8, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df9649868, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df9649cf0, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df964a200, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df964c700, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df964cad8, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df964cda0, (void*)5));
  // equal_range: 0x7e4df9645ab8
  erasePair pair1 = map.equal_range((void*)0x7e4df9645ab8);
  map.erase(pair1.first, pair1.second);
  map.insert(mapType::value_type((void*)0x7e4df9645f60, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df96505a8, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df964c700, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df964c700, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df9649cf0, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df9650078, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df9652258, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df9652638, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df96509d0, (void*)5));
  // equal_range: 0x7e4df9649868
  erasePair pair2 = map.equal_range((void*)0x7e4df9649868);
  map.erase(pair2.first, pair2.second);
  map.insert(mapType::value_type((void*)0x7e4df964def0, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df96598b0, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df965a160, (void*)5));
  // equal_range: 0x7e4df96505a8
  erasePair pair3 = map.equal_range((void*)0x7e4df96505a8);
  map.erase(pair3.first, pair3.second);
  map.insert(mapType::value_type((void*)0x7e4df9653810, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df9666340, (void*)5));
  // equal_range: 0x7e4df964c700
  erasePair pair4 = map.equal_range((void*)0x7e4df964c700);
  map.erase(pair4.first, pair4.second);
  map.insert(mapType::value_type((void*)0x7e4df965a880, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df965a880, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df965a880, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df96680c8, (void*)5));
  // equal_range: 0x7e4df9652258
  erasePair pair5 = map.equal_range((void*)0x7e4df9652258);
  map.erase(pair5.first, pair5.second);
  map.insert(mapType::value_type((void*)0x7e4df9666d98, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df966c608, (void*)5));
  map.insert(mapType::value_type((void*)0x7e4df966c9e0, (void*)5));
  erasePair test_pair = map.equal_range((void*)0x7e4df9649cf0);
  if (test_pair.first == test_pair.second) {
    return 1;
  }
  return 0;
}

Are you able to take a look?

…vm#152471)" This reverts commit e4eccd6. This was causing ASan failures in some situations involving unordered multimap containers. Details and a reproducer were posted on the original PR (llvm#152471).

#158769) …52471)" This reverts commit e4eccd6. This was causing ASan failures in some situations involving unordered multimap containers. Details and a reproducer were posted on the original PR (#152471).

nico · 2025-10-29T17:32:53Z

(This relanded in #162850.)

philnik777 marked this pull request as ready for review August 11, 2025 19:53

philnik777 requested a review from a team as a code owner August 11, 2025 19:53

llvmbot added the libc++ libc++ C++ Standard Library. Not GNU libstdc++. Not libc++abi. label Aug 11, 2025

ldionne added the performance label Aug 13, 2025

ldionne reviewed Aug 13, 2025

View reviewed changes

ldionne assigned philnik777 Aug 13, 2025

philnik777 force-pushed the optimize_hash_table_erase branch 2 times, most recently from 40ad452 to ff5a8ec Compare August 18, 2025 13:49

ldionne approved these changes Aug 22, 2025

View reviewed changes

philnik777 force-pushed the optimize_hash_table_erase branch from ff5a8ec to e006595 Compare August 25, 2025 07:11

[libc++] Optimize __hash_table::erase(iterator, iterator)

7bc9893

philnik777 force-pushed the optimize_hash_table_erase branch from e006595 to 7bc9893 Compare August 25, 2025 13:33

philnik777 merged commit e4eccd6 into llvm:main Aug 25, 2025
67 of 75 checks passed

philnik777 deleted the optimize_hash_table_erase branch August 25, 2025 19:45

boomanaiden154 mentioned this pull request Sep 16, 2025

Revert "[libc++] Optimize __hash_table::erase(iterator, iterator) (#1… #158769

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

[libc++] Optimize __hash_table::erase(iterator, iterator) #152471

[libc++] Optimize __hash_table::erase(iterator, iterator) #152471

Uh oh!

philnik777 commented Aug 7, 2025 •

edited

Loading

Uh oh!

github-actions bot commented Aug 7, 2025 •

edited

Loading

Uh oh!

llvmbot commented Aug 11, 2025

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

boomanaiden154 commented Sep 16, 2025

Uh oh!

nico commented Oct 29, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

[libc++] Optimize __hash_table::erase(iterator, iterator) #152471

[libc++] Optimize __hash_table::erase(iterator, iterator) #152471

Uh oh!

Conversation

philnik777 commented Aug 7, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

github-actions bot commented Aug 7, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

llvmbot commented Aug 11, 2025

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

boomanaiden154 commented Sep 16, 2025

Uh oh!

nico commented Oct 29, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

philnik777 commented Aug 7, 2025 •

edited

Loading

github-actions bot commented Aug 7, 2025 •

edited

Loading