4747 Commits

Author SHA1 Message Date
Damien L-G
19557a4c8f
[libc++] Fix bug in tests for std::atomic_ref<T*> increment and decrement operators (#122271)
The implementation is fine and has the proper increment/decrement
operators defined, but the tests were wrong:
- a typo (`T` instead of `std::atomic_ref<T>`) when ensuring that increment/decrement
  operators are not defined in the primary template and specialization for floating point
  types, and
- the specialization for pointer types was miscategorized.
2025-01-10 16:36:19 -05:00
Jakub Mazurkiewicz
c91d805e66
[libc++] Implement std::not_fn<NTTP> (#86133)
Implement `std::not_fn<NTTP>` from "P2714R1 Bind front and back to NTTP callables".
2025-01-10 14:14:14 -05:00
Дмитрий Изволов
69b54c1a05
[libcxx][algorithm] Optimize std::stable_sort via radix sort algorithm (#104683)
The radix sort (LSD) algorithm allows to speed up std::stable_sort
dramatically in case we sort integers.
The speed up varies from a relatively small to x10 times, depending on
type of sorted elements and the initial state of the sorted array.

```
Running ./libcxx/test/benchmarks/stable_sort.bench.out
Run on (12 X 2600 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB
  L1 Instruction 32 KiB
  L2 Unified 256 KiB (x6)
  L3 Unified 12288 KiB
Load Average: 3.48, 3.38, 3.08
---------------------------------------------------------------------------
Benchmark                                               After        Before 
---------------------------------------------------------------------------
BM_StableSort_int8_Random_1                           3.39 ns       3.58 ns 
BM_StableSort_int8_Random_4                           21.1 ns       21.9 ns 
BM_StableSort_int8_Random_16                           142 ns        147 ns 
BM_StableSort_int8_Random_64                           893 ns        903 ns 
BM_StableSort_int8_Random_256                          409 ns       5810 ns 
BM_StableSort_int8_Random_1024                        1235 ns      29973 ns 
BM_StableSort_int8_Random_4096                        4410 ns     141880 ns 
BM_StableSort_int8_Random_16384                      18044 ns     620540 ns 
BM_StableSort_int8_Random_65536                     144030 ns    2592013 ns 
BM_StableSort_int8_Random_262144                    858350 ns   10935814 ns 
BM_StableSort_int8_Random_524288                   2929988 ns   27060729 ns 
BM_StableSort_int8_Random_1048576                  6058292 ns   49622720 ns 
BM_StableSort_int8_Ascending_1                        3.42 ns       3.92 ns 
BM_StableSort_int8_Ascending_4                        5.86 ns       8.08 ns 
BM_StableSort_int8_Ascending_16                       10.6 ns       12.0 ns 
BM_StableSort_int8_Ascending_64                       28.9 ns       30.6 ns 
BM_StableSort_int8_Ascending_256                       415 ns        391 ns 
BM_StableSort_int8_Ascending_1024                     1666 ns       2309 ns 
BM_StableSort_int8_Ascending_4096                     7748 ns      12269 ns 
BM_StableSort_int8_Ascending_16384                   40588 ns      60181 ns 
BM_StableSort_int8_Ascending_65536                  178843 ns     298221 ns 
BM_StableSort_int8_Ascending_262144                 919959 ns    1402692 ns 
BM_StableSort_int8_Ascending_524288                2397397 ns    3036984 ns 
BM_StableSort_int8_Ascending_1048576               5080043 ns    7218581 ns 
BM_StableSort_int8_Descending_1                       3.44 ns       3.53 ns 
BM_StableSort_int8_Descending_4                       7.94 ns       8.29 ns 
BM_StableSort_int8_Descending_16                      59.6 ns       57.7 ns 
BM_StableSort_int8_Descending_64                      1051 ns       1027 ns 
BM_StableSort_int8_Descending_256                      422 ns       4718 ns 
BM_StableSort_int8_Descending_1024                    1676 ns      21044 ns 
BM_StableSort_int8_Descending_4096                    7766 ns      64827 ns 
BM_StableSort_int8_Descending_16384                  40230 ns      93981 ns 
BM_StableSort_int8_Descending_65536                 190978 ns     421151 ns 
BM_StableSort_int8_Descending_262144               1055141 ns    1918927 ns 
BM_StableSort_int8_Descending_524288               2875115 ns    3809153 ns 
BM_StableSort_int8_Descending_1048576              5854135 ns    8713690 ns 
BM_StableSort_int8_SingleElement_1                    3.52 ns       3.46 ns 
BM_StableSort_int8_SingleElement_4                    6.25 ns       5.79 ns 
BM_StableSort_int8_SingleElement_16                   10.7 ns       11.4 ns 
BM_StableSort_int8_SingleElement_64                   29.3 ns       30.3 ns 
BM_StableSort_int8_SingleElement_256                   858 ns        380 ns 
BM_StableSort_int8_SingleElement_1024                 3036 ns       2231 ns 
BM_StableSort_int8_SingleElement_4096                11580 ns      11866 ns 
BM_StableSort_int8_SingleElement_16384               44956 ns      59621 ns 
BM_StableSort_int8_SingleElement_65536              182006 ns     297853 ns 
BM_StableSort_int8_SingleElement_262144             962181 ns    1432857 ns 
BM_StableSort_int8_SingleElement_524288            2256687 ns    2975707 ns 
BM_StableSort_int8_SingleElement_1048576           4522556 ns    6949948 ns 
BM_StableSort_int8_PipeOrgan_1                        3.26 ns       3.64 ns 
BM_StableSort_int8_PipeOrgan_4                        6.21 ns       6.58 ns 
BM_StableSort_int8_PipeOrgan_16                       23.7 ns       25.4 ns 
BM_StableSort_int8_PipeOrgan_64                        250 ns        248 ns 
BM_StableSort_int8_PipeOrgan_256                       414 ns       2498 ns 
BM_StableSort_int8_PipeOrgan_1024                     1697 ns      10946 ns 
BM_StableSort_int8_PipeOrgan_4096                     7840 ns      37238 ns 
BM_StableSort_int8_PipeOrgan_16384                   41402 ns      74805 ns 
BM_StableSort_int8_PipeOrgan_65536                  180107 ns     357891 ns 
BM_StableSort_int8_PipeOrgan_262144                 988273 ns    1647296 ns 
BM_StableSort_int8_PipeOrgan_524288                2547374 ns    3245991 ns 
BM_StableSort_int8_PipeOrgan_1048576               5128783 ns    7342444 ns 
BM_StableSort_int8_QuickSortAdversary_1               3.14 ns       4.01 ns 
BM_StableSort_int8_QuickSortAdversary_4               6.05 ns       7.02 ns 
BM_StableSort_int8_QuickSortAdversary_16              10.5 ns       11.9 ns 
BM_StableSort_int8_QuickSortAdversary_64               520 ns        516 ns 
BM_StableSort_int8_QuickSortAdversary_256              920 ns        386 ns 
BM_StableSort_int8_QuickSortAdversary_1024            3083 ns       2299 ns 
BM_StableSort_int8_QuickSortAdversary_4096           11659 ns      12295 ns 
BM_StableSort_int8_QuickSortAdversary_16384          45721 ns      60931 ns 
BM_StableSort_int8_QuickSortAdversary_65536         186334 ns     295423 ns 
BM_StableSort_int8_QuickSortAdversary_262144        946262 ns    1399973 ns 
BM_StableSort_int8_QuickSortAdversary_524288       2282004 ns    2832266 ns 
BM_StableSort_int8_QuickSortAdversary_1048576      4691123 ns    6963253 ns 
BM_StableSort_uint8_Random_1                          3.11 ns       3.44 ns 
BM_StableSort_uint8_Random_4                          21.9 ns       23.1 ns 
BM_StableSort_uint8_Random_16                          154 ns        171 ns 
BM_StableSort_uint8_Random_64                         1000 ns       1051 ns 
BM_StableSort_uint8_Random_256                         402 ns       6498 ns 
BM_StableSort_uint8_Random_1024                       1176 ns      35310 ns 
BM_StableSort_uint8_Random_4096                       4415 ns     164087 ns 
BM_StableSort_uint8_Random_16384                     17849 ns     686769 ns 
BM_StableSort_uint8_Random_65536                    146109 ns    2932051 ns 
BM_StableSort_uint8_Random_262144                   876710 ns   12163988 ns 
BM_StableSort_uint8_Random_524288                  2858089 ns   26458830 ns 
BM_StableSort_uint8_Random_1048576                 5766942 ns   54836214 ns 
BM_StableSort_uint8_Ascending_1                       3.11 ns       3.43 ns 
BM_StableSort_uint8_Ascending_4                       6.18 ns       7.24 ns 
BM_StableSort_uint8_Ascending_16                      14.5 ns       17.0 ns 
BM_StableSort_uint8_Ascending_64                      50.7 ns       59.2 ns 
BM_StableSort_uint8_Ascending_256                      395 ns        536 ns 
BM_StableSort_uint8_Ascending_1024                    1752 ns       2956 ns 
BM_StableSort_uint8_Ascending_4096                    7785 ns      15146 ns 
BM_StableSort_uint8_Ascending_16384                  41442 ns      74136 ns 
BM_StableSort_uint8_Ascending_65536                 180879 ns     354261 ns 
BM_StableSort_uint8_Ascending_262144                945880 ns    1674256 ns 
BM_StableSort_uint8_Ascending_524288               2287832 ns    3138581 ns 
BM_StableSort_uint8_Ascending_1048576              4630290 ns    7296278 ns 
BM_StableSort_uint8_Descending_1                      3.19 ns       3.63 ns 
BM_StableSort_uint8_Descending_4                      9.60 ns       11.5 ns 
BM_StableSort_uint8_Descending_16                     78.3 ns       86.0 ns 
BM_StableSort_uint8_Descending_64                     1265 ns       1308 ns 
BM_StableSort_uint8_Descending_256                     395 ns       6556 ns 
BM_StableSort_uint8_Descending_1024                   1712 ns      24669 ns 
BM_StableSort_uint8_Descending_4096                   7748 ns      83407 ns 
BM_StableSort_uint8_Descending_16384                 40779 ns     104043 ns 
BM_StableSort_uint8_Descending_65536                181560 ns     467680 ns 
BM_StableSort_uint8_Descending_262144              1146627 ns    2102769 ns 
BM_StableSort_uint8_Descending_524288              2874096 ns    4572229 ns 
BM_StableSort_uint8_Descending_1048576             5873195 ns   10170663 ns 
BM_StableSort_uint8_SingleElement_1                   3.28 ns       3.58 ns 
BM_StableSort_uint8_SingleElement_4                   6.44 ns       7.40 ns 
BM_StableSort_uint8_SingleElement_16                  14.9 ns       16.4 ns 
BM_StableSort_uint8_SingleElement_64                  51.2 ns       52.9 ns 
BM_StableSort_uint8_SingleElement_256                  876 ns        490 ns 
BM_StableSort_uint8_SingleElement_1024                3041 ns       2750 ns 
BM_StableSort_uint8_SingleElement_4096               11947 ns      14326 ns 
BM_StableSort_uint8_SingleElement_16384              46669 ns      69984 ns 
BM_StableSort_uint8_SingleElement_65536             197903 ns     328961 ns 
BM_StableSort_uint8_SingleElement_262144           1031466 ns    1551436 ns 
BM_StableSort_uint8_SingleElement_524288           2447672 ns    3049553 ns 
BM_StableSort_uint8_SingleElement_1048576          4793087 ns    7615245 ns 
BM_StableSort_uint8_PipeOrgan_1                       3.38 ns       3.56 ns 
BM_StableSort_uint8_PipeOrgan_4                       7.16 ns       8.70 ns 
BM_StableSort_uint8_PipeOrgan_16                      31.7 ns       35.3 ns 
BM_StableSort_uint8_PipeOrgan_64                       326 ns        366 ns 
BM_StableSort_uint8_PipeOrgan_256                      409 ns       2942 ns 
BM_StableSort_uint8_PipeOrgan_1024                    1994 ns      12571 ns 
BM_StableSort_uint8_PipeOrgan_4096                    8086 ns      46278 ns 
BM_StableSort_uint8_PipeOrgan_16384                  41749 ns      79813 ns 
BM_StableSort_uint8_PipeOrgan_65536                 180697 ns     375120 ns 
BM_StableSort_uint8_PipeOrgan_262144               1004899 ns    1676143 ns 
BM_StableSort_uint8_PipeOrgan_524288               2456081 ns    3333949 ns 
BM_StableSort_uint8_PipeOrgan_1048576              5030857 ns    7591303 ns 
BM_StableSort_uint8_QuickSortAdversary_1              3.12 ns       3.46 ns 
BM_StableSort_uint8_QuickSortAdversary_4              7.25 ns       6.83 ns 
BM_StableSort_uint8_QuickSortAdversary_16             14.6 ns       16.2 ns 
BM_StableSort_uint8_QuickSortAdversary_64              650 ns        665 ns 
BM_StableSort_uint8_QuickSortAdversary_256             395 ns       2982 ns 
BM_StableSort_uint8_QuickSortAdversary_1024           3125 ns       2583 ns 
BM_StableSort_uint8_QuickSortAdversary_4096          11797 ns      13929 ns 
BM_StableSort_uint8_QuickSortAdversary_16384         45803 ns      66513 ns 
BM_StableSort_uint8_QuickSortAdversary_65536        190745 ns     313467 ns 
BM_StableSort_uint8_QuickSortAdversary_262144       974646 ns    1469014 ns 
BM_StableSort_uint8_QuickSortAdversary_524288      2317553 ns    3022065 ns 
BM_StableSort_uint8_QuickSortAdversary_1048576     4898703 ns    6854079 ns 
BM_StableSort_int16_Random_1                          3.94 ns       3.49 ns 
BM_StableSort_int16_Random_4                          20.8 ns       23.2 ns 
BM_StableSort_int16_Random_16                          133 ns        163 ns 
BM_StableSort_int16_Random_64                          903 ns        953 ns 
BM_StableSort_int16_Random_256                        5638 ns       6258 ns 
BM_StableSort_int16_Random_1024                       3056 ns      34587 ns 
BM_StableSort_int16_Random_4096                      10596 ns     168397 ns 
BM_StableSort_int16_Random_16384                     49908 ns     753031 ns 
BM_StableSort_int16_Random_65536                    444605 ns    3838368 ns 
BM_StableSort_int16_Random_262144                  2419345 ns   15657285 ns 
BM_StableSort_int16_Random_524288                  7984040 ns   32726933 ns 
BM_StableSort_int16_Random_1048576                16092424 ns   67999766 ns 
BM_StableSort_int16_Ascending_1                       3.40 ns       3.43 ns 
BM_StableSort_int16_Ascending_4                       5.45 ns       5.79 ns 
BM_StableSort_int16_Ascending_16                      12.0 ns       15.3 ns 
BM_StableSort_int16_Ascending_64                      39.6 ns       52.6 ns 
BM_StableSort_int16_Ascending_256                      470 ns        550 ns 
BM_StableSort_int16_Ascending_1024                    1686 ns       2707 ns 
BM_StableSort_int16_Ascending_4096                    5676 ns      14165 ns 
BM_StableSort_int16_Ascending_16384                  21413 ns      69483 ns 
BM_StableSort_int16_Ascending_65536                  88010 ns     334466 ns 
BM_StableSort_int16_Ascending_262144                567239 ns    1570620 ns 
BM_StableSort_int16_Ascending_524288               1553063 ns    3424666 ns 
BM_StableSort_int16_Ascending_1048576              3145577 ns    8499649 ns 
BM_StableSort_int16_Descending_1                      3.22 ns       3.54 ns 
BM_StableSort_int16_Descending_4                      6.85 ns       10.2 ns 
BM_StableSort_int16_Descending_16                     62.7 ns       62.2 ns 
BM_StableSort_int16_Descending_64                     1138 ns       1036 ns 
BM_StableSort_int16_Descending_256                    5541 ns       4696 ns 
BM_StableSort_int16_Descending_1024                   3046 ns      19577 ns 
BM_StableSort_int16_Descending_4096                  10962 ns      79149 ns 
BM_StableSort_int16_Descending_16384                 58182 ns     327709 ns 
BM_StableSort_int16_Descending_65536                447025 ns    1424896 ns 
BM_StableSort_int16_Descending_262144              1104973 ns    5921903 ns 
BM_StableSort_int16_Descending_524288              2547840 ns   17956789 ns 
BM_StableSort_int16_Descending_1048576             5093555 ns   17044318 ns 
BM_StableSort_int16_SingleElement_1                   3.56 ns       3.96 ns 
BM_StableSort_int16_SingleElement_4                   5.75 ns       6.72 ns 
BM_StableSort_int16_SingleElement_16                  12.4 ns       16.1 ns 
BM_StableSort_int16_SingleElement_64                  36.9 ns       54.4 ns 
BM_StableSort_int16_SingleElement_256                  473 ns        557 ns 
BM_StableSort_int16_SingleElement_1024                1828 ns       2826 ns 
BM_StableSort_int16_SingleElement_4096                6239 ns      14252 ns 
BM_StableSort_int16_SingleElement_16384              23695 ns      70369 ns 
BM_StableSort_int16_SingleElement_65536              93281 ns     361641 ns 
BM_StableSort_int16_SingleElement_262144            599078 ns    1640216 ns 
BM_StableSort_int16_SingleElement_524288           1659678 ns    3343087 ns 
BM_StableSort_int16_SingleElement_1048576          3184033 ns    7770271 ns 
BM_StableSort_int16_PipeOrgan_1                       3.75 ns       3.76 ns 
BM_StableSort_int16_PipeOrgan_4                       5.94 ns       7.74 ns 
BM_StableSort_int16_PipeOrgan_16                      26.7 ns       25.9 ns 
BM_StableSort_int16_PipeOrgan_64                       300 ns        263 ns 
BM_StableSort_int16_PipeOrgan_256                     2769 ns       2760 ns 
BM_StableSort_int16_PipeOrgan_1024                    2996 ns      10544 ns 
BM_StableSort_int16_PipeOrgan_4096                   11641 ns      44750 ns 
BM_StableSort_int16_PipeOrgan_16384                  57224 ns     200464 ns 
BM_StableSort_int16_PipeOrgan_65536                 416873 ns     887631 ns 
BM_StableSort_int16_PipeOrgan_262144                843264 ns    3588669 ns 
BM_StableSort_int16_PipeOrgan_524288               2027741 ns   11056924 ns 
BM_StableSort_int16_PipeOrgan_1048576              4223773 ns   13261276 ns 
BM_StableSort_int16_QuickSortAdversary_1              3.83 ns       3.68 ns 
BM_StableSort_int16_QuickSortAdversary_4              5.55 ns       6.93 ns 
BM_StableSort_int16_QuickSortAdversary_16             12.3 ns       15.2 ns 
BM_StableSort_int16_QuickSortAdversary_64              646 ns        632 ns 
BM_StableSort_int16_QuickSortAdversary_256            2751 ns       2542 ns 
BM_StableSort_int16_QuickSortAdversary_1024           3028 ns      16901 ns 
BM_StableSort_int16_QuickSortAdversary_4096          10862 ns      80222 ns 
BM_StableSort_int16_QuickSortAdversary_16384         57753 ns     317281 ns 
BM_StableSort_int16_QuickSortAdversary_65536         94064 ns     328502 ns 
BM_StableSort_int16_QuickSortAdversary_262144       557796 ns    1613208 ns 
BM_StableSort_int16_QuickSortAdversary_524288      1518451 ns    3479740 ns 
BM_StableSort_int16_QuickSortAdversary_1048576     3165129 ns    7655880 ns 
BM_StableSort_uint16_Random_1                         3.26 ns       3.44 ns 
BM_StableSort_uint16_Random_4                         21.1 ns       22.2 ns 
BM_StableSort_uint16_Random_16                         157 ns        156 ns 
BM_StableSort_uint16_Random_64                         955 ns        947 ns 
BM_StableSort_uint16_Random_256                       5886 ns       6097 ns 
BM_StableSort_uint16_Random_1024                      2787 ns      30776 ns 
BM_StableSort_uint16_Random_4096                      9973 ns     155652 ns 
BM_StableSort_uint16_Random_16384                    48628 ns     741072 ns 
BM_StableSort_uint16_Random_65536                   439609 ns    3478966 ns 
BM_StableSort_uint16_Random_262144                 2336983 ns   15197642 ns 
BM_StableSort_uint16_Random_524288                 7888701 ns   34234254 ns 
BM_StableSort_uint16_Random_1048576               14865180 ns   68516386 ns 
BM_StableSort_uint16_Ascending_1                      3.33 ns       4.00 ns 
BM_StableSort_uint16_Ascending_4                      5.79 ns       6.64 ns 
BM_StableSort_uint16_Ascending_16                     14.9 ns       15.5 ns 
BM_StableSort_uint16_Ascending_64                     50.2 ns       52.5 ns 
BM_StableSort_uint16_Ascending_256                     538 ns        546 ns 
BM_StableSort_uint16_Ascending_1024                   1645 ns       2652 ns 
BM_StableSort_uint16_Ascending_4096                   5559 ns      14517 ns 
BM_StableSort_uint16_Ascending_16384                 22803 ns      70275 ns 
BM_StableSort_uint16_Ascending_65536                 83109 ns     333446 ns 
BM_StableSort_uint16_Ascending_262144               562667 ns    1568670 ns 
BM_StableSort_uint16_Ascending_524288              1564646 ns    3059839 ns 
BM_StableSort_uint16_Ascending_1048576             3178826 ns    7048327 ns 
BM_StableSort_uint16_Descending_1                     3.34 ns       3.93 ns 
BM_StableSort_uint16_Descending_4                     8.75 ns       9.73 ns 
BM_StableSort_uint16_Descending_16                    55.9 ns       55.5 ns 
BM_StableSort_uint16_Descending_64                    1021 ns       1035 ns 
BM_StableSort_uint16_Descending_256                   4752 ns       4931 ns 
BM_StableSort_uint16_Descending_1024                  2982 ns      19727 ns 
BM_StableSort_uint16_Descending_4096                 10432 ns      83165 ns 
BM_StableSort_uint16_Descending_16384                56593 ns     326131 ns 
BM_StableSort_uint16_Descending_65536               439134 ns    1371346 ns 
BM_StableSort_uint16_Descending_262144             1220925 ns    5735665 ns 
BM_StableSort_uint16_Descending_524288             2767234 ns   16758330 ns 
BM_StableSort_uint16_Descending_1048576            5673769 ns   17541715 ns 
BM_StableSort_uint16_SingleElement_1                  3.53 ns       3.73 ns 
BM_StableSort_uint16_SingleElement_4                  6.27 ns       5.81 ns 
BM_StableSort_uint16_SingleElement_16                 14.8 ns       15.1 ns 
BM_StableSort_uint16_SingleElement_64                 51.5 ns       50.9 ns 
BM_StableSort_uint16_SingleElement_256                 536 ns        540 ns 
BM_StableSort_uint16_SingleElement_1024               1669 ns       2690 ns 
BM_StableSort_uint16_SingleElement_4096               5840 ns      14230 ns 
BM_StableSort_uint16_SingleElement_16384             22468 ns      68524 ns 
BM_StableSort_uint16_SingleElement_65536             89845 ns     332187 ns 
BM_StableSort_uint16_SingleElement_262144           590736 ns    1550868 ns 
BM_StableSort_uint16_SingleElement_524288          1573677 ns    3095703 ns 
BM_StableSort_uint16_SingleElement_1048576         3183421 ns    8251180 ns 
BM_StableSort_uint16_PipeOrgan_1                      3.70 ns       3.64 ns 
BM_StableSort_uint16_PipeOrgan_4                      7.01 ns       6.81 ns 
BM_StableSort_uint16_PipeOrgan_16                     25.7 ns       26.4 ns 
BM_StableSort_uint16_PipeOrgan_64                      283 ns        277 ns 
BM_StableSort_uint16_PipeOrgan_256                    2562 ns       2852 ns 
BM_StableSort_uint16_PipeOrgan_1024                   2863 ns      10892 ns 
BM_StableSort_uint16_PipeOrgan_4096                  10585 ns      45668 ns 
BM_StableSort_uint16_PipeOrgan_16384                 59151 ns     194358 ns 
BM_StableSort_uint16_PipeOrgan_65536                508579 ns     854692 ns 
BM_StableSort_uint16_PipeOrgan_262144               901294 ns    3606346 ns 
BM_StableSort_uint16_PipeOrgan_524288              2192498 ns   10449279 ns 
BM_StableSort_uint16_PipeOrgan_1048576             4204368 ns   11956606 ns 
BM_StableSort_uint16_QuickSortAdversary_1             3.20 ns       3.63 ns 
BM_StableSort_uint16_QuickSortAdversary_4             5.30 ns       6.38 ns 
BM_StableSort_uint16_QuickSortAdversary_16            14.5 ns       15.3 ns 
BM_StableSort_uint16_QuickSortAdversary_64             575 ns        611 ns 
BM_StableSort_uint16_QuickSortAdversary_256           2423 ns       2577 ns 
BM_StableSort_uint16_QuickSortAdversary_1024          2794 ns      16854 ns 
BM_StableSort_uint16_QuickSortAdversary_4096         10511 ns      75952 ns 
BM_StableSort_uint16_QuickSortAdversary_16384        56214 ns     333824 ns 
BM_StableSort_uint16_QuickSortAdversary_65536       422512 ns    1354867 ns 
BM_StableSort_uint16_QuickSortAdversary_262144      583301 ns    1564443 ns 
BM_StableSort_uint16_QuickSortAdversary_524288     1584319 ns    3265575 ns 
BM_StableSort_uint16_QuickSortAdversary_1048576    3197732 ns    7945245 ns 
BM_StableSort_int32_Random_1                          3.81 ns       3.70 ns 
BM_StableSort_int32_Random_4                          20.8 ns       23.4 ns 
BM_StableSort_int32_Random_16                          134 ns        161 ns 
BM_StableSort_int32_Random_64                          895 ns        984 ns 
BM_StableSort_int32_Random_256                        5640 ns       5897 ns 
BM_StableSort_int32_Random_1024                       6994 ns      32118 ns 
BM_StableSort_int32_Random_4096                      27367 ns     168960 ns 
BM_StableSort_int32_Random_16384                    183261 ns     843240 ns 
BM_StableSort_int32_Random_65536                    950914 ns    3953588 ns 
BM_StableSort_int32_Random_262144                  3673311 ns   16790171 ns 
BM_StableSort_int32_Random_524288                 11515700 ns   36023098 ns 
BM_StableSort_int32_Random_1048576                24492515 ns   78116028 ns 
BM_StableSort_int32_Ascending_1                       3.31 ns       4.48 ns 
BM_StableSort_int32_Ascending_4                       5.96 ns       6.99 ns 
BM_StableSort_int32_Ascending_16                      13.0 ns       16.0 ns 
BM_StableSort_int32_Ascending_64                      36.7 ns       53.0 ns 
BM_StableSort_int32_Ascending_256                      391 ns        471 ns 
BM_StableSort_int32_Ascending_1024                    2705 ns       2682 ns 
BM_StableSort_int32_Ascending_4096                    8773 ns      14231 ns 
BM_StableSort_int32_Ascending_16384                  34709 ns      70625 ns 
BM_StableSort_int32_Ascending_65536                 142907 ns     344482 ns 
BM_StableSort_int32_Ascending_262144                745483 ns    1591418 ns 
BM_StableSort_int32_Ascending_524288               1873701 ns    3190305 ns 
BM_StableSort_int32_Ascending_1048576              3851590 ns    7570095 ns 
BM_StableSort_int32_Descending_1                      3.22 ns       4.23 ns 
BM_StableSort_int32_Descending_4                      7.58 ns       11.2 ns 
BM_StableSort_int32_Descending_16                     63.9 ns       58.6 ns 
BM_StableSort_int32_Descending_64                     1133 ns       1017 ns 
BM_StableSort_int32_Descending_256                    4850 ns       4464 ns 
BM_StableSort_int32_Descending_1024                   7023 ns      18954 ns 
BM_StableSort_int32_Descending_4096                  28550 ns      75163 ns 
BM_StableSort_int32_Descending_16384                200880 ns     341104 ns 
BM_StableSort_int32_Descending_65536               1095910 ns    1398021 ns 
BM_StableSort_int32_Descending_262144              3818864 ns    5695486 ns 
BM_StableSort_int32_Descending_524288              5606779 ns   17593982 ns 
BM_StableSort_int32_Descending_1048576            16416366 ns   26649503 ns 
BM_StableSort_int32_SingleElement_1                   3.81 ns       3.71 ns 
BM_StableSort_int32_SingleElement_4                   6.57 ns       6.61 ns 
BM_StableSort_int32_SingleElement_16                  14.0 ns       15.8 ns 
BM_StableSort_int32_SingleElement_64                  38.7 ns       53.5 ns 
BM_StableSort_int32_SingleElement_256                  386 ns        554 ns 
BM_StableSort_int32_SingleElement_1024                2761 ns       3046 ns 
BM_StableSort_int32_SingleElement_4096                9179 ns      15188 ns 
BM_StableSort_int32_SingleElement_16384              34794 ns      70119 ns 
BM_StableSort_int32_SingleElement_65536             135190 ns     354755 ns 
BM_StableSort_int32_SingleElement_262144            760995 ns    1644072 ns 
BM_StableSort_int32_SingleElement_524288           1969575 ns    3343419 ns 
BM_StableSort_int32_SingleElement_1048576          4423816 ns    8346971 ns 
BM_StableSort_int32_PipeOrgan_1                       3.79 ns       3.63 ns 
BM_StableSort_int32_PipeOrgan_4                       6.21 ns       6.73 ns 
BM_StableSort_int32_PipeOrgan_16                      27.5 ns       26.0 ns 
BM_StableSort_int32_PipeOrgan_64                       291 ns        265 ns 
BM_StableSort_int32_PipeOrgan_256                     2557 ns       2518 ns 
BM_StableSort_int32_PipeOrgan_1024                    6765 ns      10976 ns 
BM_StableSort_int32_PipeOrgan_4096                   26373 ns      44537 ns 
BM_StableSort_int32_PipeOrgan_16384                 201466 ns     188582 ns 
BM_StableSort_int32_PipeOrgan_65536                1148533 ns     802368 ns 
BM_StableSort_int32_PipeOrgan_262144               2255177 ns    3477829 ns 
BM_StableSort_int32_PipeOrgan_524288               3947015 ns   10356637 ns 
BM_StableSort_int32_PipeOrgan_1048576             10274312 ns   16405366 ns 
BM_StableSort_int32_QuickSortAdversary_1              3.32 ns       4.36 ns 
BM_StableSort_int32_QuickSortAdversary_4              5.98 ns       7.44 ns 
BM_StableSort_int32_QuickSortAdversary_16             13.0 ns       16.3 ns 
BM_StableSort_int32_QuickSortAdversary_64              657 ns        616 ns 
BM_StableSort_int32_QuickSortAdversary_256            2569 ns       2483 ns 
BM_StableSort_int32_QuickSortAdversary_1024           6898 ns      19635 ns 
BM_StableSort_int32_QuickSortAdversary_4096          27092 ns      75108 ns 
BM_StableSort_int32_QuickSortAdversary_16384        190379 ns     316463 ns 
BM_StableSort_int32_QuickSortAdversary_65536       1109040 ns    1319018 ns 
BM_StableSort_int32_QuickSortAdversary_262144      4361925 ns    5472779 ns 
BM_StableSort_int32_QuickSortAdversary_524288      6528215 ns   17538983 ns 
BM_StableSort_int32_QuickSortAdversary_1048576    18345325 ns   27223926 ns 
BM_StableSort_uint32_Random_1                         3.67 ns       3.82 ns 
BM_StableSort_uint32_Random_4                         22.3 ns       21.8 ns 
BM_StableSort_uint32_Random_16                         155 ns        153 ns 
BM_StableSort_uint32_Random_64                         946 ns        976 ns 
BM_StableSort_uint32_Random_256                       5824 ns       6019 ns 
BM_StableSort_uint32_Random_1024                      4525 ns      32764 ns 
BM_StableSort_uint32_Random_4096                     17223 ns     158608 ns 
BM_StableSort_uint32_Random_16384                   134821 ns     748525 ns 
BM_StableSort_uint32_Random_65536                   716644 ns    3453325 ns 
BM_StableSort_uint32_Random_262144                 3628062 ns   16065414 ns 
BM_StableSort_uint32_Random_524288                10971334 ns   36567712 ns 
BM_StableSort_uint32_Random_1048576               22688377 ns   77533497 ns 
BM_StableSort_uint32_Ascending_1                      3.57 ns       3.44 ns 
BM_StableSort_uint32_Ascending_4                      5.73 ns       5.33 ns 
BM_StableSort_uint32_Ascending_16                     14.5 ns       14.0 ns 
BM_StableSort_uint32_Ascending_64                     50.3 ns       51.3 ns 
BM_StableSort_uint32_Ascending_256                     465 ns        467 ns 
BM_StableSort_uint32_Ascending_1024                   3042 ns       2530 ns 
BM_StableSort_uint32_Ascending_4096                   9842 ns      12207 ns 
BM_StableSort_uint32_Ascending_16384                 37994 ns      61726 ns 
BM_StableSort_uint32_Ascending_65536                148890 ns     294385 ns 
BM_StableSort_uint32_Ascending_262144               855080 ns    1422167 ns 
BM_StableSort_uint32_Ascending_524288              2154903 ns    3203018 ns 
BM_StableSort_uint32_Ascending_1048576             5002518 ns    7563817 ns 
BM_StableSort_uint32_Descending_1                     3.51 ns       3.40 ns 
BM_StableSort_uint32_Descending_4                     9.09 ns       7.95 ns 
BM_StableSort_uint32_Descending_16                    54.8 ns       74.4 ns 
BM_StableSort_uint32_Descending_64                    1003 ns       1305 ns 
BM_StableSort_uint32_Descending_256                   4545 ns       5300 ns 
BM_StableSort_uint32_Descending_1024                  4361 ns      21884 ns 
BM_StableSort_uint32_Descending_4096                 16018 ns      90534 ns 
BM_StableSort_uint32_Descending_16384               146274 ns     381943 ns 
BM_StableSort_uint32_Descending_65536               938248 ns    1536806 ns 
BM_StableSort_uint32_Descending_262144             3899300 ns    6387843 ns 
BM_StableSort_uint32_Descending_524288             5808157 ns   21959858 ns 
BM_StableSort_uint32_Descending_1048576           17520047 ns   26351912 ns 
BM_StableSort_uint32_SingleElement_1                  4.03 ns       3.97 ns 
BM_StableSort_uint32_SingleElement_4                  6.55 ns       6.41 ns 
BM_StableSort_uint32_SingleElement_16                 15.6 ns       15.8 ns 
BM_StableSort_uint32_SingleElement_64                 52.3 ns       58.7 ns 
BM_StableSort_uint32_SingleElement_256                 473 ns        485 ns 
BM_StableSort_uint32_SingleElement_1024               3020 ns       2407 ns 
BM_StableSort_uint32_SingleElement_4096               9998 ns      12527 ns 
BM_StableSort_uint32_SingleElement_16384             38072 ns      62228 ns 
BM_StableSort_uint32_SingleElement_65536            153706 ns     295662 ns 
BM_StableSort_uint32_SingleElement_262144           836532 ns    1477099 ns 
BM_StableSort_uint32_SingleElement_524288          2144900 ns    3157204 ns 
BM_StableSort_uint32_SingleElement_1048576         4995525 ns    7617233 ns 
BM_StableSort_uint32_PipeOrgan_1                      4.02 ns       3.99 ns 
BM_StableSort_uint32_PipeOrgan_4                      6.97 ns       6.84 ns 
BM_StableSort_uint32_PipeOrgan_16                     26.1 ns       29.7 ns 
BM_StableSort_uint32_PipeOrgan_64                      266 ns        333 ns 
BM_StableSort_uint32_PipeOrgan_256                    2462 ns       2892 ns 
BM_StableSort_uint32_PipeOrgan_1024                   4291 ns      12431 ns 
BM_StableSort_uint32_PipeOrgan_4096                  15638 ns      51449 ns 
BM_StableSort_uint32_PipeOrgan_16384                154563 ns     217460 ns 
BM_StableSort_uint32_PipeOrgan_65536                907724 ns     925873 ns 
BM_StableSort_uint32_PipeOrgan_262144              2394580 ns    4103575 ns 
BM_StableSort_uint32_PipeOrgan_524288              4177145 ns   13947158 ns 
BM_StableSort_uint32_PipeOrgan_1048576            11848224 ns   18807297 ns 
BM_StableSort_uint32_QuickSortAdversary_1             3.50 ns       3.43 ns 
BM_StableSort_uint32_QuickSortAdversary_4             5.88 ns       4.96 ns 
BM_StableSort_uint32_QuickSortAdversary_16            14.6 ns       14.0 ns 
BM_StableSort_uint32_QuickSortAdversary_64             576 ns        715 ns 
BM_StableSort_uint32_QuickSortAdversary_256           2353 ns       2797 ns 
BM_StableSort_uint32_QuickSortAdversary_1024          4176 ns      21775 ns 
BM_StableSort_uint32_QuickSortAdversary_4096         15565 ns      96188 ns 
BM_StableSort_uint32_QuickSortAdversary_16384       149092 ns     398332 ns 
BM_StableSort_uint32_QuickSortAdversary_65536       902488 ns    1552393 ns 
BM_StableSort_uint32_QuickSortAdversary_262144     3946517 ns    6560414 ns 
BM_StableSort_uint32_QuickSortAdversary_524288     6247114 ns   22420977 ns 
BM_StableSort_uint32_QuickSortAdversary_1048576   19892446 ns   26529576 ns 
BM_StableSort_int64_Random_1                          3.83 ns       3.98 ns 
BM_StableSort_int64_Random_4                          21.1 ns       24.0 ns 
BM_StableSort_int64_Random_16                          129 ns        136 ns 
BM_StableSort_int64_Random_64                          890 ns        906 ns 
BM_StableSort_int64_Random_256                        5542 ns       5901 ns 
BM_StableSort_int64_Random_1024                      16085 ns      33112 ns 
BM_StableSort_int64_Random_4096                      63895 ns     162181 ns 
BM_StableSort_int64_Random_16384                    348827 ns     790045 ns 
BM_StableSort_int64_Random_65536                   1488237 ns    3557506 ns 
BM_StableSort_int64_Random_262144                  8195713 ns   16315808 ns 
BM_StableSort_int64_Random_524288                 16586833 ns   38274075 ns 
BM_StableSort_int64_Random_1048576                40346644 ns   79182089 ns 
BM_StableSort_int64_Ascending_1                       3.76 ns       3.55 ns 
BM_StableSort_int64_Ascending_4                       5.82 ns       6.19 ns 
BM_StableSort_int64_Ascending_16                      11.7 ns       11.8 ns 
BM_StableSort_int64_Ascending_64                      32.9 ns       36.8 ns 
BM_StableSort_int64_Ascending_256                      415 ns        550 ns 
BM_StableSort_int64_Ascending_1024                    5352 ns       3347 ns 
BM_StableSort_int64_Ascending_4096                   17516 ns      19134 ns 
BM_StableSort_int64_Ascending_16384                  64147 ns      91099 ns 
BM_StableSort_int64_Ascending_65536                 322126 ns     434009 ns 
BM_StableSort_int64_Ascending_262144               1554669 ns    2057056 ns 
BM_StableSort_int64_Ascending_524288               3656527 ns    5016650 ns 
BM_StableSort_int64_Ascending_1048576             10469979 ns   12908613 ns 
BM_StableSort_int64_Descending_1                      4.09 ns       3.35 ns 
BM_StableSort_int64_Descending_4                      9.13 ns       8.01 ns 
BM_StableSort_int64_Descending_16                     76.8 ns       92.9 ns 
BM_StableSort_int64_Descending_64                     1336 ns       1417 ns 
BM_StableSort_int64_Descending_256                    5525 ns       5674 ns 
BM_StableSort_int64_Descending_1024                  17461 ns      22558 ns 
BM_StableSort_int64_Descending_4096                  64285 ns     102360 ns 
BM_StableSort_int64_Descending_16384                336946 ns     388940 ns 
BM_StableSort_int64_Descending_65536                837912 ns    1662169 ns 
BM_StableSort_int64_Descending_262144              3680806 ns    7494323 ns 
BM_StableSort_int64_Descending_524288             11023784 ns   24935033 ns 
BM_StableSort_int64_Descending_1048576            20023568 ns   33220712 ns 
BM_StableSort_int64_SingleElement_1                   3.37 ns       3.98 ns 
BM_StableSort_int64_SingleElement_4                   5.32 ns       6.92 ns 
BM_StableSort_int64_SingleElement_16                  10.9 ns       13.3 ns 
BM_StableSort_int64_SingleElement_64                  32.1 ns       43.8 ns 
BM_StableSort_int64_SingleElement_256                  420 ns        541 ns 
BM_StableSort_int64_SingleElement_1024                5689 ns       3381 ns 
BM_StableSort_int64_SingleElement_4096               19199 ns      17989 ns 
BM_StableSort_int64_SingleElement_16384              75754 ns      91963 ns 
BM_StableSort_int64_SingleElement_65536             357106 ns     500326 ns 
BM_StableSort_int64_SingleElement_262144           1672975 ns    2417734 ns 
BM_StableSort_int64_SingleElement_524288           3642891 ns    5200878 ns 
BM_StableSort_int64_SingleElement_1048576         11172007 ns   13729511 ns 
BM_StableSort_int64_PipeOrgan_1                       3.38 ns       3.94 ns 
BM_StableSort_int64_PipeOrgan_4                       5.73 ns       6.44 ns 
BM_StableSort_int64_PipeOrgan_16                      27.5 ns       29.0 ns 
BM_StableSort_int64_PipeOrgan_64                       310 ns        321 ns 
BM_StableSort_int64_PipeOrgan_256                     2761 ns       2918 ns 
BM_StableSort_int64_PipeOrgan_1024                   16105 ns      12525 ns 
BM_StableSort_int64_PipeOrgan_4096                   65289 ns      59990 ns 
BM_StableSort_int64_PipeOrgan_16384                 341757 ns     270636 ns 
BM_StableSort_int64_PipeOrgan_65536                 587452 ns    1126132 ns 
BM_StableSort_int64_PipeOrgan_262144               2837955 ns    5034180 ns 
BM_StableSort_int64_PipeOrgan_524288               6617313 ns   15267354 ns 
BM_StableSort_int64_PipeOrgan_1048576             15208796 ns   23162989 ns 
BM_StableSort_int64_QuickSortAdversary_1              3.77 ns       3.45 ns 
BM_StableSort_int64_QuickSortAdversary_4              5.55 ns       5.20 ns 
BM_StableSort_int64_QuickSortAdversary_16             12.5 ns       11.5 ns 
BM_StableSort_int64_QuickSortAdversary_64              646 ns        750 ns 
BM_StableSort_int64_QuickSortAdversary_256            2655 ns       3539 ns 
BM_StableSort_int64_QuickSortAdversary_1024          16373 ns      22349 ns 
BM_StableSort_int64_QuickSortAdversary_4096          62306 ns      97248 ns 
BM_StableSort_int64_QuickSortAdversary_16384        321755 ns     388084 ns 
BM_StableSort_int64_QuickSortAdversary_65536       1374694 ns    1596091 ns 
BM_StableSort_int64_QuickSortAdversary_262144      4374661 ns    6894139 ns 
BM_StableSort_int64_QuickSortAdversary_524288     12736074 ns   23932229 ns 
BM_StableSort_int64_QuickSortAdversary_1048576    22615219 ns   33355629 ns 
BM_StableSort_uint64_Random_1                         3.82 ns       3.49 ns 
BM_StableSort_uint64_Random_4                         22.4 ns       23.4 ns 
BM_StableSort_uint64_Random_16                         154 ns        146 ns 
BM_StableSort_uint64_Random_64                         924 ns        926 ns 
BM_StableSort_uint64_Random_256                       5864 ns       5913 ns 
BM_StableSort_uint64_Random_1024                      7168 ns      31746 ns 
BM_StableSort_uint64_Random_4096                     27668 ns     154224 ns 
BM_StableSort_uint64_Random_16384                   219526 ns     755205 ns 
BM_StableSort_uint64_Random_65536                   965251 ns    3490165 ns 
BM_StableSort_uint64_Random_262144                 6262162 ns   15889589 ns 
BM_StableSort_uint64_Random_524288                12530078 ns   36458581 ns 
BM_StableSort_uint64_Random_1048576               38462191 ns   75168445 ns 
BM_StableSort_uint64_Ascending_1                      3.30 ns       3.35 ns 
BM_StableSort_uint64_Ascending_4                      5.65 ns       5.84 ns 
BM_StableSort_uint64_Ascending_16                     14.7 ns       12.6 ns 
BM_StableSort_uint64_Ascending_64                     55.3 ns       34.6 ns 
BM_StableSort_uint64_Ascending_256                     513 ns        533 ns 
BM_StableSort_uint64_Ascending_1024                   5541 ns       3189 ns 
BM_StableSort_uint64_Ascending_4096                  17706 ns      20326 ns 
BM_StableSort_uint64_Ascending_16384                 66420 ns      93757 ns 
BM_StableSort_uint64_Ascending_65536                341425 ns     435016 ns 
BM_StableSort_uint64_Ascending_262144              1595691 ns    2088317 ns 
BM_StableSort_uint64_Ascending_524288              3808703 ns    5092832 ns 
BM_StableSort_uint64_Ascending_1048576            11060417 ns   13023250 ns 
BM_StableSort_uint64_Descending_1                     3.29 ns       3.35 ns 
BM_StableSort_uint64_Descending_4                     8.65 ns       7.92 ns 
BM_StableSort_uint64_Descending_16                    54.7 ns       80.2 ns 
BM_StableSort_uint64_Descending_64                    1028 ns       1307 ns 
BM_StableSort_uint64_Descending_256                   4521 ns       5635 ns 
BM_StableSort_uint64_Descending_1024                  7122 ns      23323 ns 
BM_StableSort_uint64_Descending_4096                 30538 ns      95892 ns 
BM_StableSort_uint64_Descending_16384               195565 ns     392721 ns 
BM_StableSort_uint64_Descending_65536               852002 ns    1720358 ns 
BM_StableSort_uint64_Descending_262144             3737884 ns    7484130 ns 
BM_StableSort_uint64_Descending_524288            11159345 ns   25690770 ns 
BM_StableSort_uint64_Descending_1048576           20648864 ns   33057383 ns 
BM_StableSort_uint64_SingleElement_1                  3.62 ns       4.10 ns 
BM_StableSort_uint64_SingleElement_4                  6.73 ns       6.64 ns 
BM_StableSort_uint64_SingleElement_16                 14.9 ns       11.3 ns 
BM_StableSort_uint64_SingleElement_64                 52.0 ns       33.0 ns 
BM_StableSort_uint64_SingleElement_256                 511 ns        582 ns 
BM_StableSort_uint64_SingleElement_1024               6499 ns       3287 ns 
BM_StableSort_uint64_SingleElement_4096              22190 ns      17616 ns 
BM_StableSort_uint64_SingleElement_16384             84378 ns      86885 ns 
BM_StableSort_uint64_SingleElement_65536            466257 ns     457144 ns 
BM_StableSort_uint64_SingleElement_262144          1993687 ns    2361999 ns 
BM_StableSort_uint64_SingleElement_524288          4759565 ns    5096771 ns 
BM_StableSort_uint64_SingleElement_1048576        12426111 ns   13468453 ns 
BM_StableSort_uint64_PipeOrgan_1                      3.73 ns       3.94 ns 
BM_StableSort_uint64_PipeOrgan_4                      7.18 ns       7.54 ns 
BM_StableSort_uint64_PipeOrgan_16                     25.2 ns       29.1 ns 
BM_StableSort_uint64_PipeOrgan_64                      260 ns        321 ns 
BM_StableSort_uint64_PipeOrgan_256                    2468 ns       2970 ns 
BM_StableSort_uint64_PipeOrgan_1024                   7025 ns      12912 ns 
BM_StableSort_uint64_PipeOrgan_4096                  28968 ns      53379 ns 
BM_StableSort_uint64_PipeOrgan_16384                194156 ns     239790 ns 
BM_StableSort_uint64_PipeOrgan_65536                599491 ns     993800 ns 
BM_StableSort_uint64_PipeOrgan_262144              2648585 ns    4689680 ns 
BM_StableSort_uint64_PipeOrgan_524288              7621109 ns   15401808 ns 
BM_StableSort_uint64_PipeOrgan_1048576            15608814 ns   23484821 ns 
BM_StableSort_uint64_QuickSortAdversary_1             3.38 ns       3.54 ns 
BM_StableSort_uint64_QuickSortAdversary_4             5.50 ns       6.03 ns 
BM_StableSort_uint64_QuickSortAdversary_16            14.2 ns       11.0 ns 
BM_StableSort_uint64_QuickSortAdversary_64             597 ns        688 ns 
BM_StableSort_uint64_QuickSortAdversary_256           2446 ns       2818 ns 
BM_StableSort_uint64_QuickSortAdversary_1024          7266 ns      20319 ns 
BM_StableSort_uint64_QuickSortAdversary_4096         31155 ns      89112 ns 
BM_StableSort_uint64_QuickSortAdversary_16384       201033 ns     390574 ns 
BM_StableSort_uint64_QuickSortAdversary_65536       871014 ns    1685639 ns 
BM_StableSort_uint64_QuickSortAdversary_262144     3978535 ns    7265830 ns 
BM_StableSort_uint64_QuickSortAdversary_524288    10279721 ns   25350004 ns 
BM_StableSort_uint64_QuickSortAdversary_1048576   20256585 ns   33054393 ns 
```
2025-01-09 19:02:35 +01:00
LoS
fb03ce7aad
[libc++] Fix test for vector data_const.pass.cpp (#122085)
The test contained some non-const accesses when we're really trying to test
that the method is const.
2025-01-09 11:22:46 -05:00
Peng Liu
6c06253b85
[libc++] Fix erroneous internal capacity evaluation in vector<bool> (#120577)
This PR fixes the erroneous internal capacity evaluation in
`vector<bool>`, which caused a subsequent SIGSEGV error when calling
`flip()` on `vector<bool>`. By fixing the internal capacity evaluation,
the SIGSEGV is automatically resolved.
2025-01-09 17:46:04 +08:00
Peng Liu
06673a9e9b
[libc++] Uglify non-standard member typedef const_reference in bitset (#121620)
According to
[[template.bitset.general]](https://eel.is/c++draft/template.bitset.general),
`std::bitset` is supposed to have only
one (public) member typedef, `reference`. However, libc++'s
implementation of `std::bitset` offers more that that. Specifically, it
offers a public typedef `const_reference` and two private typedefs
`size_type` and `difference_type`. These non-standard member typedefs,
despite being private, can cause potential ambiguities in name lookup in
user-defined classes, as demonstrated in issue #121618.

Fixing the public member typedef `const_reference` is straightforward:
we can simply replace it with an `__ugly_name` such as
`__const_reference`. However, fixing the private member typedefs
`size_type` and `difference_type` is not so straightforward as they are
required by the `__bit_iterator` class and the corresponding algorithms
optimized for `__bit_iterator`s (e.g., `ranges::fill`).
 
This PR fixes the member typedef `const_reference` by using uglified
name for it. Further work will be undertaken to address `size_type` and
`difference_type`.

Follows up #80706, #111127, and #112843,
2025-01-09 17:42:40 +08:00
James Y Knight
2b26ee6e79
[libcxx] Handle windows system error code mapping in std::error_code. (#93101)
The `std::error_code`/`std::error_category` functionality is designed to
support multiple error domains. On Unix, both system calls and libc
functions return the same error codes, and thus, libc++ today treats
`generic_category()` and `system_category()` as being equivalent.

However, on Windows, libc functions return `errno.h` error codes in the
`errno` global, but system calls return the very different `winerror.h`
error codes via `GetLastError()`.

As such, there is a need to map the winerror.h error codes into generic
errno codes. In libc++, however, the system_error facility does not
implement this mapping; instead the mapping is hidden inside libc++,
used directly by the std::filesystem implementation.

That has a few problems:

1. For std::filesystem APIs, the concrete windows error number is lost,
before users can see it. The intent of the distinction between
std::error_code and std::error_condition is that the error_code return
has the original (potentially more detailed) error code.

2. User-written code which calls Windows system APIs requires this same
mapping, so it also can also return error_code objects that other
(cross-platform) code can understand.

After this commit, an `error_code` with `generic_category()` is used to
report an error from `errno`, and, on Windows only, an `error_code` with
`system_category()` is used to report an error from `GetLastError()`. On
Unix, system_category remains identity-mapped to generic_category, but
is never used by libc++ itself.

The windows error code mapping is moved into system_error, so that
conversion of an `error_code` to `error_condition` correctly translates
the `system_category()` code into a `generic_category()` code, when
appropriate.

This allows code like:
`error_code(GetLastError(), system_category()) == errc::invalid_argument`
to work as expected -- as it does with MSVC STL.

(Continued from old phabricator review [D151493](https://reviews.llvm.org/D151493))
2025-01-08 17:34:48 -05:00
Peng Liu
71e9a48227
[libc++] Mark vector<bool>::at() as constexpr to conform to C++20 standard (#121848)
Closes #121844.
2025-01-07 16:41:58 -05:00
Damien L-G
fbd2365c46
[libc++] Improve coverage of std::atomic_ref<T>::exchange() (#121596)
Adapted from libcxx/test/std/atomics/atomics.types.generic/atomics.types.float/exchange.pass.cpp
as we did for testing other functionalities. Spotted that lapse in coverage when working on #121414.
2025-01-07 11:54:52 -05:00
Jannik Glückert
cb1c15639f
[libc++] Use copy_file_range for fs::copy (#109211)
This optimizes `std::filesystem::copy_file` to use the `copy_file_range`
syscall (Linux and FreeBSD) when available. It allows for reflinks on
filesystems such as btrfs, zfs and xfs, and server-side copy for network
filesystems such as NFS.
2025-01-06 15:38:30 -05:00
Konstantin Varlamov
ac1d560709
[libc++][hardening] Add a bounds check for valarray and bitset. (#120685)
Add a `valid-element-access` check to `valarray::operator[]` and
`bitset::operator[]`.
2024-12-24 18:22:18 -08:00
Nikolas Klauser
e8f1902cca
[libc++] Add a test to make sure the type traits derive from integral_constant (#120732) 2024-12-22 12:40:53 +01:00
Nikolas Klauser
21e6f16517 [libc++] Mark N4089 as complete
The paper has been implemented since at least LLVM 5, maybe earlier.
2024-12-22 03:43:27 +01:00
Nikolas Klauser
b9a2658a3e
[libc++][C++03] Use __cxx03/ headers in C++03 mode (#109002)
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.
2024-12-21 13:01:48 +01:00
Peng Liu
fafdf97047
[libc++] Simplify vector<bool>::flip() and add new tests (#119607)
This PR simplifies the internal bitwise logic of the `flip()` function
for `vector<bool>`, and creates new tests to validate the changes.
2024-12-19 11:48:51 -05:00
Peng Liu
4039a79de7
[libc++][test] Improve tests for assign in std::vector and vector<bool> (#119163)
This PR enhances the test coverage for std::vector::assign by adding new
tests for several important test cases that were previously missing, as
shown in the following table:

| test cases                        | forward_iterator | input_iterator |
|-----------------------------------|------------------|----------------|
| new_size > capacity()             | Yes              | Yes            |
| size() < new_size <= capacity()   | No               | No             |
| new_size <= size()                | No               | No             |

Similarly, no tests have previously covered `assign(InputIterator, InputIterator)`
and `assign(size_type, const value_type&)` for `vector<bool>`.

With this patch applied, all missing tests are covered.
2024-12-19 11:19:25 -05:00
Vitaly Buka
31272e4f83
[libc++] Update locale grouping tests (#119463)
Fixes #119047
2024-12-16 12:50:59 -05:00
Louis Dionne
4104906a23 [libc++] Revert new test for integral_constant that breaks CI
This commit reverts c3276a96d9 and 1901da32, which added a test to
ensure that type traits are derived from integral_constant. While that
is a fine test to add, the commit didn't go through a PR and as a result
it looks like some of our CI has been broken by it.

This should be an uncontroversial change, but let's re-land it via a PR
to get our usual CI coverage.
2024-12-16 10:41:16 -05:00
Nikolas Klauser
c3276a96d9 [libc++] Disable deprecation warnings in derived_from_integral_constant.compile.pass.cpp 2024-12-14 16:19:40 +01:00
Nikolas Klauser
1901da32a4 [libc++] Add a test to make sure all the type traits derived from bool_constant 2024-12-14 15:19:19 +01:00
Louis Dionne
9474e09459
[libc++] Granularize the <new> header (#119270)
This disentangles the code which previously had a mix of many #ifdefs, a
non-versioned namespace and a versioned namespace. It also makes it
clearer which parts of <new> are implemented on Windows by including <new.h>.
2024-12-13 14:17:56 -05:00
Louis Dionne
62bdb85f9b [libc++][NFC] Fix incorrect comment for vector::assign(iter, iter) test 2024-12-13 09:35:56 -05:00
Stephan T. Lavavej
cb4433b677
[libcxx][test] Silence nodiscard warnings for std::expected (#119174)
I'm exploring marking microsoft/STL's std::expected as [[nodiscard]],
which affects all functions returning std::expected, including its
own monadic member functions.

As usual, libc++'s test suite contains calls to these member functions
to make sure they compile, but it's discarding the returns. I'm adding
void casts to silence the [[nodiscard]] warnings without altering
what the test is covering.
2024-12-10 07:23:09 -05:00
Hui
f22ecdd9b9
[libc++] Move out flat_map::iterator (for reusing it in flat_multimap) (#117445) 2024-12-09 09:22:27 -05:00
Louis Dionne
6cb339f9c1
[libc++] Refactor tests for aligned allocation and sized deallocation (#117915)
This patch refactors the tests around aligned allocation and sized
deallocation to avoid relying on passing the -fsized-deallocation or
-faligned-allocation flags by default. Since both of these features are
enabled by default in >= C++14 mode, it now makes sense to make that
assumption in the test suite.

A notable exception is MinGW and some older compilers, where sized
deallocation is still not enabled by default. We treat that as a "bug"
in the test suite and we work around it by explicitly adding
-fsized-deallocation, but only under those configurations.
2024-12-06 16:12:30 -05:00
Louis Dionne
cd74ebaec6
[libc++] Make a few test helper constructors explicit (#118975) 2024-12-06 15:31:20 -05:00
Peng Liu
37797d3e80
[libc++][test] Fix and refactor exception tests for std::vector constructors (#117662)
The existing exceptions tests for `vector<T>` have several issues: some
tests did not throw exceptions at all, making them not useful for
exception-safety testing, and some tests did not throw exceptions at the
intended points, failing to serve their expected purpose. This PR fixes
those tests for vector's constructors. Morever, this PR extracted common
classes and utilities into a separate header file, and renamed those
classes using more descriptive names.
2024-12-06 09:03:17 -05:00
serge-sans-paille
f7ff3cde96
[libc++] Fix sub-overflow in std::gcd implementation (#117984)
Fix #117249
2024-12-06 07:57:49 +00:00
Peng Liu
a821937b6d
[libc++][test] Refactor increasing_allocator (#115671)
The increasing_allocator<T> class, originally introduced to test shrink_to_fit()
for std::vector, std::vector<bool>, and std::basic_string, has duplicated
definitions across several test files. Given the potential utility of this
class for capacity-related tests in various sequence containers, this patch
refactors the definition of increasing_allocator<T> into a single, reusable
location.
2024-12-05 15:44:05 -05:00
Peng Liu
c5cd1e958c
[libc++] Add exception guard for vector<bool>::__init_with_sentinel (#115491)
As a drive-by, also improve the test coverage for throwing exceptions
in vector<bool> constructors.
2024-11-28 09:09:54 -05:00
Peng Liu
5ce981e76d
[libc++] Refactor vector move constructor with allocator (#116449)
This PR simplifies the implementation of std::vector's move constructor
with an alternative allocator by invoking __init_with_size() instead of
calling assign(), which ultimately calls __assign_with_size(). The
advantage of using __init_with_size() lies in its internal use of
an exception guard, which simplifies the code. Furthermore, from a
semantic standpoint, it is more intuitive for a constructor to call
an initialization function than an assignment function.
2024-11-26 16:00:14 -05:00
Louis Dionne
44ef12b020
[libc++] Refactor tests for hijacked address operator in vector (#117457)
This reduces the amount of boilerplate needed to implement the tests.
2024-11-26 14:33:56 -05:00
vannem-sj
c7d5ef420d
[libc++] Rename operator[].pass.cpp to subscript_operator.pass.cpp (#117216)
This filename includes non FAT32 legal characters, and has caused a few
issues with glob tools that don't escape brackets properly.
2024-11-22 15:49:09 +01:00
Louis Dionne
a9882bda96
[libc++] Mark charconv test as unsupported under msan (#116933) 2024-11-22 09:05:08 +01:00
Nikolas Klauser
9ebc6f5d6d
[libc++] Include headers in <thread> conditionally (#116539) 2024-11-20 23:07:20 +01:00
Ryan Prichard
8f53a67bb8
[libc++][Android] Allow testing libc++ with clang-r536225 (#116149)
The Android clang-r536225 compiler identifies as Clang 19, but it is
based on commit fc57f88f007497a4ead0ec8607ac66e1847b02d6, which predates
the official LLVM 19.0.0 release.

Some tests need fixes:

* The sized delete tests fail because clang-r536225 leaves sized
deallocation off by default.

* std::array<T[0]> is true when this Android Clang version is used with
a trunk libc++, but we expect it to be false in the test. In practice,
Clang and libc++ usually come from the same commit on Android.
2024-11-20 14:06:58 -08:00
Nikolas Klauser
01a1ca72e8 [libc++][NFC] Format a pait test
I'll be modifying this test in a future PR.
2024-11-19 13:53:43 +01:00
Louis Dionne
3a3517c5e9
[libc++] Improve the tests for vector::erase (#116265)
In particular, test everything with both a normal and a min_allocator,
add tests for a few corner cases and add tests with types that are
trivially relocatable. Also add tests that count the number of
assignments performed by vector::erase, since that is mandated by the
Standard.

This patch is a preparation for optimizing vector::erase.
2024-11-19 00:49:22 +01:00
Nikolas Klauser
85ef9666c8
[libc++] Avoid including all of <thread> in <future> (#116541) 2024-11-18 20:04:05 +01:00
Nikolas Klauser
1636580b0a
[libc++] Avoid including <ostream> in <fstream> and <strstream> (#116014)
This reduces the include time of `<fstream>` from ~800ms to ~500ms.
2024-11-16 18:19:17 +01:00
Louis Dionne
2d6459cb28
[libc++] Fix CI issues recently introduced by localization changes (#116216)
After a recent Github Actions runner policy change [1], the version of
Xcode included in the macos-14 image went from Xcode 16 to Xcode 15,
breaking our build bots.

This moves the bots to the macos 15 (public preview) image, which
contains Xcode 16.

Also, adjust an UNSUPPORTED annotation that was incorrectly targeting
macos 13.7 when it should have been targeting a version of AppleClang.

[1]: https://github.com/actions/runner-images/issues/10703
2024-11-15 00:00:54 +01:00
Louis Dionne
965f3a95b9 [libc++][NFC] Run clang-format on vector::erase test
Since I am about to make significant changes to this test, run clang-format
on it before to avoid obscuring the review.
2024-11-14 14:13:51 +01:00
Louis Dionne
9c3a7ad7fa
[libc++] Cleanly implement the base locale API for BSD-like platforms (#115176)
Instead of going through the old locale entry points, define the base
localization API for BSD-like platforms (Apple and FreeBSD) from
scratch, using <xlocale.h> as a basis. This doesn't actually change how
that functionality is implemented, it only avoids going through a maze
to do so.

This clean new support is implemented in a separate __locale_dir/support
directory, which mirrors what we do for the threading support API.
Eventually, everything under __locale_dir/locale_base_api will go away.

rdar://131476632
2024-11-11 13:11:23 -05:00
A. Jiang
9fd3c4115c
[libc++] Fix unexpected heterogeneous comparison (#115249)
Currently, libc++ incorrectly rejects heterogeneous comparison of
`unexpected`, because the `operator==` is only a hidden friend of
`unexpected<_Err>` but not of `unexpected<_Err2>`. We need to call the
`error()` member function on `__y`.

Fixes #115326
2024-11-07 11:49:29 -05:00
Louis Dionne
427a5cf105
[libc++] Add support for bounded iterators in std::array (#110729)
This patch introduces a new kind of bounded iterator that knows the size
of its valid range at compile-time, as in std::array. This allows computing
the end of the range from the start of the range and the size, which requires
storing only the start of the range in the iterator instead of both the start
and the size (or start and end). The iterator wrapper is otherwise identical
in design to the existing __bounded_iter.

Since this requires changing the type of the iterators returned by
std::array, this new bounded iterator is controlled by an ABI flag.

As a drive-by, centralize the tests for std::array::operator[] and add
missing tests for OOB operator[] on non-empty arrays.

Fixes #70864
2024-11-07 09:23:21 -05:00
Nikolas Klauser
c6f3b7bcd0
[libc++] Refactor the configuration macros to being always defined (#112094)
This is a follow-up to #89178. This updates the `<__config_site>`
macros.
2024-11-06 10:39:19 +01:00
Nikolas Klauser
5acc4a3dc0
[libc++] Remove <stddef.h> includes from the granularized <cstddef> headers (#114788)
We can define some of these aliases without having to include the system
<stddef.h> and there doesn't seem to be much of a reason we shouldn't do
it this way.
2024-11-06 10:38:19 +01:00
Peng Liu
07443e9776
[libc++][test] Improve ThrowingT to Accurately Throw after throw_after > 1 Use (#114077)
This PR fixes the `ThrowingT` class, which currently fails to raise
exceptions after a specified number of copy construction operations. The
class is intended to throw in a controlled manner based on a specified
counter value `throw_after`. However, its current implementation of the
copy constructor fails to achieve this goal.

The problem arises because the copy constructor does not initialize the
`throw_after_n_` member, leaving `throw_after_n_` to default to `nullptr`
as defined by the in-class initializer. As a result, its copy constructor
always checks against `nullptr`, causing an immediate exception rather
than throwing after the specified number `throw_after` of uses. The fix
is straightforward: simply initialize the `throw_after_n_` member in the
member initializer list.

This issue was previously uncovered because all exception tests for
`std::vector` in `exceptions.pass.cpp` used a `throw_after` value of 1,
which coincidentally aligned with the class's behavior.
2024-11-05 11:24:05 -05:00
A. Jiang
76b71c0bc4
[libc++] Set __cpp_lib_smart_ptr_for_overwrite (#114700)
The features were implemented in LLVM 16, but mistakenly considered
unimplemented in FTM tools.
2024-11-05 13:27:40 +08:00
Joseph Huber
95a2eb70cf
[libcxx] Add testing configuration for GPU targets (#104515)
Summary:
The GPU runs these tests using the files built from the `libc` project.
These will be placed in `include/<triple>` and `lib/<triple>`. We use
the `amdhsa-loader` and `nvptx-loader` tools, which are also provided by
`libc`. These launch a kernel called `_start` which calls `main` so we
can pretend like GPU programs are normal terminal applications.

We force serial exeuction here, because `llvm-lit` runs way too many
processes in parallel, which has a bad habit of making the GPU drivers
hang or run out of resources. This allows the compilation to be run in
parallel while the jobs themselves are serialized via a file lock.

In the future this can likely be refined to accept user specified
architectures, or better handle including the root directory by exposing
that instead of just `include/<triple>/c++/v1/`.

This currently fails ~1% of the tests on AMDGPU and ~3% of the tests on
NVPTX. This will hopefully be reduced further, and later patches can
XFAIL a lot of them once it's down to a reasonable number.

Future support will likely want to allow passing in a custom
architecture instead of simply relying on `-mcpu=native`.
2024-11-04 12:58:23 -06:00