| Age | Commit message (Collapse) | Author |
|---|
|
(#163558)
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<int,_int>::ctor(&&,_different_allocs)/0 14.59 12.78 -1.81 -12.41%
std::map<int,_int>::ctor(&&,_different_allocs)/1024 16407.05 6265.11 -10141.94 -61.81%
std::map<int,_int>::ctor(&&,_different_allocs)/32 395.99 199.76 -196.23 -49.56%
std::map<int,_int>::ctor(&&,_different_allocs)/8192 141478.67 53767.84 -87710.83 -62.00%
std::map<int,_int>::ctor(const&,_alloc)/0 12.83 12.71 -0.12 -0.94%
std::map<int,_int>::ctor(const&,_alloc)/1024 9979.71 7849.11 -2130.59 -21.35%
std::map<int,_int>::ctor(const&,_alloc)/32 283.82 266.05 -17.77 -6.26%
std::map<int,_int>::ctor(const&,_alloc)/8192 81418.63 63190.41 -18228.21 -22.39%
std::map<std::string,_int>::ctor(&&,_different_allocs)/0 14.58 12.68 -1.90 -13.00%
std::map<std::string,_int>::ctor(&&,_different_allocs)/1024 19513.56 7806.04 -11707.52 -60.00%
std::map<std::string,_int>::ctor(&&,_different_allocs)/32 477.80 247.28 -230.52 -48.25%
std::map<std::string,_int>::ctor(&&,_different_allocs)/8192 504558.78 69592.21 -434966.56 -86.21%
std::map<std::string,_int>::ctor(const&,_alloc)/0 12.64 12.60 -0.04 -0.33%
std::map<std::string,_int>::ctor(const&,_alloc)/1024 43198.53 37220.54 -5977.99 -13.84%
std::map<std::string,_int>::ctor(const&,_alloc)/32 928.39 867.03 -61.36 -6.61%
std::map<std::string,_int>::ctor(const&,_alloc)/8192 461313.81 389200.82 -72112.99 -15.63%
```
|
|
|
|
Apple M4:
```
Benchmark Baseline Candidate Difference % Difference
--------------------------------------------------------------------------------------------- ---------- ----------- ------------ --------------
std::map<int,_int>::lower_bound(key)_(existent)/0 0.01 0.01 -0.00 -25.78
std::map<int,_int>::lower_bound(key)_(existent)/1024 7.94 4.28 -3.66 -46.09
std::map<int,_int>::lower_bound(key)_(existent)/32 2.73 1.69 -1.03 -37.89
std::map<int,_int>::lower_bound(key)_(existent)/8192 11.63 5.52 -6.11 -52.55
std::map<int,_int>::lower_bound(key)_(non-existent)/0 0.28 0.28 -0.00 -1.35
std::map<int,_int>::lower_bound(key)_(non-existent)/1024 17.21 7.63 -9.58 -55.67
std::map<int,_int>::lower_bound(key)_(non-existent)/32 4.71 3.26 -1.45 -30.71
std::map<int,_int>::lower_bound(key)_(non-existent)/8192 26.82 10.58 -16.24 -60.55
std::map<int,_int>::upper_bound(key)_(existent)/0 0.01 0.01 0.00 20.62
std::map<int,_int>::upper_bound(key)_(existent)/1024 7.93 3.61 -4.32 -54.49
std::map<int,_int>::upper_bound(key)_(existent)/32 2.83 1.98 -0.85 -30.01
std::map<int,_int>::upper_bound(key)_(existent)/8192 11.69 5.72 -5.97 -51.06
std::map<int,_int>::upper_bound(key)_(non-existent)/0 0.28 0.28 -0.00 -1.36
std::map<int,_int>::upper_bound(key)_(non-existent)/1024 17.21 8.00 -9.21 -53.53
std::map<int,_int>::upper_bound(key)_(non-existent)/32 4.70 2.93 -1.78 -37.76
std::map<int,_int>::upper_bound(key)_(non-existent)/8192 26.54 11.18 -15.36 -57.89
std::map<std::string,_int>::lower_bound(key)_(existent)/0 0.04 0.04 -0.00 -3.26
std::map<std::string,_int>::lower_bound(key)_(existent)/1024 27.46 26.25 -1.22 -4.43
std::map<std::string,_int>::lower_bound(key)_(existent)/32 19.17 15.71 -3.46 -18.07
std::map<std::string,_int>::lower_bound(key)_(existent)/8192 35.33 35.03 -0.30 -0.84
std::map<std::string,_int>::lower_bound(key)_(non-existent)/0 0.27 0.27 -0.00 -1.45
std::map<std::string,_int>::lower_bound(key)_(non-existent)/1024 24.88 24.17 -0.70 -2.83
std::map<std::string,_int>::lower_bound(key)_(non-existent)/32 11.67 11.63 -0.04 -0.32
std::map<std::string,_int>::lower_bound(key)_(non-existent)/8192 31.81 32.33 0.52 1.64
std::map<std::string,_int>::upper_bound(key)_(existent)/0 0.04 0.04 -0.00 -2.22
std::map<std::string,_int>::upper_bound(key)_(existent)/1024 29.91 26.51 -3.40 -11.38
std::map<std::string,_int>::upper_bound(key)_(existent)/32 19.69 17.74 -1.95 -9.92
std::map<std::string,_int>::upper_bound(key)_(existent)/8192 32.55 35.24 2.69 8.25
std::map<std::string,_int>::upper_bound(key)_(non-existent)/0 0.27 0.27 -0.00 -1.74
std::map<std::string,_int>::upper_bound(key)_(non-existent)/1024 23.87 26.77 2.91 12.18
std::map<std::string,_int>::upper_bound(key)_(non-existent)/32 11.44 11.81 0.37 3.24
std::map<std::string,_int>::upper_bound(key)_(non-existent)/8192 33.02 32.59 -0.43 -1.29
std::set<int>::lower_bound(key)_(existent)/0 0.01 0.01 0.00 0.48
std::set<int>::lower_bound(key)_(existent)/1024 7.83 4.21 -3.62 -46.23
std::set<int>::lower_bound(key)_(existent)/32 2.74 1.68 -1.06 -38.81
std::set<int>::lower_bound(key)_(existent)/8192 22.75 11.12 -11.63 -51.12
std::set<int>::lower_bound(key)_(non-existent)/0 0.28 0.27 -0.01 -3.52
std::set<int>::lower_bound(key)_(non-existent)/1024 17.15 8.40 -8.75 -51.03
std::set<int>::lower_bound(key)_(non-existent)/32 4.63 2.50 -2.13 -46.03
std::set<int>::lower_bound(key)_(non-existent)/8192 28.88 11.05 -17.82 -61.72
std::set<int>::upper_bound(key)_(existent)/0 0.01 0.01 -0.00 -7.79
std::set<int>::upper_bound(key)_(existent)/1024 7.80 3.63 -4.16 -53.42
std::set<int>::upper_bound(key)_(existent)/32 2.81 1.90 -0.91 -32.44
std::set<int>::upper_bound(key)_(existent)/8192 21.93 11.35 -10.58 -48.26
std::set<int>::upper_bound(key)_(non-existent)/0 0.28 0.27 -0.01 -3.81
std::set<int>::upper_bound(key)_(non-existent)/1024 16.76 7.38 -9.38 -55.98
std::set<int>::upper_bound(key)_(non-existent)/32 4.58 3.10 -1.48 -32.31
std::set<int>::upper_bound(key)_(non-existent)/8192 26.95 10.70 -16.25 -60.29
std::set<std::string>::lower_bound(key)_(existent)/0 0.04 0.04 0.00 0.02
std::set<std::string>::lower_bound(key)_(existent)/1024 28.08 27.04 -1.04 -3.71
std::set<std::string>::lower_bound(key)_(existent)/32 17.53 16.94 -0.58 -3.34
std::set<std::string>::lower_bound(key)_(existent)/8192 32.79 33.28 0.49 1.49
std::set<std::string>::lower_bound(key)_(non-existent)/0 0.28 0.28 -0.00 -0.06
std::set<std::string>::lower_bound(key)_(non-existent)/1024 25.23 24.38 -0.85 -3.38
std::set<std::string>::lower_bound(key)_(non-existent)/32 11.45 11.68 0.24 2.07
std::set<std::string>::lower_bound(key)_(non-existent)/8192 32.30 36.80 4.50 13.95
std::set<std::string>::upper_bound(key)_(existent)/0 0.04 0.04 -0.00 -0.14
std::set<std::string>::upper_bound(key)_(existent)/1024 26.71 26.37 -0.34 -1.27
std::set<std::string>::upper_bound(key)_(existent)/32 20.07 19.06 -1.02 -5.06
std::set<std::string>::upper_bound(key)_(existent)/8192 36.69 35.50 -1.19 -3.25
std::set<std::string>::upper_bound(key)_(non-existent)/0 0.28 0.28 -0.00 -0.16
std::set<std::string>::upper_bound(key)_(non-existent)/1024 24.48 24.90 0.42 1.73
std::set<std::string>::upper_bound(key)_(non-existent)/32 11.68 11.77 0.09 0.77
std::set<std::string>::upper_bound(key)_(non-existent)/8192 33.16 34.12 0.96 2.89
```
|
|
(#160738) (#161485)
This reverts commit b86aaacf28b358b187071bc87075f1faa2d65c4e.
The issue in LLVM has been fixed now.
|
|
(#160738)
Reverts llvm/llvm-project#157866
It breaks a lot of sanitizer buildbots
|
|
This patch adds additional overloads to `map::at` in case its known that
the argument is transparently comparable to the key type. This avoids
actually constructing the key type in some cases, potentially removing
allocations.
```
--------------------------------------------------------
Benchmark old new
--------------------------------------------------------
BM_map_find_string_literal 12.8 ns 2.68 ns
```
|
|
|
|
They're not formatted correctly anymore, since clang-format was updated.
|
|
We have multiple classes with an empty base optimization that contains
just a single type. This patch introduces `_LIBCPP_COMPRESSED_ELEMENT`
to refactor these classes to avoid having them essentially twice,
reducing the amount of code significantly.
|
|
This patch introduces a new comparator, namely `__lazy_synth_three_way`,
which tries to provide an efficient three way comparator for known types
and falls back to using the provided comparator if it doesn't know how
to do that. Currently, an efficient three way comparison is only
provided when using one of the `less` comparions object from the
standard library and `std::string`. This will be extended in future
patches.
```
------------------------------------------------------------------------------------------------------------------------------
Benchmark old new
------------------------------------------------------------------------------------------------------------------------------
std::map<std::string, int>::ctor(const&)/0 12.6 ns 12.6 ns
std::map<std::string, int>::ctor(const&)/32 858 ns 837 ns
std::map<std::string, int>::ctor(const&)/1024 46700 ns 46739 ns
std::map<std::string, int>::ctor(const&)/8192 458100 ns 449806 ns
std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/0 12.8 ns 12.7 ns
std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/32 1286 ns 1266 ns
std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/1024 93812 ns 84686 ns
std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/8192 1480346 ns 1385924 ns
std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/0 12.9 ns 12.8 ns
std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/32 1044 ns 1055 ns
std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/1024 63071 ns 62861 ns
std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/8192 595046 ns 590223 ns
std::map<std::string, int>::operator=(const&) (into cleared Container)/0 13.6 ns 13.6 ns
std::map<std::string, int>::operator=(const&) (into cleared Container)/32 880 ns 911 ns
std::map<std::string, int>::operator=(const&) (into cleared Container)/1024 48627 ns 47808 ns
std::map<std::string, int>::operator=(const&) (into cleared Container)/8192 458552 ns 454497 ns
std::map<std::string, int>::operator=(const&) (into partially populated Container)/0 13.8 ns 13.6 ns
std::map<std::string, int>::operator=(const&) (into partially populated Container)/32 864 ns 851 ns
std::map<std::string, int>::operator=(const&) (into partially populated Container)/1024 49483 ns 49555 ns
std::map<std::string, int>::operator=(const&) (into partially populated Container)/8192 456977 ns 457894 ns
std::map<std::string, int>::operator=(const&) (into populated Container)/0 1.31 ns 1.31 ns
std::map<std::string, int>::operator=(const&) (into populated Container)/32 425 ns 415 ns
std::map<std::string, int>::operator=(const&) (into populated Container)/1024 14248 ns 14225 ns
std::map<std::string, int>::operator=(const&) (into populated Container)/8192 136684 ns 133696 ns
std::map<std::string, int>::insert(value) (already present)/0 21.5 ns 16.2 ns
std::map<std::string, int>::insert(value) (already present)/32 22.7 ns 25.1 ns
std::map<std::string, int>::insert(value) (already present)/1024 54.5 ns 29.1 ns
std::map<std::string, int>::insert(value) (already present)/8192 78.4 ns 30.4 ns
std::map<std::string, int>::insert(value) (new value)/0 40.9 ns 39.0 ns
std::map<std::string, int>::insert(value) (new value)/32 58.3 ns 47.2 ns
std::map<std::string, int>::insert(value) (new value)/1024 120 ns 71.3 ns
std::map<std::string, int>::insert(value) (new value)/8192 157 ns 129 ns
std::map<std::string, int>::insert(hint, value) (good hint)/0 40.3 ns 40.7 ns
std::map<std::string, int>::insert(hint, value) (good hint)/32 48.0 ns 30.0 ns
std::map<std::string, int>::insert(hint, value) (good hint)/1024 107 ns 63.2 ns
std::map<std::string, int>::insert(hint, value) (good hint)/8192 132 ns 107 ns
std::map<std::string, int>::insert(hint, value) (bad hint)/0 27.0 ns 40.9 ns
std::map<std::string, int>::insert(hint, value) (bad hint)/32 68.3 ns 58.4 ns
std::map<std::string, int>::insert(hint, value) (bad hint)/1024 125 ns 82.0 ns
std::map<std::string, int>::insert(hint, value) (bad hint)/8192 155 ns 150 ns
std::map<std::string, int>::insert(iterator, iterator) (all new keys)/0 404 ns 405 ns
std::map<std::string, int>::insert(iterator, iterator) (all new keys)/32 2004 ns 1805 ns
std::map<std::string, int>::insert(iterator, iterator) (all new keys)/1024 102820 ns 76102 ns
std::map<std::string, int>::insert(iterator, iterator) (all new keys)/8192 1144590 ns 949266 ns
std::map<std::string, int>::insert(iterator, iterator) (half new keys)/0 408 ns 404 ns
std::map<std::string, int>::insert(iterator, iterator) (half new keys)/32 1592 ns 1377 ns
std::map<std::string, int>::insert(iterator, iterator) (half new keys)/1024 74847 ns 53921 ns
std::map<std::string, int>::insert(iterator, iterator) (half new keys)/8192 828505 ns 698716 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/0 407 ns 407 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/32 1584 ns 1557 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/1024 47157 ns 47443 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/8192 623887 ns 628385 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/0 405 ns 403 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/32 1478 ns 1510 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/1024 47852 ns 47835 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/8192 605311 ns 606951 ns
std::map<std::string, int>::erase(key) (existent)/0 129 ns 94.0 ns
std::map<std::string, int>::erase(key) (existent)/32 110 ns 106 ns
std::map<std::string, int>::erase(key) (existent)/1024 121 ns 128 ns
std::map<std::string, int>::erase(key) (existent)/8192 165 ns 66.9 ns
std::map<std::string, int>::erase(key) (non-existent)/0 0.269 ns 0.257 ns
std::map<std::string, int>::erase(key) (non-existent)/32 21.9 ns 11.3 ns
std::map<std::string, int>::erase(key) (non-existent)/1024 53.5 ns 25.4 ns
std::map<std::string, int>::erase(key) (non-existent)/8192 67.3 ns 31.9 ns
std::map<std::string, int>::erase(iterator)/0 46.3 ns 46.7 ns
std::map<std::string, int>::erase(iterator)/32 44.4 ns 41.8 ns
std::map<std::string, int>::erase(iterator)/1024 43.7 ns 46.4 ns
std::map<std::string, int>::erase(iterator)/8192 45.2 ns 44.1 ns
std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/0 407 ns 407 ns
std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/32 876 ns 906 ns
std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/1024 20880 ns 20444 ns
std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/8192 252881 ns 241583 ns
std::map<std::string, int>::clear()/0 407 ns 408 ns
std::map<std::string, int>::clear()/32 1252 ns 1323 ns
std::map<std::string, int>::clear()/1024 38488 ns 38017 ns
std::map<std::string, int>::clear()/8192 416492 ns 428534 ns
std::map<std::string, int>::find(key) (existent)/0 0.008 ns 0.008 ns
std::map<std::string, int>::find(key) (existent)/32 33.9 ns 15.3 ns
std::map<std::string, int>::find(key) (existent)/1024 43.0 ns 25.5 ns
std::map<std::string, int>::find(key) (existent)/8192 44.6 ns 29.3 ns
std::map<std::string, int>::find(key) (non-existent)/0 0.259 ns 0.257 ns
std::map<std::string, int>::find(key) (non-existent)/32 22.6 ns 11.4 ns
std::map<std::string, int>::find(key) (non-existent)/1024 48.6 ns 25.1 ns
std::map<std::string, int>::find(key) (non-existent)/8192 64.1 ns 31.1 ns
std::map<std::string, int>::count(key) (existent)/0 0.008 ns 0.008 ns
std::map<std::string, int>::count(key) (existent)/32 32.2 ns 17.3 ns
std::map<std::string, int>::count(key) (existent)/1024 42.4 ns 25.3 ns
std::map<std::string, int>::count(key) (existent)/8192 44.4 ns 31.6 ns
std::map<std::string, int>::count(key) (non-existent)/0 0.260 ns 0.259 ns
std::map<std::string, int>::count(key) (non-existent)/32 22.9 ns 11.3 ns
std::map<std::string, int>::count(key) (non-existent)/1024 49.8 ns 25.5 ns
std::map<std::string, int>::count(key) (non-existent)/8192 66.3 ns 31.9 ns
std::map<std::string, int>::contains(key) (existent)/0 0.008 ns 0.008 ns
std::map<std::string, int>::contains(key) (existent)/32 31.4 ns 18.0 ns
std::map<std::string, int>::contains(key) (existent)/1024 44.3 ns 26.5 ns
std::map<std::string, int>::contains(key) (existent)/8192 47.4 ns 30.2 ns
std::map<std::string, int>::contains(key) (non-existent)/0 0.452 ns 0.441 ns
std::map<std::string, int>::contains(key) (non-existent)/32 23.1 ns 11.5 ns
std::map<std::string, int>::contains(key) (non-existent)/1024 46.2 ns 26.3 ns
std::map<std::string, int>::contains(key) (non-existent)/8192 63.4 ns 31.4 ns
std::map<std::string, int>::lower_bound(key) (existent)/0 0.008 ns 0.008 ns
std::map<std::string, int>::lower_bound(key) (existent)/32 17.2 ns 19.0 ns
std::map<std::string, int>::lower_bound(key) (existent)/1024 27.1 ns 26.2 ns
std::map<std::string, int>::lower_bound(key) (existent)/8192 34.0 ns 36.0 ns
std::map<std::string, int>::lower_bound(key) (non-existent)/0 0.259 ns 0.257 ns
std::map<std::string, int>::lower_bound(key) (non-existent)/32 11.6 ns 11.5 ns
std::map<std::string, int>::lower_bound(key) (non-existent)/1024 24.8 ns 25.6 ns
std::map<std::string, int>::lower_bound(key) (non-existent)/8192 31.7 ns 31.6 ns
std::map<std::string, int>::upper_bound(key) (existent)/0 0.008 ns 0.008 ns
std::map<std::string, int>::upper_bound(key) (existent)/32 18.8 ns 19.7 ns
std::map<std::string, int>::upper_bound(key) (existent)/1024 25.3 ns 27.7 ns
std::map<std::string, int>::upper_bound(key) (existent)/8192 30.2 ns 29.9 ns
std::map<std::string, int>::upper_bound(key) (non-existent)/0 0.260 ns 0.259 ns
std::map<std::string, int>::upper_bound(key) (non-existent)/32 11.3 ns 12.0 ns
std::map<std::string, int>::upper_bound(key) (non-existent)/1024 25.6 ns 25.9 ns
std::map<std::string, int>::upper_bound(key) (non-existent)/8192 33.1 ns 34.2 ns
std::map<std::string, int>::equal_range(key) (existent)/0 0.008 ns 0.008 ns
std::map<std::string, int>::equal_range(key) (existent)/32 33.5 ns 15.8 ns
std::map<std::string, int>::equal_range(key) (existent)/1024 43.0 ns 25.1 ns
std::map<std::string, int>::equal_range(key) (existent)/8192 54.1 ns 30.7 ns
std::map<std::string, int>::equal_range(key) (non-existent)/0 0.265 ns 0.259 ns
std::map<std::string, int>::equal_range(key) (non-existent)/32 22.1 ns 12.1 ns
std::map<std::string, int>::equal_range(key) (non-existent)/1024 44.8 ns 24.4 ns
std::map<std::string, int>::equal_range(key) (non-existent)/8192 62.2 ns 40.1 ns
```
Fixes #66577
|
|
|
|
```
----------------------------------------------------------------------------------------------------------------------------
Benchmark old new
----------------------------------------------------------------------------------------------------------------------------
std::map<int, int>::ctor(iterator, iterator) (unsorted sequence)/0 14.2 ns 14.8 ns
std::map<int, int>::ctor(iterator, iterator) (unsorted sequence)/32 519 ns 404 ns
std::map<int, int>::ctor(iterator, iterator) (unsorted sequence)/1024 52460 ns 36242 ns
std::map<int, int>::ctor(iterator, iterator) (unsorted sequence)/8192 724222 ns 706496 ns
std::map<int, int>::ctor(iterator, iterator) (sorted sequence)/0 14.2 ns 14.7 ns
std::map<int, int>::ctor(iterator, iterator) (sorted sequence)/32 429 ns 349 ns
std::map<int, int>::ctor(iterator, iterator) (sorted sequence)/1024 23601 ns 14734 ns
std::map<int, int>::ctor(iterator, iterator) (sorted sequence)/8192 267753 ns 112155 ns
std::map<int, int>::insert(iterator, iterator) (all new keys)/0 434 ns 448 ns
std::map<int, int>::insert(iterator, iterator) (all new keys)/32 950 ns 963 ns
std::map<int, int>::insert(iterator, iterator) (all new keys)/1024 27205 ns 25344 ns
std::map<int, int>::insert(iterator, iterator) (all new keys)/8192 294248 ns 280713 ns
std::map<int, int>::insert(iterator, iterator) (half new keys)/0 435 ns 449 ns
std::map<int, int>::insert(iterator, iterator) (half new keys)/32 771 ns 706 ns
std::map<int, int>::insert(iterator, iterator) (half new keys)/1024 30841 ns 17495 ns
std::map<int, int>::insert(iterator, iterator) (half new keys)/8192 468807 ns 285847 ns
std::map<int, int>::insert(iterator, iterator) (product_iterator from same type)/0 449 ns 453 ns
std::map<int, int>::insert(iterator, iterator) (product_iterator from same type)/32 1021 ns 932 ns
std::map<int, int>::insert(iterator, iterator) (product_iterator from same type)/1024 29796 ns 19518 ns
std::map<int, int>::insert(iterator, iterator) (product_iterator from same type)/8192 345688 ns 153966 ns
std::map<int, int>::insert(iterator, iterator) (product_iterator from zip_view)/0 449 ns 450 ns
std::map<int, int>::insert(iterator, iterator) (product_iterator from zip_view)/32 1026 ns 807 ns
std::map<int, int>::insert(iterator, iterator) (product_iterator from zip_view)/1024 31632 ns 15573 ns
std::map<int, int>::insert(iterator, iterator) (product_iterator from zip_view)/8192 303024 ns 128946 ns
std::map<int, int>::erase(iterator, iterator) (erase half the container)/0 447 ns 452 ns
std::map<int, int>::erase(iterator, iterator) (erase half the container)/32 687 ns 710 ns
std::map<int, int>::erase(iterator, iterator) (erase half the container)/1024 8604 ns 8581 ns
std::map<int, int>::erase(iterator, iterator) (erase half the container)/8192 65693 ns 67406 ns
std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/0 15.0 ns 15.0 ns
std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/32 2781 ns 1845 ns
std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/1024 187999 ns 182103 ns
std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/8192 2937242 ns 2934912 ns
std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/0 15.0 ns 15.2 ns
std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/32 1326 ns 2462 ns
std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/1024 81778 ns 72193 ns
std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/8192 1177292 ns 669152 ns
std::map<std::string, int>::insert(iterator, iterator) (all new keys)/0 439 ns 454 ns
std::map<std::string, int>::insert(iterator, iterator) (all new keys)/32 2483 ns 2465 ns
std::map<std::string, int>::insert(iterator, iterator) (all new keys)/1024 187614 ns 188072 ns
std::map<std::string, int>::insert(iterator, iterator) (all new keys)/8192 1654675 ns 1706603 ns
std::map<std::string, int>::insert(iterator, iterator) (half new keys)/0 437 ns 452 ns
std::map<std::string, int>::insert(iterator, iterator) (half new keys)/32 1836 ns 1820 ns
std::map<std::string, int>::insert(iterator, iterator) (half new keys)/1024 114885 ns 121865 ns
std::map<std::string, int>::insert(iterator, iterator) (half new keys)/8192 1151960 ns 1197318 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/0 438 ns 455 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/32 1599 ns 1614 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/1024 95935 ns 82159 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/8192 776480 ns 941043 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/0 435 ns 462 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/32 1723 ns 1550 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/1024 107096 ns 92850 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/8192 893976 ns 775046 ns
std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/0 436 ns 453 ns
std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/32 775 ns 824 ns
std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/1024 20241 ns 20454 ns
std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/8192 139038 ns 138032 ns
std::set<int>::ctor(iterator, iterator) (unsorted sequence)/0 14.8 ns 14.7 ns
std::set<int>::ctor(iterator, iterator) (unsorted sequence)/32 468 ns 426 ns
std::set<int>::ctor(iterator, iterator) (unsorted sequence)/1024 54289 ns 39028 ns
std::set<int>::ctor(iterator, iterator) (unsorted sequence)/8192 738438 ns 695720 ns
std::set<int>::ctor(iterator, iterator) (sorted sequence)/0 14.7 ns 14.6 ns
std::set<int>::ctor(iterator, iterator) (sorted sequence)/32 478 ns 391 ns
std::set<int>::ctor(iterator, iterator) (sorted sequence)/1024 24017 ns 13905 ns
std::set<int>::ctor(iterator, iterator) (sorted sequence)/8192 267862 ns 111378 ns
std::set<int>::insert(iterator, iterator) (all new keys)/0 458 ns 450 ns
std::set<int>::insert(iterator, iterator) (all new keys)/32 1066 ns 956 ns
std::set<int>::insert(iterator, iterator) (all new keys)/1024 29190 ns 25212 ns
std::set<int>::insert(iterator, iterator) (all new keys)/8192 320441 ns 279602 ns
std::set<int>::insert(iterator, iterator) (half new keys)/0 454 ns 453 ns
std::set<int>::insert(iterator, iterator) (half new keys)/32 816 ns 709 ns
std::set<int>::insert(iterator, iterator) (half new keys)/1024 32072 ns 17074 ns
std::set<int>::insert(iterator, iterator) (half new keys)/8192 403386 ns 286202 ns
std::set<int>::erase(iterator, iterator) (erase half the container)/0 451 ns 452 ns
std::set<int>::erase(iterator, iterator) (erase half the container)/32 710 ns 703 ns
std::set<int>::erase(iterator, iterator) (erase half the container)/1024 8261 ns 8499 ns
std::set<int>::erase(iterator, iterator) (erase half the container)/8192 64466 ns 67343 ns
std::set<std::string>::ctor(iterator, iterator) (unsorted sequence)/0 15.2 ns 15.0 ns
std::set<std::string>::ctor(iterator, iterator) (unsorted sequence)/32 3069 ns 3005 ns
std::set<std::string>::ctor(iterator, iterator) (unsorted sequence)/1024 189552 ns 180933 ns
std::set<std::string>::ctor(iterator, iterator) (unsorted sequence)/8192 2887579 ns 2691678 ns
std::set<std::string>::ctor(iterator, iterator) (sorted sequence)/0 15.1 ns 14.9 ns
std::set<std::string>::ctor(iterator, iterator) (sorted sequence)/32 2611 ns 2514 ns
std::set<std::string>::ctor(iterator, iterator) (sorted sequence)/1024 91581 ns 78727 ns
std::set<std::string>::ctor(iterator, iterator) (sorted sequence)/8192 1192640 ns 1158959 ns
std::set<std::string>::insert(iterator, iterator) (all new keys)/0 452 ns 457 ns
std::set<std::string>::insert(iterator, iterator) (all new keys)/32 2530 ns 2544 ns
std::set<std::string>::insert(iterator, iterator) (all new keys)/1024 195352 ns 179614 ns
std::set<std::string>::insert(iterator, iterator) (all new keys)/8192 1737890 ns 1749615 ns
std::set<std::string>::insert(iterator, iterator) (half new keys)/0 451 ns 454 ns
std::set<std::string>::insert(iterator, iterator) (half new keys)/32 1949 ns 1766 ns
std::set<std::string>::insert(iterator, iterator) (half new keys)/1024 128853 ns 109467 ns
std::set<std::string>::insert(iterator, iterator) (half new keys)/8192 1233077 ns 1177289 ns
std::set<std::string>::erase(iterator, iterator) (erase half the container)/0 450 ns 451 ns
std::set<std::string>::erase(iterator, iterator) (erase half the container)/32 809 ns 812 ns
std::set<std::string>::erase(iterator, iterator) (erase half the container)/1024 21736 ns 21922 ns
std::set<std::string>::erase(iterator, iterator) (erase half the container)/8192 135884 ns 133228 ns
```
Fixes #154650
|
|
`__emplace_unique` uses `__find_equal`, which can be significantly
faster than `lower_bound`. As a nice side-effect, this also changes the
implementation to the "naive" implementation of trying `insert` first,
and if that fails assign instead. This also matches the
`insert_or_assign` overloads with a hint.
```
Zen 2:
--------------------------------------------------------------------------------------------------------
Benchmark old new
--------------------------------------------------------------------------------------------------------
std::map<int, int>::insert_or_assign(key, value) (already present)/0 1.62 ns 1.53 ns
std::map<int, int>::insert_or_assign(key, value) (already present)/32 5.78 ns 5.99 ns
std::map<int, int>::insert_or_assign(key, value) (already present)/1024 21.5 ns 15.4 ns
std::map<int, int>::insert_or_assign(key, value) (already present)/8192 26.2 ns 20.5 ns
std::map<int, int>::insert_or_assign(key, value) (new value)/0 22.5 ns 21.1 ns
std::map<int, int>::insert_or_assign(key, value) (new value)/32 42.9 ns 28.4 ns
std::map<int, int>::insert_or_assign(key, value) (new value)/1024 118 ns 92.0 ns
std::map<int, int>::insert_or_assign(key, value) (new value)/8192 227 ns 173 ns
std::map<std::string, int>::insert_or_assign(key, value) (already present)/0 13.2 ns 18.9 ns
std::map<std::string, int>::insert_or_assign(key, value) (already present)/32 65.6 ns 39.0 ns
std::map<std::string, int>::insert_or_assign(key, value) (already present)/1024 127 ns 64.4 ns
std::map<std::string, int>::insert_or_assign(key, value) (already present)/8192 134 ns 71.4 ns
std::map<std::string, int>::insert_or_assign(key, value) (new value)/0 45.6 ns 37.3 ns
std::map<std::string, int>::insert_or_assign(key, value) (new value)/32 142 ns 93.3 ns
std::map<std::string, int>::insert_or_assign(key, value) (new value)/1024 288 ns 147 ns
std::map<std::string, int>::insert_or_assign(key, value) (new value)/8192 368 ns 182 ns
Apple M4:
--------------------------------------------------------------------------------------------------------
Benchmark old new
--------------------------------------------------------------------------------------------------------
std::map<int, int>::insert_or_assign(key, value) (already present)/0 0.784 ns 0.740 ns
std::map<int, int>::insert_or_assign(key, value) (already present)/32 2.52 ns 1.77 ns
std::map<int, int>::insert_or_assign(key, value) (already present)/1024 8.72 ns 4.06 ns
std::map<int, int>::insert_or_assign(key, value) (already present)/8192 10.6 ns 3.98 ns
std::map<int, int>::insert_or_assign(key, value) (new value)/0 17.3 ns 17.2 ns
std::map<int, int>::insert_or_assign(key, value) (new value)/32 22.5 ns 19.3 ns
std::map<int, int>::insert_or_assign(key, value) (new value)/1024 56.8 ns 33.5 ns
std::map<int, int>::insert_or_assign(key, value) (new value)/8192 88.2 ns 41.0 ns
std::map<std::string, int>::insert_or_assign(key, value) (already present)/0 16.6 ns 11.8 ns
std::map<std::string, int>::insert_or_assign(key, value) (already present)/32 13.7 ns 30.7 ns
std::map<std::string, int>::insert_or_assign(key, value) (already present)/1024 46.7 ns 49.1 ns
std::map<std::string, int>::insert_or_assign(key, value) (already present)/8192 41.9 ns 76.9 ns
std::map<std::string, int>::insert_or_assign(key, value) (new value)/0 40.0 ns 40.5 ns
std::map<std::string, int>::insert_or_assign(key, value) (new value)/32 38.9 ns 40.0 ns
std::map<std::string, int>::insert_or_assign(key, value) (new value)/1024 84.9 ns 96.9 ns
std::map<std::string, int>::insert_or_assign(key, value) (new value)/8192 166 ns 149 ns
```
|
|
(#154512)" (#155565)
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.
|
|
This reverts commit af1f06e41b05c267480f1629dc0fcdf18f3b59f6.
This is causing some build failures in premerge as some of the LLDB
tests fail.
|
|
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.
|
|
|
|
(#154707)
This patch does two things:
- Remove exception specifications of `= default`ed special member
functions
- `= default` special member functions
The first part is NFC because the explicit specification does exactly
the same as the implicit specification. The second is NFC because it
does exactly what the `= default`ed special member does.
|
|
(#154225)
Prepare for:
https://github.com/llvm/llvm-project/pull/153908#discussion_r2281756219
|
|
The `__get_value()` member function was removed in LLVM 21, but the
calls in `<map>` weren't removed. This patch completes the removal and
adds regression test cases.
Fixes #152543.
|
|
Removing the unnecessary friend declarations from `<__tree>` also
removes the need for forward declaration headers for `map` and `set`,
which this patch also removes.
|
|
```
----------------------------------------------------------------------------------------------------------
Benchmark old new
----------------------------------------------------------------------------------------------------------
std::map<int, int>::ctor(const&)/0 15.5 ns 14.9 ns
std::map<int, int>::ctor(const&)/32 474 ns 321 ns
std::map<int, int>::ctor(const&)/1024 24591 ns 11101 ns
std::map<int, int>::ctor(const&)/8192 236153 ns 98868 ns
std::map<std::string, int>::ctor(const&)/0 15.2 ns 14.9 ns
std::map<std::string, int>::ctor(const&)/32 2673 ns 2340 ns
std::map<std::string, int>::ctor(const&)/1024 115354 ns 86088 ns
std::map<std::string, int>::ctor(const&)/8192 1298510 ns 626876 ns
std::map<int, int>::operator=(const&) (into cleared Container)/0 16.5 ns 16.1 ns
std::map<int, int>::operator=(const&) (into cleared Container)/32 548 ns 323 ns
std::map<int, int>::operator=(const&) (into cleared Container)/1024 28418 ns 11026 ns
std::map<int, int>::operator=(const&) (into cleared Container)/8192 281827 ns 97113 ns
std::map<int, int>::operator=(const&) (into populated Container)/0 2.42 ns 1.85 ns
std::map<int, int>::operator=(const&) (into populated Container)/32 369 ns 73.0 ns
std::map<int, int>::operator=(const&) (into populated Container)/1024 24078 ns 2322 ns
std::map<int, int>::operator=(const&) (into populated Container)/8192 266537 ns 22963 ns
std::map<std::string, int>::operator=(const&) (into cleared Container)/0 16.6 ns 16.2 ns
std::map<std::string, int>::operator=(const&) (into cleared Container)/32 2614 ns 1622 ns
std::map<std::string, int>::operator=(const&) (into cleared Container)/1024 116826 ns 63281 ns
std::map<std::string, int>::operator=(const&) (into cleared Container)/8192 1316655 ns 649177 ns
std::map<std::string, int>::operator=(const&) (into populated Container)/0 2.42 ns 1.89 ns
std::map<std::string, int>::operator=(const&) (into populated Container)/32 1264 ns 581 ns
std::map<std::string, int>::operator=(const&) (into populated Container)/1024 238826 ns 39943 ns
std::map<std::string, int>::operator=(const&) (into populated Container)/8192 2412327 ns 379456 ns
```
Fixes #77658
Fixes #62571
|
|
This fixes `insert()` calling the wrong `allocator_traits::construct` in
the associative containers by removing the special handling that lead to
the inconsistencty inside `__tree` and `__hash_table`.
|
|
We don't actually do anything special in these special member functions,
so we can just `= default` them to save a bit of code.
|
|
Most notably, this removes the notion of a distinct `value_type` and
`__container_value_type` from `__tree`, since these are now always the
same type. There are a few places we need to keep `__value_type` around,
since they are ABI visibile. In these cases `_Tp` is used directly. The
second simplification here is that we use `const value_type&` instead of
`const key_type&` in a few places and make use of the fact that the
comparator is capable of comparing any combination of `key_type` and
`value_type`.
This is a follow-up to #134819.
|
|
user defined (#140379)
This is brought up in the LWG reflector. We currently call `reserve` if
the underlying container has one. But the spec does not specify what
`reserve` should do for Sequence Container. So in theory if the
underlying container is user defined type and it can have a function
called `reserve` which does something completely different.
The fix is to just call `reserve` for STL containers if it has one
|
|
|
|
This causes a mismatch between `value_type` and
`allocator_type::value_type` in `__tree`, but I think that's acceptable.
`__tree` primarily gets a `__value_type` wrapper due to potential ABI
breaks and unwraps it to the same as `allocator_type::value_type` in the
end. A cleanup patch will also change `__tree::value_type` to be the
same as `allocator_type::value_type`, making the type mismatch only
visible where `__tree` is instantiated in `map`.
|
|
This was missed due to using prvalues in the test case, which were
picked up by the rvalue-reference overload instead.
|
|
Before this patch, we were dereferencing pointers to objects which were
never constructed. Now we always assume that nodes store `pair<const
KeyT, ValueT>` for maps instead, as they actually do. This patch also
allows for significant follow-up simplifications, since
`__node_value_type` and `__container_value_type` are the same type now.
|
|
The need for `_LIBCPP_TEMPLATE_VIS` has been removed in #133233.
|
|
This removes duplicated forward declarations of these classes.
closes: #131518
|
|
This is technically not necessary in most cases to prevent issues with ADL,
but let's be consistent. This allows us to remove the libcpp-qualify-declval
clang-tidy check, which is now enforced by the robust-against-adl clang-tidy check.
|
|
This patch implements the forwarding to frozen C++03 headers as
discussed in
https://discourse.llvm.org/t/rfc-freezing-c-03-headers-in-libc. In the
RFC, we initially proposed selecting the right headers from the Clang
driver, however consensus seemed to steer towards handling this in the
library itself. This patch implements that direction.
At a high level, the changes basically amount to making each public
header look like this:
```
// inside <vector>
#ifdef _LIBCPP_CXX03_LANG
# include <__cxx03/vector>
#else
// normal <vector> content
#endif
```
In most cases, public headers are simple umbrella headers so there isn't
much code in the #else branch. In other cases, the #else branch contains
the actual implementation of the header.
|
|
|
|
Including The frozen C++03 headers results in a lot of formatting
changes in the main headers, so this splits these changes into a
separate commit instead.
This is part of
https://discourse.llvm.org/t/rfc-freezing-c-03-headers-in-libc.
|
|
This PR is extracted from
https://github.com/llvm/llvm-project/pull/98643, as per code review
request
https://github.com/llvm/llvm-project/pull/98643#discussion_r1768967793
|
|
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.
|
|
`__has_cpp_attribute(__nodiscard__)` is always true now, so we might as
well replace `_LIBCPP_NODISCARD`. It's one less macro that can result in
bad diagnostics.
|
|
Restore `__synth_three_way` lambda to match the Standard.
GH-57222 is done, restoring the Standard wording implementation should
be possible.
https://github.com/llvm/llvm-project/blob/df28d4412c1d21b0e18896c92ac77d2fac7729f1/libcxx/include/__compare/synth_three_way.h#L28
According to comment
https://github.com/llvm/llvm-project/issues/59513#issuecomment-2068338762,
GH-59513 is not a blocker.
Co-authored-by: Hristo Hristov <zingam@outlook.com>
|
|
There is code duplication in all containers that static_assert the
allocator matches the allocator requirements in the spec. This check can
be moved into a more centralised place.
|
|
keywords in C++11 code (#96387)
|
|
As time went by, a few files have become mis-formatted w.r.t.
clang-format. This was made worse by the fact that formatting was not
being enforced in extensionless headers. This commit simply brings all
of libcxx/include in-line with clang-format again.
We might have to do this from time to time as we update our clang-format
version, but frankly this is really low effort now that we've formatted
everything once.
|
|
This changes the `is_swappable` implementation to use variable templates
first and basing the class templates on that. This avoids instantiating
them when the `_v` versions are used, which are generally less resource
intensive.
|
|
Differential Revision: https://reviews.llvm.org/D121213
|
|
These were required a long time ago due to `static_assert` not actually
being available in C++03. Now `static_assert` is simply mapped to
`_Static_assert` in C++03, making the additional parens unnecessary.
|
|
In essence, this header has always been related to configuration of
the library but we didn't want to put it inside <__config> due to
complexity reasons. Now that we have sub-headers in <__config>, we
can move <__availability> to it and stop including it everywhere since
we already obtain the required macros via <__config>.
|
|
|
|
(#87094)
This also adds a few tests that were missing.
|
|
Originally, we used __libcpp_verbose_abort to handle assertion failures.
That function was declared from all public headers. Since we don't use
that mechanism anymore, we don't need to declare __libcpp_verbose_abort
from all public headers, and we can clean up a lot of unnecessary
includes.
This patch also moves the definition of the various assertion categories
to the <__assert> header, since we now rely on regular IWYU for these
assertion macros.
rdar://105510916
|
