| Issue |
241886
|
| Summary |
[libc++] std::map::extract becomes quadratic with debug hardening
|
| Labels |
libc++
|
| Assignees |
|
| Reporter |
oltolm
|
With `_LIBCPP_HARDENING_MODE_DEBUG`, repeatedly extracting nodes from a `std::map` performs a full-tree invariant check before **each** removal. Removing all `n` nodes therefore checks trees of sizes `n`, `n−1`, …, `1`, making the operation O(n²). This makes large maps very slow to drain while debugging.
### Reproducer
```cpp
#include <chrono>
#include <iostream>
#include <map>
int main() {
for (int n : {10000, 20000}) {
std::map<int, int> values;
for (int i = 0; i < n; ++i)
values.emplace(i, i);
const auto start = std::chrono::steady_clock::now();
while (!values.empty())
values.extract(values.begin());
const auto elapsed = std::chrono::steady_clock::now() - start;
std::cout << n << ": "
<< std::chrono::duration<double>(elapsed).count()
<< " seconds\n";
}
}
```
Compile with libc++ and `-D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_DEBUG`. Compare the scaling with `_LIBCPP_HARDENING_MODE_NONE`.
### Cause
In checkout `0abb04f84202c61210a2992e897efc745b869c68`, [`map::extract`](https://github.com/llvm/llvm-project/blob/0abb04f84202c61210a2992e897efc745b869c68/libcxx/include/map#L1351) reaches [`__tree_remove`](https://github.com/llvm/llvm-project/blob/0abb04f84202c61210a2992e897efc745b869c68/libcxx/include/__tree#L352), which calls `__tree_invariant(__root)`. That function recursively visits the tree. Debug hardening [enables the internal assertion](https://github.com/llvm/llvm-project/blob/0abb04f84202c61210a2992e897efc745b869c68/libcxx/include/__assert#L83).
Could the full-tree validation be made optional or moved out of the per-removal path? I understand that [debug hardening has no performance guarantee](https://libcxx.llvm.org/Hardening.html); this report concerns the particularly severe scaling when draining a map.
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs