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

Reply via email to