aboutsummaryrefslogtreecommitdiff
path: root/libcxx/test/std/algorithms
AgeCommit message (Collapse)AuthorFilesLines
2 days[libc++][ranges] Fix `ranges::join_view` segmented iterator trait (#158347)lbonn1-39/+82
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
2025-09-11[libc++] Fix ranges_rotate.pass.cpp complexity checks (#158144)Jonathan Wakely1-0/+2
The complexity is "at most N swaps" _for each invocation of `rotate`_, but the tests currently assert that the total number of swaps for N calls is at most N. The standard allows that to be N squared, so the test is either requiring more than the standard (and the comment in the test) promises, or somebody just forgot to reset the counter on each iteration.
2025-09-11[libc++][C++03] partially cherry-pick #122641 (#157596)Nikolas Klauser1-1/+0
This patch only cherry-picks the parts that actually fix the issue, but not the numerous NFC refactorings around it.
2025-09-04[libc++][NFC] Use llvm.org/PR to link to bug reports (#156288)Nikolas Klauser10-10/+10
We've built up quite a few links directly to github within the code base. We should instead use `llvm.org/PR<issue-number>` to link to bugs, since that is resilient to the bug tracker changing in the future. This is especially relevant for tests linking to bugs, since they will probably be there for decades to come. A nice side effect is that these links are significantly shorter than the GH links, making them much less of an eyesore. This patch also replaces a few links that linked to the old bugzilla instance on llvm.org.
2025-08-25[libcxx][test] Fix typos (#155217)Stephan T. Lavavej1-1/+1
I noticed a typo in the directory name `refwrap.comparissons`, then did a quick pass to fix typos elsewhere in the tests. All fixes were manual (some carefully search-and-replaced); I used [cspell](https://www.npmjs.com/package/cspell) to find them.
2025-06-18[libc++] Optimize ranges::{for_each, for_each_n} for segmented iterators ↵Peng Liu2-7/+85
(#132896) Previously, the segmented iterator optimization was limited to `std::{for_each, for_each_n}`. This patch extends the optimization to `std::ranges::for_each` and `std::ranges::for_each_n`, ensuring consistent optimizations across these algorithms. This patch first generalizes the `std` algorithms by introducing a `Projection` parameter, which is set to `__identity` for the `std` algorithms. Then we let the `ranges` algorithms to directly call their `std` counterparts with a general `__proj` argument. Benchmarks demonstrate performance improvements of up to 21.4x for ``std::deque::iterator`` and 22.3x for ``join_view`` of ``vector<vector<char>>``. Addresses a subtask of #102817.
2025-06-11[libc++] Upgrade to GCC 15 (#138293)Nikolas Klauser1-2/+2
2025-05-21[libc++] Optimize std::for_each_n for segmented iterators (#135468)Peng Liu1-40/+99
This patch enhances the performance of `std::for_each_n` when used with segmented iterators, leading to significant performance improvements, summarized in the tables below. This addresses a subtask of https://github.com/llvm/llvm-project/issues/102817.
2025-05-15[Clang] Add warnings when mixing different charN_t types (#138708)cor3ntin2-0/+3
charN_t represent code units of different UTF encodings. Therefore the values of 2 different charN_t objects do not represent the same characters. In order to avoid comparing apples and oranges, we add new warnings to warn on: - Implicit conversions - Comparisons - Other cases involving arithmetic conversions We only produce the warning if we cannot establish the comparison would be safe through constant evaluation. The new `-Wimplicit-unicode-conversion` warning is enabled by default. Note that this PR intentionally doesn;t touches char/wchar_t, but it would be worth considering also warning on extending the new warnings to these types (in a follow up) Additionally most arithmetic operations on charN_t don't really make sense (ie what does it mean to addition code units), so we could add warnings for that. Fixes #138526
2025-05-14[libc++] Improve test coverage and readability for swap_ranges (#133752)Peng Liu2-109/+146
This patch enhances the test coverage of `{std,ranges}::swap_ranges` by adding larger test cases with 100 elements across different containers. It also inlines standalone tests for better readability, avoiding unnecessary navigation. This patch addresses a follow-up suggestion from PR #121138 to extend test coverage beyond 3 elements.
2025-05-07[libc++][docs] Confirm that P3136R1 Retiring niebloids is Complete (#135932)A. Jiang1-1/+1
As libc++ has been implementing niebloids as CPOs since LLVM 14 due to https://reviews.llvm.org/D116570. Also changes some comments in test files to use the formal term "algorithm function object". Closes #118133.
2025-05-06[libc++][NFC] Improve test readability for std::fill_n (#133771)Peng Liu1-61/+57
This patch enhances test readability by inlining standalone tests, eliminating unnecessary navigation. Additionally, several classes with ad-hoc names have been renamed for better clarity: - `A` -> `CharWrapper` as it wraps a char - `B -> CharTransformer` as it accepts a char `xc` but stores `xc + 1` - `Storage -> CharUnionStorage` as it stores a union of 2 `char`s. This patch addresses a follow-up comment from #120909 to inline tests.
2025-04-16[libc++] Extend the scope of radix sorting inside std::stable_sort to ↵Дмитрий Изволов1-1/+58
floating-point types (#129452) These changes speed up `std::stable_sort` in the case of sorting floating-point types. This applies only to IEEE 754 floats. The speedup is similar to that achieved for integers in PR #104683 (see benchmarks below). Why does this worth doing? Previously, `std::stable_sort` had almost no chance of beating `std::sort`. Now there are cases when `std::stable_sort` is preferrable, and the difference is significant. ``` --------------------------------------------------------------------------- Benchmark | std::stable_sort | std::sort | std::stable_sort | without radix_sort | | with radix_sort --------------------------------------------------------------------------- float_Random_1 | 1.62 ns | 2.15 ns | 1.61 ns float_Random_4 | 18.0 ns | 2.71 ns | 16.3 ns float_Random_16 | 118 ns | 113 ns | 112 ns float_Random_64 | 751 ns | 647 ns | 730 ns float_Random_256 | 4715 ns | 2937 ns | 4669 ns float_Random_1024 | 25713 ns | 13172 ns | 5959 ns <-- float_Random_4096 | 131307 ns | 56870 ns | 19294 ns <-- float_Random_16384 | 624996 ns | 242953 ns | 64264 ns <-- float_Random_65536 | 2895661 ns | 1027279 ns | 288553 ns <-- float_Random_262144 | 13285372 ns | 4342593 ns | 3022377 ns <-- float_Random_1048576 | 60595871 ns | 19087591 ns | 18690457 ns <-- float_Random_2097152 | 131336117 ns | 38800396 ns | 52325016 ns float_Random_4194304 | 270043042 ns | 79978019 ns | 102907726 ns double_Random_1 | 1.60 ns | 2.15 ns | 1.61 ns double_Random_4 | 15.2 ns | 2.70 ns | 16.9 ns double_Random_16 | 104 ns | 112 ns | 119 ns double_Random_64 | 712 ns | 614 ns | 755 ns double_Random_256 | 4496 ns | 2966 ns | 4820 ns double_Random_1024 | 24722 ns | 12679 ns | 6189 ns <-- double_Random_4096 | 126075 ns | 54484 ns | 20999 ns <-- double_Random_16384 | 613782 ns | 232557 ns | 110276 ns <-- double_Random_65536 | 2894972 ns | 988531 ns | 774302 ns <-- double_Random_262144 | 13460273 ns | 4278059 ns | 5115123 ns double_Random_1048576 | 61119996 ns | 18408462 ns | 27166574 ns double_Random_2097152 | 132511525 ns | 37986158 ns | 54423869 ns double_Random_4194304 | 272949862 ns | 77912616 ns | 147670834 ns ``` Comparison for only `std::stable_sort`: ``` Benchmark Time Time Old Time New -------------------------------------------------------------------------------------------------- BM_StableSort_float_Random_1024 -0.7997 25438 5096 BM_StableSort_float_Random_4096 -0.8731 128157 16260 BM_StableSort_float_Random_16384 -0.9024 621271 60623 BM_StableSort_float_Random_65536 -0.9081 2922413 268619 BM_StableSort_float_Random_262144 -0.7766 13386345 2990408 BM_StableSort_float_Random_1048576 -0.6954 60673010 18481751 BM_StableSort_float_Random_2097152 -0.6026 130977358 52052182 BM_StableSort_float_Random_4194304 -0.6252 271556583 101770500 BM_StableSort_float_Ascending_1024 -0.6430 6711 2396 BM_StableSort_float_Ascending_4096 -0.7979 38460 7773 BM_StableSort_float_Ascending_16384 -0.8471 191069 29222 BM_StableSort_float_Ascending_65536 -0.8683 882321 116194 BM_StableSort_float_Ascending_262144 -0.8346 3868552 639937 BM_StableSort_float_Ascending_1048576 -0.7460 16521233 4195953 BM_StableSort_float_Ascending_2097152 -0.5439 21757532 9922776 BM_StableSort_float_Ascending_4194304 -0.7525 67847496 16791582 BM_StableSort_float_Descending_1024 -0.6359 15038 5475 BM_StableSort_float_Descending_4096 -0.7090 62810 18278 BM_StableSort_float_Descending_16384 -0.7763 311844 69750 BM_StableSort_float_Descending_65536 -0.7228 1270513 352202 BM_StableSort_float_Descending_262144 -0.6785 5484173 1763045 BM_StableSort_float_Descending_1048576 -0.5084 20223149 9941852 BM_StableSort_float_Descending_2097152 -0.7646 60523254 14247014 BM_StableSort_float_Descending_4194304 -0.5638 95706839 41748858 BM_StableSort_float_SingleElement_1024 +0.3715 1732 2375 BM_StableSort_float_SingleElement_4096 -0.1685 9357 7781 BM_StableSort_float_SingleElement_16384 -0.3793 47307 29362 BM_StableSort_float_SingleElement_65536 -0.4925 227666 115536 BM_StableSort_float_SingleElement_262144 -0.4271 1075853 616387 BM_StableSort_float_SingleElement_1048576 -0.3736 5097599 3193279 BM_StableSort_float_SingleElement_2097152 -0.2470 9854161 7420158 BM_StableSort_float_SingleElement_4194304 -0.3384 22175964 14670720 BM_StableSort_float_PipeOrgan_1024 -0.4885 10664 5455 BM_StableSort_float_PipeOrgan_4096 -0.6340 50095 18337 BM_StableSort_float_PipeOrgan_16384 -0.7078 238700 69739 BM_StableSort_float_PipeOrgan_65536 -0.6740 1102419 359378 BM_StableSort_float_PipeOrgan_262144 -0.7460 4698739 1193511 BM_StableSort_float_PipeOrgan_1048576 -0.5657 18493972 8032392 BM_StableSort_float_PipeOrgan_2097152 -0.7116 41089206 11850349 BM_StableSort_float_PipeOrgan_4194304 -0.6650 83445011 27955737 BM_StableSort_float_QuickSortAdversary_1024 -0.6863 17402 5460 BM_StableSort_float_QuickSortAdversary_4096 -0.7715 79864 18247 BM_StableSort_float_QuickSortAdversary_16384 -0.7800 317480 69839 BM_StableSort_float_QuickSortAdversary_65536 -0.7400 1357601 352967 BM_StableSort_float_QuickSortAdversary_262144 -0.6450 5662094 2009769 BM_StableSort_float_QuickSortAdversary_1048576 -0.5092 21173627 10392107 BM_StableSort_float_QuickSortAdversary_2097152 -0.7333 61748178 16469993 BM_StableSort_float_QuickSortAdversary_4194304 -0.5607 98459863 43250182 BM_StableSort_double_Random_1024 -0.7657 24769 5802 BM_StableSort_double_Random_4096 -0.8441 126449 19717 BM_StableSort_double_Random_16384 -0.8269 614910 106447 BM_StableSort_double_Random_65536 -0.7413 2905000 751427 BM_StableSort_double_Random_262144 -0.6287 13449514 4994348 BM_StableSort_double_Random_1048576 -0.5635 60863246 26568349 BM_StableSort_double_Random_2097152 -0.5959 130293892 52654532 BM_StableSort_double_Random_4194304 -0.4772 272616445 142526267 BM_StableSort_double_Ascending_1024 -0.4870 6757 3466 BM_StableSort_double_Ascending_4096 -0.7360 37592 9923 BM_StableSort_double_Ascending_16384 -0.7971 183967 37324 BM_StableSort_double_Ascending_65536 -0.7465 897116 227398 BM_StableSort_double_Ascending_262144 -0.6764 4020980 1301033 BM_StableSort_double_Ascending_1048576 -0.6407 16421799 5900751 BM_StableSort_double_Ascending_2097152 -0.6380 29347139 10622419 BM_StableSort_double_Ascending_4194304 -0.5934 70439925 28644185 BM_StableSort_double_Descending_1024 -0.5988 15216 6105 BM_StableSort_double_Descending_4096 -0.6857 65069 20449 BM_StableSort_double_Descending_16384 -0.6922 329321 101381 BM_StableSort_double_Descending_65536 -0.7038 1367970 405242 BM_StableSort_double_Descending_262144 -0.6472 5361644 1891429 BM_StableSort_double_Descending_1048576 -0.6656 22031404 7366459 BM_StableSort_double_Descending_2097152 -0.7593 68922467 16591242 BM_StableSort_double_Descending_4194304 -0.6392 96283643 34743223 BM_StableSort_double_SingleElement_1024 +0.9128 1895 3625 BM_StableSort_double_SingleElement_4096 +0.1475 10013 11490 BM_StableSort_double_SingleElement_16384 -0.1901 52382 42424 BM_StableSort_double_SingleElement_65536 -0.2096 254698 201313 BM_StableSort_double_SingleElement_262144 -0.1833 1248478 1019648 BM_StableSort_double_SingleElement_1048576 -0.1741 5703397 4710603 BM_StableSort_double_SingleElement_2097152 -0.1751 10922197 9009835 BM_StableSort_double_SingleElement_4194304 -0.1538 26571923 22485137 BM_StableSort_double_PipeOrgan_1024 -0.4406 10752 6014 BM_StableSort_double_PipeOrgan_4096 -0.5917 49456 20195 BM_StableSort_double_PipeOrgan_16384 -0.6258 270515 101221 BM_StableSort_double_PipeOrgan_65536 -0.7098 1159462 336457 BM_StableSort_double_PipeOrgan_262144 -0.6591 4735711 1614433 BM_StableSort_double_PipeOrgan_1048576 -0.6620 19353110 6541172 BM_StableSort_double_PipeOrgan_2097152 -0.7288 49131812 13323391 BM_StableSort_double_PipeOrgan_4194304 -0.5988 81958974 32878171 BM_StableSort_double_QuickSortAdversary_1024 -0.6516 17948 6254 BM_StableSort_double_QuickSortAdversary_4096 -0.7527 82359 20363 BM_StableSort_double_QuickSortAdversary_16384 -0.7009 340410 101811 BM_StableSort_double_QuickSortAdversary_65536 -0.6854 1487480 467928 BM_StableSort_double_QuickSortAdversary_262144 -0.6386 5648460 2041377 BM_StableSort_double_QuickSortAdversary_1048576 -0.6127 22859142 8852587 BM_StableSort_double_QuickSortAdversary_2097152 -0.7161 68693975 19499381 BM_StableSort_double_QuickSortAdversary_4194304 -0.5909 95532179 39077491 OVERALL_GEOMEAN -0.6472 0 0 ```
2025-04-05[libc++] Implement ranges::iota (#68494)James E T Smith5-13/+170
# Overview As a disclaimer, this is my first PR to LLVM and while I've tried to ensure I've followed the LLVM and libc++ contributing guidelines, there's probably a good chance I missed something. If I have, just let me know and I'll try to correct it as soon as I can. This PR implements `std::ranges::iota` and `std::ranges::out_value_result` outlined in [P2440r1](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p2440r1.html). As outlined in the paper above, I've: - Implemented `out_value_result` and added to `<algorithm>` - Added `out_value_result`, `iota_result`, and two overloads of `iota` to `std::ranges` in `<numeric>` - Updated the version macro `__cpp_lib_ranges_iota` in `<version>` I've also added tests for `ranges::iota` and `ranges::out_value_result`. Lastly, I added those structs to the appropriate module files. Partially implements #105184 EDIT: Forgot to mention in the original post, thanks to @hawkinsw for taking a look at a preliminary version of this PR! # TODOs - [x] Updating the range [status doc](https://github.com/jamesETsmith/llvm-project/blob/main/libcxx/docs/Status/RangesMajorFeatures.csv) - [x] Ensure all comments from https://reviews.llvm.org/D121436 are addressed here - [X] EDIT (I'll do this in a separate PR). ~~I'm open to implementing the rest of P2440r1 (`ranges::shift_left` and `ranges::shift_right`) if that's ok, I just wanted to get feedback on `ranges::iota` first~~ - [x] I've been having trouble building the modules locally and want to make sure that's working properly Closes: #134060
2025-03-24[libc++][test][NFC] Introduce `TEST_STD_AT_LEAST_26_OR_RUNTIME_EVALUATED` ↵A. Jiang6-56/+14
(#132593) And use it for test cases that became constant-evaluation-suitable due to P2562R1. `TEST_STD_AT_LEAST_(20|23)_OR_RUNTIME_EVALUATED` are the precedents.
2025-03-20[libc++][test] Fix issues found by MSVC's STL (#131787)Stephan T. Lavavej4-8/+6
* libcxx/test/support/min_allocator.h + Fix `tiny_size_allocator::rebind` which mistakenly said `T` instead of `U`. * libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/stable_partition.pass.cpp + `std::stable_partition` requires bidirectional iterators. * libcxx/test/std/containers/sequences/vector.bool/max_size.pass.cpp + Fix allocator type given to `std::vector<bool>`. The element types are required to match, [N5008](https://isocpp.org/files/papers/N5008.pdf) \[container.alloc.reqmts\]/5: "*Mandates:* `allocator_type::value_type` is the same as `X::value_type`." * libcxx/test/std/time/time.clock/time.clock.utc/types.compile.pass.cpp + Mark `is_steady` as `[[maybe_unused]]`, as it appears within `LIBCPP_STATIC_ASSERT` only. * libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/rotate.pass.cpp * libcxx/test/std/algorithms/alg.modifying.operations/alg.swap/swap_ranges.pass.cpp * libcxx/test/std/utilities/utility/utility.swap/swap_array.pass.cpp + Fix MSVC warning C4127 "conditional expression is constant". `TEST_STD_AT_LEAST_23_OR_RUNTIME_EVALUATED` was introduced for this purpose, so it should be used consistently. * libcxx/test/std/numerics/numeric.ops/numeric.ops.gcd/gcd.pass.cpp + Fix `gcd()` precondition violation for `signed char`. This test case was causing `-128` to be passed as a `signed char` to `gcd()`, which is forbidden. * libcxx/test/std/containers/sequences/array/assert.iterators.pass.cpp * libcxx/test/std/containers/sequences/vector/vector.modifiers/assert.push_back.invalidation.pass.cpp * libcxx/test/std/input.output/iostream.format/print.fun/no_file_description.pass.cpp + Split some REQUIRES and XFAIL lines. This is a "nice to have" for MSVC's internal test harness, which is extremely simple and looks for exact comment matches to skip tests. We can recognize the specific lines "REQUIRES: has-unix-headers" and "XFAIL: msvc", but it's a headache to maintain if they're chained with other conditions. * libcxx/test/support/sized_allocator.h + Fix x86 truncation warnings. `std::allocator` takes `std::size_t`, so we need to `static_cast`. * libcxx/test/std/input.output/file.streams/fstreams/ifstream.members/offset_range.pass.cpp + Fix x86 truncation warning. `std::min()` is returning `std::streamoff`, which was being unnecessarily narrowed to `std::size_t`. * libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp + Fix MSVC warning C4127 "conditional expression is constant" for an always-true branch. This was very recently introduced by #129008 making `N` constexpr. As it's a local constant just nine lines above, we don't need to test whether 100 is greater than 0.
2025-03-20[libc++] Implement part of P2562R1: constexpr `ranges::inplace_merge` (#131947)A. Jiang5-23/+51
Drive-by changes: - Consistently mark `std::__inplace_merge::__inplace_merge_impl` `_LIBCPP_CONSTEXPR_SINCE_CXX26`. - This function template is only called by other functions that becomes constexpr since C++26, and it itself calls `std::__inplace_merge` that is constexpr since C++26. - Unblock related test coverage in constant evaluation for `stable_partition`, `ranges::stable_sort`, `std::stable_sort`, `std::stable_partition`, and `std::inplace_merge`.
2025-03-19[libc++] Fix copy_backward for vector<bool> with small storage types (#131560)Peng Liu2-0/+284
This patch fixes an issue in libc++ where `std::copy_backward` and `ranges::copy_backward` incorrectly copy `std::vector<bool>` with small storage types (e.g., `uint8_t`, `uint16_t`). The problem arises from flawed bit mask computations involving integral promotions and sign-bit extension, leading to unintended zeroing of bits. This patch corrects the bitwise operations to ensure correct bit-level copying. Fixes #131718.
2025-03-19[libc++] Fix {std, ranges}::copy for vector<bool> with small storage types ↵Peng Liu2-0/+298
(#131545) The current implementation of `{std, ranges}::copy` fails to copy `vector<bool>` correctly when the underlying storage type (`__storage_type`) is smaller than `int`, such as `unsigned char`, `unsigned short`, `uint8_t` and `uint16_t`. The root cause is that the unsigned small storage type undergoes integer promotion to (signed) `int`, which is then left and right shifted, leading to UB (before C++20) and sign-bit extension (since C++20) respectively. As a result, the underlying bit mask evaluations become incorrect, causing erroneous copying behavior. This patch resolves the issue by correcting the internal bitwise operations, ensuring that `{std, ranges}::copy` operates correctly for `vector<bool>` with any custom (unsigned) storage types. Fixes #131692.
2025-03-19[libc++] Fix {std, ranges}::equal for vector<bool> with small storage types ↵Peng Liu2-8/+203
(#130394) The current implementation of `{std, ranges}::equal` fails to correctly compare `vector<bool>`s when the underlying storage type is smaller than `int` (e.g., `unsigned char`, `unsigned short`, `uint8_t` and `uint16_t`). See [demo](https://godbolt.org/z/j4s87s6b3)). The problem arises due to integral promotions on the intermediate bitwise operations, leading to incorrect final equality comparison results. This patch fixes the issue by ensuring that `{std, ranges}::equal` operate properly for both aligned and unaligned bits. Fixes #126369.
2025-03-19[libc++] Fix ambiguous call in {ranges, std}::count (#122529)Peng Liu2-48/+124
This PR fixes an ambiguous call encountered while using the `std::ranges::count` and `std::count` algorithms with `vector<bool>` with small `size_type`s. The ambiguity arises from integral promotions during the internal bitwise arithmetic of the `count` algorithms for small integral types. This results in multiple viable candidates: `__libcpp_popcount(unsigned)`,` __libcpp_popcount(unsigned long)`, and `__libcpp_popcount(unsigned long long)`, leading to an ambiguous call error. To resolve this ambiguity, we introduce a dispatcher function, `__popcount`, which directs calls to the appropriate overloads of `__libcpp_popcount`. This closes #122528.
2025-03-19[libc++] Implement part of P2562R1: constexpr `std::inplace_merge` (#129008)A. Jiang3-197/+226
Drive-by: - Adds `constexpr_random.h` for pseudo-randomizing or shuffling in tests for constant evaluation.
2025-03-13[libc++] Fix ambiguous call in {ranges, std}::find (#122641)Peng Liu2-2/+73
This PR fixes an ambiguous call encountered when using the `std::ranges::find` or `std::find` algorithms with `vector<bool>` with small `allocator_traits::size_type`s, an issue reported in #122528. The ambiguity arises from integral promotions during the internal bitwise arithmetic of the `find` algorithms when applied to `vector<bool>` with small integral `size_type`s. This leads to multiple viable candidates for small integral types: __libcpp_ctz(unsigned), __libcpp_ctz(unsigned long), and __libcpp_ctz(unsigned long long), none of which represent a single best viable match, resulting in an ambiguous call error. To resolve this, we propose invoking an internal function __countr_zero as a dispatcher that directs the call to the appropriate overload of __libcpp_ctz. Necessary amendments have also been made to __countr_zero.
2025-03-13[libc++] Optimize ranges::rotate for vector<bool>::iterator (#121168)Peng Liu2-0/+58
This PR optimizes the performance of `std::ranges::rotate` for `vector<bool>::iterator`. The optimization yields a performance improvement of up to 2096x. Closes #64038.
2025-03-10[NFC][libcxx][test] clang-format: search.pass.cpp (#130551)AdityaK1-87/+74
2025-03-07[libc++] Implement part of P2562R1: constexpr `ranges::stable_sort` (#128860)A. Jiang4-15/+29
Drive-by: Enables test coverage for `ranges::stable_sort` with proxy iterators, and changes "constexpr in" to "constexpr since" in comments in `<algorithm>`.
2025-03-06[libc++] Implement part of P2562R1: constexpr `ranges::stable_partition` ↵A. Jiang4-8/+27
(#129839)
2025-03-04[libc++] Optimize ranges::swap_ranges for vector<bool>::iterator (#121150)Peng Liu2-0/+54
This PR optimizes the performance of `std::ranges::swap_ranges` for `vector<bool>::iterator`, addressing a subtask outlined in issue #64038. The optimizations yield performance improvements of up to **611x** for aligned range swap and **78x** for unaligned range swap comparison. Additionally, comprehensive tests covering up to 4 storage words (256 bytes) with odd and even bit sizes are provided, which validate the proposed optimizations in this patch.
2025-03-04[libc++] Implement part of P2562R1: constexpr `std::stable_partition` (#128868)A. Jiang3-39/+54
Drive-by changes: - Enables no-memory case for Clang. - Enables `robust_re_difference_type.compile.pass.cpp` and `robust_against_proxy_iterators_lifetime_bugs.pass.cpp` test coverage for `std::stable_sort` in constant evaluation since C++26. The changes were missing in the PR making `std::stable_sort` `constexpr`.
2025-02-26[libc++] Optimize ranges::equal for vector<bool>::iterator (#121084)Peng Liu2-93/+193
This PR optimizes the performance of `std::ranges::equal` for `vector<bool>::iterator`, addressing a subtask outlined in issue #64038. The optimizations yield performance improvements of up to 188x for aligned equality comparison and 82x for unaligned equality comparison. Moreover, comprehensive tests covering up to 4 storage words (256 bytes) with odd and even bit sizes are provided, which validate the proposed optimizations in this patch.
2025-02-26[libc++][test] Refactor tests for rotate and rotate_copy (#126458)Peng Liu5-341/+309
This PR refactors the tests and fix some problems: - Refactor similar tests using `types::for_each` to remove redundant code; - Explicitly include the missing header `type_algorithms.h` instead of relying on a transitive include; - Fix the incorrect constexpr declaration in `rotate.pass.cpp`, where the `test()` function is incorrectly defined as `TEST_CONSTEXPR_CXX17`, which is wrong since `std::rotate()` becomes constexpr only since C++20.
2025-02-26[libc++][test] Refactor tests for ranges::swap_range algorithms (#121138)Peng Liu3-277/+187
This PR refactors tests for `ranges::swap_range`, `std::{swap_range, iter_swap, swap}` algorithms to eliminate redundant code.
2025-02-26[libc++][test] Augment ranges::{fill, fill_n, find} with missing tests (#121209)Peng Liu6-175/+371
libc++ currently has very limited test coverage for `std::ranges{fill, fill_n, find}` with `vector<bool>::iterator` optimizations. Specifically, the existing tests for `std::ranges::fill` only covers cases of 1 - 2 bytes, which is merely 1/8 to 1/4 of the `__storage_type` word size. This renders the tests insufficient to validate functionality for whole words, with or without partial words (which necessitates at least 8 bytes of data). Moreover, no tests were provided for `ranges::{find, fill_n}` with `vector<bool>::iterator` optimizations. This PR fills in the gap.
2025-02-19[libc++][test] Refactor tests for std::{copy, move, fill} algorithms (#120909)Peng Liu14-296/+204
This refactor includes the following changes: - Refactor similar tests using `types::for_each` to remove redundant code; - Explicitly include the missing header `type_algorithms.h` in some test files; - Some tests scattered in different test functions with ad-hoc names (e.g., `test5()`, `test6()`) but belong to the same kind are now grouped into one function (`test_struct_array()`).
2025-02-19[libc++] Optimize ranges::move{,_backward} for vector<bool>::iterator (#121109)Peng Liu4-94/+250
As a follow-up to #121013 (which optimized `ranges::copy`) and #121026 (which optimized `ranges::copy_backward`), this PR enhances the performance of `std::ranges::{move, move_backward}` for `vector<bool>::iterator`, addressing a subtask outlined in issue #64038. The optimizations bring performance improvements analogous to those achieved for the `{copy, copy_backward}` algorithms: up to 2000x for aligned moves and 60x for unaligned moves. Moreover, comprehensive tests covering up to 4 storage words (256 bytes) with odd and even bit sizes are provided, which validate the proposed optimizations in this patch.
2025-02-12[libc++] Remove obsolete guards for join_view being experimental (#126697)Louis Dionne3-9/+3
These TODOs were forgotten when join_view was made non-experimental. By removing these checks, we slightly increase the coverage of the test suite.
2025-02-06[libc++] Support `constexpr` for `std::stable_sort` in radix sort branch ↵Дмитрий Изволов1-0/+2
(#125284) `std::stable_sort` is `constexpr` since PR https://github.com/llvm/llvm-project/pull/110320 But `radix_sort` branch is still non-`constexpr`. This PR fixes it. #119394 #105360
2025-02-05[libc++] Fix UB in bitwise logic of {std, ranges}::{fill, fill_n} algorithms ↵Peng Liu4-108/+255
(#122410) This PR addresses an undefined behavior that arises when using the `std::fill` and `std::fill_n` algorithms, as well as their ranges counterparts `ranges::fill` and `ranges::fill_n`, with `vector<bool, Alloc>` that utilizes a custom-sized allocator with small integral types.
2025-01-30[libc++] Optimize ranges::copy_backward for vector<bool>::iterator (#121026)Peng Liu2-67/+129
As a follow-up to #121013 (which focused on `std::ranges::copy`), this PR optimizes the performance of `std::ranges::copy_backward` for `vector<bool>::iterator`, addressing a subtask outlined in issue #64038. The optimizations yield performance improvements of up to 2000x for aligned copies and 60x for unaligned copies.
2025-01-30[libc++] Optimize ranges::copy{, _n} for vector<bool>::iterator (#121013)Peng Liu4-58/+188
This PR optimizes the performance of `std::ranges::copy` and `std::ranges::copy_n` specifically for `vector<bool>::iterator`, addressing a subtask outlined in issue #64038. The optimizations yield performance improvements of up to **2000x** for aligned copies and **60x** for unaligned copies. Additionally, new tests have been added to validate these enhancements. - Aligned source-destination bits ranges::copy ``` -------------------------------------------------------------------------- Benchmark Before After Improvement -------------------------------------------------------------------------- bm_ranges_copy_vb_aligned/8 10.8 ns 1.42 ns 8x bm_ranges_copy_vb_aligned/64 88.5 ns 2.28 ns 39x bm_ranges_copy_vb_aligned/512 709 ns 1.95 ns 364x bm_ranges_copy_vb_aligned/4096 5568 ns 5.01 ns 1111x bm_ranges_copy_vb_aligned/32768 44754 ns 38.7 ns 1156x bm_ranges_copy_vb_aligned/65536 91092 ns 73.2 ns 1244x bm_ranges_copy_vb_aligned/102400 139473 ns 127 ns 1098x bm_ranges_copy_vb_aligned/106496 189004 ns 81.5 ns 2319x bm_ranges_copy_vb_aligned/110592 153647 ns 71.1 ns 2161x bm_ranges_copy_vb_aligned/114688 159261 ns 70.2 ns 2269x bm_ranges_copy_vb_aligned/118784 181910 ns 73.5 ns 2475x bm_ranges_copy_vb_aligned/122880 174117 ns 76.5 ns 2276x bm_ranges_copy_vb_aligned/126976 176020 ns 82.0 ns 2147x bm_ranges_copy_vb_aligned/131072 180757 ns 137 ns 1319x bm_ranges_copy_vb_aligned/135168 190342 ns 158 ns 1205x bm_ranges_copy_vb_aligned/139264 192831 ns 103 ns 1872x bm_ranges_copy_vb_aligned/143360 199627 ns 89.4 ns 2233x bm_ranges_copy_vb_aligned/147456 203881 ns 88.6 ns 2301x bm_ranges_copy_vb_aligned/151552 213345 ns 88.4 ns 2413x bm_ranges_copy_vb_aligned/155648 216892 ns 92.9 ns 2335x bm_ranges_copy_vb_aligned/159744 222751 ns 96.4 ns 2311x bm_ranges_copy_vb_aligned/163840 225995 ns 173 ns 1306x bm_ranges_copy_vb_aligned/167936 235230 ns 202 ns 1165x bm_ranges_copy_vb_aligned/172032 244093 ns 131 ns 1863x bm_ranges_copy_vb_aligned/176128 244434 ns 111 ns 2202x bm_ranges_copy_vb_aligned/180224 249570 ns 108 ns 2311x bm_ranges_copy_vb_aligned/184320 254538 ns 108 ns 2357x bm_ranges_copy_vb_aligned/188416 261817 ns 113 ns 2317x bm_ranges_copy_vb_aligned/192512 269923 ns 125 ns 2159x bm_ranges_copy_vb_aligned/196608 273494 ns 210 ns 1302x bm_ranges_copy_vb_aligned/200704 280035 ns 269 ns 1041x bm_ranges_copy_vb_aligned/204800 293102 ns 231 ns 1269x ``` ranges::copy_n ``` -------------------------------------------------------------------------- Benchmark Before After Improvement -------------------------------------------------------------------------- bm_ranges_copy_n_vb_aligned/8 11.8 ns 0.89 ns 13x bm_ranges_copy_n_vb_aligned/64 91.6 ns 2.06 ns 44x bm_ranges_copy_n_vb_aligned/512 718 ns 2.45 ns 293x bm_ranges_copy_n_vb_aligned/4096 5750 ns 5.02 ns 1145x bm_ranges_copy_n_vb_aligned/32768 45824 ns 40.9 ns 1120x bm_ranges_copy_n_vb_aligned/65536 92267 ns 73.8 ns 1250x bm_ranges_copy_n_vb_aligned/102400 143267 ns 125 ns 1146x bm_ranges_copy_n_vb_aligned/106496 148625 ns 82.4 ns 1804x bm_ranges_copy_n_vb_aligned/110592 154817 ns 72.0 ns 2150x bm_ranges_copy_n_vb_aligned/114688 157953 ns 70.4 ns 2244x bm_ranges_copy_n_vb_aligned/118784 162374 ns 71.5 ns 2270x bm_ranges_copy_n_vb_aligned/122880 168638 ns 72.9 ns 2313x bm_ranges_copy_n_vb_aligned/126976 175596 ns 76.6 ns 2292x bm_ranges_copy_n_vb_aligned/131072 181164 ns 135 ns 1342x bm_ranges_copy_n_vb_aligned/135168 184697 ns 157 ns 1176x bm_ranges_copy_n_vb_aligned/139264 191395 ns 104 ns 1840x bm_ranges_copy_n_vb_aligned/143360 194954 ns 88.3 ns 2208x bm_ranges_copy_n_vb_aligned/147456 208917 ns 86.1 ns 2426x bm_ranges_copy_n_vb_aligned/151552 211101 ns 87.2 ns 2421x bm_ranges_copy_n_vb_aligned/155648 213175 ns 89.0 ns 2395x bm_ranges_copy_n_vb_aligned/159744 218988 ns 86.7 ns 2526x bm_ranges_copy_n_vb_aligned/163840 225263 ns 156 ns 1444x bm_ranges_copy_n_vb_aligned/167936 230725 ns 184 ns 1254x bm_ranges_copy_n_vb_aligned/172032 235795 ns 119 ns 1981x bm_ranges_copy_n_vb_aligned/176128 241145 ns 101 ns 2388x bm_ranges_copy_n_vb_aligned/180224 250680 ns 99.5 ns 2519x bm_ranges_copy_n_vb_aligned/184320 262954 ns 99.7 ns 2637x bm_ranges_copy_n_vb_aligned/188416 258584 ns 103 ns 2510x bm_ranges_copy_n_vb_aligned/192512 267190 ns 125 ns 2138x bm_ranges_copy_n_vb_aligned/196608 270821 ns 213 ns 1271x bm_ranges_copy_n_vb_aligned/200704 279532 ns 262 ns 1067x bm_ranges_copy_n_vb_aligned/204800 283412 ns 222 ns 1277x ``` - Unaligned source-destination bits ``` -------------------------------------------------------------------------------- Benchmark Before After Improvement -------------------------------------------------------------------------------- bm_ranges_copy_vb_unaligned/8 12.8 ns 8.59 ns 1.5x bm_ranges_copy_vb_unaligned/64 98.2 ns 8.24 ns 12x bm_ranges_copy_vb_unaligned/512 755 ns 18.1 ns 42x bm_ranges_copy_vb_unaligned/4096 6027 ns 102 ns 59x bm_ranges_copy_vb_unaligned/32768 47663 ns 774 ns 62x bm_ranges_copy_vb_unaligned/262144 378981 ns 6455 ns 59x bm_ranges_copy_vb_unaligned/1048576 1520486 ns 25942 ns 59x bm_ranges_copy_n_vb_unaligned/8 11.3 ns 8.22 ns 1.4x bm_ranges_copy_n_vb_unaligned/64 97.3 ns 7.89 ns 12x bm_ranges_copy_n_vb_unaligned/512 747 ns 18.1 ns 41x bm_ranges_copy_n_vb_unaligned/4096 5932 ns 99.0 ns 60x bm_ranges_copy_n_vb_unaligned/32768 47776 ns 749 ns 64x bm_ranges_copy_n_vb_unaligned/262144 378802 ns 6576 ns 58x bm_ranges_copy_n_vb_unaligned/1048576 1547234 ns 26229 ns 59x ```
2025-01-14[libc++] Make std::stable_sort constexpr friendly (#110320)PaulXiCao2-164/+213
Implementing `constexpr std::stable_sort`. This is part of P2562R1, tracked via issue #105360. Closes #119394 Co-authored-by: A. Jiang <de34@live.cn> Co-authored-by: Louis Dionne <ldionne.2@gmail.com>
2025-01-09[libcxx][algorithm] Optimize std::stable_sort via radix sort algorithm (#104683)Дмитрий Изволов1-54/+63
The radix sort (LSD) algorithm allows to speed up std::stable_sort dramatically in case we sort integers. The speed up varies from a relatively small to x10 times, depending on type of sorted elements and the initial state of the sorted array. ``` Running ./libcxx/test/benchmarks/stable_sort.bench.out Run on (12 X 2600 MHz CPU s) CPU Caches: L1 Data 32 KiB L1 Instruction 32 KiB L2 Unified 256 KiB (x6) L3 Unified 12288 KiB Load Average: 3.48, 3.38, 3.08 --------------------------------------------------------------------------- Benchmark After Before --------------------------------------------------------------------------- BM_StableSort_int8_Random_1 3.39 ns 3.58 ns BM_StableSort_int8_Random_4 21.1 ns 21.9 ns BM_StableSort_int8_Random_16 142 ns 147 ns BM_StableSort_int8_Random_64 893 ns 903 ns BM_StableSort_int8_Random_256 409 ns 5810 ns BM_StableSort_int8_Random_1024 1235 ns 29973 ns BM_StableSort_int8_Random_4096 4410 ns 141880 ns BM_StableSort_int8_Random_16384 18044 ns 620540 ns BM_StableSort_int8_Random_65536 144030 ns 2592013 ns BM_StableSort_int8_Random_262144 858350 ns 10935814 ns BM_StableSort_int8_Random_524288 2929988 ns 27060729 ns BM_StableSort_int8_Random_1048576 6058292 ns 49622720 ns BM_StableSort_int8_Ascending_1 3.42 ns 3.92 ns BM_StableSort_int8_Ascending_4 5.86 ns 8.08 ns BM_StableSort_int8_Ascending_16 10.6 ns 12.0 ns BM_StableSort_int8_Ascending_64 28.9 ns 30.6 ns BM_StableSort_int8_Ascending_256 415 ns 391 ns BM_StableSort_int8_Ascending_1024 1666 ns 2309 ns BM_StableSort_int8_Ascending_4096 7748 ns 12269 ns BM_StableSort_int8_Ascending_16384 40588 ns 60181 ns BM_StableSort_int8_Ascending_65536 178843 ns 298221 ns BM_StableSort_int8_Ascending_262144 919959 ns 1402692 ns BM_StableSort_int8_Ascending_524288 2397397 ns 3036984 ns BM_StableSort_int8_Ascending_1048576 5080043 ns 7218581 ns BM_StableSort_int8_Descending_1 3.44 ns 3.53 ns BM_StableSort_int8_Descending_4 7.94 ns 8.29 ns BM_StableSort_int8_Descending_16 59.6 ns 57.7 ns BM_StableSort_int8_Descending_64 1051 ns 1027 ns BM_StableSort_int8_Descending_256 422 ns 4718 ns BM_StableSort_int8_Descending_1024 1676 ns 21044 ns BM_StableSort_int8_Descending_4096 7766 ns 64827 ns BM_StableSort_int8_Descending_16384 40230 ns 93981 ns BM_StableSort_int8_Descending_65536 190978 ns 421151 ns BM_StableSort_int8_Descending_262144 1055141 ns 1918927 ns BM_StableSort_int8_Descending_524288 2875115 ns 3809153 ns BM_StableSort_int8_Descending_1048576 5854135 ns 8713690 ns BM_StableSort_int8_SingleElement_1 3.52 ns 3.46 ns BM_StableSort_int8_SingleElement_4 6.25 ns 5.79 ns BM_StableSort_int8_SingleElement_16 10.7 ns 11.4 ns BM_StableSort_int8_SingleElement_64 29.3 ns 30.3 ns BM_StableSort_int8_SingleElement_256 858 ns 380 ns BM_StableSort_int8_SingleElement_1024 3036 ns 2231 ns BM_StableSort_int8_SingleElement_4096 11580 ns 11866 ns BM_StableSort_int8_SingleElement_16384 44956 ns 59621 ns BM_StableSort_int8_SingleElement_65536 182006 ns 297853 ns BM_StableSort_int8_SingleElement_262144 962181 ns 1432857 ns BM_StableSort_int8_SingleElement_524288 2256687 ns 2975707 ns BM_StableSort_int8_SingleElement_1048576 4522556 ns 6949948 ns BM_StableSort_int8_PipeOrgan_1 3.26 ns 3.64 ns BM_StableSort_int8_PipeOrgan_4 6.21 ns 6.58 ns BM_StableSort_int8_PipeOrgan_16 23.7 ns 25.4 ns BM_StableSort_int8_PipeOrgan_64 250 ns 248 ns BM_StableSort_int8_PipeOrgan_256 414 ns 2498 ns BM_StableSort_int8_PipeOrgan_1024 1697 ns 10946 ns BM_StableSort_int8_PipeOrgan_4096 7840 ns 37238 ns BM_StableSort_int8_PipeOrgan_16384 41402 ns 74805 ns BM_StableSort_int8_PipeOrgan_65536 180107 ns 357891 ns BM_StableSort_int8_PipeOrgan_262144 988273 ns 1647296 ns BM_StableSort_int8_PipeOrgan_524288 2547374 ns 3245991 ns BM_StableSort_int8_PipeOrgan_1048576 5128783 ns 7342444 ns BM_StableSort_int8_QuickSortAdversary_1 3.14 ns 4.01 ns BM_StableSort_int8_QuickSortAdversary_4 6.05 ns 7.02 ns BM_StableSort_int8_QuickSortAdversary_16 10.5 ns 11.9 ns BM_StableSort_int8_QuickSortAdversary_64 520 ns 516 ns BM_StableSort_int8_QuickSortAdversary_256 920 ns 386 ns BM_StableSort_int8_QuickSortAdversary_1024 3083 ns 2299 ns BM_StableSort_int8_QuickSortAdversary_4096 11659 ns 12295 ns BM_StableSort_int8_QuickSortAdversary_16384 45721 ns 60931 ns BM_StableSort_int8_QuickSortAdversary_65536 186334 ns 295423 ns BM_StableSort_int8_QuickSortAdversary_262144 946262 ns 1399973 ns BM_StableSort_int8_QuickSortAdversary_524288 2282004 ns 2832266 ns BM_StableSort_int8_QuickSortAdversary_1048576 4691123 ns 6963253 ns BM_StableSort_uint8_Random_1 3.11 ns 3.44 ns BM_StableSort_uint8_Random_4 21.9 ns 23.1 ns BM_StableSort_uint8_Random_16 154 ns 171 ns BM_StableSort_uint8_Random_64 1000 ns 1051 ns BM_StableSort_uint8_Random_256 402 ns 6498 ns BM_StableSort_uint8_Random_1024 1176 ns 35310 ns BM_StableSort_uint8_Random_4096 4415 ns 164087 ns BM_StableSort_uint8_Random_16384 17849 ns 686769 ns BM_StableSort_uint8_Random_65536 146109 ns 2932051 ns BM_StableSort_uint8_Random_262144 876710 ns 12163988 ns BM_StableSort_uint8_Random_524288 2858089 ns 26458830 ns BM_StableSort_uint8_Random_1048576 5766942 ns 54836214 ns BM_StableSort_uint8_Ascending_1 3.11 ns 3.43 ns BM_StableSort_uint8_Ascending_4 6.18 ns 7.24 ns BM_StableSort_uint8_Ascending_16 14.5 ns 17.0 ns BM_StableSort_uint8_Ascending_64 50.7 ns 59.2 ns BM_StableSort_uint8_Ascending_256 395 ns 536 ns BM_StableSort_uint8_Ascending_1024 1752 ns 2956 ns BM_StableSort_uint8_Ascending_4096 7785 ns 15146 ns BM_StableSort_uint8_Ascending_16384 41442 ns 74136 ns BM_StableSort_uint8_Ascending_65536 180879 ns 354261 ns BM_StableSort_uint8_Ascending_262144 945880 ns 1674256 ns BM_StableSort_uint8_Ascending_524288 2287832 ns 3138581 ns BM_StableSort_uint8_Ascending_1048576 4630290 ns 7296278 ns BM_StableSort_uint8_Descending_1 3.19 ns 3.63 ns BM_StableSort_uint8_Descending_4 9.60 ns 11.5 ns BM_StableSort_uint8_Descending_16 78.3 ns 86.0 ns BM_StableSort_uint8_Descending_64 1265 ns 1308 ns BM_StableSort_uint8_Descending_256 395 ns 6556 ns BM_StableSort_uint8_Descending_1024 1712 ns 24669 ns BM_StableSort_uint8_Descending_4096 7748 ns 83407 ns BM_StableSort_uint8_Descending_16384 40779 ns 104043 ns BM_StableSort_uint8_Descending_65536 181560 ns 467680 ns BM_StableSort_uint8_Descending_262144 1146627 ns 2102769 ns BM_StableSort_uint8_Descending_524288 2874096 ns 4572229 ns BM_StableSort_uint8_Descending_1048576 5873195 ns 10170663 ns BM_StableSort_uint8_SingleElement_1 3.28 ns 3.58 ns BM_StableSort_uint8_SingleElement_4 6.44 ns 7.40 ns BM_StableSort_uint8_SingleElement_16 14.9 ns 16.4 ns BM_StableSort_uint8_SingleElement_64 51.2 ns 52.9 ns BM_StableSort_uint8_SingleElement_256 876 ns 490 ns BM_StableSort_uint8_SingleElement_1024 3041 ns 2750 ns BM_StableSort_uint8_SingleElement_4096 11947 ns 14326 ns BM_StableSort_uint8_SingleElement_16384 46669 ns 69984 ns BM_StableSort_uint8_SingleElement_65536 197903 ns 328961 ns BM_StableSort_uint8_SingleElement_262144 1031466 ns 1551436 ns BM_StableSort_uint8_SingleElement_524288 2447672 ns 3049553 ns BM_StableSort_uint8_SingleElement_1048576 4793087 ns 7615245 ns BM_StableSort_uint8_PipeOrgan_1 3.38 ns 3.56 ns BM_StableSort_uint8_PipeOrgan_4 7.16 ns 8.70 ns BM_StableSort_uint8_PipeOrgan_16 31.7 ns 35.3 ns BM_StableSort_uint8_PipeOrgan_64 326 ns 366 ns BM_StableSort_uint8_PipeOrgan_256 409 ns 2942 ns BM_StableSort_uint8_PipeOrgan_1024 1994 ns 12571 ns BM_StableSort_uint8_PipeOrgan_4096 8086 ns 46278 ns BM_StableSort_uint8_PipeOrgan_16384 41749 ns 79813 ns BM_StableSort_uint8_PipeOrgan_65536 180697 ns 375120 ns BM_StableSort_uint8_PipeOrgan_262144 1004899 ns 1676143 ns BM_StableSort_uint8_PipeOrgan_524288 2456081 ns 3333949 ns BM_StableSort_uint8_PipeOrgan_1048576 5030857 ns 7591303 ns BM_StableSort_uint8_QuickSortAdversary_1 3.12 ns 3.46 ns BM_StableSort_uint8_QuickSortAdversary_4 7.25 ns 6.83 ns BM_StableSort_uint8_QuickSortAdversary_16 14.6 ns 16.2 ns BM_StableSort_uint8_QuickSortAdversary_64 650 ns 665 ns BM_StableSort_uint8_QuickSortAdversary_256 395 ns 2982 ns BM_StableSort_uint8_QuickSortAdversary_1024 3125 ns 2583 ns BM_StableSort_uint8_QuickSortAdversary_4096 11797 ns 13929 ns BM_StableSort_uint8_QuickSortAdversary_16384 45803 ns 66513 ns BM_StableSort_uint8_QuickSortAdversary_65536 190745 ns 313467 ns BM_StableSort_uint8_QuickSortAdversary_262144 974646 ns 1469014 ns BM_StableSort_uint8_QuickSortAdversary_524288 2317553 ns 3022065 ns BM_StableSort_uint8_QuickSortAdversary_1048576 4898703 ns 6854079 ns BM_StableSort_int16_Random_1 3.94 ns 3.49 ns BM_StableSort_int16_Random_4 20.8 ns 23.2 ns BM_StableSort_int16_Random_16 133 ns 163 ns BM_StableSort_int16_Random_64 903 ns 953 ns BM_StableSort_int16_Random_256 5638 ns 6258 ns BM_StableSort_int16_Random_1024 3056 ns 34587 ns BM_StableSort_int16_Random_4096 10596 ns 168397 ns BM_StableSort_int16_Random_16384 49908 ns 753031 ns BM_StableSort_int16_Random_65536 444605 ns 3838368 ns BM_StableSort_int16_Random_262144 2419345 ns 15657285 ns BM_StableSort_int16_Random_524288 7984040 ns 32726933 ns BM_StableSort_int16_Random_1048576 16092424 ns 67999766 ns BM_StableSort_int16_Ascending_1 3.40 ns 3.43 ns BM_StableSort_int16_Ascending_4 5.45 ns 5.79 ns BM_StableSort_int16_Ascending_16 12.0 ns 15.3 ns BM_StableSort_int16_Ascending_64 39.6 ns 52.6 ns BM_StableSort_int16_Ascending_256 470 ns 550 ns BM_StableSort_int16_Ascending_1024 1686 ns 2707 ns BM_StableSort_int16_Ascending_4096 5676 ns 14165 ns BM_StableSort_int16_Ascending_16384 21413 ns 69483 ns BM_StableSort_int16_Ascending_65536 88010 ns 334466 ns BM_StableSort_int16_Ascending_262144 567239 ns 1570620 ns BM_StableSort_int16_Ascending_524288 1553063 ns 3424666 ns BM_StableSort_int16_Ascending_1048576 3145577 ns 8499649 ns BM_StableSort_int16_Descending_1 3.22 ns 3.54 ns BM_StableSort_int16_Descending_4 6.85 ns 10.2 ns BM_StableSort_int16_Descending_16 62.7 ns 62.2 ns BM_StableSort_int16_Descending_64 1138 ns 1036 ns BM_StableSort_int16_Descending_256 5541 ns 4696 ns BM_StableSort_int16_Descending_1024 3046 ns 19577 ns BM_StableSort_int16_Descending_4096 10962 ns 79149 ns BM_StableSort_int16_Descending_16384 58182 ns 327709 ns BM_StableSort_int16_Descending_65536 447025 ns 1424896 ns BM_StableSort_int16_Descending_262144 1104973 ns 5921903 ns BM_StableSort_int16_Descending_524288 2547840 ns 17956789 ns BM_StableSort_int16_Descending_1048576 5093555 ns 17044318 ns BM_StableSort_int16_SingleElement_1 3.56 ns 3.96 ns BM_StableSort_int16_SingleElement_4 5.75 ns 6.72 ns BM_StableSort_int16_SingleElement_16 12.4 ns 16.1 ns BM_StableSort_int16_SingleElement_64 36.9 ns 54.4 ns BM_StableSort_int16_SingleElement_256 473 ns 557 ns BM_StableSort_int16_SingleElement_1024 1828 ns 2826 ns BM_StableSort_int16_SingleElement_4096 6239 ns 14252 ns BM_StableSort_int16_SingleElement_16384 23695 ns 70369 ns BM_StableSort_int16_SingleElement_65536 93281 ns 361641 ns BM_StableSort_int16_SingleElement_262144 599078 ns 1640216 ns BM_StableSort_int16_SingleElement_524288 1659678 ns 3343087 ns BM_StableSort_int16_SingleElement_1048576 3184033 ns 7770271 ns BM_StableSort_int16_PipeOrgan_1 3.75 ns 3.76 ns BM_StableSort_int16_PipeOrgan_4 5.94 ns 7.74 ns BM_StableSort_int16_PipeOrgan_16 26.7 ns 25.9 ns BM_StableSort_int16_PipeOrgan_64 300 ns 263 ns BM_StableSort_int16_PipeOrgan_256 2769 ns 2760 ns BM_StableSort_int16_PipeOrgan_1024 2996 ns 10544 ns BM_StableSort_int16_PipeOrgan_4096 11641 ns 44750 ns BM_StableSort_int16_PipeOrgan_16384 57224 ns 200464 ns BM_StableSort_int16_PipeOrgan_65536 416873 ns 887631 ns BM_StableSort_int16_PipeOrgan_262144 843264 ns 3588669 ns BM_StableSort_int16_PipeOrgan_524288 2027741 ns 11056924 ns BM_StableSort_int16_PipeOrgan_1048576 4223773 ns 13261276 ns BM_StableSort_int16_QuickSortAdversary_1 3.83 ns 3.68 ns BM_StableSort_int16_QuickSortAdversary_4 5.55 ns 6.93 ns BM_StableSort_int16_QuickSortAdversary_16 12.3 ns 15.2 ns BM_StableSort_int16_QuickSortAdversary_64 646 ns 632 ns BM_StableSort_int16_QuickSortAdversary_256 2751 ns 2542 ns BM_StableSort_int16_QuickSortAdversary_1024 3028 ns 16901 ns BM_StableSort_int16_QuickSortAdversary_4096 10862 ns 80222 ns BM_StableSort_int16_QuickSortAdversary_16384 57753 ns 317281 ns BM_StableSort_int16_QuickSortAdversary_65536 94064 ns 328502 ns BM_StableSort_int16_QuickSortAdversary_262144 557796 ns 1613208 ns BM_StableSort_int16_QuickSortAdversary_524288 1518451 ns 3479740 ns BM_StableSort_int16_QuickSortAdversary_1048576 3165129 ns 7655880 ns BM_StableSort_uint16_Random_1 3.26 ns 3.44 ns BM_StableSort_uint16_Random_4 21.1 ns 22.2 ns BM_StableSort_uint16_Random_16 157 ns 156 ns BM_StableSort_uint16_Random_64 955 ns 947 ns BM_StableSort_uint16_Random_256 5886 ns 6097 ns BM_StableSort_uint16_Random_1024 2787 ns 30776 ns BM_StableSort_uint16_Random_4096 9973 ns 155652 ns BM_StableSort_uint16_Random_16384 48628 ns 741072 ns BM_StableSort_uint16_Random_65536 439609 ns 3478966 ns BM_StableSort_uint16_Random_262144 2336983 ns 15197642 ns BM_StableSort_uint16_Random_524288 7888701 ns 34234254 ns BM_StableSort_uint16_Random_1048576 14865180 ns 68516386 ns BM_StableSort_uint16_Ascending_1 3.33 ns 4.00 ns BM_StableSort_uint16_Ascending_4 5.79 ns 6.64 ns BM_StableSort_uint16_Ascending_16 14.9 ns 15.5 ns BM_StableSort_uint16_Ascending_64 50.2 ns 52.5 ns BM_StableSort_uint16_Ascending_256 538 ns 546 ns BM_StableSort_uint16_Ascending_1024 1645 ns 2652 ns BM_StableSort_uint16_Ascending_4096 5559 ns 14517 ns BM_StableSort_uint16_Ascending_16384 22803 ns 70275 ns BM_StableSort_uint16_Ascending_65536 83109 ns 333446 ns BM_StableSort_uint16_Ascending_262144 562667 ns 1568670 ns BM_StableSort_uint16_Ascending_524288 1564646 ns 3059839 ns BM_StableSort_uint16_Ascending_1048576 3178826 ns 7048327 ns BM_StableSort_uint16_Descending_1 3.34 ns 3.93 ns BM_StableSort_uint16_Descending_4 8.75 ns 9.73 ns BM_StableSort_uint16_Descending_16 55.9 ns 55.5 ns BM_StableSort_uint16_Descending_64 1021 ns 1035 ns BM_StableSort_uint16_Descending_256 4752 ns 4931 ns BM_StableSort_uint16_Descending_1024 2982 ns 19727 ns BM_StableSort_uint16_Descending_4096 10432 ns 83165 ns BM_StableSort_uint16_Descending_16384 56593 ns 326131 ns BM_StableSort_uint16_Descending_65536 439134 ns 1371346 ns BM_StableSort_uint16_Descending_262144 1220925 ns 5735665 ns BM_StableSort_uint16_Descending_524288 2767234 ns 16758330 ns BM_StableSort_uint16_Descending_1048576 5673769 ns 17541715 ns BM_StableSort_uint16_SingleElement_1 3.53 ns 3.73 ns BM_StableSort_uint16_SingleElement_4 6.27 ns 5.81 ns BM_StableSort_uint16_SingleElement_16 14.8 ns 15.1 ns BM_StableSort_uint16_SingleElement_64 51.5 ns 50.9 ns BM_StableSort_uint16_SingleElement_256 536 ns 540 ns BM_StableSort_uint16_SingleElement_1024 1669 ns 2690 ns BM_StableSort_uint16_SingleElement_4096 5840 ns 14230 ns BM_StableSort_uint16_SingleElement_16384 22468 ns 68524 ns BM_StableSort_uint16_SingleElement_65536 89845 ns 332187 ns BM_StableSort_uint16_SingleElement_262144 590736 ns 1550868 ns BM_StableSort_uint16_SingleElement_524288 1573677 ns 3095703 ns BM_StableSort_uint16_SingleElement_1048576 3183421 ns 8251180 ns BM_StableSort_uint16_PipeOrgan_1 3.70 ns 3.64 ns BM_StableSort_uint16_PipeOrgan_4 7.01 ns 6.81 ns BM_StableSort_uint16_PipeOrgan_16 25.7 ns 26.4 ns BM_StableSort_uint16_PipeOrgan_64 283 ns 277 ns BM_StableSort_uint16_PipeOrgan_256 2562 ns 2852 ns BM_StableSort_uint16_PipeOrgan_1024 2863 ns 10892 ns BM_StableSort_uint16_PipeOrgan_4096 10585 ns 45668 ns BM_StableSort_uint16_PipeOrgan_16384 59151 ns 194358 ns BM_StableSort_uint16_PipeOrgan_65536 508579 ns 854692 ns BM_StableSort_uint16_PipeOrgan_262144 901294 ns 3606346 ns BM_StableSort_uint16_PipeOrgan_524288 2192498 ns 10449279 ns BM_StableSort_uint16_PipeOrgan_1048576 4204368 ns 11956606 ns BM_StableSort_uint16_QuickSortAdversary_1 3.20 ns 3.63 ns BM_StableSort_uint16_QuickSortAdversary_4 5.30 ns 6.38 ns BM_StableSort_uint16_QuickSortAdversary_16 14.5 ns 15.3 ns BM_StableSort_uint16_QuickSortAdversary_64 575 ns 611 ns BM_StableSort_uint16_QuickSortAdversary_256 2423 ns 2577 ns BM_StableSort_uint16_QuickSortAdversary_1024 2794 ns 16854 ns BM_StableSort_uint16_QuickSortAdversary_4096 10511 ns 75952 ns BM_StableSort_uint16_QuickSortAdversary_16384 56214 ns 333824 ns BM_StableSort_uint16_QuickSortAdversary_65536 422512 ns 1354867 ns BM_StableSort_uint16_QuickSortAdversary_262144 583301 ns 1564443 ns BM_StableSort_uint16_QuickSortAdversary_524288 1584319 ns 3265575 ns BM_StableSort_uint16_QuickSortAdversary_1048576 3197732 ns 7945245 ns BM_StableSort_int32_Random_1 3.81 ns 3.70 ns BM_StableSort_int32_Random_4 20.8 ns 23.4 ns BM_StableSort_int32_Random_16 134 ns 161 ns BM_StableSort_int32_Random_64 895 ns 984 ns BM_StableSort_int32_Random_256 5640 ns 5897 ns BM_StableSort_int32_Random_1024 6994 ns 32118 ns BM_StableSort_int32_Random_4096 27367 ns 168960 ns BM_StableSort_int32_Random_16384 183261 ns 843240 ns BM_StableSort_int32_Random_65536 950914 ns 3953588 ns BM_StableSort_int32_Random_262144 3673311 ns 16790171 ns BM_StableSort_int32_Random_524288 11515700 ns 36023098 ns BM_StableSort_int32_Random_1048576 24492515 ns 78116028 ns BM_StableSort_int32_Ascending_1 3.31 ns 4.48 ns BM_StableSort_int32_Ascending_4 5.96 ns 6.99 ns BM_StableSort_int32_Ascending_16 13.0 ns 16.0 ns BM_StableSort_int32_Ascending_64 36.7 ns 53.0 ns BM_StableSort_int32_Ascending_256 391 ns 471 ns BM_StableSort_int32_Ascending_1024 2705 ns 2682 ns BM_StableSort_int32_Ascending_4096 8773 ns 14231 ns BM_StableSort_int32_Ascending_16384 34709 ns 70625 ns BM_StableSort_int32_Ascending_65536 142907 ns 344482 ns BM_StableSort_int32_Ascending_262144 745483 ns 1591418 ns BM_StableSort_int32_Ascending_524288 1873701 ns 3190305 ns BM_StableSort_int32_Ascending_1048576 3851590 ns 7570095 ns BM_StableSort_int32_Descending_1 3.22 ns 4.23 ns BM_StableSort_int32_Descending_4 7.58 ns 11.2 ns BM_StableSort_int32_Descending_16 63.9 ns 58.6 ns BM_StableSort_int32_Descending_64 1133 ns 1017 ns BM_StableSort_int32_Descending_256 4850 ns 4464 ns BM_StableSort_int32_Descending_1024 7023 ns 18954 ns BM_StableSort_int32_Descending_4096 28550 ns 75163 ns BM_StableSort_int32_Descending_16384 200880 ns 341104 ns BM_StableSort_int32_Descending_65536 1095910 ns 1398021 ns BM_StableSort_int32_Descending_262144 3818864 ns 5695486 ns BM_StableSort_int32_Descending_524288 5606779 ns 17593982 ns BM_StableSort_int32_Descending_1048576 16416366 ns 26649503 ns BM_StableSort_int32_SingleElement_1 3.81 ns 3.71 ns BM_StableSort_int32_SingleElement_4 6.57 ns 6.61 ns BM_StableSort_int32_SingleElement_16 14.0 ns 15.8 ns BM_StableSort_int32_SingleElement_64 38.7 ns 53.5 ns BM_StableSort_int32_SingleElement_256 386 ns 554 ns BM_StableSort_int32_SingleElement_1024 2761 ns 3046 ns BM_StableSort_int32_SingleElement_4096 9179 ns 15188 ns BM_StableSort_int32_SingleElement_16384 34794 ns 70119 ns BM_StableSort_int32_SingleElement_65536 135190 ns 354755 ns BM_StableSort_int32_SingleElement_262144 760995 ns 1644072 ns BM_StableSort_int32_SingleElement_524288 1969575 ns 3343419 ns BM_StableSort_int32_SingleElement_1048576 4423816 ns 8346971 ns BM_StableSort_int32_PipeOrgan_1 3.79 ns 3.63 ns BM_StableSort_int32_PipeOrgan_4 6.21 ns 6.73 ns BM_StableSort_int32_PipeOrgan_16 27.5 ns 26.0 ns BM_StableSort_int32_PipeOrgan_64 291 ns 265 ns BM_StableSort_int32_PipeOrgan_256 2557 ns 2518 ns BM_StableSort_int32_PipeOrgan_1024 6765 ns 10976 ns BM_StableSort_int32_PipeOrgan_4096 26373 ns 44537 ns BM_StableSort_int32_PipeOrgan_16384 201466 ns 188582 ns BM_StableSort_int32_PipeOrgan_65536 1148533 ns 802368 ns BM_StableSort_int32_PipeOrgan_262144 2255177 ns 3477829 ns BM_StableSort_int32_PipeOrgan_524288 3947015 ns 10356637 ns BM_StableSort_int32_PipeOrgan_1048576 10274312 ns 16405366 ns BM_StableSort_int32_QuickSortAdversary_1 3.32 ns 4.36 ns BM_StableSort_int32_QuickSortAdversary_4 5.98 ns 7.44 ns BM_StableSort_int32_QuickSortAdversary_16 13.0 ns 16.3 ns BM_StableSort_int32_QuickSortAdversary_64 657 ns 616 ns BM_StableSort_int32_QuickSortAdversary_256 2569 ns 2483 ns BM_StableSort_int32_QuickSortAdversary_1024 6898 ns 19635 ns BM_StableSort_int32_QuickSortAdversary_4096 27092 ns 75108 ns BM_StableSort_int32_QuickSortAdversary_16384 190379 ns 316463 ns BM_StableSort_int32_QuickSortAdversary_65536 1109040 ns 1319018 ns BM_StableSort_int32_QuickSortAdversary_262144 4361925 ns 5472779 ns BM_StableSort_int32_QuickSortAdversary_524288 6528215 ns 17538983 ns BM_StableSort_int32_QuickSortAdversary_1048576 18345325 ns 27223926 ns BM_StableSort_uint32_Random_1 3.67 ns 3.82 ns BM_StableSort_uint32_Random_4 22.3 ns 21.8 ns BM_StableSort_uint32_Random_16 155 ns 153 ns BM_StableSort_uint32_Random_64 946 ns 976 ns BM_StableSort_uint32_Random_256 5824 ns 6019 ns BM_StableSort_uint32_Random_1024 4525 ns 32764 ns BM_StableSort_uint32_Random_4096 17223 ns 158608 ns BM_StableSort_uint32_Random_16384 134821 ns 748525 ns BM_StableSort_uint32_Random_65536 716644 ns 3453325 ns BM_StableSort_uint32_Random_262144 3628062 ns 16065414 ns BM_StableSort_uint32_Random_524288 10971334 ns 36567712 ns BM_StableSort_uint32_Random_1048576 22688377 ns 77533497 ns BM_StableSort_uint32_Ascending_1 3.57 ns 3.44 ns BM_StableSort_uint32_Ascending_4 5.73 ns 5.33 ns BM_StableSort_uint32_Ascending_16 14.5 ns 14.0 ns BM_StableSort_uint32_Ascending_64 50.3 ns 51.3 ns BM_StableSort_uint32_Ascending_256 465 ns 467 ns BM_StableSort_uint32_Ascending_1024 3042 ns 2530 ns BM_StableSort_uint32_Ascending_4096 9842 ns 12207 ns BM_StableSort_uint32_Ascending_16384 37994 ns 61726 ns BM_StableSort_uint32_Ascending_65536 148890 ns 294385 ns BM_StableSort_uint32_Ascending_262144 855080 ns 1422167 ns BM_StableSort_uint32_Ascending_524288 2154903 ns 3203018 ns BM_StableSort_uint32_Ascending_1048576 5002518 ns 7563817 ns BM_StableSort_uint32_Descending_1 3.51 ns 3.40 ns BM_StableSort_uint32_Descending_4 9.09 ns 7.95 ns BM_StableSort_uint32_Descending_16 54.8 ns 74.4 ns BM_StableSort_uint32_Descending_64 1003 ns 1305 ns BM_StableSort_uint32_Descending_256 4545 ns 5300 ns BM_StableSort_uint32_Descending_1024 4361 ns 21884 ns BM_StableSort_uint32_Descending_4096 16018 ns 90534 ns BM_StableSort_uint32_Descending_16384 146274 ns 381943 ns BM_StableSort_uint32_Descending_65536 938248 ns 1536806 ns BM_StableSort_uint32_Descending_262144 3899300 ns 6387843 ns BM_StableSort_uint32_Descending_524288 5808157 ns 21959858 ns BM_StableSort_uint32_Descending_1048576 17520047 ns 26351912 ns BM_StableSort_uint32_SingleElement_1 4.03 ns 3.97 ns BM_StableSort_uint32_SingleElement_4 6.55 ns 6.41 ns BM_StableSort_uint32_SingleElement_16 15.6 ns 15.8 ns BM_StableSort_uint32_SingleElement_64 52.3 ns 58.7 ns BM_StableSort_uint32_SingleElement_256 473 ns 485 ns BM_StableSort_uint32_SingleElement_1024 3020 ns 2407 ns BM_StableSort_uint32_SingleElement_4096 9998 ns 12527 ns BM_StableSort_uint32_SingleElement_16384 38072 ns 62228 ns BM_StableSort_uint32_SingleElement_65536 153706 ns 295662 ns BM_StableSort_uint32_SingleElement_262144 836532 ns 1477099 ns BM_StableSort_uint32_SingleElement_524288 2144900 ns 3157204 ns BM_StableSort_uint32_SingleElement_1048576 4995525 ns 7617233 ns BM_StableSort_uint32_PipeOrgan_1 4.02 ns 3.99 ns BM_StableSort_uint32_PipeOrgan_4 6.97 ns 6.84 ns BM_StableSort_uint32_PipeOrgan_16 26.1 ns 29.7 ns BM_StableSort_uint32_PipeOrgan_64 266 ns 333 ns BM_StableSort_uint32_PipeOrgan_256 2462 ns 2892 ns BM_StableSort_uint32_PipeOrgan_1024 4291 ns 12431 ns BM_StableSort_uint32_PipeOrgan_4096 15638 ns 51449 ns BM_StableSort_uint32_PipeOrgan_16384 154563 ns 217460 ns BM_StableSort_uint32_PipeOrgan_65536 907724 ns 925873 ns BM_StableSort_uint32_PipeOrgan_262144 2394580 ns 4103575 ns BM_StableSort_uint32_PipeOrgan_524288 4177145 ns 13947158 ns BM_StableSort_uint32_PipeOrgan_1048576 11848224 ns 18807297 ns BM_StableSort_uint32_QuickSortAdversary_1 3.50 ns 3.43 ns BM_StableSort_uint32_QuickSortAdversary_4 5.88 ns 4.96 ns BM_StableSort_uint32_QuickSortAdversary_16 14.6 ns 14.0 ns BM_StableSort_uint32_QuickSortAdversary_64 576 ns 715 ns BM_StableSort_uint32_QuickSortAdversary_256 2353 ns 2797 ns BM_StableSort_uint32_QuickSortAdversary_1024 4176 ns 21775 ns BM_StableSort_uint32_QuickSortAdversary_4096 15565 ns 96188 ns BM_StableSort_uint32_QuickSortAdversary_16384 149092 ns 398332 ns BM_StableSort_uint32_QuickSortAdversary_65536 902488 ns 1552393 ns BM_StableSort_uint32_QuickSortAdversary_262144 3946517 ns 6560414 ns BM_StableSort_uint32_QuickSortAdversary_524288 6247114 ns 22420977 ns BM_StableSort_uint32_QuickSortAdversary_1048576 19892446 ns 26529576 ns BM_StableSort_int64_Random_1 3.83 ns 3.98 ns BM_StableSort_int64_Random_4 21.1 ns 24.0 ns BM_StableSort_int64_Random_16 129 ns 136 ns BM_StableSort_int64_Random_64 890 ns 906 ns BM_StableSort_int64_Random_256 5542 ns 5901 ns BM_StableSort_int64_Random_1024 16085 ns 33112 ns BM_StableSort_int64_Random_4096 63895 ns 162181 ns BM_StableSort_int64_Random_16384 348827 ns 790045 ns BM_StableSort_int64_Random_65536 1488237 ns 3557506 ns BM_StableSort_int64_Random_262144 8195713 ns 16315808 ns BM_StableSort_int64_Random_524288 16586833 ns 38274075 ns BM_StableSort_int64_Random_1048576 40346644 ns 79182089 ns BM_StableSort_int64_Ascending_1 3.76 ns 3.55 ns BM_StableSort_int64_Ascending_4 5.82 ns 6.19 ns BM_StableSort_int64_Ascending_16 11.7 ns 11.8 ns BM_StableSort_int64_Ascending_64 32.9 ns 36.8 ns BM_StableSort_int64_Ascending_256 415 ns 550 ns BM_StableSort_int64_Ascending_1024 5352 ns 3347 ns BM_StableSort_int64_Ascending_4096 17516 ns 19134 ns BM_StableSort_int64_Ascending_16384 64147 ns 91099 ns BM_StableSort_int64_Ascending_65536 322126 ns 434009 ns BM_StableSort_int64_Ascending_262144 1554669 ns 2057056 ns BM_StableSort_int64_Ascending_524288 3656527 ns 5016650 ns BM_StableSort_int64_Ascending_1048576 10469979 ns 12908613 ns BM_StableSort_int64_Descending_1 4.09 ns 3.35 ns BM_StableSort_int64_Descending_4 9.13 ns 8.01 ns BM_StableSort_int64_Descending_16 76.8 ns 92.9 ns BM_StableSort_int64_Descending_64 1336 ns 1417 ns BM_StableSort_int64_Descending_256 5525 ns 5674 ns BM_StableSort_int64_Descending_1024 17461 ns 22558 ns BM_StableSort_int64_Descending_4096 64285 ns 102360 ns BM_StableSort_int64_Descending_16384 336946 ns 388940 ns BM_StableSort_int64_Descending_65536 837912 ns 1662169 ns BM_StableSort_int64_Descending_262144 3680806 ns 7494323 ns BM_StableSort_int64_Descending_524288 11023784 ns 24935033 ns BM_StableSort_int64_Descending_1048576 20023568 ns 33220712 ns BM_StableSort_int64_SingleElement_1 3.37 ns 3.98 ns BM_StableSort_int64_SingleElement_4 5.32 ns 6.92 ns BM_StableSort_int64_SingleElement_16 10.9 ns 13.3 ns BM_StableSort_int64_SingleElement_64 32.1 ns 43.8 ns BM_StableSort_int64_SingleElement_256 420 ns 541 ns BM_StableSort_int64_SingleElement_1024 5689 ns 3381 ns BM_StableSort_int64_SingleElement_4096 19199 ns 17989 ns BM_StableSort_int64_SingleElement_16384 75754 ns 91963 ns BM_StableSort_int64_SingleElement_65536 357106 ns 500326 ns BM_StableSort_int64_SingleElement_262144 1672975 ns 2417734 ns BM_StableSort_int64_SingleElement_524288 3642891 ns 5200878 ns BM_StableSort_int64_SingleElement_1048576 11172007 ns 13729511 ns BM_StableSort_int64_PipeOrgan_1 3.38 ns 3.94 ns BM_StableSort_int64_PipeOrgan_4 5.73 ns 6.44 ns BM_StableSort_int64_PipeOrgan_16 27.5 ns 29.0 ns BM_StableSort_int64_PipeOrgan_64 310 ns 321 ns BM_StableSort_int64_PipeOrgan_256 2761 ns 2918 ns BM_StableSort_int64_PipeOrgan_1024 16105 ns 12525 ns BM_StableSort_int64_PipeOrgan_4096 65289 ns 59990 ns BM_StableSort_int64_PipeOrgan_16384 341757 ns 270636 ns BM_StableSort_int64_PipeOrgan_65536 587452 ns 1126132 ns BM_StableSort_int64_PipeOrgan_262144 2837955 ns 5034180 ns BM_StableSort_int64_PipeOrgan_524288 6617313 ns 15267354 ns BM_StableSort_int64_PipeOrgan_1048576 15208796 ns 23162989 ns BM_StableSort_int64_QuickSortAdversary_1 3.77 ns 3.45 ns BM_StableSort_int64_QuickSortAdversary_4 5.55 ns 5.20 ns BM_StableSort_int64_QuickSortAdversary_16 12.5 ns 11.5 ns BM_StableSort_int64_QuickSortAdversary_64 646 ns 750 ns BM_StableSort_int64_QuickSortAdversary_256 2655 ns 3539 ns BM_StableSort_int64_QuickSortAdversary_1024 16373 ns 22349 ns BM_StableSort_int64_QuickSortAdversary_4096 62306 ns 97248 ns BM_StableSort_int64_QuickSortAdversary_16384 321755 ns 388084 ns BM_StableSort_int64_QuickSortAdversary_65536 1374694 ns 1596091 ns BM_StableSort_int64_QuickSortAdversary_262144 4374661 ns 6894139 ns BM_StableSort_int64_QuickSortAdversary_524288 12736074 ns 23932229 ns BM_StableSort_int64_QuickSortAdversary_1048576 22615219 ns 33355629 ns BM_StableSort_uint64_Random_1 3.82 ns 3.49 ns BM_StableSort_uint64_Random_4 22.4 ns 23.4 ns BM_StableSort_uint64_Random_16 154 ns 146 ns BM_StableSort_uint64_Random_64 924 ns 926 ns BM_StableSort_uint64_Random_256 5864 ns 5913 ns BM_StableSort_uint64_Random_1024 7168 ns 31746 ns BM_StableSort_uint64_Random_4096 27668 ns 154224 ns BM_StableSort_uint64_Random_16384 219526 ns 755205 ns BM_StableSort_uint64_Random_65536 965251 ns 3490165 ns BM_StableSort_uint64_Random_262144 6262162 ns 15889589 ns BM_StableSort_uint64_Random_524288 12530078 ns 36458581 ns BM_StableSort_uint64_Random_1048576 38462191 ns 75168445 ns BM_StableSort_uint64_Ascending_1 3.30 ns 3.35 ns BM_StableSort_uint64_Ascending_4 5.65 ns 5.84 ns BM_StableSort_uint64_Ascending_16 14.7 ns 12.6 ns BM_StableSort_uint64_Ascending_64 55.3 ns 34.6 ns BM_StableSort_uint64_Ascending_256 513 ns 533 ns BM_StableSort_uint64_Ascending_1024 5541 ns 3189 ns BM_StableSort_uint64_Ascending_4096 17706 ns 20326 ns BM_StableSort_uint64_Ascending_16384 66420 ns 93757 ns BM_StableSort_uint64_Ascending_65536 341425 ns 435016 ns BM_StableSort_uint64_Ascending_262144 1595691 ns 2088317 ns BM_StableSort_uint64_Ascending_524288 3808703 ns 5092832 ns BM_StableSort_uint64_Ascending_1048576 11060417 ns 13023250 ns BM_StableSort_uint64_Descending_1 3.29 ns 3.35 ns BM_StableSort_uint64_Descending_4 8.65 ns 7.92 ns BM_StableSort_uint64_Descending_16 54.7 ns 80.2 ns BM_StableSort_uint64_Descending_64 1028 ns 1307 ns BM_StableSort_uint64_Descending_256 4521 ns 5635 ns BM_StableSort_uint64_Descending_1024 7122 ns 23323 ns BM_StableSort_uint64_Descending_4096 30538 ns 95892 ns BM_StableSort_uint64_Descending_16384 195565 ns 392721 ns BM_StableSort_uint64_Descending_65536 852002 ns 1720358 ns BM_StableSort_uint64_Descending_262144 3737884 ns 7484130 ns BM_StableSort_uint64_Descending_524288 11159345 ns 25690770 ns BM_StableSort_uint64_Descending_1048576 20648864 ns 33057383 ns BM_StableSort_uint64_SingleElement_1 3.62 ns 4.10 ns BM_StableSort_uint64_SingleElement_4 6.73 ns 6.64 ns BM_StableSort_uint64_SingleElement_16 14.9 ns 11.3 ns BM_StableSort_uint64_SingleElement_64 52.0 ns 33.0 ns BM_StableSort_uint64_SingleElement_256 511 ns 582 ns BM_StableSort_uint64_SingleElement_1024 6499 ns 3287 ns BM_StableSort_uint64_SingleElement_4096 22190 ns 17616 ns BM_StableSort_uint64_SingleElement_16384 84378 ns 86885 ns BM_StableSort_uint64_SingleElement_65536 466257 ns 457144 ns BM_StableSort_uint64_SingleElement_262144 1993687 ns 2361999 ns BM_StableSort_uint64_SingleElement_524288 4759565 ns 5096771 ns BM_StableSort_uint64_SingleElement_1048576 12426111 ns 13468453 ns BM_StableSort_uint64_PipeOrgan_1 3.73 ns 3.94 ns BM_StableSort_uint64_PipeOrgan_4 7.18 ns 7.54 ns BM_StableSort_uint64_PipeOrgan_16 25.2 ns 29.1 ns BM_StableSort_uint64_PipeOrgan_64 260 ns 321 ns BM_StableSort_uint64_PipeOrgan_256 2468 ns 2970 ns BM_StableSort_uint64_PipeOrgan_1024 7025 ns 12912 ns BM_StableSort_uint64_PipeOrgan_4096 28968 ns 53379 ns BM_StableSort_uint64_PipeOrgan_16384 194156 ns 239790 ns BM_StableSort_uint64_PipeOrgan_65536 599491 ns 993800 ns BM_StableSort_uint64_PipeOrgan_262144 2648585 ns 4689680 ns BM_StableSort_uint64_PipeOrgan_524288 7621109 ns 15401808 ns BM_StableSort_uint64_PipeOrgan_1048576 15608814 ns 23484821 ns BM_StableSort_uint64_QuickSortAdversary_1 3.38 ns 3.54 ns BM_StableSort_uint64_QuickSortAdversary_4 5.50 ns 6.03 ns BM_StableSort_uint64_QuickSortAdversary_16 14.2 ns 11.0 ns BM_StableSort_uint64_QuickSortAdversary_64 597 ns 688 ns BM_StableSort_uint64_QuickSortAdversary_256 2446 ns 2818 ns BM_StableSort_uint64_QuickSortAdversary_1024 7266 ns 20319 ns BM_StableSort_uint64_QuickSortAdversary_4096 31155 ns 89112 ns BM_StableSort_uint64_QuickSortAdversary_16384 201033 ns 390574 ns BM_StableSort_uint64_QuickSortAdversary_65536 871014 ns 1685639 ns BM_StableSort_uint64_QuickSortAdversary_262144 3978535 ns 7265830 ns BM_StableSort_uint64_QuickSortAdversary_524288 10279721 ns 25350004 ns BM_StableSort_uint64_QuickSortAdversary_1048576 20256585 ns 33054393 ns ```
2024-10-31[libc++] Granularize <cstddef> includes (#108696)Nikolas Klauser4-0/+4
2024-09-16[libc++][modules] Fix missing and incorrect includes (#108850)Louis Dionne11-2/+17
This patch adds a large number of missing includes in the libc++ headers and the test suite. Those were found as part of the effort to move towards a mostly monolithic top-level std module.
2024-09-16[libc++] Remove get_temporary_buffer and return_temporary_buffer (#100914)A. Jiang1-3/+3
Works towards P0619R4 / #99985. The use of `std::get_temporary_buffer` and `std::return_temporary_buffer` are replaced with `unique_ptr`-based RAII buffer holder. Escape hatches: - `_LIBCPP_ENABLE_CXX20_REMOVED_TEMPORARY_BUFFER` restores `std::get_temporary_buffer` and `std::return_temporary_buffer`. Drive-by changes: - In `<syncstream>`, states that `get_temporary_buffer` is now removed, because `<syncstream>` is added in C++20.
2024-08-20[libc++] Fix several double-moves in the code base (#104616)Louis Dionne3-133/+163
This patch hardens the "test iterators" we use to test algorithms by ensuring that they don't get double-moved. As a result of this hardening, the tests started reporting multiple failures where we would double-move iterators, which are being fixed in this patch. In particular: - Fixed a double-move in pstl.partition - Add coverage for begin()/end() in subrange tests - Fix tests for ranges::ends_with and ranges::contains, which were incorrectly calling begin() twice on the same subrange containing non-copyable input iterators. Fixes #100709
2024-08-05[libc++] Check correctly ref-qualified __is_callable in algorithms (#101553)Louis Dionne6-26/+48
We were only checking that the comparator was rvalue callable, when in reality the algorithms always call comparators as lvalues. This patch also refactors the tests for callable requirements and expands it to a few missing algorithms. This is take 2 of #73451, which was reverted because it broke some CI bots. The issue was that we checked __is_callable with arguments in the wrong order inside std::upper_bound. This has now been fixed and a test was added. Fixes #69554
2024-08-04[libc++] Optimize lexicographical_compare (#65279)Nikolas Klauser1-54/+36
If the comparison operation is equivalent to < and that is a total order, we know that we can use equality comparison on that type instead to extract some information. Furthermore, if equality comparison on that type is trivial, the user can't observe that we're calling it. So instead of using the user-provided total order, we use std::mismatch, which uses equality comparison (and is vertorized). Additionally, if the type is trivially lexicographically comparable, we can go one step further and use std::memcmp directly instead of calling std::mismatch. Benchmarks: ``` ------------------------------------------------------------------------------------- Benchmark old new ------------------------------------------------------------------------------------- bm_lexicographical_compare<unsigned char>/1 1.17 ns 2.34 ns bm_lexicographical_compare<unsigned char>/2 1.64 ns 2.57 ns bm_lexicographical_compare<unsigned char>/3 2.23 ns 2.58 ns bm_lexicographical_compare<unsigned char>/4 2.82 ns 2.57 ns bm_lexicographical_compare<unsigned char>/5 3.34 ns 2.11 ns bm_lexicographical_compare<unsigned char>/6 3.94 ns 2.21 ns bm_lexicographical_compare<unsigned char>/7 4.56 ns 2.11 ns bm_lexicographical_compare<unsigned char>/8 5.25 ns 2.11 ns bm_lexicographical_compare<unsigned char>/16 9.88 ns 2.11 ns bm_lexicographical_compare<unsigned char>/64 38.9 ns 2.36 ns bm_lexicographical_compare<unsigned char>/512 317 ns 6.54 ns bm_lexicographical_compare<unsigned char>/4096 2517 ns 41.4 ns bm_lexicographical_compare<unsigned char>/32768 20052 ns 488 ns bm_lexicographical_compare<unsigned char>/262144 159579 ns 4409 ns bm_lexicographical_compare<unsigned char>/1048576 640456 ns 20342 ns bm_lexicographical_compare<signed char>/1 1.18 ns 2.37 ns bm_lexicographical_compare<signed char>/2 1.65 ns 2.60 ns bm_lexicographical_compare<signed char>/3 2.23 ns 2.83 ns bm_lexicographical_compare<signed char>/4 2.81 ns 3.06 ns bm_lexicographical_compare<signed char>/5 3.35 ns 3.30 ns bm_lexicographical_compare<signed char>/6 3.90 ns 3.99 ns bm_lexicographical_compare<signed char>/7 4.56 ns 3.78 ns bm_lexicographical_compare<signed char>/8 5.20 ns 4.02 ns bm_lexicographical_compare<signed char>/16 9.80 ns 6.21 ns bm_lexicographical_compare<signed char>/64 39.0 ns 3.16 ns bm_lexicographical_compare<signed char>/512 318 ns 7.58 ns bm_lexicographical_compare<signed char>/4096 2514 ns 47.4 ns bm_lexicographical_compare<signed char>/32768 20096 ns 504 ns bm_lexicographical_compare<signed char>/262144 156617 ns 4146 ns bm_lexicographical_compare<signed char>/1048576 624265 ns 19810 ns bm_lexicographical_compare<int>/1 1.15 ns 2.12 ns bm_lexicographical_compare<int>/2 1.60 ns 2.36 ns bm_lexicographical_compare<int>/3 2.21 ns 2.59 ns bm_lexicographical_compare<int>/4 2.74 ns 2.83 ns bm_lexicographical_compare<int>/5 3.26 ns 3.06 ns bm_lexicographical_compare<int>/6 3.81 ns 4.53 ns bm_lexicographical_compare<int>/7 4.41 ns 4.72 ns bm_lexicographical_compare<int>/8 5.08 ns 2.36 ns bm_lexicographical_compare<int>/16 9.54 ns 3.08 ns bm_lexicographical_compare<int>/64 37.8 ns 4.71 ns bm_lexicographical_compare<int>/512 309 ns 24.6 ns bm_lexicographical_compare<int>/4096 2422 ns 204 ns bm_lexicographical_compare<int>/32768 19362 ns 1947 ns bm_lexicographical_compare<int>/262144 155727 ns 19793 ns bm_lexicographical_compare<int>/1048576 623614 ns 80180 ns bm_ranges_lexicographical_compare<unsigned char>/1 1.07 ns 2.35 ns bm_ranges_lexicographical_compare<unsigned char>/2 1.72 ns 2.13 ns bm_ranges_lexicographical_compare<unsigned char>/3 2.46 ns 2.12 ns bm_ranges_lexicographical_compare<unsigned char>/4 3.17 ns 2.12 ns bm_ranges_lexicographical_compare<unsigned char>/5 3.86 ns 2.12 ns bm_ranges_lexicographical_compare<unsigned char>/6 4.55 ns 2.12 ns bm_ranges_lexicographical_compare<unsigned char>/7 5.25 ns 2.12 ns bm_ranges_lexicographical_compare<unsigned char>/8 5.95 ns 2.13 ns bm_ranges_lexicographical_compare<unsigned char>/16 11.7 ns 2.13 ns bm_ranges_lexicographical_compare<unsigned char>/64 45.5 ns 2.36 ns bm_ranges_lexicographical_compare<unsigned char>/512 366 ns 6.35 ns bm_ranges_lexicographical_compare<unsigned char>/4096 2886 ns 40.9 ns bm_ranges_lexicographical_compare<unsigned char>/32768 23054 ns 489 ns bm_ranges_lexicographical_compare<unsigned char>/262144 185302 ns 4339 ns bm_ranges_lexicographical_compare<unsigned char>/1048576 741576 ns 19430 ns bm_ranges_lexicographical_compare<signed char>/1 1.10 ns 2.12 ns bm_ranges_lexicographical_compare<signed char>/2 1.66 ns 2.35 ns bm_ranges_lexicographical_compare<signed char>/3 2.23 ns 2.58 ns bm_ranges_lexicographical_compare<signed char>/4 2.82 ns 2.82 ns bm_ranges_lexicographical_compare<signed char>/5 3.34 ns 3.06 ns bm_ranges_lexicographical_compare<signed char>/6 3.92 ns 3.99 ns bm_ranges_lexicographical_compare<signed char>/7 4.64 ns 4.10 ns bm_ranges_lexicographical_compare<signed char>/8 5.21 ns 4.61 ns bm_ranges_lexicographical_compare<signed char>/16 9.79 ns 7.42 ns bm_ranges_lexicographical_compare<signed char>/64 38.9 ns 2.93 ns bm_ranges_lexicographical_compare<signed char>/512 317 ns 7.31 ns bm_ranges_lexicographical_compare<signed char>/4096 2500 ns 47.5 ns bm_ranges_lexicographical_compare<signed char>/32768 19940 ns 496 ns bm_ranges_lexicographical_compare<signed char>/262144 159166 ns 4393 ns bm_ranges_lexicographical_compare<signed char>/1048576 638206 ns 19786 ns bm_ranges_lexicographical_compare<int>/1 1.10 ns 2.12 ns bm_ranges_lexicographical_compare<int>/2 1.64 ns 3.04 ns bm_ranges_lexicographical_compare<int>/3 2.23 ns 2.58 ns bm_ranges_lexicographical_compare<int>/4 2.81 ns 2.81 ns bm_ranges_lexicographical_compare<int>/5 3.35 ns 3.05 ns bm_ranges_lexicographical_compare<int>/6 3.94 ns 4.60 ns bm_ranges_lexicographical_compare<int>/7 4.60 ns 4.81 ns bm_ranges_lexicographical_compare<int>/8 5.19 ns 2.35 ns bm_ranges_lexicographical_compare<int>/16 9.85 ns 2.87 ns bm_ranges_lexicographical_compare<int>/64 38.9 ns 4.70 ns bm_ranges_lexicographical_compare<int>/512 318 ns 24.5 ns bm_ranges_lexicographical_compare<int>/4096 2494 ns 202 ns bm_ranges_lexicographical_compare<int>/32768 20000 ns 1939 ns bm_ranges_lexicographical_compare<int>/262144 160433 ns 19730 ns bm_ranges_lexicographical_compare<int>/1048576 642636 ns 80760 ns ```
2024-08-01[libc++] Revert "Check correctly ref-qualified __is_callable in algorithms ↵Louis Dionne5-30/+26
(#73451)" This reverts commit 8d151f804ff43aaed1edf810bb2a07607b8bba14, which broke some build bots. I think that is caused by an invalid argument order when checking __is_comparable in upper_bound.
2024-08-01[libc++] Check correctly ref-qualified __is_callable in algorithms (#73451)Nhat Nguyen5-26/+30
We were only checking that the comparator was rvalue callable, when in reality the algorithms always call comparators as lvalues. This patch also refactors the tests for callable requirements and expands it to a few missing algorithms. Fixes #69554
generated by cgit v1.1 at 2025-09-29 19:30:19 +0000