llvm-project.git/libcxx/include/set, branch main

[libc++] Optimize __tree copy/move constructor/assignment with allocator (#163558)

2025-11-12T14:53:37+00:00

This patch applies the same optimization as implemented in #151304 to
the overloads taking an allocator as the second argument.

Apple M4:
```
Benchmark                                                               old             new    Difference    % Difference
-----------------------------------------------------------  --------------  --------------  ------------  --------------
std::map::ctor(&&,_different_allocs)/0                      14.59           12.78         -1.81         -12.41%
std::map::ctor(&&,_different_allocs)/1024                16407.05         6265.11     -10141.94         -61.81%
std::map::ctor(&&,_different_allocs)/32                    395.99          199.76       -196.23         -49.56%
std::map::ctor(&&,_different_allocs)/8192               141478.67        53767.84     -87710.83         -62.00%
std::map::ctor(const&,_alloc)/0                             12.83           12.71         -0.12          -0.94%
std::map::ctor(const&,_alloc)/1024                        9979.71         7849.11      -2130.59         -21.35%
std::map::ctor(const&,_alloc)/32                           283.82          266.05        -17.77          -6.26%
std::map::ctor(const&,_alloc)/8192                       81418.63        63190.41     -18228.21         -22.39%
std::map::ctor(&&,_different_allocs)/0              14.58           12.68         -1.90         -13.00%
std::map::ctor(&&,_different_allocs)/1024        19513.56         7806.04     -11707.52         -60.00%
std::map::ctor(&&,_different_allocs)/32            477.80          247.28       -230.52         -48.25%
std::map::ctor(&&,_different_allocs)/8192       504558.78        69592.21    -434966.56         -86.21%
std::map::ctor(const&,_alloc)/0                     12.64           12.60         -0.04          -0.33%
std::map::ctor(const&,_alloc)/1024               43198.53        37220.54      -5977.99         -13.84%
std::map::ctor(const&,_alloc)/32                   928.39          867.03        -61.36          -6.61%
std::map::ctor(const&,_alloc)/8192              461313.81       389200.82     -72112.99         -15.63%
```

[libc++] Remove a few unused includes (#165687)

2025-11-02T09:27:56+00:00

[libc++] Optimize {set,map}::{lower,upper}_bound (#161366)

2025-10-09T06:45:03+00:00

Apple M4:
```
Benchmark                                                                                        Baseline    Candidate    Difference    % Difference
---------------------------------------------------------------------------------------------  ----------  -----------  ------------  --------------
std::map::lower_bound(key)_(existent)/0                                                    0.01         0.01         -0.00          -25.78
std::map::lower_bound(key)_(existent)/1024                                                 7.94         4.28         -3.66          -46.09
std::map::lower_bound(key)_(existent)/32                                                   2.73         1.69         -1.03          -37.89
std::map::lower_bound(key)_(existent)/8192                                                11.63         5.52         -6.11          -52.55
std::map::lower_bound(key)_(non-existent)/0                                                0.28         0.28         -0.00           -1.35
std::map::lower_bound(key)_(non-existent)/1024                                            17.21         7.63         -9.58          -55.67
std::map::lower_bound(key)_(non-existent)/32                                               4.71         3.26         -1.45          -30.71
std::map::lower_bound(key)_(non-existent)/8192                                            26.82        10.58        -16.24          -60.55
std::map::upper_bound(key)_(existent)/0                                                    0.01         0.01          0.00           20.62
std::map::upper_bound(key)_(existent)/1024                                                 7.93         3.61         -4.32          -54.49
std::map::upper_bound(key)_(existent)/32                                                   2.83         1.98         -0.85          -30.01
std::map::upper_bound(key)_(existent)/8192                                                11.69         5.72         -5.97          -51.06
std::map::upper_bound(key)_(non-existent)/0                                                0.28         0.28         -0.00           -1.36
std::map::upper_bound(key)_(non-existent)/1024                                            17.21         8.00         -9.21          -53.53
std::map::upper_bound(key)_(non-existent)/32                                               4.70         2.93         -1.78          -37.76
std::map::upper_bound(key)_(non-existent)/8192                                            26.54        11.18        -15.36          -57.89
std::map::lower_bound(key)_(existent)/0                                            0.04         0.04         -0.00           -3.26
std::map::lower_bound(key)_(existent)/1024                                        27.46        26.25         -1.22           -4.43
std::map::lower_bound(key)_(existent)/32                                          19.17        15.71         -3.46          -18.07
std::map::lower_bound(key)_(existent)/8192                                        35.33        35.03         -0.30           -0.84
std::map::lower_bound(key)_(non-existent)/0                                        0.27         0.27         -0.00           -1.45
std::map::lower_bound(key)_(non-existent)/1024                                    24.88        24.17         -0.70           -2.83
std::map::lower_bound(key)_(non-existent)/32                                      11.67        11.63         -0.04           -0.32
std::map::lower_bound(key)_(non-existent)/8192                                    31.81        32.33          0.52            1.64
std::map::upper_bound(key)_(existent)/0                                            0.04         0.04         -0.00           -2.22
std::map::upper_bound(key)_(existent)/1024                                        29.91        26.51         -3.40          -11.38
std::map::upper_bound(key)_(existent)/32                                          19.69        17.74         -1.95           -9.92
std::map::upper_bound(key)_(existent)/8192                                        32.55        35.24          2.69            8.25
std::map::upper_bound(key)_(non-existent)/0                                        0.27         0.27         -0.00           -1.74
std::map::upper_bound(key)_(non-existent)/1024                                    23.87        26.77          2.91           12.18
std::map::upper_bound(key)_(non-existent)/32                                      11.44        11.81          0.37            3.24
std::map::upper_bound(key)_(non-existent)/8192                                    33.02        32.59         -0.43           -1.29
std::set::lower_bound(key)_(existent)/0                                                         0.01         0.01          0.00            0.48
std::set::lower_bound(key)_(existent)/1024                                                      7.83         4.21         -3.62          -46.23
std::set::lower_bound(key)_(existent)/32                                                        2.74         1.68         -1.06          -38.81
std::set::lower_bound(key)_(existent)/8192                                                     22.75        11.12        -11.63          -51.12
std::set::lower_bound(key)_(non-existent)/0                                                     0.28         0.27         -0.01           -3.52
std::set::lower_bound(key)_(non-existent)/1024                                                 17.15         8.40         -8.75          -51.03
std::set::lower_bound(key)_(non-existent)/32                                                    4.63         2.50         -2.13          -46.03
std::set::lower_bound(key)_(non-existent)/8192                                                 28.88        11.05        -17.82          -61.72
std::set::upper_bound(key)_(existent)/0                                                         0.01         0.01         -0.00           -7.79
std::set::upper_bound(key)_(existent)/1024                                                      7.80         3.63         -4.16          -53.42
std::set::upper_bound(key)_(existent)/32                                                        2.81         1.90         -0.91          -32.44
std::set::upper_bound(key)_(existent)/8192                                                     21.93        11.35        -10.58          -48.26
std::set::upper_bound(key)_(non-existent)/0                                                     0.28         0.27         -0.01           -3.81
std::set::upper_bound(key)_(non-existent)/1024                                                 16.76         7.38         -9.38          -55.98
std::set::upper_bound(key)_(non-existent)/32                                                    4.58         3.10         -1.48          -32.31
std::set::upper_bound(key)_(non-existent)/8192                                                 26.95        10.70        -16.25          -60.29
std::set::lower_bound(key)_(existent)/0                                                 0.04         0.04          0.00            0.02
std::set::lower_bound(key)_(existent)/1024                                             28.08        27.04         -1.04           -3.71
std::set::lower_bound(key)_(existent)/32                                               17.53        16.94         -0.58           -3.34
std::set::lower_bound(key)_(existent)/8192                                             32.79        33.28          0.49            1.49
std::set::lower_bound(key)_(non-existent)/0                                             0.28         0.28         -0.00           -0.06
std::set::lower_bound(key)_(non-existent)/1024                                         25.23        24.38         -0.85           -3.38
std::set::lower_bound(key)_(non-existent)/32                                           11.45        11.68          0.24            2.07
std::set::lower_bound(key)_(non-existent)/8192                                         32.30        36.80          4.50           13.95
std::set::upper_bound(key)_(existent)/0                                                 0.04         0.04         -0.00           -0.14
std::set::upper_bound(key)_(existent)/1024                                             26.71        26.37         -0.34           -1.27
std::set::upper_bound(key)_(existent)/32                                               20.07        19.06         -1.02           -5.06
std::set::upper_bound(key)_(existent)/8192                                             36.69        35.50         -1.19           -3.25
std::set::upper_bound(key)_(non-existent)/0                                             0.28         0.28         -0.00           -0.16
std::set::upper_bound(key)_(non-existent)/1024                                         24.48        24.90          0.42            1.73
std::set::upper_bound(key)_(non-existent)/32                                           11.68        11.77          0.09            0.77
std::set::upper_bound(key)_(non-existent)/8192                                         33.16        34.12          0.96            2.89
```

[libc++] Make the naming of the iterator_traits aliases consistent (#161661)

2025-10-07T12:42:11+00:00

This renames all the `iterator_traits` alises to be
`__iterator_`. e.g `iterator_traits::value_type` will be
`__iterator_value_type`.

[libc++][NFC] Refactor __is_allocator to be a variable template (#159584)

2025-09-24T08:41:29+00:00

[libc++][NFC] Reformat some deduction guides (#160085)

2025-09-22T13:23:20+00:00

They're not formatted correctly anymore, since clang-format was updated.

[libc++] Optimize {map,set}::insert(InputIterator, InputIterator) (#154703)

2025-09-03T06:15:29+00:00

```
----------------------------------------------------------------------------------------------------------------------------
Benchmark                                                                                                old             new
----------------------------------------------------------------------------------------------------------------------------
std::map::ctor(iterator, iterator) (unsorted sequence)/0                                   14.2 ns         14.8 ns
std::map::ctor(iterator, iterator) (unsorted sequence)/32                                   519 ns          404 ns
std::map::ctor(iterator, iterator) (unsorted sequence)/1024                               52460 ns        36242 ns
std::map::ctor(iterator, iterator) (unsorted sequence)/8192                              724222 ns       706496 ns
std::map::ctor(iterator, iterator) (sorted sequence)/0                                     14.2 ns         14.7 ns
std::map::ctor(iterator, iterator) (sorted sequence)/32                                     429 ns          349 ns
std::map::ctor(iterator, iterator) (sorted sequence)/1024                                 23601 ns        14734 ns
std::map::ctor(iterator, iterator) (sorted sequence)/8192                                267753 ns       112155 ns
std::map::insert(iterator, iterator) (all new keys)/0                                       434 ns          448 ns
std::map::insert(iterator, iterator) (all new keys)/32                                      950 ns          963 ns
std::map::insert(iterator, iterator) (all new keys)/1024                                  27205 ns        25344 ns
std::map::insert(iterator, iterator) (all new keys)/8192                                 294248 ns       280713 ns
std::map::insert(iterator, iterator) (half new keys)/0                                      435 ns          449 ns
std::map::insert(iterator, iterator) (half new keys)/32                                     771 ns          706 ns
std::map::insert(iterator, iterator) (half new keys)/1024                                 30841 ns        17495 ns
std::map::insert(iterator, iterator) (half new keys)/8192                                468807 ns       285847 ns
std::map::insert(iterator, iterator) (product_iterator from same type)/0                    449 ns          453 ns
std::map::insert(iterator, iterator) (product_iterator from same type)/32                  1021 ns          932 ns
std::map::insert(iterator, iterator) (product_iterator from same type)/1024               29796 ns        19518 ns
std::map::insert(iterator, iterator) (product_iterator from same type)/8192              345688 ns       153966 ns
std::map::insert(iterator, iterator) (product_iterator from zip_view)/0                     449 ns          450 ns
std::map::insert(iterator, iterator) (product_iterator from zip_view)/32                   1026 ns          807 ns
std::map::insert(iterator, iterator) (product_iterator from zip_view)/1024                31632 ns        15573 ns
std::map::insert(iterator, iterator) (product_iterator from zip_view)/8192               303024 ns       128946 ns
std::map::erase(iterator, iterator) (erase half the container)/0                            447 ns          452 ns
std::map::erase(iterator, iterator) (erase half the container)/32                           687 ns          710 ns
std::map::erase(iterator, iterator) (erase half the container)/1024                        8604 ns         8581 ns
std::map::erase(iterator, iterator) (erase half the container)/8192                       65693 ns        67406 ns
std::map::ctor(iterator, iterator) (unsorted sequence)/0                           15.0 ns         15.0 ns
std::map::ctor(iterator, iterator) (unsorted sequence)/32                          2781 ns         1845 ns
std::map::ctor(iterator, iterator) (unsorted sequence)/1024                      187999 ns       182103 ns
std::map::ctor(iterator, iterator) (unsorted sequence)/8192                     2937242 ns      2934912 ns
std::map::ctor(iterator, iterator) (sorted sequence)/0                             15.0 ns         15.2 ns
std::map::ctor(iterator, iterator) (sorted sequence)/32                            1326 ns         2462 ns
std::map::ctor(iterator, iterator) (sorted sequence)/1024                         81778 ns        72193 ns
std::map::ctor(iterator, iterator) (sorted sequence)/8192                       1177292 ns       669152 ns
std::map::insert(iterator, iterator) (all new keys)/0                               439 ns          454 ns
std::map::insert(iterator, iterator) (all new keys)/32                             2483 ns         2465 ns
std::map::insert(iterator, iterator) (all new keys)/1024                         187614 ns       188072 ns
std::map::insert(iterator, iterator) (all new keys)/8192                        1654675 ns      1706603 ns
std::map::insert(iterator, iterator) (half new keys)/0                              437 ns          452 ns
std::map::insert(iterator, iterator) (half new keys)/32                            1836 ns         1820 ns
std::map::insert(iterator, iterator) (half new keys)/1024                        114885 ns       121865 ns
std::map::insert(iterator, iterator) (half new keys)/8192                       1151960 ns      1197318 ns
std::map::insert(iterator, iterator) (product_iterator from same type)/0            438 ns          455 ns
std::map::insert(iterator, iterator) (product_iterator from same type)/32          1599 ns         1614 ns
std::map::insert(iterator, iterator) (product_iterator from same type)/1024       95935 ns        82159 ns
std::map::insert(iterator, iterator) (product_iterator from same type)/8192      776480 ns       941043 ns
std::map::insert(iterator, iterator) (product_iterator from zip_view)/0             435 ns          462 ns
std::map::insert(iterator, iterator) (product_iterator from zip_view)/32           1723 ns         1550 ns
std::map::insert(iterator, iterator) (product_iterator from zip_view)/1024       107096 ns        92850 ns
std::map::insert(iterator, iterator) (product_iterator from zip_view)/8192       893976 ns       775046 ns
std::map::erase(iterator, iterator) (erase half the container)/0                    436 ns          453 ns
std::map::erase(iterator, iterator) (erase half the container)/32                   775 ns          824 ns
std::map::erase(iterator, iterator) (erase half the container)/1024               20241 ns        20454 ns
std::map::erase(iterator, iterator) (erase half the container)/8192              139038 ns       138032 ns
std::set::ctor(iterator, iterator) (unsorted sequence)/0                                        14.8 ns         14.7 ns
std::set::ctor(iterator, iterator) (unsorted sequence)/32                                        468 ns          426 ns
std::set::ctor(iterator, iterator) (unsorted sequence)/1024                                    54289 ns        39028 ns
std::set::ctor(iterator, iterator) (unsorted sequence)/8192                                   738438 ns       695720 ns
std::set::ctor(iterator, iterator) (sorted sequence)/0                                          14.7 ns         14.6 ns
std::set::ctor(iterator, iterator) (sorted sequence)/32                                          478 ns          391 ns
std::set::ctor(iterator, iterator) (sorted sequence)/1024                                      24017 ns        13905 ns
std::set::ctor(iterator, iterator) (sorted sequence)/8192                                     267862 ns       111378 ns
std::set::insert(iterator, iterator) (all new keys)/0                                            458 ns          450 ns
std::set::insert(iterator, iterator) (all new keys)/32                                          1066 ns          956 ns
std::set::insert(iterator, iterator) (all new keys)/1024                                       29190 ns        25212 ns
std::set::insert(iterator, iterator) (all new keys)/8192                                      320441 ns       279602 ns
std::set::insert(iterator, iterator) (half new keys)/0                                           454 ns          453 ns
std::set::insert(iterator, iterator) (half new keys)/32                                          816 ns          709 ns
std::set::insert(iterator, iterator) (half new keys)/1024                                      32072 ns        17074 ns
std::set::insert(iterator, iterator) (half new keys)/8192                                     403386 ns       286202 ns
std::set::erase(iterator, iterator) (erase half the container)/0                                 451 ns          452 ns
std::set::erase(iterator, iterator) (erase half the container)/32                                710 ns          703 ns
std::set::erase(iterator, iterator) (erase half the container)/1024                             8261 ns         8499 ns
std::set::erase(iterator, iterator) (erase half the container)/8192                            64466 ns        67343 ns
std::set::ctor(iterator, iterator) (unsorted sequence)/0                                15.2 ns         15.0 ns
std::set::ctor(iterator, iterator) (unsorted sequence)/32                               3069 ns         3005 ns
std::set::ctor(iterator, iterator) (unsorted sequence)/1024                           189552 ns       180933 ns
std::set::ctor(iterator, iterator) (unsorted sequence)/8192                          2887579 ns      2691678 ns
std::set::ctor(iterator, iterator) (sorted sequence)/0                                  15.1 ns         14.9 ns
std::set::ctor(iterator, iterator) (sorted sequence)/32                                 2611 ns         2514 ns
std::set::ctor(iterator, iterator) (sorted sequence)/1024                              91581 ns        78727 ns
std::set::ctor(iterator, iterator) (sorted sequence)/8192                            1192640 ns      1158959 ns
std::set::insert(iterator, iterator) (all new keys)/0                                    452 ns          457 ns
std::set::insert(iterator, iterator) (all new keys)/32                                  2530 ns         2544 ns
std::set::insert(iterator, iterator) (all new keys)/1024                              195352 ns       179614 ns
std::set::insert(iterator, iterator) (all new keys)/8192                             1737890 ns      1749615 ns
std::set::insert(iterator, iterator) (half new keys)/0                                   451 ns          454 ns
std::set::insert(iterator, iterator) (half new keys)/32                                 1949 ns         1766 ns
std::set::insert(iterator, iterator) (half new keys)/1024                             128853 ns       109467 ns
std::set::insert(iterator, iterator) (half new keys)/8192                            1233077 ns      1177289 ns
std::set::erase(iterator, iterator) (erase half the container)/0                         450 ns          451 ns
std::set::erase(iterator, iterator) (erase half the container)/32                        809 ns          812 ns
std::set::erase(iterator, iterator) (erase half the container)/1024                    21736 ns        21922 ns
std::set::erase(iterator, iterator) (erase half the container)/8192                   135884 ns       133228 ns
```

Fixes #154650

Reapply "[libc++] Refactor key extraction for __hash_table and __tree (#154512)" (#155565)

2025-08-27T12:38:14+00:00

The original PR has been reverted because of an LLDB test failure. This
patch now works around the test failure by simply allowing the new
symbols to show up in a stack trace.

This reverts commit 72c04bb882ad70230bce309c3013d9cc2c99e9a7.

Original commit message:

This patch replaces `__can_extract_key` with an overload set to try to
extract the key. This simplifies the code, since we don't need to have
separate overload sets for the unordered and associative containers. It
also allows extending the set of extraction cases more easily, since we
have a single place to define how the key is extracted.

Revert "[libc++] Refactor key extraction for __hash_table and __tree (#154512)"

2025-08-26T16:13:56+00:00

This reverts commit af1f06e41b05c267480f1629dc0fcdf18f3b59f6.

This is causing some build failures in premerge as some of the LLDB
tests fail.

[libc++] Refactor key extraction for __hash_table and __tree (#154512)

2025-08-26T14:26:59+00:00

This patch replaces `__can_extract_key` with an overload set to try to
extract the key. This simplifies the code, since we don't need to have
separate overload sets for the unordered and associative containers. It
also allows extending the set of extraction cases more easily, since we
have a single place to define how the key is extracted.