aboutsummaryrefslogtreecommitdiff
path: root/libcxx/include
AgeCommit message (Collapse)AuthorFilesLines
9 hours[libc++] Vectorize std::find (#156431)Nikolas Klauser3-23/+94
``` Apple M4: ----------------------------------------------------------------------------- Benchmark old new ----------------------------------------------------------------------------- std::find(vector<char>) (bail 25%)/8 1.43 ns 1.44 ns std::find(vector<char>) (bail 25%)/1024 5.54 ns 5.59 ns std::find(vector<char>) (bail 25%)/8192 38.4 ns 39.1 ns std::find(vector<char>) (bail 25%)/32768 134 ns 136 ns std::find(vector<int>) (bail 25%)/8 1.56 ns 1.57 ns std::find(vector<int>) (bail 25%)/1024 65.3 ns 65.4 ns std::find(vector<int>) (bail 25%)/8192 465 ns 464 ns std::find(vector<int>) (bail 25%)/32768 1832 ns 1832 ns std::find(vector<long long>) (bail 25%)/8 0.920 ns 1.20 ns std::find(vector<long long>) (bail 25%)/1024 65.2 ns 31.2 ns std::find(vector<long long>) (bail 25%)/8192 464 ns 255 ns std::find(vector<long long>) (bail 25%)/32768 1833 ns 992 ns std::find(vector<char>) (process all)/8 1.21 ns 1.22 ns std::find(vector<char>) (process all)/50 1.92 ns 1.93 ns std::find(vector<char>) (process all)/1024 16.6 ns 16.9 ns std::find(vector<char>) (process all)/8192 134 ns 136 ns std::find(vector<char>) (process all)/32768 488 ns 503 ns std::find(vector<int>) (process all)/8 2.45 ns 2.48 ns std::find(vector<int>) (process all)/50 12.7 ns 12.7 ns std::find(vector<int>) (process all)/1024 236 ns 236 ns std::find(vector<int>) (process all)/8192 1830 ns 1834 ns std::find(vector<int>) (process all)/32768 7351 ns 7346 ns std::find(vector<long long>) (process all)/8 2.02 ns 1.45 ns std::find(vector<long long>) (process all)/50 12.0 ns 6.12 ns std::find(vector<long long>) (process all)/1024 235 ns 123 ns std::find(vector<long long>) (process all)/8192 1830 ns 983 ns std::find(vector<long long>) (process all)/32768 7306 ns 3969 ns std::find(vector<bool>) (process all)/8 1.14 ns 1.15 ns std::find(vector<bool>) (process all)/50 1.16 ns 1.17 ns std::find(vector<bool>) (process all)/1024 4.51 ns 4.53 ns std::find(vector<bool>) (process all)/8192 33.6 ns 33.5 ns std::find(vector<bool>) (process all)/1048576 3660 ns 3660 ns ```
35 hours[libc++] Remove a bunch of unused includes from <flat_*> (#160658)Nikolas Klauser6-31/+4
2 days[libc++][ranges] Fix `ranges::join_view` segmented iterator trait (#158347)lbonn1-2/+7
The outer iterator needs to move to the next segment when calling __compose. Without this change, `find_segment_if` would never reach the end of the join_view which caused erroneous result when calling `ranges::find` on a join_view of bidirectional ranges. Other specializations using the segmented iterator trait were likely to be affected as well. Fixes #158279 Fixes #93180
4 daysRevert "[libc++] Avoid constructing additional objects when using map::at" ↵Andrew Lazarev11-185/+8
(#160738) Reverts llvm/llvm-project#157866 It breaks a lot of sanitizer buildbots
4 days[libc++] Use _BitInt and __builtin_popcountg in bitset::count() (#160679)Nikolas Klauser1-1/+10
This has multiple benefits: 1) The compiler has to do way less work to figure out things fold into a simple `popcount`, improving compile times quite a bit 2) The compiler inlines better, since the compile doesn't have to do complicated optimizations to get to the same point. Looking at the pipeline, it seems that without this, LLVM has to go all the way to GVN to get to the same code as there is after the first InstCombine pass with this change. Currently this applies only to `bitset`s with at most 64 bits, but that is by far the most common case.
4 days[libc++] Remove alignment attributes from _LIBCPP_COMPRESSED_PAIR (#158595)Nikolas Klauser1-7/+7
These attributes aren't required anymore, since the potential overalignemnt of the objects is handled by the surrounding anonymous struct.
4 days[libc++] Simplify vector<bool> fill constructors (#160521)Nikolas Klauser1-19/+8
#119632 introduced a code size and performance regression. This was verified by running the included benchmark against trunk and trunk with #119632 reverted. Instead of actually reverting that patch, we can inline `__construct_at_end` into the few places it's used instead, simplifying the implementation further (by not handling special cases we never actually encounter). ``` Benchmark Baseline Candidate Difference % Difference ------------------------ ---------- ----------- ------------ -------------- BM_vector_bool_size_ctor 29.91 8.56 -21.35 -71.37 ```
4 days[libc++] Remove __time_get_storage::{__analyze,init} from the ABI (#158469)Nikolas Klauser2-21/+4
These functions have never been used outside the dylib, so there is no point in exporting them.
4 days[libc++] Avoid constructing additional objects when using map::at (#157866)Nikolas Klauser11-8/+185
This patch adds additional overloads to `map::at` in case its known that the argument is transparently comparable to the key type. This avoids actually constructing the key type in some cases, potentially removing allocations. ``` -------------------------------------------------------- Benchmark old new -------------------------------------------------------- BM_map_find_string_literal 12.8 ns 2.68 ns ```
4 days[libc++][C++03] cherry-pick #104773 (#158244)Nikolas Klauser1-5/+8
4 days[libc++] Fold __search_substring into _Traits::find in case the second ↵Nikolas Klauser1-0/+7
string has length 1 (#160076) Apple M4: ``` Benchmark Baseline Candidate Difference % Difference ----------------------------------------------------------- ---------- ----------- ------------ -------------- BM_string_literal/1024 16.99 16.79 -0.21 -1.21 BM_string_literal/128 3.44 3.34 -0.10 -2.88 BM_string_literal/16 1.80 1.69 -0.11 -5.93 BM_string_literal/2048 38.44 38.38 -0.07 -0.17 BM_string_literal/256 5.77 5.65 -0.12 -2.02 BM_string_literal/32 2.03 1.92 -0.11 -5.44 BM_string_literal/4096 73.92 73.74 -0.18 -0.25 BM_string_literal/512 9.49 9.41 -0.08 -0.84 BM_string_literal/64 2.59 2.45 -0.14 -5.38 BM_string_literal/8 1.79 1.69 -0.11 -5.90 BM_string_literal/8192 132.09 131.81 -0.28 -0.21 ```
4 days[libc++][C++03] cherry-pick #106566 (#158250)Nikolas Klauser1-3/+15
4 days[libc++] Refactor some .fail.cpp tests and fix time_point_cast not SFINAEing ↵Nikolas Klauser2-2/+2
away (#159288) All of the `.fail.cpp` tests are actually testing constraints, so we should just test that the overloads SFINAE away correctly.
5 days[libc++][string] P3044R2: sub-`string_view` from `string` (#147095)Hristo Hristov3-0/+18
Implements [P3044R2](https://wg21.link/P3044R2) Note: `substr.pass.cpp` is refactored to accommodate the test of `basic_string_view`'s `subview` which is an alias of `substr` without changing the test cases. Closes #148140 # References - https://github.com/cplusplus/draft/pull/7975 - https://wg21.link/string.substr - https://wg21.link/string.view.ops --------- Co-authored-by: Hristo Hristov <zingam@outlook.com> Co-authored-by: Nikolas Klauser <nikolasklauser@berlin.de>
5 days[libc++] Fix __gnu_cxx::hash_multiset copy construction (#160466)Nikolas Klauser1-4/+1
5 days[libc++][C++03] cherry-pick #119801 (#158247)Nikolas Klauser1-1/+1
5 days[libc++][NFC] Refactor __is_allocator to be a variable template (#159584)Nikolas Klauser18-238/+226
5 days[libc++] Simplify __memory/shared_count.h a bit (#160048)Nikolas Klauser3-33/+23
This removes a few checks that aren't required anymore and moves some code around to the places where it's actually used.
5 days[libc++] Simplify some of the <bit> functions (#160267)Nikolas Klauser4-29/+18
6 days[libc++] Implement Resolution of LWG 3886 (#155356)William Tran-Viet2-12/+13
Resolves #118336 - Implement the resolution of [LWG3886](https://cplusplus.github.io/LWG/issue3886) for `optional` and `expected`
6 days[libc++] Fix use of static in constexpr (#160180)Prabhu Rajasekaran1-1/+1
`static` is not allowed inside constexpr functions in C++ versions below 23. This is causing a build error when compiled with GCC and warning when compiled with Clang. This patch fixes this. --------- Co-authored-by: A. Jiang <de34@live.cn>
6 days[libc++][atomic_ref] Use __atomic_fetch_{add,sub} builtins on ↵Damien L-G5-36/+79
floating-points whenever possible (#135685) Fix #135109 Clang is able to emit an `atomicrmw` instruction from the `__atomic_fetch_add` and `__atomic_fetch_sub` builtins on floating-point types.
6 days[libc++] Fix __gnu_cxx::hash_multimap copy construction (#160043)Nikolas Klauser1-4/+1
6 days[libc++] Remove outdated FIXME comment in ctype<char> (#160008)Fady Farag2-2/+2
The FIXME comment about not hardcoding table_size is unclear about its original intent.
6 days[libc++][NFC] Remove guard around noop_coroutine_handle.h (#160044)Nikolas Klauser1-9/+5
This check is always true, since all supported version of Clang have `__builtin_coro_noop` and the only other supported compiler is GCC.
6 days[libc++] Remove a few unused includes from <string> and <vector> (#160087)Nikolas Klauser2-5/+0
7 days[libc++][NFC] Reformat some deduction guides (#160085)Nikolas Klauser5-41/+33
They're not formatted correctly anymore, since clang-format was updated.
11 days[libc++] Refactor memory allocation in basic_string (#128423)Nikolas Klauser2-187/+134
This patch introduces a string-internal API to make the allocation and deallocation the long string simpler. Before this we had a lot of code duplication, so ensuring that things were actually correct was non-trivial.
11 days[libc++] Introduce _LIBCPP_COMPRESSED_ELEMENT (#134253)Nikolas Klauser4-158/+27
We have multiple classes with an empty base optimization that contains just a single type. This patch introduces `_LIBCPP_COMPRESSED_ELEMENT` to refactor these classes to avoid having them essentially twice, reducing the amount of code significantly.
12 daysRevert "[libc++] Optimize __hash_table::erase(iterator, iterator) (#1… ↵Aiden Grossman1-74/+28
(#158769) …52471)" This reverts commit e4eccd6a3c2415c10bb8217c247d7aca76cc9ad5. This was causing ASan failures in some situations involving unordered multimap containers. Details and a reproducer were posted on the original PR (#152471).
12 daysReapply "[libc++] Mark __{emplace,push}_back_slow_path as noinline (#94379)" ↵Nikolas Klauser1-6/+26
(#158606) This reverts commit 7f2e9b17098f42c85ef469b029bb84ef4eea189c. The LLDB failures have been resolved in trunk.
13 days[libc++] Replace __resize_default_init with resize_and_overwrite (#157121)Nikolas Klauser1-32/+8
Since `__resize_default_init` is only ever used inside the dylib we can remove the libc++-internal API and switch to the public one. This patch inlines a bunch of functions that aren't required anymore and simplifies the code that way.
2025-09-15[libc++] Specialize __lazy_synth_three_way_comparator for std::greater and ↵Nikolas Klauser1-6/+22
friends (#157624) This specializes `__lazy_synth_three_way_comparator` to forward to `__default_three_way_comparator` if the comparator desugars to `__greater_tag`. This is the same as the desugaring to `__less_tag` except that the sign has to be inverted.
2025-09-12Revert "[libc++] Mark __{emplace,push}_back_slow_path as noinline (#94379)"Aiden Grossman1-26/+6
This reverts commit 1bafd020c7c80be476f211bc239ce43424f7e0ce. This breaks the LLDB data formatters which means these failures show up on every premerge run. Reverting for now until fixing the LLDB formatters can be coordinated with a relanding.
2025-09-12[libcxx] adds size-based `__split_buffer` representation to unstable ABI ↵Christopher Di Bella3-276/+668
(#139632) **tl;dr** We can significantly improve the runtime performance of `std::vector` by changing its representation from three pointers to one pointer and two integers. This document explains the details of this change, along with the justifications for making it. See the [RFC] for more information. `vector` depends on `__split_buffer` for inserting elements. Changing `__split_buffer` to match `vector`'s representation simplifies the model, as it eliminates the need to convert between two different representations of a contiguous buffer in the same configuration of libc++. [RFC]: https://discourse.llvm.org/t/adding-a-size-based-vector-to-libc-s-unstable-abi/86306 --------- Co-authored-by: Jorge Gorbe Moya <jgorbe@google.com>
2025-09-12[libc++] Mark __{emplace,push}_back_slow_path as noinline (#94379)Nikolas Klauser1-6/+26
These are almost certainly intended to not be inlined. This significantly reduces code size when `push_back` and `emplace_back` are used heavily. Fixes #94360
2025-09-12[libc++] Extend __default_three_way_comparator to any types that only ↵Nikolas Klauser4-11/+39
implements operator<=> (#157602) This uses the new `__builtin_lt_synthesises_from_spaceship` builtin from clang to use three way comparison for arbitrary user-defined types that only provide a spaceship operator.
2025-09-12[libc++][C++03] cherry-pick #101889 (#157881)Nikolas Klauser4-36/+46
2025-09-11[libc++] Remove UB from `std::__tree_node` construction (#153908)Vinay Deshmukh3-20/+35
This patch also updates `__hash_table` to match what we do in `__tree` now. Fixes #102547 Fixes https://github.com/llvm/llvm-project/pull/134330#discussion_r2265558356
2025-09-11[libc++][C++03] partially cherry-pick #122641 (#157596)Nikolas Klauser1-3/+3
This patch only cherry-picks the parts that actually fix the issue, but not the numerous NFC refactorings around it.
2025-09-10[NFC][libc++] Fix typo in `libcxx/include/__memory/pointer_traits.h` (#157304)Vinay Deshmukh1-1/+1
* Apply the typo fix as a separate NFC patch from here: https://github.com/llvm/llvm-project/pull/134330/files#r2313015079
2025-09-09[libc++] Remove some of the type aliases in __hash_table (#157114)Nikolas Klauser3-54/+25
2025-09-09[libc++][C++03] cherry-pick #112102 (#157104)Nikolas Klauser1-1/+17
2025-09-09[libc++] Fix missing macro definition for lgamma (#157610)Joseph Huber1-0/+2
2025-09-09[libc++][NFC] Move some really simple function defintions into the body of ↵Nikolas Klauser1-46/+25
__tree (#157424)
2025-09-08[libc++] Conditionally declare `lgamma_r` as noexcept (#156547)Yuxuan Chen1-4/+14
An older PR https://github.com/llvm/llvm-project/pull/102036 suggested that LLVM libc declares `lgamma_r` as noexcept and is incompatible with this redeclaration. However, I recently discovered that glibc also declares the math functions to be noexcept under C++ mode. This line usually don't cause issues because both the glibc and this file are included as "system headers". According to [this godbolt](https://godbolt.org/z/o7Wd9PP58), both GCC and clang ignore the different exception specification between multiple declarations if they are in system headers. However, this seems not the case for NVCC/EDG, so a fix for this redeclaration is still desirable. This patch proposes that we should declare the function as noexcept under known libc integrations to keep the declared function consistent.
2025-09-08[libc++] Improve the performance of std::make_heap a bit (#154092)Nikolas Klauser4-24/+37
``` Apple M4: ----------------------------------------------------------------------------------------------------- Benchmark old new ----------------------------------------------------------------------------------------------------- BM_MakeHeap_uint32_Random_1 0.285 ns 0.271 ns BM_MakeHeap_uint32_Random_4 2.09 ns 1.80 ns BM_MakeHeap_uint32_Random_16 1.85 ns 1.83 ns BM_MakeHeap_uint32_Random_64 1.92 ns 1.50 ns BM_MakeHeap_uint32_Random_256 2.10 ns 1.87 ns BM_MakeHeap_uint32_Random_1024 1.73 ns 1.86 ns BM_MakeHeap_uint32_Random_16384 2.17 ns 2.05 ns BM_MakeHeap_uint32_Random_262144 1.77 ns 1.77 ns BM_MakeHeap_uint32_Ascending_1 0.288 ns 0.277 ns BM_MakeHeap_uint32_Ascending_4 0.658 ns 0.481 ns BM_MakeHeap_uint32_Ascending_16 0.636 ns 0.637 ns BM_MakeHeap_uint32_Ascending_64 0.643 ns 0.601 ns BM_MakeHeap_uint32_Ascending_256 0.710 ns 0.636 ns BM_MakeHeap_uint32_Ascending_1024 0.747 ns 0.660 ns BM_MakeHeap_uint32_Ascending_16384 0.713 ns 0.633 ns BM_MakeHeap_uint32_Ascending_262144 0.769 ns 0.731 ns BM_MakeHeap_uint32_Descending_1 0.294 ns 0.280 ns BM_MakeHeap_uint32_Descending_4 0.379 ns 0.305 ns BM_MakeHeap_uint32_Descending_16 0.376 ns 0.268 ns BM_MakeHeap_uint32_Descending_64 0.358 ns 0.271 ns BM_MakeHeap_uint32_Descending_256 0.377 ns 0.284 ns BM_MakeHeap_uint32_Descending_1024 0.355 ns 0.267 ns BM_MakeHeap_uint32_Descending_16384 0.348 ns 0.248 ns BM_MakeHeap_uint32_Descending_262144 0.349 ns 0.247 ns BM_MakeHeap_uint32_SingleElement_1 0.292 ns 0.280 ns BM_MakeHeap_uint32_SingleElement_4 0.570 ns 0.332 ns BM_MakeHeap_uint32_SingleElement_16 0.635 ns 0.604 ns BM_MakeHeap_uint32_SingleElement_64 0.653 ns 0.567 ns BM_MakeHeap_uint32_SingleElement_256 0.703 ns 0.609 ns BM_MakeHeap_uint32_SingleElement_1024 0.737 ns 0.604 ns BM_MakeHeap_uint32_SingleElement_16384 0.699 ns 0.574 ns BM_MakeHeap_uint32_SingleElement_262144 0.803 ns 0.684 ns BM_MakeHeap_uint32_PipeOrgan_1 0.291 ns 0.284 ns BM_MakeHeap_uint32_PipeOrgan_4 0.588 ns 0.399 ns BM_MakeHeap_uint32_PipeOrgan_16 0.648 ns 1.12 ns BM_MakeHeap_uint32_PipeOrgan_64 0.662 ns 0.771 ns BM_MakeHeap_uint32_PipeOrgan_256 0.723 ns 0.672 ns BM_MakeHeap_uint32_PipeOrgan_1024 0.749 ns 0.674 ns BM_MakeHeap_uint32_PipeOrgan_16384 0.708 ns 0.638 ns BM_MakeHeap_uint32_PipeOrgan_262144 0.786 ns 0.743 ns BM_MakeHeap_uint32_Heap_1 0.298 ns 0.282 ns BM_MakeHeap_uint32_Heap_4 0.396 ns 0.308 ns BM_MakeHeap_uint32_Heap_16 0.377 ns 0.268 ns BM_MakeHeap_uint32_Heap_64 0.356 ns 0.271 ns BM_MakeHeap_uint32_Heap_256 0.378 ns 0.290 ns BM_MakeHeap_uint32_Heap_1024 0.356 ns 0.275 ns BM_MakeHeap_uint32_Heap_16384 0.348 ns 0.252 ns BM_MakeHeap_uint32_Heap_262144 0.347 ns 0.250 ns BM_MakeHeap_uint32_QuickSortAdversary_1 0.290 ns 0.284 ns BM_MakeHeap_uint32_QuickSortAdversary_4 0.627 ns 0.409 ns BM_MakeHeap_uint32_QuickSortAdversary_16 0.640 ns 0.653 ns BM_MakeHeap_uint32_QuickSortAdversary_64 0.577 ns 0.484 ns BM_MakeHeap_uint32_QuickSortAdversary_256 0.613 ns 0.521 ns BM_MakeHeap_uint32_QuickSortAdversary_1024 0.652 ns 0.514 ns BM_MakeHeap_uint32_QuickSortAdversary_16384 0.428 ns 0.308 ns BM_MakeHeap_uint32_QuickSortAdversary_262144 0.373 ns 0.261 ns BM_MakeHeap_uint64_Random_1 0.291 ns 0.281 ns BM_MakeHeap_uint64_Random_4 2.20 ns 1.97 ns BM_MakeHeap_uint64_Random_16 1.93 ns 1.70 ns BM_MakeHeap_uint64_Random_64 1.89 ns 1.48 ns BM_MakeHeap_uint64_Random_256 2.10 ns 1.99 ns BM_MakeHeap_uint64_Random_1024 1.41 ns 2.04 ns BM_MakeHeap_uint64_Random_16384 2.12 ns 1.83 ns BM_MakeHeap_uint64_Random_262144 1.83 ns 1.63 ns BM_MakeHeap_uint64_Ascending_1 0.288 ns 0.283 ns BM_MakeHeap_uint64_Ascending_4 0.624 ns 0.493 ns BM_MakeHeap_uint64_Ascending_16 0.648 ns 0.688 ns BM_MakeHeap_uint64_Ascending_64 0.671 ns 0.634 ns BM_MakeHeap_uint64_Ascending_256 0.739 ns 0.680 ns BM_MakeHeap_uint64_Ascending_1024 0.761 ns 0.698 ns BM_MakeHeap_uint64_Ascending_16384 0.740 ns 0.685 ns BM_MakeHeap_uint64_Ascending_262144 0.849 ns 0.837 ns BM_MakeHeap_uint64_Descending_1 0.304 ns 0.287 ns BM_MakeHeap_uint64_Descending_4 0.395 ns 0.312 ns BM_MakeHeap_uint64_Descending_16 0.374 ns 0.276 ns BM_MakeHeap_uint64_Descending_64 0.358 ns 0.272 ns BM_MakeHeap_uint64_Descending_256 0.389 ns 0.303 ns BM_MakeHeap_uint64_Descending_1024 0.361 ns 0.278 ns BM_MakeHeap_uint64_Descending_16384 0.352 ns 0.253 ns BM_MakeHeap_uint64_Descending_262144 0.350 ns 0.251 ns BM_MakeHeap_uint64_SingleElement_1 0.295 ns 0.285 ns BM_MakeHeap_uint64_SingleElement_4 0.569 ns 0.358 ns BM_MakeHeap_uint64_SingleElement_16 0.649 ns 0.652 ns BM_MakeHeap_uint64_SingleElement_64 0.673 ns 0.565 ns BM_MakeHeap_uint64_SingleElement_256 0.732 ns 0.651 ns BM_MakeHeap_uint64_SingleElement_1024 0.759 ns 0.632 ns BM_MakeHeap_uint64_SingleElement_16384 0.748 ns 0.614 ns BM_MakeHeap_uint64_SingleElement_262144 0.947 ns 0.797 ns BM_MakeHeap_uint64_PipeOrgan_1 0.295 ns 0.284 ns BM_MakeHeap_uint64_PipeOrgan_4 0.601 ns 0.496 ns BM_MakeHeap_uint64_PipeOrgan_16 0.655 ns 1.18 ns BM_MakeHeap_uint64_PipeOrgan_64 0.682 ns 0.803 ns BM_MakeHeap_uint64_PipeOrgan_256 0.759 ns 0.710 ns BM_MakeHeap_uint64_PipeOrgan_1024 0.759 ns 0.713 ns BM_MakeHeap_uint64_PipeOrgan_16384 0.739 ns 0.696 ns BM_MakeHeap_uint64_PipeOrgan_262144 0.870 ns 0.849 ns BM_MakeHeap_uint64_Heap_1 0.290 ns 0.284 ns BM_MakeHeap_uint64_Heap_4 0.413 ns 0.314 ns BM_MakeHeap_uint64_Heap_16 0.378 ns 0.277 ns BM_MakeHeap_uint64_Heap_64 0.362 ns 0.272 ns BM_MakeHeap_uint64_Heap_256 0.389 ns 0.303 ns BM_MakeHeap_uint64_Heap_1024 0.362 ns 0.283 ns BM_MakeHeap_uint64_Heap_16384 0.352 ns 0.253 ns BM_MakeHeap_uint64_Heap_262144 0.350 ns 0.251 ns BM_MakeHeap_uint64_QuickSortAdversary_1 0.293 ns 0.284 ns BM_MakeHeap_uint64_QuickSortAdversary_4 0.606 ns 0.494 ns BM_MakeHeap_uint64_QuickSortAdversary_16 0.645 ns 0.691 ns BM_MakeHeap_uint64_QuickSortAdversary_64 0.607 ns 0.511 ns BM_MakeHeap_uint64_QuickSortAdversary_256 0.641 ns 0.537 ns BM_MakeHeap_uint64_QuickSortAdversary_1024 0.657 ns 0.529 ns BM_MakeHeap_uint64_QuickSortAdversary_16384 0.435 ns 0.316 ns BM_MakeHeap_uint64_QuickSortAdversary_262144 0.382 ns 0.266 ns BM_MakeHeap_pair<uint32, uint32>_Random_1 0.297 ns 0.378 ns BM_MakeHeap_pair<uint32, uint32>_Random_4 2.80 ns 0.765 ns BM_MakeHeap_pair<uint32, uint32>_Random_16 2.92 ns 2.20 ns BM_MakeHeap_pair<uint32, uint32>_Random_64 3.17 ns 3.64 ns BM_MakeHeap_pair<uint32, uint32>_Random_256 3.44 ns 3.20 ns BM_MakeHeap_pair<uint32, uint32>_Random_1024 3.35 ns 3.64 ns BM_MakeHeap_pair<uint32, uint32>_Random_16384 3.22 ns 3.50 ns BM_MakeHeap_pair<uint32, uint32>_Random_262144 3.61 ns 3.46 ns BM_MakeHeap_pair<uint32, uint32>_Ascending_1 0.291 ns 0.379 ns BM_MakeHeap_pair<uint32, uint32>_Ascending_4 0.779 ns 0.436 ns BM_MakeHeap_pair<uint32, uint32>_Ascending_16 0.943 ns 1.01 ns BM_MakeHeap_pair<uint32, uint32>_Ascending_64 1.17 ns 1.26 ns BM_MakeHeap_pair<uint32, uint32>_Ascending_256 1.38 ns 1.44 ns BM_MakeHeap_pair<uint32, uint32>_Ascending_1024 1.37 ns 1.43 ns BM_MakeHeap_pair<uint32, uint32>_Ascending_16384 1.29 ns 1.31 ns BM_MakeHeap_pair<uint32, uint32>_Ascending_262144 1.37 ns 1.40 ns BM_MakeHeap_pair<uint32, uint32>_Descending_1 0.292 ns 0.382 ns BM_MakeHeap_pair<uint32, uint32>_Descending_4 0.440 ns 0.347 ns BM_MakeHeap_pair<uint32, uint32>_Descending_16 0.529 ns 0.520 ns BM_MakeHeap_pair<uint32, uint32>_Descending_64 0.540 ns 0.527 ns BM_MakeHeap_pair<uint32, uint32>_Descending_256 0.637 ns 0.583 ns BM_MakeHeap_pair<uint32, uint32>_Descending_1024 0.552 ns 0.513 ns BM_MakeHeap_pair<uint32, uint32>_Descending_16384 0.522 ns 0.488 ns BM_MakeHeap_pair<uint32, uint32>_Descending_262144 0.515 ns 0.492 ns BM_MakeHeap_pair<uint32, uint32>_SingleElement_1 0.299 ns 0.377 ns BM_MakeHeap_pair<uint32, uint32>_SingleElement_4 0.787 ns 0.474 ns BM_MakeHeap_pair<uint32, uint32>_SingleElement_16 1.07 ns 0.921 ns BM_MakeHeap_pair<uint32, uint32>_SingleElement_64 1.20 ns 1.15 ns BM_MakeHeap_pair<uint32, uint32>_SingleElement_256 1.30 ns 1.27 ns BM_MakeHeap_pair<uint32, uint32>_SingleElement_1024 1.30 ns 1.31 ns BM_MakeHeap_pair<uint32, uint32>_SingleElement_16384 1.29 ns 1.28 ns BM_MakeHeap_pair<uint32, uint32>_SingleElement_262144 1.37 ns 1.38 ns BM_MakeHeap_pair<uint32, uint32>_PipeOrgan_1 0.293 ns 0.385 ns BM_MakeHeap_pair<uint32, uint32>_PipeOrgan_4 0.677 ns 0.438 ns BM_MakeHeap_pair<uint32, uint32>_PipeOrgan_16 1.04 ns 1.00 ns BM_MakeHeap_pair<uint32, uint32>_PipeOrgan_64 1.20 ns 1.27 ns BM_MakeHeap_pair<uint32, uint32>_PipeOrgan_256 1.40 ns 1.43 ns BM_MakeHeap_pair<uint32, uint32>_PipeOrgan_1024 1.36 ns 1.43 ns BM_MakeHeap_pair<uint32, uint32>_PipeOrgan_16384 1.27 ns 1.31 ns BM_MakeHeap_pair<uint32, uint32>_PipeOrgan_262144 1.37 ns 1.41 ns BM_MakeHeap_pair<uint32, uint32>_Heap_1 0.292 ns 0.378 ns BM_MakeHeap_pair<uint32, uint32>_Heap_4 0.440 ns 0.380 ns BM_MakeHeap_pair<uint32, uint32>_Heap_16 0.560 ns 0.606 ns BM_MakeHeap_pair<uint32, uint32>_Heap_64 0.588 ns 0.573 ns BM_MakeHeap_pair<uint32, uint32>_Heap_256 0.632 ns 0.607 ns BM_MakeHeap_pair<uint32, uint32>_Heap_1024 0.598 ns 0.580 ns BM_MakeHeap_pair<uint32, uint32>_Heap_16384 0.576 ns 0.563 ns BM_MakeHeap_pair<uint32, uint32>_Heap_262144 0.572 ns 0.561 ns BM_MakeHeap_pair<uint32, uint32>_QuickSortAdversary_1 0.304 ns 0.379 ns BM_MakeHeap_pair<uint32, uint32>_QuickSortAdversary_4 0.823 ns 0.430 ns BM_MakeHeap_pair<uint32, uint32>_QuickSortAdversary_16 1.08 ns 1.03 ns BM_MakeHeap_pair<uint32, uint32>_QuickSortAdversary_64 1.18 ns 1.23 ns BM_MakeHeap_pair<uint32, uint32>_QuickSortAdversary_256 1.39 ns 1.43 ns BM_MakeHeap_pair<uint32, uint32>_QuickSortAdversary_1024 1.36 ns 1.42 ns BM_MakeHeap_pair<uint32, uint32>_QuickSortAdversary_16384 1.28 ns 1.32 ns BM_MakeHeap_pair<uint32, uint32>_QuickSortAdversary_262144 1.34 ns 1.37 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Random_1 0.276 ns 0.511 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Random_4 4.25 ns 1.96 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Random_16 4.84 ns 3.77 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Random_64 5.53 ns 4.93 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Random_256 5.30 ns 5.06 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Random_1024 5.29 ns 5.02 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Random_16384 5.53 ns 5.31 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Random_262144 5.49 ns 5.29 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Ascending_1 0.275 ns 0.443 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Ascending_4 1.22 ns 0.764 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Ascending_16 1.39 ns 1.49 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Ascending_64 1.66 ns 1.76 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Ascending_256 1.85 ns 1.99 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Ascending_1024 1.90 ns 2.02 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Ascending_16384 2.15 ns 2.27 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Ascending_262144 2.25 ns 2.37 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Descending_1 0.274 ns 0.445 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Descending_4 0.939 ns 0.520 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Descending_16 1.02 ns 0.811 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Descending_64 1.01 ns 0.941 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Descending_256 1.03 ns 1.01 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Descending_1024 0.969 ns 0.947 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Descending_16384 0.882 ns 0.876 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Descending_262144 0.893 ns 0.871 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_SingleElement_1 0.276 ns 0.443 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_SingleElement_4 1.34 ns 0.870 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_SingleElement_16 1.60 ns 1.59 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_SingleElement_64 1.91 ns 2.00 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_SingleElement_256 1.91 ns 2.08 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_SingleElement_1024 1.91 ns 2.10 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_SingleElement_16384 2.13 ns 2.35 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_SingleElement_262144 2.25 ns 2.48 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_PipeOrgan_1 0.275 ns 0.446 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_PipeOrgan_4 1.07 ns 0.671 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_PipeOrgan_16 1.36 ns 1.44 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_PipeOrgan_64 1.70 ns 1.80 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_PipeOrgan_256 1.88 ns 2.05 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_PipeOrgan_1024 1.92 ns 2.06 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_PipeOrgan_16384 2.11 ns 2.26 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_PipeOrgan_262144 2.18 ns 2.34 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Heap_1 0.274 ns 0.441 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Heap_4 0.938 ns 0.587 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Heap_16 1.01 ns 0.873 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Heap_64 1.08 ns 1.00 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Heap_256 1.21 ns 1.18 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Heap_1024 1.37 ns 1.29 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Heap_16384 1.31 ns 1.26 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_Heap_262144 1.29 ns 1.25 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_QuickSortAdversary_1 0.275 ns 0.447 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_QuickSortAdversary_4 1.22 ns 0.764 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_QuickSortAdversary_16 1.35 ns 1.46 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_QuickSortAdversary_64 1.63 ns 1.73 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_QuickSortAdversary_256 1.83 ns 1.87 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_QuickSortAdversary_1024 1.81 ns 1.94 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_QuickSortAdversary_16384 2.06 ns 2.19 ns BM_MakeHeap_tuple<uint32, uint64, uint32>_QuickSortAdversary_262144 2.14 ns 2.31 ns BM_MakeHeap_string_Random_1 0.289 ns 0.446 ns BM_MakeHeap_string_Random_4 7.43 ns 4.84 ns BM_MakeHeap_string_Random_16 9.73 ns 8.92 ns BM_MakeHeap_string_Random_64 11.5 ns 11.5 ns BM_MakeHeap_string_Random_256 12.6 ns 12.4 ns BM_MakeHeap_string_Random_1024 13.2 ns 13.2 ns BM_MakeHeap_string_Random_16384 15.4 ns 15.4 ns BM_MakeHeap_string_Random_262144 21.4 ns 21.5 ns BM_MakeHeap_string_Ascending_1 0.287 ns 0.447 ns BM_MakeHeap_string_Ascending_4 3.22 ns 2.44 ns BM_MakeHeap_string_Ascending_16 3.77 ns 3.62 ns BM_MakeHeap_string_Ascending_64 4.84 ns 5.17 ns BM_MakeHeap_string_Ascending_256 5.79 ns 6.04 ns BM_MakeHeap_string_Ascending_1024 5.93 ns 6.60 ns BM_MakeHeap_string_Ascending_16384 6.84 ns 7.25 ns BM_MakeHeap_string_Ascending_262144 13.5 ns 14.3 ns BM_MakeHeap_string_Descending_1 0.293 ns 0.447 ns BM_MakeHeap_string_Descending_4 2.61 ns 1.83 ns BM_MakeHeap_string_Descending_16 2.64 ns 2.60 ns BM_MakeHeap_string_Descending_64 2.75 ns 2.74 ns BM_MakeHeap_string_Descending_256 3.78 ns 3.57 ns BM_MakeHeap_string_Descending_1024 3.20 ns 3.51 ns BM_MakeHeap_string_Descending_16384 3.57 ns 3.85 ns BM_MakeHeap_string_Descending_262144 6.27 ns 6.39 ns BM_MakeHeap_string_SingleElement_1 0.291 ns 0.448 ns BM_MakeHeap_string_SingleElement_4 3.88 ns 2.71 ns BM_MakeHeap_string_SingleElement_16 5.08 ns 4.96 ns BM_MakeHeap_string_SingleElement_64 6.14 ns 6.29 ns BM_MakeHeap_string_SingleElement_256 6.13 ns 6.46 ns BM_MakeHeap_string_SingleElement_1024 5.98 ns 6.60 ns BM_MakeHeap_string_SingleElement_16384 5.88 ns 6.39 ns BM_MakeHeap_string_SingleElement_262144 9.95 ns 10.2 ns BM_MakeHeap_string_PipeOrgan_1 0.292 ns 0.447 ns BM_MakeHeap_string_PipeOrgan_4 2.97 ns 2.51 ns BM_MakeHeap_string_PipeOrgan_16 3.76 ns 3.91 ns BM_MakeHeap_string_PipeOrgan_64 4.89 ns 5.20 ns BM_MakeHeap_string_PipeOrgan_256 5.77 ns 6.09 ns BM_MakeHeap_string_PipeOrgan_1024 6.14 ns 6.40 ns BM_MakeHeap_string_PipeOrgan_16384 6.83 ns 7.32 ns BM_MakeHeap_string_PipeOrgan_262144 13.8 ns 14.6 ns BM_MakeHeap_string_Heap_1 0.288 ns 0.515 ns BM_MakeHeap_string_Heap_4 3.62 ns 4.20 ns BM_MakeHeap_string_Heap_16 5.36 ns 5.23 ns BM_MakeHeap_string_Heap_64 5.79 ns 5.38 ns BM_MakeHeap_string_Heap_256 5.70 ns 5.40 ns BM_MakeHeap_string_Heap_1024 5.78 ns 5.37 ns BM_MakeHeap_string_Heap_16384 6.09 ns 5.67 ns BM_MakeHeap_string_Heap_262144 6.37 ns 5.96 ns BM_MakeHeap_string_QuickSortAdversary_1 0.282 ns 0.448 ns BM_MakeHeap_string_QuickSortAdversary_4 7.45 ns 5.60 ns BM_MakeHeap_string_QuickSortAdversary_16 9.76 ns 8.85 ns BM_MakeHeap_string_QuickSortAdversary_64 11.5 ns 11.2 ns BM_MakeHeap_string_QuickSortAdversary_256 12.0 ns 11.8 ns BM_MakeHeap_string_QuickSortAdversary_1024 12.2 ns 12.0 ns BM_MakeHeap_string_QuickSortAdversary_16384 13.7 ns 13.6 ns BM_MakeHeap_string_QuickSortAdversary_262144 14.1 ns 14.8 ns BM_MakeHeap_float_Random_1 0.287 ns 0.287 ns BM_MakeHeap_float_Random_4 2.29 ns 2.60 ns BM_MakeHeap_float_Random_16 4.00 ns 2.48 ns BM_MakeHeap_float_Random_64 4.41 ns 1.92 ns BM_MakeHeap_float_Random_256 4.73 ns 2.05 ns BM_MakeHeap_float_Random_1024 4.90 ns 2.27 ns BM_MakeHeap_float_Random_16384 4.42 ns 2.27 ns BM_MakeHeap_float_Random_262144 4.72 ns 1.39 ns BM_MakeHeap_float_Ascending_1 0.291 ns 0.293 ns BM_MakeHeap_float_Ascending_4 0.633 ns 0.428 ns BM_MakeHeap_float_Ascending_16 0.638 ns 0.874 ns BM_MakeHeap_float_Ascending_64 0.614 ns 0.698 ns BM_MakeHeap_float_Ascending_256 0.663 ns 0.713 ns BM_MakeHeap_float_Ascending_1024 0.660 ns 0.761 ns BM_MakeHeap_float_Ascending_16384 0.628 ns 0.725 ns BM_MakeHeap_float_Ascending_262144 0.629 ns 0.814 ns BM_MakeHeap_float_Descending_1 0.290 ns 0.290 ns BM_MakeHeap_float_Descending_4 0.421 ns 0.316 ns BM_MakeHeap_float_Descending_16 0.302 ns 0.225 ns BM_MakeHeap_float_Descending_64 0.293 ns 0.212 ns BM_MakeHeap_float_Descending_256 0.314 ns 0.246 ns BM_MakeHeap_float_Descending_1024 0.300 ns 0.231 ns BM_MakeHeap_float_Descending_16384 0.308 ns 0.205 ns BM_MakeHeap_float_Descending_262144 0.309 ns 0.203 ns BM_MakeHeap_float_SingleElement_1 0.289 ns 0.292 ns BM_MakeHeap_float_SingleElement_4 0.569 ns 0.347 ns BM_MakeHeap_float_SingleElement_16 0.538 ns 0.825 ns BM_MakeHeap_float_SingleElement_64 0.585 ns 0.727 ns BM_MakeHeap_float_SingleElement_256 0.603 ns 0.708 ns BM_MakeHeap_float_SingleElement_1024 0.618 ns 0.760 ns BM_MakeHeap_float_SingleElement_16384 0.599 ns 0.726 ns BM_MakeHeap_float_SingleElement_262144 0.723 ns 0.820 ns BM_MakeHeap_float_PipeOrgan_1 0.289 ns 0.291 ns BM_MakeHeap_float_PipeOrgan_4 0.457 ns 0.420 ns BM_MakeHeap_float_PipeOrgan_16 0.670 ns 1.32 ns BM_MakeHeap_float_PipeOrgan_64 0.764 ns 0.889 ns BM_MakeHeap_float_PipeOrgan_256 0.793 ns 0.757 ns BM_MakeHeap_float_PipeOrgan_1024 0.755 ns 0.764 ns BM_MakeHeap_float_PipeOrgan_16384 0.723 ns 0.723 ns BM_MakeHeap_float_PipeOrgan_262144 0.654 ns 0.817 ns BM_MakeHeap_float_Heap_1 0.291 ns 0.289 ns BM_MakeHeap_float_Heap_4 0.388 ns 0.316 ns BM_MakeHeap_float_Heap_16 0.317 ns 0.225 ns BM_MakeHeap_float_Heap_64 0.353 ns 0.213 ns BM_MakeHeap_float_Heap_256 0.361 ns 0.246 ns BM_MakeHeap_float_Heap_1024 0.381 ns 0.233 ns BM_MakeHeap_float_Heap_16384 0.390 ns 0.205 ns BM_MakeHeap_float_Heap_262144 0.379 ns 0.202 ns BM_MakeHeap_float_QuickSortAdversary_1 0.295 ns 0.289 ns BM_MakeHeap_float_QuickSortAdversary_4 0.640 ns 0.422 ns BM_MakeHeap_float_QuickSortAdversary_16 0.658 ns 0.871 ns BM_MakeHeap_float_QuickSortAdversary_64 0.574 ns 0.659 ns BM_MakeHeap_float_QuickSortAdversary_256 0.631 ns 0.550 ns BM_MakeHeap_float_QuickSortAdversary_1024 0.617 ns 0.552 ns BM_MakeHeap_float_QuickSortAdversary_16384 0.424 ns 0.283 ns BM_MakeHeap_float_QuickSortAdversary_262144 0.386 ns 0.219 ns ``` Fixes #120752
2025-09-08[libc++][C++03] cherry-pick #126273 (#157095)Nikolas Klauser1-3/+7
2025-09-08[libc++] Optimize most of the __tree search algorithms (#155245)Nikolas Klauser8-45/+270
This patch introduces a new comparator, namely `__lazy_synth_three_way`, which tries to provide an efficient three way comparator for known types and falls back to using the provided comparator if it doesn't know how to do that. Currently, an efficient three way comparison is only provided when using one of the `less` comparions object from the standard library and `std::string`. This will be extended in future patches. ``` ------------------------------------------------------------------------------------------------------------------------------ Benchmark old new ------------------------------------------------------------------------------------------------------------------------------ std::map<std::string, int>::ctor(const&)/0 12.6 ns 12.6 ns std::map<std::string, int>::ctor(const&)/32 858 ns 837 ns std::map<std::string, int>::ctor(const&)/1024 46700 ns 46739 ns std::map<std::string, int>::ctor(const&)/8192 458100 ns 449806 ns std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/0 12.8 ns 12.7 ns std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/32 1286 ns 1266 ns std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/1024 93812 ns 84686 ns std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/8192 1480346 ns 1385924 ns std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/0 12.9 ns 12.8 ns std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/32 1044 ns 1055 ns std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/1024 63071 ns 62861 ns std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/8192 595046 ns 590223 ns std::map<std::string, int>::operator=(const&) (into cleared Container)/0 13.6 ns 13.6 ns std::map<std::string, int>::operator=(const&) (into cleared Container)/32 880 ns 911 ns std::map<std::string, int>::operator=(const&) (into cleared Container)/1024 48627 ns 47808 ns std::map<std::string, int>::operator=(const&) (into cleared Container)/8192 458552 ns 454497 ns std::map<std::string, int>::operator=(const&) (into partially populated Container)/0 13.8 ns 13.6 ns std::map<std::string, int>::operator=(const&) (into partially populated Container)/32 864 ns 851 ns std::map<std::string, int>::operator=(const&) (into partially populated Container)/1024 49483 ns 49555 ns std::map<std::string, int>::operator=(const&) (into partially populated Container)/8192 456977 ns 457894 ns std::map<std::string, int>::operator=(const&) (into populated Container)/0 1.31 ns 1.31 ns std::map<std::string, int>::operator=(const&) (into populated Container)/32 425 ns 415 ns std::map<std::string, int>::operator=(const&) (into populated Container)/1024 14248 ns 14225 ns std::map<std::string, int>::operator=(const&) (into populated Container)/8192 136684 ns 133696 ns std::map<std::string, int>::insert(value) (already present)/0 21.5 ns 16.2 ns std::map<std::string, int>::insert(value) (already present)/32 22.7 ns 25.1 ns std::map<std::string, int>::insert(value) (already present)/1024 54.5 ns 29.1 ns std::map<std::string, int>::insert(value) (already present)/8192 78.4 ns 30.4 ns std::map<std::string, int>::insert(value) (new value)/0 40.9 ns 39.0 ns std::map<std::string, int>::insert(value) (new value)/32 58.3 ns 47.2 ns std::map<std::string, int>::insert(value) (new value)/1024 120 ns 71.3 ns std::map<std::string, int>::insert(value) (new value)/8192 157 ns 129 ns std::map<std::string, int>::insert(hint, value) (good hint)/0 40.3 ns 40.7 ns std::map<std::string, int>::insert(hint, value) (good hint)/32 48.0 ns 30.0 ns std::map<std::string, int>::insert(hint, value) (good hint)/1024 107 ns 63.2 ns std::map<std::string, int>::insert(hint, value) (good hint)/8192 132 ns 107 ns std::map<std::string, int>::insert(hint, value) (bad hint)/0 27.0 ns 40.9 ns std::map<std::string, int>::insert(hint, value) (bad hint)/32 68.3 ns 58.4 ns std::map<std::string, int>::insert(hint, value) (bad hint)/1024 125 ns 82.0 ns std::map<std::string, int>::insert(hint, value) (bad hint)/8192 155 ns 150 ns std::map<std::string, int>::insert(iterator, iterator) (all new keys)/0 404 ns 405 ns std::map<std::string, int>::insert(iterator, iterator) (all new keys)/32 2004 ns 1805 ns std::map<std::string, int>::insert(iterator, iterator) (all new keys)/1024 102820 ns 76102 ns std::map<std::string, int>::insert(iterator, iterator) (all new keys)/8192 1144590 ns 949266 ns std::map<std::string, int>::insert(iterator, iterator) (half new keys)/0 408 ns 404 ns std::map<std::string, int>::insert(iterator, iterator) (half new keys)/32 1592 ns 1377 ns std::map<std::string, int>::insert(iterator, iterator) (half new keys)/1024 74847 ns 53921 ns std::map<std::string, int>::insert(iterator, iterator) (half new keys)/8192 828505 ns 698716 ns std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/0 407 ns 407 ns std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/32 1584 ns 1557 ns std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/1024 47157 ns 47443 ns std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/8192 623887 ns 628385 ns std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/0 405 ns 403 ns std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/32 1478 ns 1510 ns std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/1024 47852 ns 47835 ns std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/8192 605311 ns 606951 ns std::map<std::string, int>::erase(key) (existent)/0 129 ns 94.0 ns std::map<std::string, int>::erase(key) (existent)/32 110 ns 106 ns std::map<std::string, int>::erase(key) (existent)/1024 121 ns 128 ns std::map<std::string, int>::erase(key) (existent)/8192 165 ns 66.9 ns std::map<std::string, int>::erase(key) (non-existent)/0 0.269 ns 0.257 ns std::map<std::string, int>::erase(key) (non-existent)/32 21.9 ns 11.3 ns std::map<std::string, int>::erase(key) (non-existent)/1024 53.5 ns 25.4 ns std::map<std::string, int>::erase(key) (non-existent)/8192 67.3 ns 31.9 ns std::map<std::string, int>::erase(iterator)/0 46.3 ns 46.7 ns std::map<std::string, int>::erase(iterator)/32 44.4 ns 41.8 ns std::map<std::string, int>::erase(iterator)/1024 43.7 ns 46.4 ns std::map<std::string, int>::erase(iterator)/8192 45.2 ns 44.1 ns std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/0 407 ns 407 ns std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/32 876 ns 906 ns std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/1024 20880 ns 20444 ns std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/8192 252881 ns 241583 ns std::map<std::string, int>::clear()/0 407 ns 408 ns std::map<std::string, int>::clear()/32 1252 ns 1323 ns std::map<std::string, int>::clear()/1024 38488 ns 38017 ns std::map<std::string, int>::clear()/8192 416492 ns 428534 ns std::map<std::string, int>::find(key) (existent)/0 0.008 ns 0.008 ns std::map<std::string, int>::find(key) (existent)/32 33.9 ns 15.3 ns std::map<std::string, int>::find(key) (existent)/1024 43.0 ns 25.5 ns std::map<std::string, int>::find(key) (existent)/8192 44.6 ns 29.3 ns std::map<std::string, int>::find(key) (non-existent)/0 0.259 ns 0.257 ns std::map<std::string, int>::find(key) (non-existent)/32 22.6 ns 11.4 ns std::map<std::string, int>::find(key) (non-existent)/1024 48.6 ns 25.1 ns std::map<std::string, int>::find(key) (non-existent)/8192 64.1 ns 31.1 ns std::map<std::string, int>::count(key) (existent)/0 0.008 ns 0.008 ns std::map<std::string, int>::count(key) (existent)/32 32.2 ns 17.3 ns std::map<std::string, int>::count(key) (existent)/1024 42.4 ns 25.3 ns std::map<std::string, int>::count(key) (existent)/8192 44.4 ns 31.6 ns std::map<std::string, int>::count(key) (non-existent)/0 0.260 ns 0.259 ns std::map<std::string, int>::count(key) (non-existent)/32 22.9 ns 11.3 ns std::map<std::string, int>::count(key) (non-existent)/1024 49.8 ns 25.5 ns std::map<std::string, int>::count(key) (non-existent)/8192 66.3 ns 31.9 ns std::map<std::string, int>::contains(key) (existent)/0 0.008 ns 0.008 ns std::map<std::string, int>::contains(key) (existent)/32 31.4 ns 18.0 ns std::map<std::string, int>::contains(key) (existent)/1024 44.3 ns 26.5 ns std::map<std::string, int>::contains(key) (existent)/8192 47.4 ns 30.2 ns std::map<std::string, int>::contains(key) (non-existent)/0 0.452 ns 0.441 ns std::map<std::string, int>::contains(key) (non-existent)/32 23.1 ns 11.5 ns std::map<std::string, int>::contains(key) (non-existent)/1024 46.2 ns 26.3 ns std::map<std::string, int>::contains(key) (non-existent)/8192 63.4 ns 31.4 ns std::map<std::string, int>::lower_bound(key) (existent)/0 0.008 ns 0.008 ns std::map<std::string, int>::lower_bound(key) (existent)/32 17.2 ns 19.0 ns std::map<std::string, int>::lower_bound(key) (existent)/1024 27.1 ns 26.2 ns std::map<std::string, int>::lower_bound(key) (existent)/8192 34.0 ns 36.0 ns std::map<std::string, int>::lower_bound(key) (non-existent)/0 0.259 ns 0.257 ns std::map<std::string, int>::lower_bound(key) (non-existent)/32 11.6 ns 11.5 ns std::map<std::string, int>::lower_bound(key) (non-existent)/1024 24.8 ns 25.6 ns std::map<std::string, int>::lower_bound(key) (non-existent)/8192 31.7 ns 31.6 ns std::map<std::string, int>::upper_bound(key) (existent)/0 0.008 ns 0.008 ns std::map<std::string, int>::upper_bound(key) (existent)/32 18.8 ns 19.7 ns std::map<std::string, int>::upper_bound(key) (existent)/1024 25.3 ns 27.7 ns std::map<std::string, int>::upper_bound(key) (existent)/8192 30.2 ns 29.9 ns std::map<std::string, int>::upper_bound(key) (non-existent)/0 0.260 ns 0.259 ns std::map<std::string, int>::upper_bound(key) (non-existent)/32 11.3 ns 12.0 ns std::map<std::string, int>::upper_bound(key) (non-existent)/1024 25.6 ns 25.9 ns std::map<std::string, int>::upper_bound(key) (non-existent)/8192 33.1 ns 34.2 ns std::map<std::string, int>::equal_range(key) (existent)/0 0.008 ns 0.008 ns std::map<std::string, int>::equal_range(key) (existent)/32 33.5 ns 15.8 ns std::map<std::string, int>::equal_range(key) (existent)/1024 43.0 ns 25.1 ns std::map<std::string, int>::equal_range(key) (existent)/8192 54.1 ns 30.7 ns std::map<std::string, int>::equal_range(key) (non-existent)/0 0.265 ns 0.259 ns std::map<std::string, int>::equal_range(key) (non-existent)/32 22.1 ns 12.1 ns std::map<std::string, int>::equal_range(key) (non-existent)/1024 44.8 ns 24.4 ns std::map<std::string, int>::equal_range(key) (non-existent)/8192 62.2 ns 40.1 ns ``` Fixes #66577
2025-09-05[libc++][C++03] cherry-pick #125423 (#156824)Nikolas Klauser1-7/+15
generated by cgit v1.1 at 2025-09-29 17:49:16 +0000