llvm-project.git/libcxx/include/module.modulemap.in, branch users/mingmingl-llvm/samplefdo-profile-format

[libc++] Optimize most of the __tree search algorithms (#155245)

2025-09-08T07:56:14+00:00

This patch introduces a new comparator, namely `__lazy_synth_three_way`,
which tries to provide an efficient three way comparator for known types
and falls back to using the provided comparator if it doesn't know how
to do that. Currently, an efficient three way comparison is only
provided when using one of the `less` comparions object from the
standard library and `std::string`. This will be extended in future
patches.

```
------------------------------------------------------------------------------------------------------------------------------
Benchmark                                                                                                  old             new
------------------------------------------------------------------------------------------------------------------------------
std::map::ctor(const&)/0                                                             12.6 ns         12.6 ns
std::map::ctor(const&)/32                                                             858 ns          837 ns
std::map::ctor(const&)/1024                                                         46700 ns        46739 ns
std::map::ctor(const&)/8192                                                        458100 ns       449806 ns
std::map::ctor(iterator, iterator) (unsorted sequence)/0                             12.8 ns         12.7 ns
std::map::ctor(iterator, iterator) (unsorted sequence)/32                            1286 ns         1266 ns
std::map::ctor(iterator, iterator) (unsorted sequence)/1024                         93812 ns        84686 ns
std::map::ctor(iterator, iterator) (unsorted sequence)/8192                       1480346 ns      1385924 ns
std::map::ctor(iterator, iterator) (sorted sequence)/0                               12.9 ns         12.8 ns
std::map::ctor(iterator, iterator) (sorted sequence)/32                              1044 ns         1055 ns
std::map::ctor(iterator, iterator) (sorted sequence)/1024                           63071 ns        62861 ns
std::map::ctor(iterator, iterator) (sorted sequence)/8192                          595046 ns       590223 ns
std::map::operator=(const&) (into cleared Container)/0                               13.6 ns         13.6 ns
std::map::operator=(const&) (into cleared Container)/32                               880 ns          911 ns
std::map::operator=(const&) (into cleared Container)/1024                           48627 ns        47808 ns
std::map::operator=(const&) (into cleared Container)/8192                          458552 ns       454497 ns
std::map::operator=(const&) (into partially populated Container)/0                   13.8 ns         13.6 ns
std::map::operator=(const&) (into partially populated Container)/32                   864 ns          851 ns
std::map::operator=(const&) (into partially populated Container)/1024               49483 ns        49555 ns
std::map::operator=(const&) (into partially populated Container)/8192              456977 ns       457894 ns
std::map::operator=(const&) (into populated Container)/0                             1.31 ns         1.31 ns
std::map::operator=(const&) (into populated Container)/32                             425 ns          415 ns
std::map::operator=(const&) (into populated Container)/1024                         14248 ns        14225 ns
std::map::operator=(const&) (into populated Container)/8192                        136684 ns       133696 ns
std::map::insert(value) (already present)/0                                          21.5 ns         16.2 ns
std::map::insert(value) (already present)/32                                         22.7 ns         25.1 ns
std::map::insert(value) (already present)/1024                                       54.5 ns         29.1 ns
std::map::insert(value) (already present)/8192                                       78.4 ns         30.4 ns
std::map::insert(value) (new value)/0                                                40.9 ns         39.0 ns
std::map::insert(value) (new value)/32                                               58.3 ns         47.2 ns
std::map::insert(value) (new value)/1024                                              120 ns         71.3 ns
std::map::insert(value) (new value)/8192                                              157 ns          129 ns
std::map::insert(hint, value) (good hint)/0                                          40.3 ns         40.7 ns
std::map::insert(hint, value) (good hint)/32                                         48.0 ns         30.0 ns
std::map::insert(hint, value) (good hint)/1024                                        107 ns         63.2 ns
std::map::insert(hint, value) (good hint)/8192                                        132 ns          107 ns
std::map::insert(hint, value) (bad hint)/0                                           27.0 ns         40.9 ns
std::map::insert(hint, value) (bad hint)/32                                          68.3 ns         58.4 ns
std::map::insert(hint, value) (bad hint)/1024                                         125 ns         82.0 ns
std::map::insert(hint, value) (bad hint)/8192                                         155 ns          150 ns
std::map::insert(iterator, iterator) (all new keys)/0                                 404 ns          405 ns
std::map::insert(iterator, iterator) (all new keys)/32                               2004 ns         1805 ns
std::map::insert(iterator, iterator) (all new keys)/1024                           102820 ns        76102 ns
std::map::insert(iterator, iterator) (all new keys)/8192                          1144590 ns       949266 ns
std::map::insert(iterator, iterator) (half new keys)/0                                408 ns          404 ns
std::map::insert(iterator, iterator) (half new keys)/32                              1592 ns         1377 ns
std::map::insert(iterator, iterator) (half new keys)/1024                           74847 ns        53921 ns
std::map::insert(iterator, iterator) (half new keys)/8192                          828505 ns       698716 ns
std::map::insert(iterator, iterator) (product_iterator from same type)/0              407 ns          407 ns
std::map::insert(iterator, iterator) (product_iterator from same type)/32            1584 ns         1557 ns
std::map::insert(iterator, iterator) (product_iterator from same type)/1024         47157 ns        47443 ns
std::map::insert(iterator, iterator) (product_iterator from same type)/8192        623887 ns       628385 ns
std::map::insert(iterator, iterator) (product_iterator from zip_view)/0               405 ns          403 ns
std::map::insert(iterator, iterator) (product_iterator from zip_view)/32             1478 ns         1510 ns
std::map::insert(iterator, iterator) (product_iterator from zip_view)/1024          47852 ns        47835 ns
std::map::insert(iterator, iterator) (product_iterator from zip_view)/8192         605311 ns       606951 ns
std::map::erase(key) (existent)/0                                                     129 ns         94.0 ns
std::map::erase(key) (existent)/32                                                    110 ns          106 ns
std::map::erase(key) (existent)/1024                                                  121 ns          128 ns
std::map::erase(key) (existent)/8192                                                  165 ns         66.9 ns
std::map::erase(key) (non-existent)/0                                               0.269 ns        0.257 ns
std::map::erase(key) (non-existent)/32                                               21.9 ns         11.3 ns
std::map::erase(key) (non-existent)/1024                                             53.5 ns         25.4 ns
std::map::erase(key) (non-existent)/8192                                             67.3 ns         31.9 ns
std::map::erase(iterator)/0                                                          46.3 ns         46.7 ns
std::map::erase(iterator)/32                                                         44.4 ns         41.8 ns
std::map::erase(iterator)/1024                                                       43.7 ns         46.4 ns
std::map::erase(iterator)/8192                                                       45.2 ns         44.1 ns
std::map::erase(iterator, iterator) (erase half the container)/0                      407 ns          407 ns
std::map::erase(iterator, iterator) (erase half the container)/32                     876 ns          906 ns
std::map::erase(iterator, iterator) (erase half the container)/1024                 20880 ns        20444 ns
std::map::erase(iterator, iterator) (erase half the container)/8192                252881 ns       241583 ns
std::map::clear()/0                                                                   407 ns          408 ns
std::map::clear()/32                                                                 1252 ns         1323 ns
std::map::clear()/1024                                                              38488 ns        38017 ns
std::map::clear()/8192                                                             416492 ns       428534 ns
std::map::find(key) (existent)/0                                                    0.008 ns        0.008 ns
std::map::find(key) (existent)/32                                                    33.9 ns         15.3 ns
std::map::find(key) (existent)/1024                                                  43.0 ns         25.5 ns
std::map::find(key) (existent)/8192                                                  44.6 ns         29.3 ns
std::map::find(key) (non-existent)/0                                                0.259 ns        0.257 ns
std::map::find(key) (non-existent)/32                                                22.6 ns         11.4 ns
std::map::find(key) (non-existent)/1024                                              48.6 ns         25.1 ns
std::map::find(key) (non-existent)/8192                                              64.1 ns         31.1 ns
std::map::count(key) (existent)/0                                                   0.008 ns        0.008 ns
std::map::count(key) (existent)/32                                                   32.2 ns         17.3 ns
std::map::count(key) (existent)/1024                                                 42.4 ns         25.3 ns
std::map::count(key) (existent)/8192                                                 44.4 ns         31.6 ns
std::map::count(key) (non-existent)/0                                               0.260 ns        0.259 ns
std::map::count(key) (non-existent)/32                                               22.9 ns         11.3 ns
std::map::count(key) (non-existent)/1024                                             49.8 ns         25.5 ns
std::map::count(key) (non-existent)/8192                                             66.3 ns         31.9 ns
std::map::contains(key) (existent)/0                                                0.008 ns        0.008 ns
std::map::contains(key) (existent)/32                                                31.4 ns         18.0 ns
std::map::contains(key) (existent)/1024                                              44.3 ns         26.5 ns
std::map::contains(key) (existent)/8192                                              47.4 ns         30.2 ns
std::map::contains(key) (non-existent)/0                                            0.452 ns        0.441 ns
std::map::contains(key) (non-existent)/32                                            23.1 ns         11.5 ns
std::map::contains(key) (non-existent)/1024                                          46.2 ns         26.3 ns
std::map::contains(key) (non-existent)/8192                                          63.4 ns         31.4 ns
std::map::lower_bound(key) (existent)/0                                             0.008 ns        0.008 ns
std::map::lower_bound(key) (existent)/32                                             17.2 ns         19.0 ns
std::map::lower_bound(key) (existent)/1024                                           27.1 ns         26.2 ns
std::map::lower_bound(key) (existent)/8192                                           34.0 ns         36.0 ns
std::map::lower_bound(key) (non-existent)/0                                         0.259 ns        0.257 ns
std::map::lower_bound(key) (non-existent)/32                                         11.6 ns         11.5 ns
std::map::lower_bound(key) (non-existent)/1024                                       24.8 ns         25.6 ns
std::map::lower_bound(key) (non-existent)/8192                                       31.7 ns         31.6 ns
std::map::upper_bound(key) (existent)/0                                             0.008 ns        0.008 ns
std::map::upper_bound(key) (existent)/32                                             18.8 ns         19.7 ns
std::map::upper_bound(key) (existent)/1024                                           25.3 ns         27.7 ns
std::map::upper_bound(key) (existent)/8192                                           30.2 ns         29.9 ns
std::map::upper_bound(key) (non-existent)/0                                         0.260 ns        0.259 ns
std::map::upper_bound(key) (non-existent)/32                                         11.3 ns         12.0 ns
std::map::upper_bound(key) (non-existent)/1024                                       25.6 ns         25.9 ns
std::map::upper_bound(key) (non-existent)/8192                                       33.1 ns         34.2 ns
std::map::equal_range(key) (existent)/0                                             0.008 ns        0.008 ns
std::map::equal_range(key) (existent)/32                                             33.5 ns         15.8 ns
std::map::equal_range(key) (existent)/1024                                           43.0 ns         25.1 ns
std::map::equal_range(key) (existent)/8192                                           54.1 ns         30.7 ns
std::map::equal_range(key) (non-existent)/0                                         0.265 ns        0.259 ns
std::map::equal_range(key) (non-existent)/32                                         22.1 ns         12.1 ns
std::map::equal_range(key) (non-existent)/1024                                       44.8 ns         24.4 ns
std::map::equal_range(key) (non-existent)/8192                                       62.2 ns         40.1 ns
```

Fixes #66577

[libc++][NFC] Use llvm.org/PR to link to bug reports (#156288)

2025-09-04T07:20:02+00:00

We've built up quite a few links directly to github within the code
base. We should instead use `llvm.org/PR` 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.

[libc++] Simplify further (#156351)

2025-09-02T06:42:39+00:00

This essentially inlines `__make_tuple_types` and simplifies the support
code. This significantly simplifies the implementation, since
`__make_tuple_types` has multiple features, but the different places
that use it only make use of a subset of the features. Inlining it
separates concerns better and leads to less code in total.

[libc++] Disable cv-qualified arithmetic hash specializations (#155786)

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

#140407 accidentally enabled `hash` for cv-qualified types. This patch
disables these specializations again.

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.

[libc++] Remove unnecessary friend declarations from <__tree> (#152133)

2025-08-07T07:18:31+00:00

Removing the unnecessary friend declarations from `<__tree>` also
removes the need for forward declaration headers for `map` and `set`,
which this patch also removes.

[libc++] Remove SFINAE on __tuple_impl constructors (#151654)

2025-08-05T07:48:46+00:00

The SFINAE isn't required, since the primary `tuple` class already does
the SFINAE checks. This removes a bit of code that was only used for
these constraints.

This also moves the `tuple_element` specialization for `tuple` to
`__fwd/tuple.h` to avoid a dependency on `__tuple/sfinae_helpers.h`
(which should be moved in a follow-up).

[libc++][format][NFC] Granularize `__fmt_pair_like` (#150583)

2025-07-29T08:40:06+00:00

`` needs `format_kind` and `range_format` since C++26, but it
shouldn't drag in too many other stuffs necessary for
`<__format/concepts.h>`.