llvm-project.git/libcxx/include/__algorithm, branch main Unnamed repository; edit this file 'description' to name the repository. [libc++] Simplify most of the segmented iterator optimizations (#164797) 2025-11-07T07:27:55+00:00 Nikolas Klauser nikolasklauser@berlin.de 2025-11-07T07:27:55+00:00 fc5e0c071bfba9c8cc86ecff926b84a999970613 This patch does two things. (1) It replaces SFINAE with `if constexpr`, avoiding some overload resolution and unnecessary boilerplate. (2) It removes an overload from `__for_each_n` to forward to `__for_each`, since `__for_each` doesn't provide any further optimizations. 
This patch does two things.
(1) It replaces SFINAE with `if constexpr`, avoiding some overload
resolution and unnecessary boilerplate.
(2) It removes an overload from `__for_each_n` to forward to
`__for_each`, since `__for_each` doesn't provide any further
optimizations.
 [libcxx] Optimize `rng::generate_n` for segmented iterators (#165280) 2025-10-28T14:22:26+00:00 Connector Switch c8ef@outlook.com 2025-10-28T14:22:26+00:00 0621fd0b8837192612d21785ad60664516513cea Part of #102817. This patch optimizes `rng::generate_n` for segmented iterators by forwarding the implementation directly to `std::generate_n`. - before ``` rng::generate_n(deque<int>)/32 21.7 ns 22.0 ns 32000000 rng::generate_n(deque<int>)/50 30.8 ns 30.7 ns 22400000 rng::generate_n(deque<int>)/1024 492 ns 488 ns 1120000 rng::generate_n(deque<int>)/8192 3938 ns 3924 ns 179200 ``` - after ``` rng::generate_n(deque<int>)/32 11.0 ns 11.0 ns 64000000 rng::generate_n(deque<int>)/50 16.2 ns 16.1 ns 40727273 rng::generate_n(deque<int>)/1024 292 ns 286 ns 2240000 rng::generate_n(deque<int>)/8192 2291 ns 2302 ns 298667 ``` 
Part of #102817.

This patch optimizes `rng::generate_n` for segmented iterators by
forwarding the implementation directly to `std::generate_n`.

- before

```
rng::generate_n(deque<int>)/32          21.7 ns         22.0 ns     32000000
rng::generate_n(deque<int>)/50          30.8 ns         30.7 ns     22400000
rng::generate_n(deque<int>)/1024         492 ns          488 ns      1120000
rng::generate_n(deque<int>)/8192        3938 ns         3924 ns       179200
```

- after

```
rng::generate_n(deque<int>)/32          11.0 ns         11.0 ns     64000000
rng::generate_n(deque<int>)/50          16.2 ns         16.1 ns     40727273
rng::generate_n(deque<int>)/1024         292 ns          286 ns      2240000
rng::generate_n(deque<int>)/8192        2291 ns         2302 ns       298667
```
 [libc++][IWYU] Remove `std::move` header in `std::for_each` (#164272) 2025-10-21T15:03:09+00:00 Connector Switch c8ef@outlook.com 2025-10-21T15:03:09+00:00 abf80b54bc752dc44f821da1fa9d2d3117a3c8c0 It seems this was accidentally included; there's no use of std::move in this header. 
It seems this was accidentally included; there's no use of std::move in
this header.
 [libcxx] Optimize `std::generate_n` for segmented iterators (#164266) 2025-10-21T10:01:36+00:00 Connector Switch c8ef@outlook.com 2025-10-21T10:01:36+00:00 c06ae43e26aa5cd472d0b25d5904c44d20e84067 Part of #102817. This is a natural follow-up to #163006. We are forwarding `std::generate_n` to `std::__for_each_n` (`std::for_each_n` needs c++17), resulting in improved performance for segmented iterators. before: ``` std::generate_n(deque<int>)/32 17.5 ns 17.3 ns 40727273 std::generate_n(deque<int>)/50 25.7 ns 25.5 ns 26352941 std::generate_n(deque<int>)/1024 490 ns 487 ns 1445161 std::generate_n(deque<int>)/8192 3908 ns 3924 ns 179200 ``` after: ``` std::generate_n(deque<int>)/32 11.1 ns 11.0 ns 64000000 std::generate_n(deque<int>)/50 16.1 ns 16.0 ns 44800000 std::generate_n(deque<int>)/1024 291 ns 292 ns 2357895 std::generate_n(deque<int>)/8192 2269 ns 2250 ns 298667 ``` 
Part of #102817.

This is a natural follow-up to #163006. We are forwarding
`std::generate_n` to `std::__for_each_n` (`std::for_each_n` needs
c++17), resulting in improved performance for segmented iterators.

before:

```
std::generate_n(deque<int>)/32          17.5 ns         17.3 ns     40727273
std::generate_n(deque<int>)/50          25.7 ns         25.5 ns     26352941
std::generate_n(deque<int>)/1024         490 ns          487 ns      1445161
std::generate_n(deque<int>)/8192        3908 ns         3924 ns       179200
```

after:

```
std::generate_n(deque<int>)/32          11.1 ns         11.0 ns     64000000
std::generate_n(deque<int>)/50          16.1 ns         16.0 ns     44800000
std::generate_n(deque<int>)/1024         291 ns          292 ns      2357895
std::generate_n(deque<int>)/8192        2269 ns         2250 ns       298667
```
 [libcxx] Optimize std::generate for segmented iterators (#163006) 2025-10-20T11:37:33+00:00 Connector Switch c8ef@outlook.com 2025-10-20T11:37:33+00:00 46e88169284aadb06fafcbe18ff440ff0fdebfa3 Part of #102817. This patch attempts to optimize the performance of `std::generate` for segmented iterators. Below are the benchmark numbers from `libcxx\test\benchmarks\algorithms\modifying\generate.bench.cpp`. Test cases that use segmented iterators have also been added. - before ``` std::generate(deque<int>)/32 194 ns 193 ns 3733333 std::generate(deque<int>)/50 276 ns 276 ns 2488889 std::generate(deque<int>)/1024 5096 ns 5022 ns 112000 std::generate(deque<int>)/8192 40806 ns 40806 ns 17231 ``` - after ``` std::generate(deque<int>)/32 106 ns 105 ns 6400000 std::generate(deque<int>)/50 139 ns 138 ns 4977778 std::generate(deque<int>)/1024 2713 ns 2699 ns 248889 std::generate(deque<int>)/8192 18983 ns 19252 ns 37333 ``` --------- Co-authored-by: A. Jiang <de34@live.cn> 
Part of #102817.

This patch attempts to optimize the performance of `std::generate` for
segmented iterators. Below are the benchmark numbers from
`libcxx\test\benchmarks\algorithms\modifying\generate.bench.cpp`. Test
cases that use segmented iterators have also been added.

- before

```
std::generate(deque<int>)/32           194 ns          193 ns      3733333
std::generate(deque<int>)/50           276 ns          276 ns      2488889
std::generate(deque<int>)/1024        5096 ns         5022 ns       112000
std::generate(deque<int>)/8192       40806 ns        40806 ns        17231
```

- after

```
std::generate(deque<int>)/32           106 ns          105 ns      6400000
std::generate(deque<int>)/50           139 ns          138 ns      4977778
std::generate(deque<int>)/1024        2713 ns         2699 ns       248889
std::generate(deque<int>)/8192       18983 ns        19252 ns        37333
```

---------

Co-authored-by: A. Jiang <de34@live.cn>
 [libc++] Optimize std::{,ranges}::{fill,fill_n} for segmented iterators (#132665) 2025-10-16T23:41:24+00:00 Peng Liu winner245@hotmail.com 2025-10-16T23:41:24+00:00 d0cee6939a1a889b14dcfc0bb049f38063c81f9b This patch optimizes `std::fill`, `std::fill_n`, `std::ranges::fill`, and `std::ranges::fill_n` for segmented iterators, achieving substantial performance improvements. Specifically, for `deque<int>` iterators, the performance improvements are above 10x for all these algorithms. The optimization also enables filling segmented memory of `deque<int>` to approach the performance of filling contiguous memory of `vector<int>`. Benchmark results comparing the before and after implementations are provided below. For additional context, we’ve included `vector<int>` results, which remain unchanged, as this patch specifically targets segmented iterators and leaves non-segmented iterator behavior untouched. Fixes two subtasks outlined in #102817. #### `fill_n` ``` ----------------------------------------------------------------------------- Benchmark Before After Speedup ----------------------------------------------------------------------------- std::fill_n(deque<int>)/32 11.4 ns 2.28 ns 5.0x std::fill_n(deque<int>)/50 19.7 ns 3.40 ns 5.8x std::fill_n(deque<int>)/1024 391 ns 37.3 ns 10.5x std::fill_n(deque<int>)/8192 3174 ns 301 ns 10.5x std::fill_n(deque<int>)/65536 26504 ns 2951 ns 9.0x std::fill_n(deque<int>)/1048576 407960 ns 80658 ns 5.1x rng::fill_n(deque<int>)/32 14.3 ns 2.15 ns 6.6x rng::fill_n(deque<int>)/50 20.2 ns 3.22 ns 6.3x rng::fill_n(deque<int>)/1024 381 ns 37.8 ns 10.1x rng::fill_n(deque<int>)/8192 3101 ns 294 ns 10.5x rng::fill_n(deque<int>)/65536 25098 ns 2926 ns 8.6x rng::fill_n(deque<int>)/1048576 394342 ns 78874 ns 5.0x std::fill_n(vector<int>)/32 1.76 ns 1.72 ns 1.0x std::fill_n(vector<int>)/50 3.00 ns 2.73 ns 1.1x std::fill_n(vector<int>)/1024 38.4 ns 37.9 ns 1.0x std::fill_n(vector<int>)/8192 258 ns 252 ns 1.0x std::fill_n(vector<int>)/65536 2993 ns 2889 ns 1.0x std::fill_n(vector<int>)/1048576 80328 ns 80468 ns 1.0x rng::fill_n(vector<int>)/32 1.99 ns 1.35 ns 1.5x rng::fill_n(vector<int>)/50 2.66 ns 2.12 ns 1.3x rng::fill_n(vector<int>)/1024 37.7 ns 35.8 ns 1.1x rng::fill_n(vector<int>)/8192 253 ns 250 ns 1.0x rng::fill_n(vector<int>)/65536 2922 ns 2930 ns 1.0x rng::fill_n(vector<int>)/1048576 79739 ns 79742 ns 1.0x ``` #### `fill` ``` -------------------------------------------------------------------------- Benchmark Before After Speedup -------------------------------------------------------------------------- std::fill(deque<int>)/32 13.7 ns 2.45 ns 5.6x std::fill(deque<int>)/50 21.7 ns 4.57 ns 4.7x std::fill(deque<int>)/1024 367 ns 38.5 ns 9.5x std::fill(deque<int>)/8192 2896 ns 247 ns 11.7x std::fill(deque<int>)/65536 23723 ns 2907 ns 8.2x std::fill(deque<int>)/1048576 379043 ns 79885 ns 4.7x rng::fill(deque<int>)/32 13.6 ns 2.70 ns 5.0x rng::fill(deque<int>)/50 23.4 ns 3.94 ns 5.9x rng::fill(deque<int>)/1024 377 ns 37.9 ns 9.9x rng::fill(deque<int>)/8192 2914 ns 286 ns 10.2x rng::fill(deque<int>)/65536 23612 ns 2939 ns 8.0x rng::fill(deque<int>)/1048576 379841 ns 80079 ns 4.7x std::fill(vector<int>)/32 1.99 ns 1.79 ns 1.1x std::fill(vector<int>)/50 3.05 ns 3.06 ns 1.0x std::fill(vector<int>)/1024 37.6 ns 38.0 ns 1.0x std::fill(vector<int>)/8192 255 ns 257 ns 1.0x std::fill(vector<int>)/65536 2966 ns 2981 ns 1.0x std::fill(vector<int>)/1048576 78300 ns 80348 ns 1.0x rng::fill(vector<int>)/32 1.77 ns 1.75 ns 1.0x rng::fill(vector<int>)/50 4.85 ns 2.31 ns 2.1x rng::fill(vector<int>)/1024 39.6 ns 36.1 ns 1.1x rng::fill(vector<int>)/8192 238 ns 251 ns 0.9x rng::fill(vector<int>)/65536 2941 ns 2918 ns 1.0x rng::fill(vector<int>)/1048576 80497 ns 80442 ns 1.0x ``` --------- Co-authored-by: Louis Dionne <ldionne.2@gmail.com> Co-authored-by: A. Jiang <de34@live.cn> 
This patch optimizes `std::fill`, `std::fill_n`, `std::ranges::fill`,
and `std::ranges::fill_n` for segmented iterators, achieving substantial
performance improvements. Specifically, for `deque<int>` iterators, the
performance improvements are above 10x for all these algorithms. The
optimization also enables filling segmented memory of `deque<int>` to
approach the performance of filling contiguous memory of `vector<int>`.


Benchmark results comparing the before and after implementations are
provided below. For additional context, we’ve included `vector<int>`
results, which remain unchanged, as this patch specifically targets
segmented iterators and leaves non-segmented iterator behavior
untouched.



Fixes two subtasks outlined in #102817.

#### `fill_n`

```
-----------------------------------------------------------------------------
Benchmark                                Before            After      Speedup
-----------------------------------------------------------------------------
std::fill_n(deque<int>)/32              11.4 ns          2.28 ns        5.0x
std::fill_n(deque<int>)/50              19.7 ns          3.40 ns        5.8x
std::fill_n(deque<int>)/1024             391 ns          37.3 ns       10.5x
std::fill_n(deque<int>)/8192            3174 ns           301 ns       10.5x
std::fill_n(deque<int>)/65536          26504 ns          2951 ns        9.0x
std::fill_n(deque<int>)/1048576       407960 ns         80658 ns        5.1x
rng::fill_n(deque<int>)/32              14.3 ns          2.15 ns        6.6x
rng::fill_n(deque<int>)/50              20.2 ns          3.22 ns        6.3x
rng::fill_n(deque<int>)/1024             381 ns          37.8 ns       10.1x
rng::fill_n(deque<int>)/8192            3101 ns           294 ns       10.5x
rng::fill_n(deque<int>)/65536          25098 ns          2926 ns        8.6x
rng::fill_n(deque<int>)/1048576       394342 ns         78874 ns        5.0x
std::fill_n(vector<int>)/32             1.76 ns          1.72 ns        1.0x
std::fill_n(vector<int>)/50             3.00 ns          2.73 ns        1.1x
std::fill_n(vector<int>)/1024           38.4 ns          37.9 ns        1.0x
std::fill_n(vector<int>)/8192            258 ns           252 ns        1.0x
std::fill_n(vector<int>)/65536          2993 ns          2889 ns        1.0x
std::fill_n(vector<int>)/1048576       80328 ns         80468 ns        1.0x
rng::fill_n(vector<int>)/32             1.99 ns          1.35 ns        1.5x
rng::fill_n(vector<int>)/50             2.66 ns          2.12 ns        1.3x
rng::fill_n(vector<int>)/1024           37.7 ns          35.8 ns        1.1x
rng::fill_n(vector<int>)/8192            253 ns           250 ns        1.0x
rng::fill_n(vector<int>)/65536          2922 ns          2930 ns        1.0x
rng::fill_n(vector<int>)/1048576       79739 ns         79742 ns        1.0x
```

#### `fill`

```
--------------------------------------------------------------------------
Benchmark                              Before            After     Speedup
--------------------------------------------------------------------------
std::fill(deque<int>)/32              13.7 ns          2.45 ns        5.6x
std::fill(deque<int>)/50              21.7 ns          4.57 ns        4.7x
std::fill(deque<int>)/1024             367 ns          38.5 ns        9.5x
std::fill(deque<int>)/8192            2896 ns           247 ns       11.7x
std::fill(deque<int>)/65536          23723 ns          2907 ns        8.2x
std::fill(deque<int>)/1048576       379043 ns         79885 ns        4.7x
rng::fill(deque<int>)/32              13.6 ns          2.70 ns        5.0x
rng::fill(deque<int>)/50              23.4 ns          3.94 ns        5.9x
rng::fill(deque<int>)/1024             377 ns          37.9 ns        9.9x
rng::fill(deque<int>)/8192            2914 ns           286 ns       10.2x
rng::fill(deque<int>)/65536          23612 ns          2939 ns        8.0x
rng::fill(deque<int>)/1048576       379841 ns         80079 ns        4.7x
std::fill(vector<int>)/32             1.99 ns          1.79 ns        1.1x
std::fill(vector<int>)/50             3.05 ns          3.06 ns        1.0x
std::fill(vector<int>)/1024           37.6 ns          38.0 ns        1.0x
std::fill(vector<int>)/8192            255 ns           257 ns        1.0x
std::fill(vector<int>)/65536          2966 ns          2981 ns        1.0x
std::fill(vector<int>)/1048576       78300 ns         80348 ns        1.0x
rng::fill(vector<int>)/32             1.77 ns          1.75 ns        1.0x
rng::fill(vector<int>)/50             4.85 ns          2.31 ns        2.1x
rng::fill(vector<int>)/1024           39.6 ns          36.1 ns        1.1x
rng::fill(vector<int>)/8192            238 ns           251 ns        0.9x
rng::fill(vector<int>)/65536          2941 ns          2918 ns        1.0x
rng::fill(vector<int>)/1048576       80497 ns         80442 ns        1.0x
```

---------

Co-authored-by: Louis Dionne <ldionne.2@gmail.com>
Co-authored-by: A. Jiang <de34@live.cn>
 [libc++] Avoid transitive inclusion for `<__algorithm/find.h>` (#162508) 2025-10-09T09:57:59+00:00 A. Jiang de34@live.cn 2025-10-09T09:57:59+00:00 d6d5026b5107b940d7a7853ab16480f83c14384d Currently, `size_t` and `__libcpp_is_constant_evaluated` are obtained by transitive inclusion in `<__algorithm/find.h>` when `<cwchar>` is not included. This broke module build when `_LIBCPP_HAS_WIDE_CHARACTERS` is `1` and caused CI failure. We should explicitly include the corresponding internal headers. 
Currently, `size_t` and `__libcpp_is_constant_evaluated` are obtained by
transitive inclusion in `<__algorithm/find.h>` when `<cwchar>` is not
included. This broke module build when `_LIBCPP_HAS_WIDE_CHARACTERS` is
`1` and caused CI failure. We should explicitly include the
corresponding internal headers.
 [libc++] Make the naming of the iterator_traits aliases consistent (#161661) 2025-10-07T12:42:11+00:00 Nikolas Klauser nikolasklauser@berlin.de 2025-10-07T12:42:11+00:00 70b7874ab2e11a92b550397944d1f2b05e01398b This renames all the `iterator_traits` alises to be `__iterator_<type-name>`. e.g `iterator_traits<T>::value_type` will be `__iterator_value_type<T>`. 
This renames all the `iterator_traits` alises to be
`__iterator_<type-name>`. e.g `iterator_traits<T>::value_type` will be
`__iterator_value_type<T>`.
 Reapply "[libc++] Avoid constructing additional objects when using map::at" (#160738) (#161485) 2025-10-02T09:15:33+00:00 Nikolas Klauser nikolasklauser@berlin.de 2025-10-02T09:15:33+00:00 55803b8af1e4ddde1c0c43a9cd283133205c295d This reverts commit b86aaacf28b358b187071bc87075f1faa2d65c4e. The issue in LLVM has been fixed now. 
This reverts commit b86aaacf28b358b187071bc87075f1faa2d65c4e.

The issue in LLVM has been fixed now.
 [libc++] Fix <__algorithm/find.h> when using -flax-vector-conversions=none (#161362) 2025-10-02T08:05:26+00:00 Nikolas Klauser nikolasklauser@berlin.de 2025-10-02T08:05:26+00:00 66558d70dc11fd04ce908ac94424ed7c6bd9e35b