Modify std::sort: add BlockQuickSort partitioning algorithm for arithmetic types

[nilayvaish]

Summary

This diff modifies std::sort in two ways:

• for arithmetic types we update the core partitioning algorithm to use BlockQuickSort for partitioning. The partition function was carefully written to let the compiler generates SIMD instructions without actually writing SIMD intrinsics in the loop. We see up to 50% better performance for sorting arithmetic types. The use of the BlockQuickSort partitioning has been limited to arithmetic types since the algorithm works well when branch instructions can be avoided during partitioning. This usually not true for types other than the arithmetic ones.

• for other types (tuples, strings) updates have been made to improve performance by about 10%.

Performance numbers comparing std::sort (old) and Bitset sort (new) on libcxx benchmark.

name                                                             old cpu/op  new cpu/op  delta
BM_Sort_uint32_Random_1                                          3.72ns ± 5%  3.78ns ±16%      ~     (p=0.819 n=36+34)
BM_Sort_uint32_Random_4                                          5.42ns ± 5%  5.29ns ± 7%    -2.42%  (p=0.000 n=35+31)
BM_Sort_uint32_Random_16                                         10.5ns ± 3%  11.9ns ±15%   +13.08%  (p=0.000 n=36+40)
BM_Sort_uint32_Random_64                                         18.6ns ± 7%  18.5ns ±15%    -0.95%  (p=0.002 n=33+40)
BM_Sort_uint32_Random_256                                        26.2ns ± 4%  21.3ns ± 8%   -18.89%  (p=0.000 n=37+34)
BM_Sort_uint32_Random_1024                                       33.4ns ± 5%  23.3ns ± 4%   -30.37%  (p=0.000 n=39+35)
BM_Sort_uint32_Random_16384                                      47.7ns ± 5%  26.7ns ± 5%   -44.06%  (p=0.000 n=39+35)
BM_Sort_uint32_Random_262144                                     62.6ns ± 3%  30.1ns ± 6%   -51.81%  (p=0.000 n=37+36)
BM_Sort_uint32_Ascending_1                                       3.71ns ± 3%  4.28ns ± 3%   +15.53%  (p=0.000 n=37+35)
BM_Sort_uint32_Ascending_4                                       1.47ns ± 3%  1.46ns ± 3%      ~     (p=0.083 n=36+37)
BM_Sort_uint32_Ascending_16                                      0.93ns ± 4%  1.02ns ± 3%    +9.32%  (p=0.000 n=36+36)
BM_Sort_uint32_Ascending_64                                      1.23ns ± 5%  1.51ns ± 3%   +22.56%  (p=0.000 n=34+36)
BM_Sort_uint32_Ascending_256                                     1.21ns ± 3%  1.57ns ± 4%   +29.77%  (p=0.000 n=33+35)
BM_Sort_uint32_Ascending_1024                                    1.03ns ± 4%  1.43ns ± 3%   +38.44%  (p=0.000 n=32+35)
BM_Sort_uint32_Ascending_16384                                   0.94ns ± 8%  1.36ns ± 5%   +44.09%  (p=0.000 n=32+35)
BM_Sort_uint32_Ascending_262144                                  0.93ns ± 3%  1.35ns ± 7%   +45.06%  (p=0.000 n=32+36)
BM_Sort_uint32_Descending_1                                      3.69ns ± 2%  4.27ns ± 3%   +15.73%  (p=0.000 n=31+36)
BM_Sort_uint32_Descending_4                                      1.74ns ± 2%  1.78ns ± 3%    +2.29%  (p=0.000 n=31+38)
BM_Sort_uint32_Descending_16                                     3.92ns ± 4%  4.20ns ± 4%    +7.13%  (p=0.000 n=32+38)
BM_Sort_uint32_Descending_64                                     2.09ns ± 4%  3.25ns ± 4%   +55.10%  (p=0.000 n=33+37)
BM_Sort_uint32_Descending_256                                    1.98ns ± 7%  2.93ns ± 4%   +47.95%  (p=0.000 n=34+36)
BM_Sort_uint32_Descending_1024                                   2.23ns ± 6%  2.64ns ± 3%   +18.22%  (p=0.000 n=34+38)
BM_Sort_uint32_Descending_16384                                  1.93ns ± 6%  2.43ns ± 4%   +25.99%  (p=0.000 n=34+35)
BM_Sort_uint32_Descending_262144                                 1.89ns ± 3%  2.38ns ± 4%   +25.41%  (p=0.000 n=33+35)
BM_Sort_uint32_SingleElement_1                                   3.67ns ± 2%  4.28ns ± 4%   +16.60%  (p=0.000 n=34+34)
BM_Sort_uint32_SingleElement_4                                   1.48ns ± 4%  1.48ns ± 5%      ~     (p=0.951 n=35+33)
BM_Sort_uint32_SingleElement_16                                  0.93ns ± 3%  1.02ns ± 4%    +9.51%  (p=0.000 n=36+33)
BM_Sort_uint32_SingleElement_64                                  0.76ns ± 3%  1.59ns ± 8%  +109.78%  (p=0.000 n=36+32)
BM_Sort_uint32_SingleElement_256                                 0.82ns ± 4%  1.45ns ± 5%   +76.62%  (p=0.000 n=37+34)
BM_Sort_uint32_SingleElement_1024                                0.77ns ± 4%  1.31ns ± 4%   +71.40%  (p=0.000 n=34+34)
BM_Sort_uint32_SingleElement_16384                               0.64ns ± 4%  1.24ns ± 6%   +93.29%  (p=0.000 n=35+36)
BM_Sort_uint32_SingleElement_262144                              0.63ns ± 3%  1.23ns ± 4%   +95.17%  (p=0.000 n=35+35)
BM_Sort_uint32_PipeOrgan_1                                       3.68ns ± 2%  4.42ns ± 3%   +20.31%  (p=0.000 n=34+36)
BM_Sort_uint32_PipeOrgan_4                                       1.54ns ± 3%  1.53ns ± 3%      ~     (p=0.128 n=34+36)
BM_Sort_uint32_PipeOrgan_16                                      2.22ns ± 3%  1.99ns ± 3%   -10.28%  (p=0.000 n=33+36)
BM_Sort_uint32_PipeOrgan_64                                      4.41ns ± 3%  3.39ns ± 4%   -23.17%  (p=0.000 n=35+37)
BM_Sort_uint32_PipeOrgan_256                                     2.75ns ± 5%  3.07ns ± 3%   +11.74%  (p=0.000 n=37+37)
BM_Sort_uint32_PipeOrgan_1024                                    3.58ns ± 2%  5.48ns ± 3%   +52.97%  (p=0.000 n=37+36)
BM_Sort_uint32_PipeOrgan_16384                                   4.10ns ± 3%  6.53ns ± 3%   +59.27%  (p=0.000 n=37+37)
BM_Sort_uint32_PipeOrgan_262144                                  4.90ns ± 3%  7.39ns ± 3%   +50.71%  (p=0.000 n=34+37)
BM_Sort_uint32_QuickSortAdversary_1                              3.68ns ± 2%  4.28ns ± 3%   +16.19%  (p=0.000 n=36+37)
BM_Sort_uint32_QuickSortAdversary_4                              1.46ns ± 4%  1.46ns ± 3%      ~     (p=0.736 n=35+38)
BM_Sort_uint32_QuickSortAdversary_16                             0.93ns ± 3%  1.02ns ± 4%    +9.69%  (p=0.000 n=36+37)
BM_Sort_uint32_QuickSortAdversary_64                             13.6ns ± 4%  17.9ns ± 8%   +31.37%  (p=0.000 n=36+35)
BM_Sort_uint32_QuickSortAdversary_256                            20.0ns ± 4%  25.7ns ± 4%   +28.69%  (p=0.000 n=36+35)
BM_Sort_uint32_QuickSortAdversary_1024                           28.3ns ± 6%  31.7ns ± 3%   +12.12%  (p=0.000 n=36+37)
BM_Sort_uint32_QuickSortAdversary_16384                          45.8ns ± 3%  50.6ns ± 4%   +10.32%  (p=0.000 n=38+36)
BM_Sort_uint32_QuickSortAdversary_262144                         61.6ns ± 4%  68.2ns ± 4%   +10.68%  (p=0.000 n=37+37)
BM_Sort_uint64_Random_1                                          3.71ns ± 4%  4.00ns ± 4%    +7.93%  (p=0.000 n=34+35)
BM_Sort_uint64_Random_4                                          5.52ns ± 8%  5.22ns ± 6%    -5.41%  (p=0.000 n=32+32)
BM_Sort_uint64_Random_16                                         10.7ns ±15%  10.2ns ± 7%      ~     (p=0.077 n=40+31)
BM_Sort_uint64_Random_64                                         19.0ns ±14%  18.2ns ±14%    -4.31%  (p=0.001 n=40+40)
BM_Sort_uint64_Random_256                                        25.7ns ± 9%  22.1ns ±15%   -13.82%  (p=0.000 n=33+40)
BM_Sort_uint64_Random_1024                                       32.4ns ± 6%  23.8ns ±16%   -26.64%  (p=0.000 n=33+40)
BM_Sort_uint64_Random_16384                                      46.8ns ± 3%  27.1ns ±16%   -42.15%  (p=0.000 n=33+40)
BM_Sort_uint64_Random_262144                                     61.3ns ± 4%  30.4ns ±16%   -50.34%  (p=0.000 n=34+40)
BM_Sort_uint64_Ascending_1                                       3.67ns ± 3%  3.87ns ±16%    +5.36%  (p=0.049 n=35+40)
BM_Sort_uint64_Ascending_4                                       1.46ns ± 3%  1.46ns ± 3%      ~     (p=0.130 n=37+31)
BM_Sort_uint64_Ascending_16                                      1.09ns ± 3%  0.91ns ± 6%   -16.79%  (p=0.000 n=38+32)
BM_Sort_uint64_Ascending_64                                      1.25ns ± 3%  1.29ns ± 5%    +3.11%  (p=0.000 n=38+34)
BM_Sort_uint64_Ascending_256                                     1.37ns ± 3%  1.42ns ± 3%    +3.07%  (p=0.000 n=39+35)
BM_Sort_uint64_Ascending_1024                                    1.12ns ± 3%  1.17ns ± 3%    +5.28%  (p=0.000 n=37+36)
BM_Sort_uint64_Ascending_16384                                   0.98ns ± 3%  1.09ns ± 3%   +10.95%  (p=0.000 n=36+37)
BM_Sort_uint64_Ascending_262144                                  0.98ns ± 3%  1.08ns ± 3%   +10.97%  (p=0.000 n=36+37)
BM_Sort_uint64_Descending_1                                      3.68ns ± 3%  3.67ns ± 3%      ~     (p=0.652 n=36+36)
BM_Sort_uint64_Descending_4                                      1.71ns ± 3%  1.73ns ± 3%    +1.50%  (p=0.000 n=33+34)
BM_Sort_uint64_Descending_16                                     4.96ns ± 2%  5.49ns ± 3%   +10.73%  (p=0.000 n=31+36)
BM_Sort_uint64_Descending_64                                     2.14ns ± 6%  3.03ns ± 3%   +41.72%  (p=0.000 n=32+35)
BM_Sort_uint64_Descending_256                                    2.03ns ± 4%  2.86ns ± 4%   +40.55%  (p=0.000 n=32+34)
BM_Sort_uint64_Descending_1024                                   2.20ns ± 2%  2.29ns ± 3%    +4.20%  (p=0.000 n=31+36)
BM_Sort_uint64_Descending_16384                                  1.89ns ± 3%  2.08ns ± 3%   +10.00%  (p=0.000 n=31+37)
BM_Sort_uint64_Descending_262144                                 1.92ns ± 3%  2.07ns ± 4%    +7.95%  (p=0.000 n=31+36)
BM_Sort_uint64_SingleElement_1                                   3.68ns ± 5%  3.67ns ± 3%      ~     (p=0.716 n=31+37)
BM_Sort_uint64_SingleElement_4                                   1.46ns ± 3%  1.46ns ± 3%      ~     (p=0.557 n=34+37)
BM_Sort_uint64_SingleElement_16                                  1.09ns ± 2%  0.91ns ± 3%   -16.93%  (p=0.000 n=33+36)
BM_Sort_uint64_SingleElement_64                                  0.83ns ± 4%  1.47ns ± 4%   +78.03%  (p=0.000 n=34+34)
BM_Sort_uint64_SingleElement_256                                 0.95ns ± 4%  1.28ns ± 4%   +35.17%  (p=0.000 n=35+35)
BM_Sort_uint64_SingleElement_1024                                0.76ns ± 3%  1.05ns ± 3%   +37.78%  (p=0.000 n=35+33)
BM_Sort_uint64_SingleElement_16384                               0.71ns ± 2%  0.98ns ± 5%   +38.43%  (p=0.000 n=34+33)
BM_Sort_uint64_SingleElement_262144                              0.72ns ± 3%  0.98ns ± 4%   +35.93%  (p=0.000 n=35+33)
BM_Sort_uint64_PipeOrgan_1                                       3.68ns ± 3%  3.68ns ± 3%      ~     (p=0.650 n=35+33)
BM_Sort_uint64_PipeOrgan_4                                       1.53ns ± 2%  1.54ns ± 4%      ~     (p=0.424 n=33+36)
BM_Sort_uint64_PipeOrgan_16                                      2.23ns ± 3%  2.06ns ± 4%    -7.68%  (p=0.000 n=34+35)
BM_Sort_uint64_PipeOrgan_64                                      5.46ns ± 2%  3.41ns ± 4%   -37.67%  (p=0.000 n=33+36)
BM_Sort_uint64_PipeOrgan_256                                     2.92ns ± 4%  2.91ns ± 3%      ~     (p=0.257 n=35+35)
BM_Sort_uint64_PipeOrgan_1024                                    3.72ns ± 3%  5.35ns ± 4%   +43.95%  (p=0.000 n=35+35)
BM_Sort_uint64_PipeOrgan_16384                                   4.12ns ± 3%  6.37ns ± 3%   +54.74%  (p=0.000 n=34+36)
BM_Sort_uint64_PipeOrgan_262144                                  4.99ns ± 3%  7.25ns ± 5%   +45.45%  (p=0.000 n=35+35)
BM_Sort_uint64_QuickSortAdversary_1                              3.67ns ± 2%  3.65ns ± 3%      ~     (p=0.071 n=35+37)
BM_Sort_uint64_QuickSortAdversary_4                              1.46ns ± 3%  1.46ns ± 3%      ~     (p=0.214 n=36+37)
BM_Sort_uint64_QuickSortAdversary_16                             1.09ns ± 3%  0.91ns ± 3%   -16.73%  (p=0.000 n=36+38)
BM_Sort_uint64_QuickSortAdversary_64                             13.7ns ± 3%  17.8ns ± 5%   +29.86%  (p=0.000 n=36+37)
BM_Sort_uint64_QuickSortAdversary_256                            20.0ns ± 3%  25.9ns ± 3%   +29.25%  (p=0.000 n=35+38)
BM_Sort_uint64_QuickSortAdversary_1024                           28.1ns ± 3%  31.0ns ± 4%   +10.35%  (p=0.000 n=33+37)
BM_Sort_uint64_QuickSortAdversary_16384                          45.8ns ± 2%  50.5ns ± 4%   +10.29%  (p=0.000 n=36+37)
BM_Sort_uint64_QuickSortAdversary_262144                         64.9ns ± 3%  69.5ns ± 3%    +7.15%  (p=0.000 n=36+36)
BM_Sort_pair<uint32, uint32>_Random_1                            4.03ns ± 5%  4.33ns ± 4%    +7.31%  (p=0.000 n=36+36)
BM_Sort_pair<uint32, uint32>_Random_4                            6.78ns ± 5%  6.71ns ± 4%    -1.09%  (p=0.040 n=35+35)
BM_Sort_pair<uint32, uint32>_Random_16                           25.2ns ± 6%  16.8ns ± 7%   -33.35%  (p=0.000 n=35+35)
BM_Sort_pair<uint32, uint32>_Random_64                           35.6ns ± 7%  27.2ns ± 8%   -23.73%  (p=0.000 n=34+36)
BM_Sort_pair<uint32, uint32>_Random_256                          43.5ns ±13%  34.0ns ± 8%   -21.78%  (p=0.000 n=32+34)
BM_Sort_pair<uint32, uint32>_Random_1024                         50.6ns ± 8%  40.8ns ± 5%   -19.35%  (p=0.000 n=32+32)
BM_Sort_pair<uint32, uint32>_Random_16384                        66.0ns ± 3%  55.9ns ± 6%   -15.24%  (p=0.000 n=32+32)
BM_Sort_pair<uint32, uint32>_Random_262144                       82.4ns ± 4%  72.0ns ± 5%   -12.64%  (p=0.000 n=32+31)
BM_Sort_pair<uint32, uint32>_Ascending_1                         4.00ns ± 2%  4.50ns ±16%   +12.59%  (p=0.000 n=33+40)
BM_Sort_pair<uint32, uint32>_Ascending_4                         2.22ns ± 3%  2.34ns ±16%    +5.46%  (p=0.041 n=33+40)
BM_Sort_pair<uint32, uint32>_Ascending_16                        2.33ns ± 4%  1.30ns ±15%   -44.33%  (p=0.000 n=34+40)
BM_Sort_pair<uint32, uint32>_Ascending_64                        1.39ns ± 4%  1.50ns ± 8%    +8.48%  (p=0.000 n=35+32)
BM_Sort_pair<uint32, uint32>_Ascending_256                       1.47ns ± 4%  1.56ns ± 3%    +5.96%  (p=0.000 n=37+31)
BM_Sort_pair<uint32, uint32>_Ascending_1024                      1.34ns ± 3%  1.35ns ± 4%    +1.22%  (p=0.000 n=38+31)
BM_Sort_pair<uint32, uint32>_Ascending_16384                     1.18ns ± 2%  1.18ns ± 3%      ~     (p=0.687 n=37+32)
BM_Sort_pair<uint32, uint32>_Ascending_262144                    1.18ns ± 3%  1.17ns ± 2%      ~     (p=0.153 n=38+34)
BM_Sort_pair<uint32, uint32>_Descending_1                        4.00ns ± 2%  4.29ns ± 3%    +7.22%  (p=0.000 n=37+36)
BM_Sort_pair<uint32, uint32>_Descending_4                        2.91ns ± 3%  2.92ns ± 3%      ~     (p=0.065 n=37+35)
BM_Sort_pair<uint32, uint32>_Descending_16                       4.96ns ± 4%  6.51ns ± 2%   +31.36%  (p=0.000 n=37+30)
BM_Sort_pair<uint32, uint32>_Descending_64                       3.13ns ± 2%  2.92ns ± 3%    -6.71%  (p=0.000 n=36+37)
BM_Sort_pair<uint32, uint32>_Descending_256                      2.56ns ± 3%  2.73ns ± 5%    +6.55%  (p=0.000 n=35+37)
BM_Sort_pair<uint32, uint32>_Descending_1024                     3.11ns ± 3%  2.34ns ± 4%   -24.85%  (p=0.000 n=36+35)
BM_Sort_pair<uint32, uint32>_Descending_16384                    2.84ns ± 3%  2.14ns ± 5%   -24.48%  (p=0.000 n=37+37)
BM_Sort_pair<uint32, uint32>_Descending_262144                   2.86ns ± 3%  2.15ns ± 3%   -25.08%  (p=0.000 n=36+35)
BM_Sort_pair<uint32, uint32>_SingleElement_1                     3.99ns ± 3%  4.28ns ± 3%    +7.08%  (p=0.000 n=33+35)
BM_Sort_pair<uint32, uint32>_SingleElement_4                     2.32ns ± 6%  2.30ns ± 3%    -0.77%  (p=0.032 n=32+35)
BM_Sort_pair<uint32, uint32>_SingleElement_16                    1.67ns ± 4%  1.27ns ± 4%   -24.13%  (p=0.000 n=32+35)
BM_Sort_pair<uint32, uint32>_SingleElement_64                    1.64ns ± 7%  1.83ns ± 4%   +11.54%  (p=0.000 n=31+35)
BM_Sort_pair<uint32, uint32>_SingleElement_256                   1.57ns ± 3%  1.90ns ± 3%   +21.46%  (p=0.000 n=31+36)
BM_Sort_pair<uint32, uint32>_SingleElement_1024                  1.49ns ±15%  1.63ns ± 3%    +9.42%  (p=0.000 n=40+37)
BM_Sort_pair<uint32, uint32>_SingleElement_16384                 1.29ns ±17%  1.57ns ± 3%   +21.51%  (p=0.000 n=33+36)
BM_Sort_pair<uint32, uint32>_SingleElement_262144                1.26ns ± 4%  1.56ns ± 4%   +24.11%  (p=0.000 n=33+36)
BM_Sort_pair<uint32, uint32>_PipeOrgan_1                         4.01ns ± 2%  4.28ns ± 3%    +6.68%  (p=0.000 n=32+35)
BM_Sort_pair<uint32, uint32>_PipeOrgan_4                         2.38ns ± 5%  2.42ns ± 4%    +1.61%  (p=0.000 n=34+35)
BM_Sort_pair<uint32, uint32>_PipeOrgan_16                        4.83ns ± 2%  2.71ns ± 7%   -43.96%  (p=0.000 n=34+34)
BM_Sort_pair<uint32, uint32>_PipeOrgan_64                        4.53ns ± 3%  3.89ns ± 7%   -14.11%  (p=0.000 n=35+33)
BM_Sort_pair<uint32, uint32>_PipeOrgan_256                       5.53ns ± 4%  2.81ns ± 4%   -49.13%  (p=0.000 n=36+33)
BM_Sort_pair<uint32, uint32>_PipeOrgan_1024                      6.49ns ± 4%  5.29ns ± 3%   -18.50%  (p=0.000 n=35+32)
BM_Sort_pair<uint32, uint32>_PipeOrgan_16384                     7.21ns ± 4%  5.97ns ± 3%   -17.24%  (p=0.000 n=36+33)
BM_Sort_pair<uint32, uint32>_PipeOrgan_262144                    7.98ns ± 5%  6.59ns ± 3%   -17.46%  (p=0.000 n=33+33)
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_1                3.99ns ± 3%  4.27ns ± 3%    +6.95%  (p=0.000 n=36+34)
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_4                2.40ns ± 3%  2.37ns ± 3%    -1.00%  (p=0.007 n=34+34)
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_16               4.96ns ± 5%  2.72ns ± 7%   -45.07%  (p=0.000 n=35+35)
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_64               7.24ns ± 4%  7.51ns ± 4%    +3.63%  (p=0.000 n=34+35)
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_256              9.85ns ± 5%  7.12ns ± 4%   -27.70%  (p=0.000 n=34+35)
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_1024             11.6ns ± 6%   8.8ns ± 5%   -23.86%  (p=0.000 n=35+35)
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_16384            32.7ns ± 3%  20.8ns ± 4%   -36.26%  (p=0.000 n=35+35)
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_262144           36.4ns ± 3%  24.0ns ± 4%   -34.12%  (p=0.000 n=34+36)
BM_Sort_tuple<uint32, uint64, uint32>_Random_1                   4.04ns ± 6%  4.34ns ± 4%    +7.55%  (p=0.000 n=37+37)
BM_Sort_tuple<uint32, uint64, uint32>_Random_4                   7.19ns ± 6%  7.26ns ± 5%    +0.99%  (p=0.042 n=36+38)
BM_Sort_tuple<uint32, uint64, uint32>_Random_16                  30.4ns ± 6%  21.8ns ± 7%   -28.28%  (p=0.000 n=34+37)
BM_Sort_tuple<uint32, uint64, uint32>_Random_64                  42.8ns ±11%  33.5ns ± 9%   -21.70%  (p=0.000 n=36+38)
BM_Sort_tuple<uint32, uint64, uint32>_Random_256                 49.9ns ± 6%  40.3ns ± 9%   -19.20%  (p=0.000 n=35+38)
BM_Sort_tuple<uint32, uint64, uint32>_Random_1024                56.3ns ± 3%  46.1ns ± 4%   -18.08%  (p=0.000 n=35+35)
BM_Sort_tuple<uint32, uint64, uint32>_Random_16384               72.2ns ± 5%  62.1ns ± 3%   -14.05%  (p=0.000 n=37+36)
BM_Sort_tuple<uint32, uint64, uint32>_Random_262144              88.7ns ± 6%  79.0ns ± 6%   -10.93%  (p=0.000 n=36+36)
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_1                3.96ns ± 3%  4.36ns ± 3%    +9.96%  (p=0.000 n=34+37)
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_4                2.39ns ± 2%  2.39ns ± 3%      ~     (p=0.604 n=36+37)
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_16               3.04ns ± 4%  1.48ns ± 3%   -51.20%  (p=0.000 n=34+35)
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_64               2.44ns ± 3%  2.30ns ± 5%    -5.61%  (p=0.000 n=36+35)
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_256              2.35ns ± 3%  2.39ns ± 5%    +1.78%  (p=0.000 n=33+34)
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_1024             2.12ns ± 5%  2.08ns ± 4%    -1.80%  (p=0.000 n=33+34)
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_16384            2.02ns ± 3%  2.00ns ± 5%    -1.25%  (p=0.000 n=32+32)
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_262144           2.06ns ± 5%  2.11ns ± 9%      ~     (p=0.618 n=32+40)
BM_Sort_tuple<uint32, uint64, uint32>_Descending_1               3.97ns ± 2%  4.57ns ±16%   +15.19%  (p=0.000 n=32+40)
BM_Sort_tuple<uint32, uint64, uint32>_Descending_4               3.64ns ± 3%  4.05ns ±15%   +11.05%  (p=0.000 n=33+40)
BM_Sort_tuple<uint32, uint64, uint32>_Descending_16              5.68ns ± 5%  9.36ns ±16%   +64.92%  (p=0.000 n=35+40)
BM_Sort_tuple<uint32, uint64, uint32>_Descending_64              4.27ns ± 4%  3.88ns ± 8%    -9.13%  (p=0.000 n=35+32)
BM_Sort_tuple<uint32, uint64, uint32>_Descending_256             3.58ns ± 3%  3.76ns ±14%    +5.12%  (p=0.002 n=38+40)
BM_Sort_tuple<uint32, uint64, uint32>_Descending_1024            4.16ns ± 3%  3.21ns ± 5%   -22.77%  (p=0.000 n=38+31)
BM_Sort_tuple<uint32, uint64, uint32>_Descending_16384           3.90ns ± 4%  3.00ns ± 3%   -23.12%  (p=0.000 n=38+32)
BM_Sort_tuple<uint32, uint64, uint32>_Descending_262144          4.52ns ± 3%  3.42ns ± 3%   -24.29%  (p=0.000 n=38+33)
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_1            3.97ns ± 3%  4.31ns ± 3%    +8.78%  (p=0.000 n=39+34)
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_4            2.54ns ± 2%  2.54ns ± 4%      ~     (p=0.341 n=38+36)
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_16           2.39ns ± 3%  1.70ns ± 6%   -28.90%  (p=0.000 n=38+35)
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_64           2.61ns ± 2%  3.23ns ± 3%   +24.07%  (p=0.000 n=35+35)
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_256          2.83ns ± 2%  2.97ns ± 4%    +4.83%  (p=0.000 n=35+37)
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_1024         2.44ns ± 4%  2.44ns ± 3%      ~     (p=0.481 n=36+36)
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_16384        2.19ns ± 3%  2.37ns ± 6%    +8.01%  (p=0.000 n=36+37)
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_262144       2.34ns ± 2%  2.36ns ± 5%    +1.11%  (p=0.001 n=36+36)
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_1                3.96ns ± 2%  4.31ns ± 3%    +8.76%  (p=0.000 n=33+35)
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_4                2.65ns ± 6%  2.67ns ± 4%      ~     (p=0.139 n=32+37)
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_16               5.64ns ± 3%  3.56ns ± 3%   -36.80%  (p=0.000 n=31+35)
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_64               6.12ns ±16%  5.04ns ± 4%   -17.64%  (p=0.000 n=40+37)
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_256              6.78ns ± 6%  3.73ns ± 3%   -44.94%  (p=0.000 n=31+36)
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_1024             8.36ns ±15%  6.51ns ± 4%   -22.13%  (p=0.000 n=40+37)
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_16384            9.24ns ±15%  7.91ns ± 3%   -14.34%  (p=0.000 n=40+37)
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_262144           10.7ns ± 3%   9.3ns ± 6%   -12.36%  (p=0.000 n=32+36)
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_1       3.97ns ± 3%  4.31ns ± 3%    +8.63%  (p=0.000 n=32+35)
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_4       2.79ns ± 3%  2.76ns ± 4%    -0.95%  (p=0.002 n=33+33)
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_16      5.07ns ± 3%  3.69ns ± 4%   -27.35%  (p=0.000 n=35+33)
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_64      9.26ns ± 3%  8.34ns ± 7%    -9.88%  (p=0.000 n=35+33)
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_256     11.8ns ± 5%   9.7ns ± 3%   -17.83%  (p=0.000 n=37+33)
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_1024    19.2ns ± 4%  14.5ns ±10%   -24.59%  (p=0.000 n=36+33)
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_16384   45.5ns ± 4%  37.4ns ± 9%   -17.71%  (p=0.000 n=35+33)
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_262144  50.0ns ± 4%  43.2ns ± 3%   -13.69%  (p=0.000 n=35+34)
BM_Sort_string_Random_1                                          4.66ns ± 6%  4.40ns ± 4%    -5.55%  (p=0.000 n=35+37)
BM_Sort_string_Random_4                                          14.9ns ± 3%  15.0ns ± 6%      ~     (p=0.863 n=36+38)
BM_Sort_string_Random_16                                         45.5ns ± 6%  35.8ns ± 8%   -21.37%  (p=0.000 n=36+36)
BM_Sort_string_Random_64                                         66.6ns ± 4%  58.2ns ± 3%   -12.69%  (p=0.000 n=36+37)
BM_Sort_string_Random_256                                        86.0ns ± 5%  77.4ns ± 3%   -10.01%  (p=0.000 n=37+37)
BM_Sort_string_Random_1024                                        106ns ± 3%    96ns ± 6%    -9.39%  (p=0.000 n=37+37)
BM_Sort_string_Random_16384                                       154ns ± 3%   141ns ± 5%    -8.03%  (p=0.000 n=35+36)
BM_Sort_string_Random_262144                                      213ns ± 4%   197ns ± 4%    -7.59%  (p=0.000 n=34+34)
BM_Sort_string_Ascending_1                                       4.59ns ± 2%  4.56ns ±17%    -0.60%  (p=0.002 n=32+40)
BM_Sort_string_Ascending_4                                       7.52ns ± 9%  7.54ns ±12%      ~     (p=0.554 n=37+40)
BM_Sort_string_Ascending_16                                      13.1ns ± 6%   8.8ns ±12%   -33.26%  (p=0.000 n=39+38)
BM_Sort_string_Ascending_64                                      14.8ns ±10%  14.5ns ±11%    -2.15%  (p=0.013 n=40+37)
BM_Sort_string_Ascending_256                                     14.0ns ± 6%  14.1ns ±10%      ~     (p=0.760 n=37+40)
BM_Sort_string_Ascending_1024                                    12.9ns ±10%  12.8ns ±20%      ~     (p=0.055 n=35+40)
BM_Sort_string_Ascending_16384                                   17.2ns ±13%  17.4ns ±21%      ~     (p=1.000 n=37+40)
BM_Sort_string_Ascending_262144                                  17.5ns ±12%  17.5ns ±25%      ~     (p=0.392 n=35+39)
BM_Sort_string_Descending_1                                      4.59ns ± 3%  4.34ns ± 3%    -5.51%  (p=0.000 n=32+33)
BM_Sort_string_Descending_4                                      10.1ns ± 5%   9.8ns ± 4%    -2.84%  (p=0.000 n=36+34)
BM_Sort_string_Descending_16                                     22.0ns ± 4%  39.6ns ± 4%   +79.84%  (p=0.000 n=36+33)
BM_Sort_string_Descending_64                                     21.4ns ±12%  21.3ns ±14%      ~     (p=0.542 n=37+39)
BM_Sort_string_Descending_256                                    19.4ns ±13%  18.9ns ±13%    -2.74%  (p=0.039 n=37+39)
BM_Sort_string_Descending_1024                                   22.7ns ± 5%  17.6ns ±15%   -22.52%  (p=0.000 n=35+40)
BM_Sort_string_Descending_16384                                  27.9ns ±14%  22.6ns ±10%   -19.11%  (p=0.000 n=40+37)
BM_Sort_string_Descending_262144                                 33.8ns ±14%  26.1ns ±21%   -22.74%  (p=0.000 n=39+38)
BM_Sort_string_SingleElement_1                                   4.58ns ± 2%  4.35ns ± 3%    -5.14%  (p=0.000 n=35+37)
BM_Sort_string_SingleElement_4                                   7.92ns ± 3%  7.92ns ± 7%      ~     (p=0.625 n=38+39)
BM_Sort_string_SingleElement_16                                  18.0ns ± 3%   7.9ns ± 6%   -56.23%  (p=0.000 n=36+35)
BM_Sort_string_SingleElement_64                                  20.3ns ± 5%  19.3ns ±15%    -4.83%  (p=0.000 n=34+38)
BM_Sort_string_SingleElement_256                                 19.4ns ± 7%  18.1ns ±14%    -6.67%  (p=0.000 n=36+39)
BM_Sort_string_SingleElement_1024                                19.3ns ± 9%  17.4ns ±17%    -9.40%  (p=0.000 n=35+40)
BM_Sort_string_SingleElement_16384                               17.5ns ±12%  16.2ns ±20%    -7.91%  (p=0.000 n=37+40)
BM_Sort_string_SingleElement_262144                              16.7ns ±18%  15.3ns ±27%    -8.56%  (p=0.000 n=40+40)
BM_Sort_string_PipeOrgan_1                                       4.60ns ± 2%  4.33ns ± 3%    -5.80%  (p=0.000 n=33+31)
BM_Sort_string_PipeOrgan_4                                       8.29ns ± 4%  8.17ns ± 8%    -1.50%  (p=0.004 n=39+36)
BM_Sort_string_PipeOrgan_16                                      22.9ns ± 3%  16.4ns ± 6%   -28.45%  (p=0.000 n=39+38)
BM_Sort_string_PipeOrgan_64                                      30.7ns ± 4%  28.9ns ± 7%    -6.05%  (p=0.000 n=38+37)
BM_Sort_string_PipeOrgan_256                                     38.1ns ± 3%  22.5ns ± 9%   -40.78%  (p=0.000 n=37+37)
BM_Sort_string_PipeOrgan_1024                                    45.4ns ± 4%  36.2ns ± 6%   -20.33%  (p=0.000 n=37+37)
BM_Sort_string_PipeOrgan_16384                                   56.2ns ± 4%  49.0ns ± 8%   -12.73%  (p=0.000 n=36+38)
BM_Sort_string_PipeOrgan_262144                                  77.8ns ±13%  62.8ns ±10%   -19.27%  (p=0.000 n=39+39)
BM_Sort_string_QuickSortAdversary_1                              4.80ns ±16%  4.34ns ± 4%    -9.56%  (p=0.000 n=39+34)
BM_Sort_string_QuickSortAdversary_4                              14.8ns ± 5%  14.7ns ± 4%    -0.80%  (p=0.037 n=33+33)
BM_Sort_string_QuickSortAdversary_16                             44.6ns ± 4%  34.8ns ± 5%   -21.98%  (p=0.000 n=35+34)
BM_Sort_string_QuickSortAdversary_64                             66.2ns ± 3%  58.1ns ± 4%   -12.32%  (p=0.000 n=36+35)
BM_Sort_string_QuickSortAdversary_256                            85.4ns ± 5%  76.9ns ± 6%    -9.99%  (p=0.000 n=36+36)
BM_Sort_string_QuickSortAdversary_1024                            106ns ± 4%    96ns ± 3%    -9.62%  (p=0.000 n=34+37)
BM_Sort_string_QuickSortAdversary_16384                           153ns ± 3%   141ns ± 4%    -8.22%  (p=0.000 n=34+37)
BM_Sort_string_QuickSortAdversary_262144                          211ns ± 5%   195ns ± 6%    -7.77%  (p=0.000 n=35+38)

[nilayvaish]

Fix the failed compilation issue

[nilayvaish]

Update comments in the file.

[nilayvaish]

This diff is based on https://reviews.llvm.org/D93233. We have other changes there (updates to fixed length sorting functions, bitonic sort) that we might consider later.

[philnik]

Could you do the formatting changes in its own patch? This will probably merge-conflict with D118029. I think D118029 will be landed in the near future, so it would be nice to have data relative to that patch.
There also seems to be a lot of regression in many test cases, mainly for the types smaller than 8 bytes. The larger ones seem to be better across the board. You say in the description that you have optimized different things. Are these optimizations orthogonal? If that is the case I think it would be nice to have them in separate patches to be able to review them separately.

[nilayvaish]

Rebase

[nilayvaish]

Fix a badly resolved merge.

[nilayvaish]

In D122780#3420119, @philnik wrote:

Could you do the formatting changes in its own patch?

Moved formatting changes to https://reviews.llvm.org/D122858.

This will probably merge-conflict with D118029. I think D118029 will be landed in the near future, so it would be nice to have data relative to that patch.

I'll update the data once D118029 has landed. Since D118029 and this diff are changing different parts of the code, I expect the performance numbers to hold mostly, may go down a little bit maybe.

There also seems to be a lot of regression in many test cases, mainly for the types smaller than 8 bytes. The larger ones seem to be better across the board.

The test cases that have regressed are the ones where a specific pattern is being tested. While we theoretically match the time complexity i.e. wherever current implementation is linear (ascending, descending, single element), the new implementation is also linear. Where the current implementation is non-linear, the new implementation is also non linear. We do more memory operations as we create temporary bitsets for recording comparison operations. But this cost is overcome by avoiding branches in the new implementation. When branches are easy to predict, the current implementation does better.

You say in the description that you have optimized different things. Are these optimizations orthogonal? If that is the case I think it would be nice to have them in separate patches to be able to review them separately.

If we don't do those other things (unguarded insertion sort, ninther pivot selection, equal elements on the left), the new implementation would appear more bad on those patterns. I would suggest that we review whole diff in one go.

[nilayvaish]

Rebase

[nilayvaish]

Updated performance numbers:

name                                                             old cpu/op  new cpu/op   delta
BM_Sort_uint32_Random_1                                          3.69ns ± 2%   3.71ns ± 4%     ~     (p=0.305 n=37+36)
BM_Sort_uint32_Random_4                                          2.07ns ± 5%   2.05ns ± 6%     ~     (p=0.079 n=36+34)
BM_Sort_uint32_Random_16                                         9.54ns ± 7%  11.54ns ± 8%  +20.98%  (p=0.000 n=35+37)
BM_Sort_uint32_Random_64                                         17.1ns ± 6%   17.1ns ± 7%     ~     (p=0.927 n=35+36)
BM_Sort_uint32_Random_256                                        24.7ns ± 6%   20.7ns ± 4%  -15.88%  (p=0.000 n=35+33)
BM_Sort_uint32_Random_1024                                       31.9ns ± 5%   22.9ns ± 3%  -28.35%  (p=0.000 n=36+36)
BM_Sort_uint32_Random_16384                                      46.0ns ± 4%   26.2ns ± 3%  -42.95%  (p=0.000 n=34+36)
BM_Sort_uint32_Random_262144                                     60.0ns ± 3%   29.7ns ± 5%  -50.49%  (p=0.000 n=32+38)
BM_Sort_uint32_Ascending_1                                       3.68ns ± 3%   3.99ns ± 2%   +8.42%  (p=0.000 n=32+34)
BM_Sort_uint32_Ascending_4                                       2.02ns ± 4%   2.03ns ± 3%     ~     (p=0.401 n=32+34)
BM_Sort_uint32_Ascending_16                                      0.94ns ±11%   0.97ns ± 6%   +4.07%  (p=0.000 n=34+34)
BM_Sort_uint32_Ascending_64                                      1.18ns ± 3%   1.22ns ± 6%   +3.45%  (p=0.000 n=32+33)
BM_Sort_uint32_Ascending_256                                     1.18ns ± 5%   1.30ns ± 3%  +10.69%  (p=0.000 n=32+33)
BM_Sort_uint32_Ascending_1024                                    1.02ns ± 3%   1.13ns ± 3%  +11.43%  (p=0.000 n=32+31)
BM_Sort_uint32_Ascending_16384                                   0.94ns ± 6%   1.06ns ± 5%  +12.72%  (p=0.000 n=35+34)
BM_Sort_uint32_Ascending_262144                                  0.93ns ± 4%   1.05ns ± 3%  +12.79%  (p=0.000 n=34+33)
BM_Sort_uint32_Descending_1                                      3.68ns ± 3%   3.98ns ± 3%   +8.35%  (p=0.000 n=34+33)
BM_Sort_uint32_Descending_4                                      2.05ns ± 5%   2.04ns ± 5%     ~     (p=0.362 n=36+34)
BM_Sort_uint32_Descending_16                                     5.58ns ± 3%   4.16ns ± 3%  -25.54%  (p=0.000 n=36+34)
BM_Sort_uint32_Descending_64                                     1.98ns ± 3%   2.93ns ± 5%  +48.08%  (p=0.000 n=36+34)
BM_Sort_uint32_Descending_256                                    1.78ns ± 4%   2.60ns ± 7%  +46.08%  (p=0.000 n=36+34)
BM_Sort_uint32_Descending_1024                                   2.22ns ± 3%   2.36ns ± 4%   +6.34%  (p=0.000 n=38+35)
BM_Sort_uint32_Descending_16384                                  1.92ns ± 3%   2.11ns ± 3%  +10.35%  (p=0.000 n=34+35)
BM_Sort_uint32_Descending_262144                                 1.89ns ± 5%   2.07ns ± 3%   +9.86%  (p=0.000 n=36+35)
BM_Sort_uint32_SingleElement_1                                   3.67ns ± 3%   3.98ns ± 4%   +8.34%  (p=0.000 n=38+36)
BM_Sort_uint32_SingleElement_4                                   2.04ns ± 2%   2.04ns ± 3%     ~     (p=0.956 n=38+35)
BM_Sort_uint32_SingleElement_16                                  0.92ns ± 3%   0.96ns ± 3%   +4.63%  (p=0.000 n=37+35)
BM_Sort_uint32_SingleElement_64                                  0.77ns ± 5%   1.22ns ± 4%  +59.65%  (p=0.000 n=35+35)
BM_Sort_uint32_SingleElement_256                                 0.82ns ± 4%   1.16ns ± 5%  +42.37%  (p=0.000 n=34+36)
BM_Sort_uint32_SingleElement_1024                                0.75ns ± 3%   1.01ns ± 3%  +34.68%  (p=0.000 n=34+36)
BM_Sort_uint32_SingleElement_16384                               0.64ns ± 4%   0.93ns ± 4%  +46.27%  (p=0.000 n=36+36)
BM_Sort_uint32_SingleElement_262144                              0.63ns ± 5%   0.93ns ± 4%  +47.74%  (p=0.000 n=35+36)
BM_Sort_uint32_PipeOrgan_1                                       3.68ns ± 4%   3.99ns ± 3%   +8.53%  (p=0.000 n=33+36)
BM_Sort_uint32_PipeOrgan_4                                       2.02ns ± 3%   2.02ns ± 3%     ~     (p=0.931 n=35+36)
BM_Sort_uint32_PipeOrgan_16                                      2.11ns ± 4%   1.94ns ± 3%   -8.31%  (p=0.000 n=35+35)
BM_Sort_uint32_PipeOrgan_64                                      5.68ns ± 3%   3.36ns ± 4%  -40.75%  (p=0.000 n=34+36)
BM_Sort_uint32_PipeOrgan_256                                     2.71ns ± 5%   2.73ns ± 4%     ~     (p=0.089 n=34+34)
BM_Sort_uint32_PipeOrgan_1024                                    3.54ns ± 5%   5.31ns ± 3%  +49.79%  (p=0.000 n=32+33)
BM_Sort_uint32_PipeOrgan_16384                                   4.18ns ± 3%   6.41ns ± 4%  +53.16%  (p=0.000 n=33+33)
BM_Sort_uint32_PipeOrgan_262144                                  5.01ns ± 6%   7.25ns ± 6%  +44.83%  (p=0.000 n=33+33)
BM_Sort_uint32_QuickSortAdversary_1                              3.66ns ± 2%   3.97ns ± 5%   +8.54%  (p=0.000 n=33+31)
BM_Sort_uint32_QuickSortAdversary_4                              2.02ns ± 3%   2.02ns ± 3%     ~     (p=0.427 n=34+31)
BM_Sort_uint32_QuickSortAdversary_16                             0.92ns ± 4%   0.96ns ± 3%   +4.26%  (p=0.000 n=34+32)
BM_Sort_uint32_QuickSortAdversary_64                             13.5ns ± 3%   17.9ns ± 8%  +32.71%  (p=0.000 n=36+31)
BM_Sort_uint32_QuickSortAdversary_256                            19.9ns ± 5%   26.3ns ± 7%  +32.11%  (p=0.000 n=36+33)
BM_Sort_uint32_QuickSortAdversary_1024                           28.2ns ± 3%   31.8ns ± 3%  +12.79%  (p=0.000 n=37+31)
BM_Sort_uint32_QuickSortAdversary_16384                          45.6ns ± 3%   50.6ns ± 3%  +10.89%  (p=0.000 n=37+33)
BM_Sort_uint32_QuickSortAdversary_262144                         61.3ns ± 3%   68.4ns ± 3%  +11.56%  (p=0.000 n=33+32)
BM_Sort_uint64_Random_1                                          3.69ns ± 4%   3.99ns ± 3%   +8.31%  (p=0.000 n=32+35)
BM_Sort_uint64_Random_4                                          2.04ns ± 3%   2.04ns ± 5%     ~     (p=0.920 n=33+37)
BM_Sort_uint64_Random_16                                         10.2ns ± 6%   11.5ns ± 5%  +13.17%  (p=0.000 n=36+39)
BM_Sort_uint64_Random_64                                         17.9ns ± 6%   17.4ns ± 5%   -3.17%  (p=0.000 n=35+38)
BM_Sort_uint64_Random_256                                        25.5ns ± 7%   20.9ns ± 4%  -18.08%  (p=0.000 n=37+37)
BM_Sort_uint64_Random_1024                                       32.7ns ± 7%   22.5ns ± 4%  -31.07%  (p=0.000 n=37+39)
BM_Sort_uint64_Random_16384                                      47.0ns ± 5%   25.6ns ± 3%  -45.62%  (p=0.000 n=37+38)
BM_Sort_uint64_Random_262144                                     61.4ns ± 3%   28.6ns ± 4%  -53.40%  (p=0.000 n=39+38)
BM_Sort_uint64_Ascending_1                                       3.67ns ± 3%   3.67ns ± 3%     ~     (p=0.823 n=38+38)
BM_Sort_uint64_Ascending_4                                       2.02ns ± 3%   2.02ns ± 4%     ~     (p=0.978 n=37+37)
BM_Sort_uint64_Ascending_16                                      0.99ns ± 3%   1.00ns ± 3%   +0.91%  (p=0.010 n=37+36)
BM_Sort_uint64_Ascending_64                                      1.20ns ± 3%   1.28ns ± 4%   +6.52%  (p=0.000 n=36+36)
BM_Sort_uint64_Ascending_256                                     1.25ns ± 3%   1.41ns ± 4%  +12.36%  (p=0.000 n=35+36)
BM_Sort_uint64_Ascending_1024                                    1.12ns ± 4%   1.17ns ± 3%   +4.30%  (p=0.000 n=35+37)
BM_Sort_uint64_Ascending_16384                                   0.98ns ± 2%   1.09ns ± 4%  +11.78%  (p=0.000 n=34+36)
BM_Sort_uint64_Ascending_262144                                  0.97ns ± 3%   1.09ns ± 3%  +12.23%  (p=0.000 n=32+37)
BM_Sort_uint64_Descending_1                                      3.66ns ± 3%   3.67ns ± 3%     ~     (p=0.650 n=31+34)
BM_Sort_uint64_Descending_4                                      2.02ns ± 4%   2.01ns ± 3%     ~     (p=0.209 n=32+35)
BM_Sort_uint64_Descending_16                                     4.60ns ± 7%   4.14ns ± 3%  -10.01%  (p=0.000 n=33+34)
BM_Sort_uint64_Descending_64                                     1.99ns ± 3%   3.03ns ± 3%  +52.13%  (p=0.000 n=31+35)
BM_Sort_uint64_Descending_256                                    1.85ns ± 4%   2.64ns ± 5%  +42.65%  (p=0.000 n=32+33)
BM_Sort_uint64_Descending_1024                                   2.22ns ± 4%   2.26ns ± 3%   +2.09%  (p=0.000 n=31+33)
BM_Sort_uint64_Descending_16384                                  1.94ns ±14%   2.07ns ± 3%   +6.47%  (p=0.000 n=32+34)
BM_Sort_uint64_Descending_262144                                 1.95ns ± 5%   2.07ns ± 4%   +6.09%  (p=0.000 n=33+33)
BM_Sort_uint64_SingleElement_1                                   3.68ns ± 6%   3.68ns ± 3%     ~     (p=0.963 n=34+31)
BM_Sort_uint64_SingleElement_4                                   2.03ns ± 3%   2.02ns ± 3%   -0.66%  (p=0.030 n=34+33)
BM_Sort_uint64_SingleElement_16                                  0.99ns ± 2%   1.00ns ± 3%     ~     (p=0.063 n=34+33)
BM_Sort_uint64_SingleElement_64                                  0.82ns ± 3%   1.27ns ± 3%  +55.10%  (p=0.000 n=35+35)
BM_Sort_uint64_SingleElement_256                                 0.94ns ± 4%   1.26ns ± 3%  +34.16%  (p=0.000 n=37+34)
BM_Sort_uint64_SingleElement_1024                                0.76ns ± 3%   1.05ns ± 4%  +37.93%  (p=0.000 n=38+34)
BM_Sort_uint64_SingleElement_16384                               0.71ns ± 3%   0.99ns ± 2%  +38.10%  (p=0.000 n=38+35)
BM_Sort_uint64_SingleElement_262144                              0.72ns ± 2%   0.98ns ± 5%  +35.93%  (p=0.000 n=39+36)
BM_Sort_uint64_PipeOrgan_1                                       3.66ns ± 4%   3.67ns ± 3%     ~     (p=0.081 n=38+35)
BM_Sort_uint64_PipeOrgan_4                                       2.02ns ± 3%   2.02ns ± 3%     ~     (p=0.729 n=35+35)
BM_Sort_uint64_PipeOrgan_16                                      2.30ns ± 3%   1.98ns ± 5%  -13.98%  (p=0.000 n=35+35)
BM_Sort_uint64_PipeOrgan_64                                      5.92ns ± 5%   3.45ns ± 5%  -41.72%  (p=0.000 n=35+36)
BM_Sort_uint64_PipeOrgan_256                                     2.75ns ± 3%   2.79ns ± 4%   +1.53%  (p=0.000 n=35+36)
BM_Sort_uint64_PipeOrgan_1024                                    3.71ns ± 5%   5.24ns ± 4%  +41.29%  (p=0.000 n=35+36)
BM_Sort_uint64_PipeOrgan_16384                                   4.21ns ± 4%   6.26ns ± 3%  +48.90%  (p=0.000 n=34+36)
BM_Sort_uint64_PipeOrgan_262144                                  5.07ns ± 4%   7.17ns ± 5%  +41.46%  (p=0.000 n=35+35)
BM_Sort_uint64_QuickSortAdversary_1                              3.66ns ± 2%   3.68ns ± 4%     ~     (p=0.211 n=34+36)
BM_Sort_uint64_QuickSortAdversary_4                              2.02ns ± 3%   2.02ns ± 5%     ~     (p=0.138 n=35+36)
BM_Sort_uint64_QuickSortAdversary_16                             0.99ns ± 3%   1.00ns ± 4%   +0.95%  (p=0.010 n=34+36)
BM_Sort_uint64_QuickSortAdversary_64                             13.5ns ± 4%   17.9ns ± 3%  +32.41%  (p=0.000 n=33+35)
BM_Sort_uint64_QuickSortAdversary_256                            20.1ns ± 3%   26.4ns ± 5%  +31.81%  (p=0.000 n=33+35)
BM_Sort_uint64_QuickSortAdversary_1024                           28.1ns ± 4%   30.9ns ± 4%   +9.99%  (p=0.000 n=34+33)
BM_Sort_uint64_QuickSortAdversary_16384                          46.1ns ± 3%   50.1ns ± 3%   +8.70%  (p=0.000 n=34+33)
BM_Sort_uint64_QuickSortAdversary_262144                         65.0ns ± 6%   69.5ns ± 3%   +6.88%  (p=0.000 n=34+31)
BM_Sort_pair<uint32, uint32>_Random_1                            4.04ns ± 4%   4.32ns ± 4%   +6.88%  (p=0.000 n=35+31)
BM_Sort_pair<uint32, uint32>_Random_4                            6.75ns ± 7%   6.76ns ± 8%     ~     (p=0.895 n=34+33)
BM_Sort_pair<uint32, uint32>_Random_16                           25.4ns ± 8%   16.3ns ±14%  -35.71%  (p=0.000 n=33+33)
BM_Sort_pair<uint32, uint32>_Random_64                           35.9ns ±10%   27.0ns ±10%  -24.73%  (p=0.000 n=34+34)
BM_Sort_pair<uint32, uint32>_Random_256                          43.1ns ± 9%   33.7ns ± 8%  -21.96%  (p=0.000 n=35+35)
BM_Sort_pair<uint32, uint32>_Random_1024                         50.4ns ± 4%   40.6ns ± 5%  -19.46%  (p=0.000 n=34+35)
BM_Sort_pair<uint32, uint32>_Random_16384                        66.7ns ± 3%   55.6ns ± 3%  -16.61%  (p=0.000 n=32+35)
BM_Sort_pair<uint32, uint32>_Random_262144                       82.4ns ± 7%   71.4ns ± 7%  -13.40%  (p=0.000 n=32+35)
BM_Sort_pair<uint32, uint32>_Ascending_1                         4.00ns ± 3%   4.30ns ± 3%   +7.48%  (p=0.000 n=33+35)
BM_Sort_pair<uint32, uint32>_Ascending_4                         2.21ns ± 6%   2.22ns ± 3%     ~     (p=0.072 n=33+38)
BM_Sort_pair<uint32, uint32>_Ascending_16                        2.31ns ± 4%   1.15ns ± 3%  -49.95%  (p=0.000 n=36+36)
BM_Sort_pair<uint32, uint32>_Ascending_64                        1.45ns ±27%   1.50ns ± 3%   +3.19%  (p=0.004 n=40+39)
BM_Sort_pair<uint32, uint32>_Ascending_256                       1.47ns ± 4%   1.55ns ± 3%   +5.80%  (p=0.000 n=37+38)
BM_Sort_pair<uint32, uint32>_Ascending_1024                      1.34ns ± 4%   1.36ns ± 3%   +1.32%  (p=0.000 n=38+38)
BM_Sort_pair<uint32, uint32>_Ascending_16384                     1.18ns ± 2%   1.18ns ± 3%     ~     (p=0.064 n=36+38)
BM_Sort_pair<uint32, uint32>_Ascending_262144                    1.17ns ± 3%   1.18ns ± 4%     ~     (p=0.280 n=38+37)
BM_Sort_pair<uint32, uint32>_Descending_1                        3.99ns ± 3%   4.30ns ± 5%   +7.68%  (p=0.000 n=37+36)
BM_Sort_pair<uint32, uint32>_Descending_4                        2.91ns ± 4%   2.94ns ± 3%   +0.91%  (p=0.013 n=35+36)
BM_Sort_pair<uint32, uint32>_Descending_16                       4.92ns ± 2%   8.05ns ± 6%  +63.62%  (p=0.000 n=35+36)
BM_Sort_pair<uint32, uint32>_Descending_64                       3.08ns ± 4%   2.98ns ± 3%   -3.01%  (p=0.000 n=36+37)
BM_Sort_pair<uint32, uint32>_Descending_256                      2.55ns ± 3%   2.60ns ± 3%   +2.00%  (p=0.000 n=34+37)
BM_Sort_pair<uint32, uint32>_Descending_1024                     3.10ns ± 3%   2.33ns ± 5%  -24.98%  (p=0.000 n=35+37)
BM_Sort_pair<uint32, uint32>_Descending_16384                    2.81ns ± 3%   2.14ns ± 3%  -23.94%  (p=0.000 n=36+35)
BM_Sort_pair<uint32, uint32>_Descending_262144                   2.90ns ± 7%   2.14ns ± 3%  -26.05%  (p=0.000 n=36+36)
BM_Sort_pair<uint32, uint32>_SingleElement_1                     4.00ns ± 3%   4.28ns ± 3%   +6.92%  (p=0.000 n=32+35)
BM_Sort_pair<uint32, uint32>_SingleElement_4                     2.29ns ± 5%   2.30ns ± 3%     ~     (p=0.130 n=32+35)
BM_Sort_pair<uint32, uint32>_SingleElement_16                    1.68ns ± 6%   1.27ns ± 3%  -24.46%  (p=0.000 n=32+34)
BM_Sort_pair<uint32, uint32>_SingleElement_64                    1.42ns ± 7%   1.83ns ± 2%  +28.97%  (p=0.000 n=32+34)
BM_Sort_pair<uint32, uint32>_SingleElement_256                   1.57ns ±10%   1.92ns ± 3%  +22.22%  (p=0.000 n=32+33)
BM_Sort_pair<uint32, uint32>_SingleElement_1024                  1.42ns ± 5%   1.63ns ± 3%  +14.74%  (p=0.000 n=31+33)
BM_Sort_pair<uint32, uint32>_SingleElement_16384                 1.27ns ± 3%   1.57ns ± 4%  +24.15%  (p=0.000 n=33+31)
BM_Sort_pair<uint32, uint32>_SingleElement_262144                1.25ns ± 3%   1.58ns ±17%  +25.53%  (p=0.000 n=34+33)
BM_Sort_pair<uint32, uint32>_PipeOrgan_1                         3.99ns ± 3%   4.28ns ± 3%   +7.16%  (p=0.000 n=33+33)
BM_Sort_pair<uint32, uint32>_PipeOrgan_4                         2.37ns ± 4%   2.38ns ± 6%     ~     (p=0.331 n=35+32)
BM_Sort_pair<uint32, uint32>_PipeOrgan_16                        4.83ns ± 4%   3.02ns ± 3%  -37.51%  (p=0.000 n=36+33)
BM_Sort_pair<uint32, uint32>_PipeOrgan_64                        4.52ns ± 3%   3.69ns ± 5%  -18.30%  (p=0.000 n=36+34)
BM_Sort_pair<uint32, uint32>_PipeOrgan_256                       5.41ns ± 3%   2.70ns ± 5%  -50.05%  (p=0.000 n=37+34)
BM_Sort_pair<uint32, uint32>_PipeOrgan_1024                      6.51ns ± 3%   5.11ns ± 3%  -21.56%  (p=0.000 n=37+33)
BM_Sort_pair<uint32, uint32>_PipeOrgan_16384                     7.21ns ± 3%   5.81ns ± 3%  -19.41%  (p=0.000 n=37+35)
BM_Sort_pair<uint32, uint32>_PipeOrgan_262144                    7.99ns ± 3%   6.43ns ± 3%  -19.51%  (p=0.000 n=37+35)
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_1                3.99ns ± 3%   4.29ns ± 4%   +7.41%  (p=0.000 n=38+35)
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_4                2.29ns ± 3%   2.37ns ± 3%   +3.49%  (p=0.000 n=37+35)
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_16               4.90ns ± 3%   2.51ns ± 3%  -48.72%  (p=0.000 n=38+34)
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_64               7.29ns ± 3%   6.73ns ± 3%   -7.76%  (p=0.000 n=36+35)
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_256              9.87ns ± 3%   6.57ns ± 3%  -33.47%  (p=0.000 n=36+35)
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_1024             11.5ns ± 5%    8.2ns ± 4%  -28.47%  (p=0.000 n=35+34)
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_16384            32.8ns ± 5%   20.2ns ± 4%  -38.24%  (p=0.000 n=34+35)
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_262144           36.6ns ± 5%   23.2ns ± 3%  -36.68%  (p=0.000 n=35+36)
BM_Sort_tuple<uint32, uint64, uint32>_Random_1                   4.01ns ± 8%   4.35ns ± 3%   +8.43%  (p=0.000 n=35+36)
BM_Sort_tuple<uint32, uint64, uint32>_Random_4                   7.21ns ± 6%   7.28ns ± 6%     ~     (p=0.051 n=34+35)
BM_Sort_tuple<uint32, uint64, uint32>_Random_16                  30.5ns ±11%   20.0ns ± 5%  -34.65%  (p=0.000 n=33+34)
BM_Sort_tuple<uint32, uint64, uint32>_Random_64                  42.2ns ± 5%   33.1ns ± 7%  -21.45%  (p=0.000 n=33+37)
BM_Sort_tuple<uint32, uint64, uint32>_Random_256                 50.4ns ± 8%   40.2ns ± 8%  -20.21%  (p=0.000 n=34+34)
BM_Sort_tuple<uint32, uint64, uint32>_Random_1024                56.0ns ± 4%   46.2ns ±10%  -17.38%  (p=0.000 n=34+33)
BM_Sort_tuple<uint32, uint64, uint32>_Random_16384               71.8ns ± 3%   62.2ns ± 4%  -13.31%  (p=0.000 n=33+33)
BM_Sort_tuple<uint32, uint64, uint32>_Random_262144              88.6ns ± 6%   79.4ns ± 8%  -10.44%  (p=0.000 n=34+32)
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_1                3.95ns ± 3%   4.33ns ± 7%   +9.49%  (p=0.000 n=34+31)
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_4                2.39ns ± 3%   2.40ns ± 5%     ~     (p=0.174 n=36+32)
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_16               3.08ns ± 3%   1.49ns ±16%  -51.48%  (p=0.000 n=36+40)
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_64               2.43ns ± 6%   2.42ns ± 2%     ~     (p=0.248 n=34+32)
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_256              2.34ns ± 3%   2.34ns ± 2%     ~     (p=0.808 n=33+32)
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_1024             2.11ns ± 3%   2.11ns ± 4%     ~     (p=0.683 n=33+36)
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_16384            2.02ns ± 4%   2.00ns ± 2%   -1.27%  (p=0.000 n=34+35)
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_262144           2.07ns ± 2%   2.04ns ± 2%   -1.39%  (p=0.000 n=32+34)
BM_Sort_tuple<uint32, uint64, uint32>_Descending_1               3.96ns ± 2%   4.33ns ± 3%   +9.34%  (p=0.000 n=32+36)
BM_Sort_tuple<uint32, uint64, uint32>_Descending_4               3.65ns ± 2%   3.82ns ± 4%   +4.55%  (p=0.000 n=33+38)
BM_Sort_tuple<uint32, uint64, uint32>_Descending_16              5.76ns ± 3%   8.76ns ± 3%  +52.10%  (p=0.000 n=35+38)
BM_Sort_tuple<uint32, uint64, uint32>_Descending_64              4.28ns ± 4%   3.97ns ± 3%   -7.35%  (p=0.000 n=36+39)
BM_Sort_tuple<uint32, uint64, uint32>_Descending_256             3.63ns ± 3%   3.64ns ± 3%     ~     (p=0.304 n=36+38)
BM_Sort_tuple<uint32, uint64, uint32>_Descending_1024            4.13ns ± 3%   3.16ns ± 4%  -23.47%  (p=0.000 n=36+38)
BM_Sort_tuple<uint32, uint64, uint32>_Descending_16384           3.90ns ± 4%   2.93ns ± 3%  -24.81%  (p=0.000 n=37+38)
BM_Sort_tuple<uint32, uint64, uint32>_Descending_262144          4.50ns ± 2%   3.35ns ± 2%  -25.61%  (p=0.000 n=37+38)
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_1            3.96ns ± 2%   4.32ns ± 3%   +9.14%  (p=0.000 n=37+36)
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_4            2.53ns ± 3%   2.56ns ± 4%   +1.12%  (p=0.001 n=37+36)
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_16           2.38ns ± 2%   1.69ns ± 4%  -29.20%  (p=0.000 n=36+34)
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_64           2.60ns ± 4%   3.08ns ± 5%  +18.20%  (p=0.000 n=37+37)
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_256          2.83ns ± 3%   2.97ns ± 3%   +4.99%  (p=0.000 n=36+35)
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_1024         2.43ns ± 2%   2.42ns ± 2%     ~     (p=0.616 n=36+36)
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_16384        2.19ns ± 2%   2.36ns ± 4%   +7.43%  (p=0.000 n=35+36)
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_262144       2.34ns ± 3%   2.37ns ± 6%   +1.11%  (p=0.008 n=35+37)
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_1                3.96ns ± 4%   4.32ns ± 3%   +9.07%  (p=0.000 n=32+35)
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_4                2.62ns ± 3%   2.68ns ± 5%   +1.96%  (p=0.000 n=32+36)
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_16               5.62ns ± 7%   3.10ns ± 3%  -44.80%  (p=0.000 n=32+34)
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_64               5.74ns ± 3%   4.95ns ± 4%  -13.71%  (p=0.000 n=32+33)
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_256              6.81ns ± 5%   3.71ns ±10%  -45.55%  (p=0.000 n=31+33)
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_1024             7.81ns ± 4%   6.29ns ± 4%  -19.49%  (p=0.000 n=31+31)
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_16384            8.73ns ± 2%   7.57ns ±11%  -13.28%  (p=0.000 n=31+32)
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_262144           10.6ns ± 3%    8.9ns ± 4%  -16.67%  (p=0.000 n=34+33)
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_1       3.96ns ± 3%   4.30ns ± 4%   +8.63%  (p=0.000 n=34+32)
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_4       2.76ns ± 2%   2.76ns ± 3%     ~     (p=0.690 n=34+34)
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_16      5.11ns ± 3%   3.73ns ±16%  -26.99%  (p=0.000 n=35+40)
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_64      9.15ns ± 4%   8.32ns ± 5%   -9.09%  (p=0.000 n=37+35)
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_256     11.6ns ± 3%    9.6ns ± 4%  -17.00%  (p=0.000 n=36+35)
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_1024    19.6ns ± 3%   14.3ns ± 4%  -27.33%  (p=0.000 n=36+36)
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_16384   45.7ns ± 3%   37.2ns ± 3%  -18.61%  (p=0.000 n=37+34)
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_262144  50.5ns ± 5%   43.1ns ± 4%  -14.67%  (p=0.000 n=38+35)
BM_Sort_string_Random_1                                          4.65ns ± 3%   4.38ns ± 2%   -5.68%  (p=0.000 n=35+36)
BM_Sort_string_Random_4                                          15.1ns ± 7%   14.9ns ± 5%     ~     (p=0.051 n=35+36)
BM_Sort_string_Random_16                                         45.7ns ± 7%   35.3ns ± 4%  -22.67%  (p=0.000 n=34+33)
BM_Sort_string_Random_64                                         66.6ns ± 3%   58.2ns ± 4%  -12.61%  (p=0.000 n=34+32)
BM_Sort_string_Random_256                                        86.0ns ± 7%   76.8ns ± 4%  -10.77%  (p=0.000 n=35+32)
BM_Sort_string_Random_1024                                        106ns ± 4%     96ns ± 3%   -8.90%  (p=0.000 n=36+31)
BM_Sort_string_Random_16384                                       153ns ± 4%    140ns ± 3%   -8.58%  (p=0.000 n=37+33)
BM_Sort_string_Random_262144                                      211ns ± 5%    195ns ± 5%   -7.61%  (p=0.000 n=34+34)
BM_Sort_string_Ascending_1                                       4.59ns ± 2%   4.35ns ± 4%   -5.19%  (p=0.000 n=32+36)
BM_Sort_string_Ascending_4                                       7.42ns ± 7%   7.38ns ± 7%     ~     (p=0.461 n=37+39)
BM_Sort_string_Ascending_16                                      12.9ns ± 7%    8.7ns ±10%  -33.09%  (p=0.000 n=39+39)
BM_Sort_string_Ascending_64                                      14.9ns ±11%   14.6ns ±12%     ~     (p=0.111 n=40+39)
BM_Sort_string_Ascending_256                                     14.0ns ±16%   14.0ns ±10%     ~     (p=0.473 n=40+39)
BM_Sort_string_Ascending_1024                                    12.8ns ±11%   12.5ns ± 9%   -2.45%  (p=0.041 n=38+38)
BM_Sort_string_Ascending_16384                                   17.1ns ±17%   16.8ns ±15%     ~     (p=0.236 n=37+37)
BM_Sort_string_Ascending_262144                                  17.4ns ±21%   17.1ns ±19%     ~     (p=0.483 n=38+37)
BM_Sort_string_Descending_1                                      4.60ns ± 3%   4.35ns ± 4%   -5.33%  (p=0.000 n=33+33)
BM_Sort_string_Descending_4                                      9.78ns ± 4%   9.75ns ± 6%     ~     (p=0.307 n=37+36)
BM_Sort_string_Descending_16                                     22.5ns ± 4%   39.5ns ± 2%  +75.41%  (p=0.000 n=36+35)
BM_Sort_string_Descending_64                                     21.2ns ± 5%   20.5ns ± 9%   -3.26%  (p=0.000 n=38+36)
BM_Sort_string_Descending_256                                    18.9ns ± 9%   18.3ns ±12%   -3.35%  (p=0.000 n=36+36)
BM_Sort_string_Descending_1024                                   22.3ns ± 8%   17.1ns ± 8%  -23.29%  (p=0.000 n=35+34)
BM_Sort_string_Descending_16384                                  27.5ns ±15%   22.1ns ±11%  -19.56%  (p=0.000 n=38+38)
BM_Sort_string_Descending_262144                                 33.6ns ±16%   25.6ns ±16%  -23.90%  (p=0.000 n=40+37)
BM_Sort_string_SingleElement_1                                   4.58ns ± 2%   4.33ns ± 2%   -5.42%  (p=0.000 n=33+31)
BM_Sort_string_SingleElement_4                                   7.93ns ± 7%   7.95ns ± 7%     ~     (p=0.674 n=35+34)
BM_Sort_string_SingleElement_16                                  17.7ns ± 4%    8.1ns ± 8%  -54.04%  (p=0.000 n=34+35)
BM_Sort_string_SingleElement_64                                  20.0ns ±10%   18.9ns ±10%   -5.55%  (p=0.000 n=37+38)
BM_Sort_string_SingleElement_256                                 19.2ns ±11%   17.1ns ± 7%  -11.09%  (p=0.000 n=40+34)
BM_Sort_string_SingleElement_1024                                18.5ns ±10%   16.6ns ± 8%  -10.48%  (p=0.000 n=36+36)
BM_Sort_string_SingleElement_16384                               16.7ns ±12%   15.2ns ± 9%   -9.02%  (p=0.000 n=37+38)
BM_Sort_string_SingleElement_262144                              15.9ns ±17%   14.3ns ±10%  -10.54%  (p=0.000 n=39+37)
BM_Sort_string_PipeOrgan_1                                       4.59ns ± 3%   4.33ns ± 3%   -5.57%  (p=0.000 n=36+38)
BM_Sort_string_PipeOrgan_4                                       8.18ns ± 6%   8.10ns ± 8%     ~     (p=0.117 n=38+36)
BM_Sort_string_PipeOrgan_16                                      23.9ns ± 5%   16.3ns ± 6%  -31.92%  (p=0.000 n=36+36)
BM_Sort_string_PipeOrgan_64                                      30.6ns ± 7%   28.8ns ± 7%   -5.81%  (p=0.000 n=36+36)
BM_Sort_string_PipeOrgan_256                                     38.4ns ± 6%   22.1ns ± 9%  -42.48%  (p=0.000 n=35+33)
BM_Sort_string_PipeOrgan_1024                                    45.5ns ± 5%   36.6ns ± 5%  -19.55%  (p=0.000 n=36+34)
BM_Sort_string_PipeOrgan_16384                                   57.1ns ± 5%   51.4ns ±15%   -9.92%  (p=0.000 n=34+40)
BM_Sort_string_PipeOrgan_262144                                  77.9ns ±14%   63.0ns ±11%  -19.12%  (p=0.000 n=37+37)
BM_Sort_string_QuickSortAdversary_1                              4.59ns ± 4%   4.33ns ± 3%   -5.74%  (p=0.000 n=32+33)
BM_Sort_string_QuickSortAdversary_4                              14.8ns ± 2%   14.6ns ± 3%   -1.05%  (p=0.002 n=34+34)
BM_Sort_string_QuickSortAdversary_16                             44.9ns ± 4%   34.8ns ± 6%  -22.41%  (p=0.000 n=36+37)
BM_Sort_string_QuickSortAdversary_64                             66.4ns ± 3%   57.7ns ± 5%  -13.18%  (p=0.000 n=35+35)
BM_Sort_string_QuickSortAdversary_256                            85.7ns ± 3%   76.3ns ± 5%  -10.97%  (p=0.000 n=38+36)
BM_Sort_string_QuickSortAdversary_1024                            105ns ± 5%     96ns ± 4%   -9.31%  (p=0.000 n=38+35)
BM_Sort_string_QuickSortAdversary_16384                           152ns ± 4%    140ns ± 4%   -7.50%  (p=0.000 n=36+35)
BM_Sort_string_QuickSortAdversary_262144                          208ns ± 4%    194ns ± 4%   -6.85%  (p=0.000 n=36+36)
BM_Sort_float_Random_1                                           3.68ns ± 3%   3.99ns ± 3%   +8.61%  (p=0.000 n=34+32)
BM_Sort_float_Random_4                                           1.83ns ± 4%   1.84ns ± 5%     ~     (p=0.203 n=35+31)
BM_Sort_float_Random_16                                          11.3ns ± 7%   11.4ns ± 4%     ~     (p=0.123 n=35+31)
BM_Sort_float_Random_64                                          19.8ns ± 5%   19.0ns ±14%   -4.04%  (p=0.002 n=33+40)
BM_Sort_float_Random_256                                         28.1ns ± 4%   21.7ns ±17%  -22.53%  (p=0.000 n=34+33)
BM_Sort_float_Random_1024                                        36.2ns ± 9%   23.2ns ± 8%  -36.06%  (p=0.000 n=34+32)
BM_Sort_float_Random_16384                                       52.3ns ± 3%   25.9ns ± 5%  -50.36%  (p=0.000 n=34+34)
BM_Sort_float_Random_262144                                      68.1ns ± 4%   28.8ns ± 3%  -57.62%  (p=0.000 n=34+36)
BM_Sort_float_Ascending_1                                        3.65ns ± 3%   3.66ns ± 3%     ~     (p=0.625 n=33+34)
BM_Sort_float_Ascending_4                                        1.82ns ± 3%   1.84ns ± 4%   +1.15%  (p=0.001 n=34+36)
BM_Sort_float_Ascending_16                                       0.98ns ± 6%   0.99ns ± 3%   +1.49%  (p=0.000 n=35+36)
BM_Sort_float_Ascending_64                                       1.16ns ± 3%   1.40ns ± 3%  +21.38%  (p=0.000 n=37+35)
BM_Sort_float_Ascending_256                                      1.29ns ± 8%   1.29ns ± 4%     ~     (p=0.067 n=35+35)
BM_Sort_float_Ascending_1024                                     1.12ns ± 6%   1.13ns ± 3%   +1.25%  (p=0.001 n=32+36)
BM_Sort_float_Ascending_16384                                    1.03ns ± 2%   1.04ns ± 3%   +0.90%  (p=0.011 n=31+36)
BM_Sort_float_Ascending_262144                                   1.02ns ± 3%   1.03ns ± 3%     ~     (p=0.365 n=33+38)
BM_Sort_float_Descending_1                                       3.65ns ± 3%   3.65ns ± 4%     ~     (p=0.470 n=32+39)
BM_Sort_float_Descending_4                                       1.83ns ±10%   1.84ns ± 4%     ~     (p=0.057 n=32+37)
BM_Sort_float_Descending_16                                      4.59ns ± 3%   4.59ns ± 4%     ~     (p=0.909 n=32+37)
BM_Sort_float_Descending_64                                      2.01ns ± 4%   3.02ns ± 4%  +50.33%  (p=0.000 n=34+38)
BM_Sort_float_Descending_256                                     1.91ns ± 4%   2.55ns ± 3%  +33.07%  (p=0.000 n=34+36)
BM_Sort_float_Descending_1024                                    2.34ns ± 4%   2.20ns ± 3%   -5.85%  (p=0.000 n=36+36)
BM_Sort_float_Descending_16384                                   2.08ns ± 3%   2.00ns ± 3%   -3.76%  (p=0.000 n=37+36)
BM_Sort_float_Descending_262144                                  2.05ns ± 4%   1.95ns ± 4%   -4.96%  (p=0.000 n=37+35)
BM_Sort_float_SingleElement_1                                    3.64ns ± 2%   3.65ns ± 3%     ~     (p=0.547 n=36+36)
BM_Sort_float_SingleElement_4                                    1.81ns ± 3%   1.84ns ± 5%   +1.67%  (p=0.000 n=35+36)
BM_Sort_float_SingleElement_16                                   0.98ns ± 3%   1.00ns ± 5%   +1.87%  (p=0.000 n=36+36)
BM_Sort_float_SingleElement_64                                   1.16ns ± 5%   1.41ns ± 4%  +21.76%  (p=0.000 n=36+34)
BM_Sort_float_SingleElement_256                                  1.16ns ± 3%   1.37ns ± 2%  +18.26%  (p=0.000 n=35+33)
BM_Sort_float_SingleElement_1024                                 1.09ns ± 3%   1.25ns ± 3%  +14.79%  (p=0.000 n=34+35)
BM_Sort_float_SingleElement_16384                                1.02ns ± 5%   1.19ns ± 3%  +16.51%  (p=0.000 n=35+34)
BM_Sort_float_SingleElement_262144                               0.97ns ± 4%   1.18ns ± 3%  +20.82%  (p=0.000 n=34+33)
BM_Sort_float_PipeOrgan_1                                        3.64ns ± 3%   3.66ns ± 3%     ~     (p=0.060 n=33+33)
BM_Sort_float_PipeOrgan_4                                        1.82ns ± 6%   1.84ns ± 4%   +1.12%  (p=0.002 n=33+34)
BM_Sort_float_PipeOrgan_16                                       2.26ns ± 5%   1.93ns ± 6%  -14.67%  (p=0.000 n=33+34)
BM_Sort_float_PipeOrgan_64                                       5.72ns ± 5%   3.50ns ± 6%  -38.89%  (p=0.000 n=33+33)
BM_Sort_float_PipeOrgan_256                                      2.69ns ± 7%   2.74ns ±16%   +1.85%  (p=0.001 n=34+32)
BM_Sort_float_PipeOrgan_1024                                     3.68ns ± 3%   5.17ns ±10%  +40.55%  (p=0.000 n=32+32)
BM_Sort_float_PipeOrgan_16384                                    4.22ns ± 3%   5.99ns ± 8%  +42.02%  (p=0.000 n=31+32)
BM_Sort_float_PipeOrgan_262144                                   5.06ns ± 6%   6.53ns ± 8%  +29.10%  (p=0.000 n=31+33)
BM_Sort_float_QuickSortAdversary_1                               3.66ns ± 4%   3.65ns ± 3%     ~     (p=0.112 n=32+31)
BM_Sort_float_QuickSortAdversary_4                               1.83ns ± 3%   1.83ns ± 3%     ~     (p=0.167 n=32+31)
BM_Sort_float_QuickSortAdversary_16                              0.98ns ± 3%   1.01ns ± 7%   +3.79%  (p=0.000 n=33+34)
BM_Sort_float_QuickSortAdversary_64                              11.1ns ± 4%   15.3ns ± 5%  +38.16%  (p=0.000 n=34+36)
BM_Sort_float_QuickSortAdversary_256                             15.2ns ± 3%   22.3ns ± 4%  +46.97%  (p=0.000 n=35+38)
BM_Sort_float_QuickSortAdversary_1024                            41.1ns ± 4%   41.5ns ± 6%   +1.01%  (p=0.036 n=35+37)
BM_Sort_float_QuickSortAdversary_16384                           60.7ns ± 3%   62.5ns ± 3%   +3.01%  (p=0.000 n=38+35)
BM_Sort_float_QuickSortAdversary_262144                          70.1ns ± 3%   72.8ns ± 5%   +3.79%  (p=0.000 n=38+35)

[nilayvaish]

Ping!

[philnik]

I haven't checked the logic yet, because I'm still not convinced that it's a good idea. While the numbers for random data look great, every other pattern is pessimized a bit to a lot with trivial arithmetic types. The numbers for the non-arithmetic types look good across the board.

libcxx/include/__algorithm/sort.h

144

Why is this named _3? That's quite confusing.

178

You can use std:: in new code. Applies throughout the patch.

269–270

I don't think the comment is necessary here. Could you add a __libcpp_blsr in the same style as the __libcpp_popcount functions?

273–275

That would allow you to make this a template instead of having the same thing twice.

Do you even use __32bit_set anywhere? I couldn't find it.

Could you just use uint64_t and uint32_t directly and just call the __libcpp functions instead of having the extra indirection?

273–275

Why can't these be _LIBCPP_CONSTEXPR?

310–311

Could you add a _LIBCPP_ASSERT for the precondition?

313–315

Could you shorten this to something like // __bitset_partition uses bitsets for storing the outcomes of the comparisons? I think that makes it clear.

318

Could you split this up into a few more functions? There are very clear sections to divide this functions.

470–471

Again, please add a _LIBCPP_ASSERT.

[philnik]

libcxx/include/__algorithm/sort.h

295–296

706–707

723–729

Where do you check that the default comparator is used?

[nilayvaish]

Changes to address reviewer comments.

[nilayvaish]

libcxx/include/__algorithm/sort.h

144

Dropped _3. This was named so likely because it was using __sort3 for the first three elements. I have dropped that code.

178

Changed _VSTD to std throughout the file.

273–275

Fixed.

295–296

I have fixed it. But clang-format might reformat it.

706–707

Same comment as above.

723–729

Fixed. Actually I was not aware how to test for the default comparator. I have now switched to using __use_branchless_sort declaration that is used at other places in this file.

[nilayvaish]

Previous diff failed to apply. So uploading a new one.

[nilayvaish]

Move block_size to detail namespace
Include bits for libcpp_* functions.

[nilayvaish]

Drop inline for __block_size

[nilayvaish]

Change block_size to enum.

We found similar code in string header file as well.

[nilayvaish]

Pinging the reviewers!

[nilayvaish]

Pinging the reviewers!

[nilayvaish]

Pinging the reviewers again!

[philnik]

Sorry it's taking so long. Louis doesn't have a lot of time currently and I think he should take a look first and say if we want to go this direction.

[nilayvaish]

In D122780#3532562, @philnik wrote:

Sorry it's taking so long. Louis doesn't have a lot of time currently and I think he should take a look first and say if we want to go this direction.

I think Louis is in favor of this change. You can read his comment in the earlier version of this diff: https://reviews.llvm.org/D93233. Is there something I can do to speed up the process? Maybe we can involve some of the other libcxx reviewers. What do you think?

[nilayvaish]

Pinging the reviewers!

[thakis]

Have you checked what this does to:

• impact of binary size of outputs
• compile time

? (E.g. for the clang binary, or your favorite medium-size open source project.)

[tschuett]

I am different. I would enjoy a description of the algorithm at the top of the header and not on line 644.

[ldionne]

I am in favour of making our std::sort implementation better, and at some point this did seem like the right path forward. Since then we also made some changes with branchless sorting (ping @marcogelmi), and we added a bunch of benchmarks so that we have a better understanding of the impact of this change. I wonder whether this is still the right approach given that information.

It seems like you rebased onto main with the branchless sort changes and also re-ran the benchmarks against that. Looking at the results, it looks like this basically improves the performance by a fairly significant margin for randomly distributed integers, but seems to also decrease the performance quite a bit for integers with some sort of structure (e.g. already sorted, descending or ascending). In particular, I assume the reduction of branch mispredictions is not a huge factor anymore since we introduced branchless sorting, or am I off here? The fact that it doesn't seem to provide improvements across the board definitely make it a trickier change to vet, since we'll have to decide whether we want to make this tradeoff.

As it stands, we basically have to decide whether to optimize for randomly sorted data or to also take into account common patterns IIUC. That's not a super easy call to make, since we're talking about 40-50% improvements and 40-50% regressions in each case. I remember @Morwenn had mentioned pdqsort previously, and that seemed to be an algorithm that would handle both random data and also patterns properly. Would that solve the problems of this algorithm?

Sorry if this isn't super helpful, but I literally don't know how to make this call. I'd very much welcome the perspective of other folks who have given a lot of thought to sorting algorithms.

FWIW, making a major change to std::sort isn't a problem, as long as we have sufficient tests to validate its correctness, and that we are confident about its performance.

[nilayvaish]

In D122780#3850519, @ldionne wrote:

It seems like you rebased onto main with the branchless sort changes and also re-ran the benchmarks against that. Looking at the results, it looks like this basically improves the performance by a fairly significant margin for randomly distributed integers, but seems to also decrease the performance quite a bit for integers with some sort of structure (e.g. already sorted, descending or ascending). In particular, I assume the reduction of branch mispredictions is not a huge factor anymore since we introduced branchless sorting, or am I off here? The fact that it doesn't seem to provide improvements across the board definitely make it a trickier change to vet, since we'll have to decide whether we want to make this tradeoff.

As it stands, we basically have to decide whether to optimize for randomly sorted data or to also take into account common patterns IIUC. That's not a super easy call to make, since we're talking about 40-50% improvements and 40-50% regressions in each case. I remember @Morwenn had mentioned pdqsort previously, and that seemed to be an algorithm that would handle both random data and also patterns properly. Would that solve the problems of this algorithm?

Sorry if this isn't super helpful, but I literally don't know how to make this call. I'd very much welcome the perspective of other folks who have given a lot of thought to sorting algorithms.

FWIW, making a major change to std::sort isn't a problem, as long as we have sufficient tests to validate its correctness, and that we are confident about its performance.

Below I provide the benchmark numbers for both BlockQuickSort and PdqSort. The baseline in both cases is the current implementation of std::sort. The numbers were collected on Intel's Skylake machines. Each benchmark was executed 20 times. To get to a combined performance number, I have added weights for each of the benchmark. The weights are just some bunch numbers I chose, I do not have any empirical data to justify these. I assumed that randomly permuted inputs have a significantly higher probability and that medium length sequences are also more probable than super short and super long sequences. The weighted average appears at the end: 15% improvement overall. Both PdqSort and BlockQuickSort arrive at a similar weighted average. I genreally think that the two implementations perform close to each other. So we can choose either.

`															
			  					BlockQuickSort							PdqSort						
name						old cpu/op		new cpu/op		delta			old cpu/op		new cpu/op		delta		Weight
BM_Sort_uint32_Random_1				4.27ns ± 1%		4.41ns ± 1%		3.16%			4.49ns ±13%		3.77ns ± 2%		-16.01%		10
BM_Sort_uint32_Random_4				1.96ns ± 1%		1.96ns ± 1%		0.00%			1.98ns ± 6%		6.25ns ± 3%		216.00%		100
BM_Sort_uint32_Random_16			10.5ns ± 0%		11.2ns ± 0%		6.31%			10.6ns ± 1%		11.3ns ± 2%		6.93%		1000
BM_Sort_uint32_Random_64			18.9ns ± 1%		17.1ns ± 1%		-9.36%			19.0ns ± 2%		16.9ns ± 2%		-10.94%		1000
BM_Sort_uint32_Random_256			26.6ns ± 1%		21.3ns ± 1%		-20.03%			26.5ns ± 1%		20.5ns ± 1%		-22.84%		1000
BM_Sort_uint32_Random_1024			34.1ns ± 1%		24.5ns ± 5%		-28.15%			34.2ns ± 1%		23.0ns ± 1%		-32.61%		1000
BM_Sort_uint32_Random_16384			49.1ns ± 1%		29.8ns ± 0%		-39.30%			49.4ns ± 2%		27.4ns ± 1%		-44.58%		100
BM_Sort_uint32_Random_262144			63.8ns ± 1%		35.3ns ± 1%		-44.61%			64.0ns ± 1%		31.7ns ± 1%		-50.51%		10
BM_Sort_uint32_Ascending_1			4.27ns ± 0%		4.42ns ± 1%		3.47%			4.28ns ± 1%		3.78ns ± 1%		-11.66%		1
BM_Sort_uint32_Ascending_4			2.05ns ±14%		1.98ns ± 0%		-3.68%			1.97ns ± 1%		1.74ns ± 1%		-11.46%		1
BM_Sort_uint32_Ascending_16			0.93ns ±13%		0.85ns ± 1%		-8.51%			0.89ns ± 0%		0.89ns ± 1%		0.00%		1
BM_Sort_uint32_Ascending_64			1.15ns ±13%		1.29ns ± 1%		11.64%			1.09ns ± 0%		1.52ns ± 1%		38.61%		1
BM_Sort_uint32_Ascending_256			1.29ns ±13%		1.44ns ± 0%		11.95%			1.24ns ± 1%		1.55ns ± 1%		25.71%		1
BM_Sort_uint32_Ascending_1024			1.09ns ±14%		1.26ns ± 1%		15.89%			1.04ns ± 1%		1.37ns ± 3%		31.41%		1
BM_Sort_uint32_Ascending_16384			1.01ns ±13%		1.20ns ± 1%		19.09%			0.96ns ± 0%		1.31ns ± 1%		35.76%		1
BM_Sort_uint32_Ascending_262144			0.96ns ± 1%		1.18ns ± 1%		22.80%			0.96ns ± 1%		1.30ns ± 2%		34.60%		1
BM_Sort_uint32_Descending_1			4.27ns ± 1%		4.42ns ± 1%		3.63%			4.28ns ± 1%		3.77ns ± 1%		-11.87%		1
BM_Sort_uint32_Descending_4			1.96ns ± 1%		1.95ns ± 1%		0.00%			2.05ns ±13%		2.44ns ± 1%		18.65%		1
BM_Sort_uint32_Descending_16			4.28ns ±11%		4.32ns ± 2%		0.00%			4.21ns ±13%		4.60ns ± 3%		9.17%		1
BM_Sort_uint32_Descending_64			2.12ns ± 9%		2.95ns ± 1%		38.73%			2.05ns ±13%		3.00ns ± 1%		46.11%		1
BM_Sort_uint32_Descending_256			2.29ns ± 9%		3.01ns ± 0%		31.56%			2.20ns ±14%		2.77ns ± 1%		26.14%		1
BM_Sort_uint32_Descending_1024			2.47ns ± 9%		2.86ns ± 0%		15.65%			2.38ns ±13%		2.58ns ± 2%		8.41%		1
BM_Sort_uint32_Descending_16384			2.15ns ± 9%		2.73ns ± 1%		27.04%			2.07ns ±13%		2.42ns ± 1%		17.10%		1
BM_Sort_uint32_Descending_262144		2.12ns ± 9%		2.71ns ± 1%		27.39%			2.04ns ±13%		2.40ns ± 2%		17.67%		1
BM_Sort_uint32_SingleElement_1			4.66ns ± 9%		4.42ns ± 0%		0.00%			4.44ns ±11%		4.08ns ± 9%		-8.09%		1
BM_Sort_uint32_SingleElement_4			2.10ns ±11%		2.08ns ±11%		0.00%			1.94ns ± 1%		1.93ns ±10%		0.00%		1
BM_Sort_uint32_SingleElement_16			0.89ns ± 0%		0.92ns ±10%		0.00%			0.90ns ± 1%		1.05ns ±10%		16.78%		1
BM_Sort_uint32_SingleElement_64			0.73ns ± 0%		1.67ns ±10%		129.82%			0.72ns ± 1%		1.53ns ±10%		111.51%		1
BM_Sort_uint32_SingleElement_256		0.83ns ± 1%		1.43ns ±10%		72.31%			0.83ns ± 1%		1.30ns ±10%		56.47%		1
BM_Sort_uint32_SingleElement_1024		0.76ns ± 2%		1.30ns ±10%		70.36%			0.76ns ± 2%		1.14ns ± 8%		49.38%		1
BM_Sort_uint32_SingleElement_16384		0.66ns ± 1%		1.22ns ±13%		85.32%			0.66ns ± 1%		1.02ns ± 5%		54.70%		1
BM_Sort_uint32_SingleElement_262144		0.65ns ± 1%		1.14ns ± 1%		76.14%			0.65ns ± 1%		0.98ns ± 3%		51.70%		1
BM_Sort_uint32_PipeOrgan_1			4.27ns ± 0%		4.42ns ± 1%		3.43%			4.29ns ± 1%		3.78ns ± 1%		-12.01%		1
BM_Sort_uint32_PipeOrgan_4			1.94ns ± 0%		1.97ns ± 1%		1.38%			1.94ns ± 0%		1.89ns ± 1%		-2.76%		1
BM_Sort_uint32_PipeOrgan_16			1.77ns ± 0%		1.82ns ± 0%		2.67%			1.77ns ± 1%		2.07ns ± 1%		17.10%		1
BM_Sort_uint32_PipeOrgan_64			4.56ns ±13%		3.49ns ± 0%		-23.44%			4.35ns ± 1%		4.50ns ± 1%		3.53%		1
BM_Sort_uint32_PipeOrgan_256			2.71ns ±13%		3.13ns ±13%		15.54%			2.59ns ± 1%		3.80ns ± 1%		46.54%		1
BM_Sort_uint32_PipeOrgan_1024			3.64ns ±13%		6.13ns ±11%		68.19%			3.47ns ± 1%		5.18ns ± 2%		49.18%		1
BM_Sort_uint32_PipeOrgan_16384			4.43ns ±13%		7.65ns ±10%		72.70%			4.21ns ± 0%		6.00ns ± 1%		42.45%		1
BM_Sort_uint32_PipeOrgan_262144			5.28ns ±13%		8.83ns ±11%		67.17%			5.04ns ± 0%		6.79ns ± 1%		34.71%		1
BM_Sort_uint32_QuickSortAdversary_1		4.47ns ±13%		4.70ns ±11%		5.06%			4.27ns ± 0%		3.77ns ± 1%		-11.77%		1
BM_Sort_uint32_QuickSortAdversary_4		2.00ns ± 9%		1.98ns ± 1%		0.00%			1.97ns ± 0%		1.74ns ± 1%		-11.27%		1
BM_Sort_uint32_QuickSortAdversary_16		0.89ns ± 1%		0.90ns ±16%		0.63%			0.89ns ± 0%		0.93ns ± 1%		4.28%		1
BM_Sort_uint32_QuickSortAdversary_64		13.9ns ± 0%		18.4ns ± 0%		32.53%			14.7ns ±12%		15.5ns ± 1%		5.29%		1
BM_Sort_uint32_QuickSortAdversary_256		20.5ns ± 0%		26.8ns ± 0%		31.00%			21.8ns ±12%		20.6ns ± 1%		0.00%		1
BM_Sort_uint32_QuickSortAdversary_1024		29.3ns ± 0%		37.4ns ± 1%		27.73%			31.1ns ±12%		28.2ns ± 3%		-9.36%		1
BM_Sort_uint32_QuickSortAdversary_16384		47.2ns ± 0%		59.7ns ± 2%		26.46%			50.1ns ±12%		44.7ns ± 1%		-10.89%		1
BM_Sort_uint32_QuickSortAdversary_262144	66.6ns ± 0%		78.6ns ± 1%		17.96%			70.8ns ±12%		60.0ns ± 1%		-15.32%		1
BM_Sort_uint64_Random_1				4.26ns ± 0%		4.41ns ± 1%		3.44%			4.52ns ±13%		3.77ns ± 1%		-16.41%		10
BM_Sort_uint64_Random_4				1.96ns ± 0%		1.95ns ± 1%		-0.34%			2.06ns ±13%		6.22ns ± 1%		202.72%		100
BM_Sort_uint64_Random_16			10.5ns ± 0%		11.6ns ± 1%		10.77%			10.9ns ±14%		10.5ns ± 1%		0.00%		1000
BM_Sort_uint64_Random_64			18.8ns ± 0%		17.5ns ± 1%		-6.60%			18.8ns ± 3%		16.7ns ± 1%		-11.33%		1000
BM_Sort_uint64_Random_256			26.4ns ± 0%		21.7ns ± 1%		-17.88%			26.4ns ± 0%		20.4ns ± 1%		-22.67%		1000
BM_Sort_uint64_Random_1024			33.8ns ± 1%		24.6ns ± 1%		-27.15%			33.8ns ± 0%		22.7ns ± 1%		-32.91%		1000
BM_Sort_uint64_Random_16384			48.7ns ± 0%		30.1ns ± 1%		-38.10%			48.7ns ± 0%		27.1ns ± 1%		-44.21%		100
BM_Sort_uint64_Random_262144			63.4ns ± 1%		35.7ns ± 1%		-43.71%			63.3ns ± 1%		31.5ns ± 2%		-50.24%		10
BM_Sort_uint64_Ascending_1			4.28ns ± 1%		4.41ns ± 1%		3.08%			4.27ns ± 1%		3.77ns ± 1%		-11.80%		1
BM_Sort_uint64_Ascending_4			1.96ns ± 1%		1.96ns ± 0%		0.00%			1.95ns ± 0%		1.81ns ± 1%		-7.50%		1
BM_Sort_uint64_Ascending_16			0.89ns ± 1%		0.93ns ± 1%		3.79%			0.89ns ± 1%		1.09ns ± 1%		21.85%		1
BM_Sort_uint64_Ascending_64			1.20ns ±13%		1.31ns ± 1%		9.64%			1.15ns ± 1%		1.52ns ± 1%		32.50%		1
BM_Sort_uint64_Ascending_256			1.42ns ±12%		1.50ns ± 1%		5.25%			1.37ns ± 2%		1.50ns ± 3%		9.43%		1
BM_Sort_uint64_Ascending_1024			1.17ns ±12%		1.28ns ± 1%		9.80%			1.13ns ± 1%		1.31ns ± 2%		16.35%		1
BM_Sort_uint64_Ascending_16384			1.05ns ±12%		1.21ns ± 1%		15.72%			1.00ns ± 1%		1.16ns ± 1%		15.71%		1
BM_Sort_uint64_Ascending_262144			1.05ns ±13%		1.20ns ± 1%		14.62%			1.01ns ± 1%		1.15ns ± 1%		14.46%		1
BM_Sort_uint64_Descending_1			4.27ns ± 1%		4.42ns ± 1%		3.41%			4.27ns ± 1%		3.77ns ± 1%		-11.74%		1
BM_Sort_uint64_Descending_4			1.95ns ± 0%		1.96ns ± 0%		0.32%			2.04ns ±14%		2.44ns ± 1%		19.76%		1
BM_Sort_uint64_Descending_16			3.87ns ± 1%		4.13ns ± 1%		6.73%			4.08ns ±13%		5.15ns ± 1%		26.21%		1
BM_Sort_uint64_Descending_64			1.98ns ± 5%		2.97ns ± 1%		50.29%			2.05ns ±13%		2.94ns ± 2%		43.02%		1
BM_Sort_uint64_Descending_256			2.18ns ±10%		3.09ns ± 1%		41.56%			2.14ns ±12%		2.88ns ± 2%		34.52%		1
BM_Sort_uint64_Descending_1024			2.46ns ± 9%		2.86ns ± 1%		16.28%			2.36ns ±12%		2.43ns ± 1%		2.65%		1
BM_Sort_uint64_Descending_16384			2.13ns ± 9%		2.75ns ± 2%		29.10%			2.04ns ±13%		2.28ns ± 1%		11.95%		1
BM_Sort_uint64_Descending_262144		2.14ns ± 9%		2.72ns ± 1%		27.48%			2.06ns ±12%		2.30ns ± 1%		11.59%		1
BM_Sort_uint64_SingleElement_1			4.67ns ± 9%		4.42ns ± 0%		0.00%			4.38ns ±10%		4.18ns ±10%		0.00%		1
BM_Sort_uint64_SingleElement_4			2.14ns ± 9%		2.04ns ±14%		0.00%			1.96ns ± 0%		2.01ns ±10%		0.00%		1
BM_Sort_uint64_SingleElement_16			0.89ns ± 1%		0.99ns ±11%		10.85%			0.89ns ± 0%		1.21ns ±10%		35.14%		1
BM_Sort_uint64_SingleElement_64			1.09ns ± 1%		1.83ns ±11%		68.80%			1.09ns ± 1%		1.70ns ± 9%		56.29%		1
BM_Sort_uint64_SingleElement_256		1.26ns ± 3%		1.48ns ±10%		18.25%			1.26ns ± 2%		1.46ns ± 4%		16.46%		1
BM_Sort_uint64_SingleElement_1024		1.09ns ± 1%		1.30ns ±10%		19.87%			1.08ns ± 1%		1.26ns ± 2%		16.01%		1
BM_Sort_uint64_SingleElement_16384		1.04ns ± 1%		1.23ns ±12%		19.17%			1.04ns ± 1%		1.24ns ± 5%		19.30%		1
BM_Sort_uint64_SingleElement_262144		1.01ns ± 1%		1.15ns ± 2%		13.41%			1.01ns ± 1%		1.17ns ± 3%		14.88%		1
BM_Sort_uint64_PipeOrgan_1			4.27ns ± 1%		4.42ns ± 1%		3.40%			4.27ns ± 0%		3.78ns ± 1%		-11.58%		1
BM_Sort_uint64_PipeOrgan_4			1.96ns ± 0%		1.96ns ± 1%		0.00%			1.96ns ± 0%		1.97ns ± 1%		0.42%		1
BM_Sort_uint64_PipeOrgan_16			1.82ns ± 9%		1.91ns ± 1%		4.60%			1.81ns ± 0%		2.17ns ± 1%		20.11%		1
BM_Sort_uint64_PipeOrgan_64			4.56ns ±13%		3.48ns ± 4%		-23.73%			4.37ns ± 1%		4.30ns ± 1%		-1.66%		1
BM_Sort_uint64_PipeOrgan_256			2.81ns ±13%		3.31ns ±10%		17.65%			2.70ns ± 1%		3.69ns ± 1%		37.06%		1
BM_Sort_uint64_PipeOrgan_1024			3.73ns ±14%		6.35ns ±10%		70.14%			3.60ns ± 2%		5.11ns ± 1%		42.01%		1
BM_Sort_uint64_PipeOrgan_16384			4.40ns ±13%		7.91ns ±10%		79.99%			4.20ns ± 1%		5.86ns ± 1%		39.65%		1
BM_Sort_uint64_PipeOrgan_262144			5.30ns ±13%		9.10ns ±10%		71.74%			5.06ns ± 1%		6.68ns ± 1%		32.06%		1
BM_Sort_uint64_QuickSortAdversary_1		4.32ns ± 8%		4.47ns ± 5%		3.35%			4.27ns ± 1%		3.77ns ± 1%		-11.70%		1
BM_Sort_uint64_QuickSortAdversary_4		1.95ns ± 0%		1.96ns ± 1%		0.29%			2.03ns ±14%		1.81ns ± 1%		-11.02%		1
BM_Sort_uint64_QuickSortAdversary_16		0.89ns ± 1%		0.91ns ± 1%		2.17%			0.95ns ±12%		1.08ns ± 2%		14.17%		1
BM_Sort_uint64_QuickSortAdversary_64		13.9ns ± 0%		18.7ns ± 0%		34.55%			14.7ns ±12%		16.0ns ± 1%		0.00%		1
BM_Sort_uint64_QuickSortAdversary_256		20.6ns ± 1%		26.7ns ± 1%		29.68%			21.9ns ±11%		21.0ns ± 1%		0.00%		1
BM_Sort_uint64_QuickSortAdversary_1024		29.1ns ± 0%		37.3ns ± 1%		28.18%			30.9ns ±12%		28.2ns ± 1%		-8.58%		1
BM_Sort_uint64_QuickSortAdversary_16384		47.6ns ± 0%		59.6ns ± 1%		25.26%			51.5ns ±10%		45.7ns ± 1%		-11.16%		1
BM_Sort_uint64_QuickSortAdversary_262144	66.9ns ± 1%		80.8ns ± 1%		20.77%			73.2ns ±11%		63.2ns ± 2%		-13.65%		1
BM_Sort_pair<uint32, uint32>_Random_1		4.43ns ± 1%		4.42ns ± 1%		-0.29%			4.67ns ±13%		3.78ns ± 1%		-19.16%		10
BM_Sort_pair<uint32, uint32>_Random_4		6.70ns ± 0%		6.78ns ± 1%		1.18%			6.70ns ± 1%		6.54ns ± 2%		-2.42%		100
BM_Sort_pair<uint32, uint32>_Random_16		25.6ns ± 1%		17.3ns ± 2%		-32.40%			25.5ns ± 1%		15.3ns ± 1%		-39.91%		1000
BM_Sort_pair<uint32, uint32>_Random_64		35.9ns ± 1%		28.4ns ± 1%		-20.89%			35.9ns ± 1%		27.6ns ± 1%		-23.20%		1000
BM_Sort_pair<uint32, uint32>_Random_256		43.6ns ± 0%		35.6ns ± 1%		-18.15%			43.6ns ± 1%		35.1ns ± 1%		-19.36%		1000
BM_Sort_pair<uint32, uint32>_Random_1024	51.5ns ± 0%		42.8ns ± 1%		-16.76%			51.5ns ± 1%		42.6ns ± 2%		-17.35%		1000
BM_Sort_pair<uint32, uint32>_Random_16384	67.6ns ± 1%		58.5ns ± 1%		-13.51%			67.8ns ± 2%		58.3ns ± 2%		-14.09%		100
BM_Sort_pair<uint32, uint32>_Random_262144	83.9ns ± 4%		74.4ns ± 4%		-11.37%			83.7ns ± 4%		73.9ns ± 4%		-11.72%		10
BM_Sort_pair<uint32, uint32>_Ascending_1	4.44ns ± 1%		4.42ns ± 1%		-0.27%			4.44ns ± 0%		3.78ns ± 1%		-14.92%		1
BM_Sort_pair<uint32, uint32>_Ascending_4	2.13ns ± 0%		2.12ns ± 1%		0.00%			2.13ns ± 1%		2.10ns ± 4%		-1.26%		1
BM_Sort_pair<uint32, uint32>_Ascending_16	2.23ns ± 0%		1.61ns ± 2%		-27.64%			2.22ns ± 1%		1.58ns ± 1%		-28.86%		1
BM_Sort_pair<uint32, uint32>_Ascending_64	1.39ns ± 1%		1.50ns ± 1%		7.76%			1.39ns ± 1%		1.66ns ± 1%		19.24%		1
BM_Sort_pair<uint32, uint32>_Ascending_256	1.56ns ±13%		1.57ns ± 2%		0.94%			1.49ns ± 1%		1.81ns ± 2%		21.72%		1
BM_Sort_pair<uint32, uint32>_Ascending_1024	1.43ns ±13%		1.38ns ± 1%		0.00%			1.37ns ± 1%		1.66ns ± 2%		21.47%		1
BM_Sort_pair<uint32, uint32>_Ascending_16384	1.27ns ±13%		1.21ns ± 1%		-4.34%			1.21ns ± 1%		1.49ns ± 2%		23.07%		1
BM_Sort_pair<uint32, uint32>_Ascending_262144	1.26ns ±12%		1.21ns ± 2%		0.00%			1.21ns ± 1%		1.48ns ± 1%		22.73%		1
BM_Sort_pair<uint32, uint32>_Descending_1	4.63ns ±13%		4.42ns ± 0%		-4.44%			4.43ns ± 1%		3.79ns ± 1%		-14.39%		1
BM_Sort_pair<uint32, uint32>_Descending_4	3.00ns ± 1%		2.97ns ± 1%		-0.85%			2.99ns ± 1%		3.31ns ± 1%		10.61%		1
BM_Sort_pair<uint32, uint32>_Descending_16	4.83ns ± 1%		7.39ns ± 1%		52.92%			5.02ns ±14%		7.30ns ± 2%		45.36%		1
BM_Sort_pair<uint32, uint32>_Descending_64	3.25ns ± 1%		2.85ns ± 1%		-12.27%			3.43ns ±12%		3.12ns ± 1%		-8.86%		1
BM_Sort_pair<uint32, uint32>_Descending_256	2.78ns ± 1%		2.78ns ± 1%		0.00%			2.89ns ±13%		3.22ns ± 1%		11.36%		1
BM_Sort_pair<uint32, uint32>_Descending_1024	3.38ns ± 0%		2.32ns ± 1%		-31.18%			3.56ns ±13%		2.61ns ± 1%		-26.54%		1
BM_Sort_pair<uint32, uint32>_Descending_16384	3.04ns ± 1%		2.12ns ± 1%		-30.14%			3.19ns ±13%		2.40ns ± 1%		-24.79%		1
BM_Sort_pair<uint32, uint32>_Descending_262144	3.21ns ±13%		2.13ns ± 0%		-33.77%			3.21ns ±13%		2.40ns ± 1%		-25.28%		1
BM_Sort_pair<uint32, uint32>_SingleElement_1	4.83ns ± 9%		4.42ns ± 0%		-8.47%			4.66ns ±13%		3.95ns ±14%		-15.29%		1
BM_Sort_pair<uint32, uint32>_SingleElement_4	2.41ns ± 9%		2.13ns ± 0%		-11.64%			2.31ns ±13%		2.44ns ±10%		0.00%		1
BM_Sort_pair<uint32, uint32>_SingleElement_16	2.02ns ±23%		1.75ns ± 1%		0.00%			1.74ns ±17%		1.81ns ±10%		0.00%		1
BM_Sort_pair<uint32, uint32>_SingleElement_64	1.53ns ± 9%		1.91ns ±13%		24.46%			1.41ns ± 1%		2.01ns ±11%		43.16%		1
BM_Sort_pair<uint32, uint32>_SingleElement_256	1.71ns ± 8%		2.00ns ±11%		17.25%			1.59ns ± 2%		1.85ns ±10%		16.66%		1
BM_Sort_pair<uint32, uint32>_SingleElement_1024		1.50ns ±13%		1.75ns ±12%		16.59%			1.45ns ± 1%		1.52ns ±10%		0.00%		1
BM_Sort_pair<uint32, uint32>_SingleElement_16384	1.30ns ± 1%		1.71ns ±11%		31.45%			1.31ns ± 1%		1.44ns ±10%		10.59%		1
BM_Sort_pair<uint32, uint32>_SingleElement_262144	1.29ns ± 1%		1.71ns ±11%		32.70%			1.29ns ± 0%		1.37ns ±12%		0.00%		1
BM_Sort_pair<uint32, uint32>_PipeOrgan_1		4.43ns ± 0%		4.74ns ±11%		0.00%			4.44ns ± 1%		3.78ns ± 1%		-14.72%		1
BM_Sort_pair<uint32, uint32>_PipeOrgan_4		2.29ns ± 0%		2.44ns ±11%		0.00%			2.29ns ± 0%		2.35ns ± 1%		2.76%		1
BM_Sort_pair<uint32, uint32>_PipeOrgan_16		4.68ns ± 1%		3.01ns ± 1%		-35.66%			4.68ns ± 1%		2.83ns ± 1%		-39.52%		1
BM_Sort_pair<uint32, uint32>_PipeOrgan_64		4.52ns ± 1%		4.05ns ± 1%		-10.38%			4.52ns ± 1%		5.29ns ± 1%		17.23%		1
BM_Sort_pair<uint32, uint32>_PipeOrgan_256		5.60ns ± 1%		2.80ns ± 1%		-49.95%			5.59ns ± 1%		4.33ns ± 1%		-22.61%		1
BM_Sort_pair<uint32, uint32>_PipeOrgan_1024		6.41ns ± 1%		5.54ns ± 1%		-13.62%			6.40ns ± 1%		5.49ns ± 1%		-14.31%		1
BM_Sort_pair<uint32, uint32>_PipeOrgan_16384		7.27ns ± 1%		6.27ns ± 1%		-13.68%			7.26ns ± 0%		5.97ns ± 1%		-17.72%		1
BM_Sort_pair<uint32, uint32>_PipeOrgan_262144		8.11ns ± 1%		6.98ns ± 5%		-13.96%			8.11ns ± 1%		6.65ns ± 1%		-18.00%		1
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_1	4.45ns ± 1%		4.42ns ± 1%		-0.71%			4.43ns ± 0%		3.78ns ± 1%		-14.72%		1
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_4	2.30ns ± 8%		2.39ns ±12%		0.00%			2.28ns ± 1%		2.28ns ± 1%		0.00%		1
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_16	4.94ns ±13%		3.11ns ±10%		-36.97%			4.73ns ± 1%		2.78ns ± 1%		-41.18%		1
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_64	7.06ns ±13%		7.96ns ±10%		12.87%			6.74ns ± 0%		7.36ns ± 3%		9.20%		1
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_256	9.69ns ±13%		7.81ns ±11%		-19.36%			9.27ns ± 1%		7.41ns ± 1%		-20.07%		1
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_1024	11.3ns ±14%		10.0ns ±11%		-11.64%			10.9ns ± 1%		9.0ns ± 3%		-17.40%		1
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_16384	34.2ns ±13%		24.3ns ±12%		-28.84%			32.7ns ± 0%		22.9ns ± 1%		-30.03%		1
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_262144	36.3ns ± 0%		26.8ns ±13%		-26.00%			36.3ns ± 0%		25.1ns ± 4%		-30.91%		1
BM_Sort_tuple<uint32, uint64, uint32>_Random_1		4.78ns ± 1%		4.76ns ± 1%		-0.54%			5.07ns ±12%		4.11ns ± 1%		-18.90%		10
BM_Sort_tuple<uint32, uint64, uint32>_Random_4		7.20ns ± 0%		7.29ns ± 3%		1.23%			7.91ns ±14%		7.89ns ± 1%		0.00%		100
BM_Sort_tuple<uint32, uint64, uint32>_Random_16		31.6ns ± 1%		19.7ns ± 2%		-37.59%			34.3ns ±10%		20.4ns ± 1%		-40.67%		1000
BM_Sort_tuple<uint32, uint64, uint32>_Random_64		44.4ns ± 1%		33.7ns ± 1%		-24.11%			48.2ns ±11%		33.8ns ± 1%		-30.04%		1000
BM_Sort_tuple<uint32, uint64, uint32>_Random_256	51.7ns ± 1%		40.4ns ± 0%		-21.84%			56.0ns ±12%		41.2ns ± 1%		-26.43%		1000
BM_Sort_tuple<uint32, uint64, uint32>_Random_1024	59.3ns ± 1%		47.1ns ± 1%		-20.69%			63.6ns ±11%		48.0ns ± 1%		-24.51%		1000
BM_Sort_tuple<uint32, uint64, uint32>_Random_16384	75.6ns ± 1%		63.6ns ± 2%		-15.89%			81.0ns ±11%		64.7ns ± 1%		-20.16%		100
BM_Sort_tuple<uint32, uint64, uint32>_Random_262144	93.5ns ± 2%		81.1ns ± 5%		-13.24%			98.1ns ±13%		81.4ns ± 3%		-17.09%		10
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_1	4.81ns ± 2%		4.76ns ± 1%		-0.94%			4.85ns ± 6%		4.13ns ± 1%		-14.86%		1
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_4	2.33ns ± 2%		2.33ns ± 4%		0.00%			2.35ns ± 3%		2.23ns ± 4%		-5.15%		1
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_16	3.17ns ± 1%		1.74ns ± 2%		-45.24%			3.18ns ± 2%		1.61ns ± 2%		-49.24%		1
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_64	2.57ns ± 3%		2.50ns ± 5%		-2.81%			2.62ns ± 6%		2.77ns ± 2%		6.03%		1
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_256	2.59ns ± 2%		2.49ns ± 4%		-3.67%			2.61ns ± 3%		2.88ns ± 3%		10.45%		1
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_1024	2.23ns ± 4%		2.18ns ± 3%		-2.32%			2.23ns ± 2%		2.48ns ± 2%		10.98%		1
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_16384	2.10ns ± 2%		2.06ns ± 2%		-1.54%			2.11ns ± 2%		2.34ns ± 1%		10.78%		1
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_262144	2.12ns ± 2%		2.08ns ± 2%		-1.59%			2.12ns ± 1%		2.32ns ± 2%		9.44%		1
BM_Sort_tuple<uint32, uint64, uint32>_Descending_1	4.81ns ± 1%		4.78ns ± 2%		-0.55%			4.84ns ± 2%		4.12ns ± 1%		-14.87%		1
BM_Sort_tuple<uint32, uint64, uint32>_Descending_4	3.89ns ± 3%		3.77ns ± 1%		-3.04%			3.89ns ± 1%		4.07ns ± 1%		4.81%		1
BM_Sort_tuple<uint32, uint64, uint32>_Descending_16	5.95ns ±10%		10.26ns ± 1%		72.39%			5.92ns ± 0%		9.28ns ± 3%		56.86%		1
BM_Sort_tuple<uint32, uint64, uint32>_Descending_64	4.63ns ±12%		4.06ns ± 2%		-12.37%			4.48ns ± 3%		4.11ns ± 2%		-8.15%		1
BM_Sort_tuple<uint32, uint64, uint32>_Descending_256	3.82ns ±13%		3.74ns ± 3%		0.00%			3.69ns ± 2%		4.25ns ± 1%		15.14%		1
BM_Sort_tuple<uint32, uint64, uint32>_Descending_1024	4.56ns ±13%		3.23ns ± 1%		-29.31%			4.39ns ± 1%		3.68ns ± 5%		-16.16%		1
BM_Sort_tuple<uint32, uint64, uint32>_Descending_16384	4.23ns ±13%		3.00ns ± 1%		-29.09%			4.06ns ± 1%		3.32ns ± 2%		-18.30%		1
BM_Sort_tuple<uint32, uint64, uint32>_Descending_262144	4.65ns ± 3%		3.40ns ± 1%		-27.01%			4.66ns ± 2%		3.65ns ± 1%		-21.53%		1
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_1		4.82ns ± 2%		4.77ns ± 2%		-1.05%			5.06ns ±14%		4.13ns ± 1%		-18.47%		1
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_4		2.50ns ± 2%		2.51ns ± 4%		0.00%			2.64ns ±15%		2.35ns ± 7%		-10.75%		1
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_16		2.45ns ± 1%		1.99ns ± 2%		-18.72%			2.60ns ±12%		1.69ns ± 5%		-34.99%		1
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_64		2.78ns ±11%		3.36ns ± 4%		20.88%			2.87ns ±13%		2.94ns ± 5%		0.00%		1
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_256		3.11ns ±24%		3.09ns ± 3%		0.00%			3.05ns ±16%		2.99ns ± 9%		0.00%		1
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_1024	2.70ns ± 9%		2.52ns ± 3%		-6.38%			2.63ns ±11%		2.36ns ± 9%		-10.36%		1
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_16384	2.48ns ±12%		2.44ns ± 3%		0.00%			2.30ns ± 2%		2.32ns ± 9%		0.00%		1
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_262144	2.60ns ± 8%		2.45ns ± 7%		-5.71%			2.43ns ± 3%		2.38ns ± 9%		0.00%		1
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_1		5.73ns ±10%		5.05ns ±13%		-11.87%			5.27ns ± 4%		4.61ns ±11%		-12.43%		1
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_4		2.71ns ±12%		2.71ns ±13%		0.00%			2.58ns ± 0%		2.95ns ±10%		14.52%		1
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_16		5.81ns ± 2%		4.29ns ±13%		-26.10%			5.81ns ± 1%		3.64ns ±10%		-37.30%		1
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_64		6.05ns ± 3%		5.64ns ±14%		-6.68%			6.04ns ± 2%		8.07ns ±13%		33.50%		1
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_256		7.43ns ± 3%		4.01ns ±12%		-46.12%			7.45ns ± 1%		5.67ns ± 2%		-23.87%		1
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_1024		8.91ns ± 1%		6.92ns ±14%		-22.30%			8.98ns ± 1%		7.61ns ± 1%		-15.22%		1
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_16384		9.65ns ± 1%		7.87ns ± 1%		-18.47%			9.75ns ± 1%		8.66ns ± 1%		-11.20%		1
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_262144		11.7ns ± 1%		9.2ns ± 1%		-21.28%			11.8ns ± 1%		9.8ns ± 1%		-16.53%		1
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_1	4.80ns ± 2%		4.79ns ± 2%		0.00%			4.83ns ± 2%		4.14ns ± 4%		-14.23%		1
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_4	2.71ns ± 1%		2.71ns ± 2%		0.00%			2.71ns ± 1%		2.69ns ± 1%		-0.74%		1
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_16	5.97ns ± 1%		4.22ns ±13%		-29.33%			5.97ns ± 0%		3.98ns ± 1%		-33.38%		1
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_64	10.0ns ± 2%		9.3ns ±12%		-6.99%			9.95ns ± 1%		9.07ns ± 1%		-8.84%		1
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_256	12.5ns ± 1%		10.7ns ±12%		-13.94%			12.6ns ± 4%		10.2ns ± 1%		-18.73%		1
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_1024	23.2ns ± 2%		15.5ns ±11%		-33.05%			23.3ns ± 4%		14.6ns ± 1%		-37.55%		1
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_16384	48.5ns ± 1%		41.0ns ±10%		-15.46%			48.5ns ± 1%		39.0ns ± 2%		-19.70%		1
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_262144	53.6ns ± 6%		47.2ns ±10%		-11.88%			53.5ns ± 1%		43.7ns ± 1%		-18.20%		1
BM_Sort_string_Random_1				5.01ns ± 1%		5.03ns ± 2%		0.00%			5.29ns ±12%		5.82ns ± 1%		10.12%		10
BM_Sort_string_Random_4				16.3ns ± 4%		16.0ns ± 5%		0.00%			17.2ns ±16%		18.2ns ± 5%		5.71%		100
BM_Sort_string_Random_16			48.7ns ± 3%		38.2ns ± 4%		-21.57%			52.4ns ±13%		41.5ns ± 4%		-20.66%		1000
BM_Sort_string_Random_64			74.6ns ± 3%		65.0ns ± 6%		-12.84%			75.5ns ± 3%		66.6ns ± 4%		-11.81%		1000
BM_Sort_string_Random_256			96.0ns ± 2%		85.1ns ± 2%		-11.35%			96.9ns ± 3%		86.6ns ± 4%		-10.59%		1000
BM_Sort_string_Random_1024			119ns ± 3%		105ns ± 4%		-11.64%			120ns ± 3%		107ns ± 4%		-11.06%		1000
BM_Sort_string_Random_16384			182ns ± 5%		161ns ± 8%		-11.68%			186ns ± 5%		163ns ± 6%		-12.11%		100
BM_Sort_string_Random_262144			265ns ±17%		230ns ±13%		-13.39%			276ns ±22%		227ns ± 9%		-17.60%		10
BM_Sort_string_Ascending_1			5.03ns ± 2%		5.00ns ± 1%		-0.75%			5.05ns ± 2%		5.81ns ± 1%		15.09%		1
BM_Sort_string_Ascending_4			9.03ns ±12%		8.84ns ±14%		0.00%			8.87ns ± 6%		8.98ns ±14%		0.00%		1
BM_Sort_string_Ascending_16			16.0ns ± 9%		10.9ns ±22%		-32.14%			16.5ns ±22%		11.1ns ±12%		-32.85%		1
BM_Sort_string_Ascending_64			20.6ns ±17%		19.8ns ±19%		0.00%			20.6ns ±31%		20.0ns ±23%		0.00%		1
BM_Sort_string_Ascending_256			19.6ns ±19%		19.1ns ±20%		0.00%			19.6ns ±14%		20.0ns ±17%		0.00%		1
BM_Sort_string_Ascending_1024			18.7ns ±14%		17.9ns ±23%		0.00%			19.4ns ±18%		19.2ns ±27%		0.00%		1
BM_Sort_string_Ascending_16384			36.4ns ±28%		34.4ns ±46%		0.00%			39.7ns ±17%		38.0ns ±18%		0.00%		1
BM_Sort_string_Ascending_262144			40.3ns ±32%		36.1ns ±49%		0.00%			44.4ns ±21%		38.8ns ±29%		-12.62%		1
BM_Sort_string_Descending_1			5.05ns ± 2%		5.03ns ± 2%		-0.50%			5.04ns ± 2%		5.81ns ± 2%		15.46%		1
BM_Sort_string_Descending_4			11.3ns ± 7%		11.8ns ±14%		4.51%			11.5ns ± 5%		14.0ns ± 6%		22.42%		1
BM_Sort_string_Descending_16			27.7ns ±13%		47.9ns ±16%		73.17%			27.2ns ± 5%		50.3ns ± 9%		85.19%		1
BM_Sort_string_Descending_64			28.0ns ±19%		26.4ns ±18%		0.00%			28.1ns ±11%		26.3ns ±15%		-6.21%		1
BM_Sort_string_Descending_256			25.7ns ±14%		24.5ns ±27%		0.00%			26.9ns ±15%		24.4ns ±19%		-9.56%		1
BM_Sort_string_Descending_1024			30.5ns ±16%		23.0ns ±19%		-24.39%			32.6ns ±15%		24.3ns ±16%		-25.51%		1
BM_Sort_string_Descending_16384			47.9ns ±20%		42.9ns ±37%		-10.55%			49.1ns ±42%		42.1ns ±30%		-14.24%		1
BM_Sort_string_Descending_262144		69.3ns ±35%		53.2ns ±67%		-23.20%			74.0ns ±50%		56.8ns ±47%		-23.32%		1
BM_Sort_string_SingleElement_1			5.07ns ± 2%		5.09ns ± 7%		0.00%			5.21ns ±13%		5.81ns ± 1%		11.44%		1
BM_Sort_string_SingleElement_4			8.94ns ± 8%		9.14ns ±12%		0.00%			9.03ns ±13%		9.08ns ±11%		0.00%		1
BM_Sort_string_SingleElement_16			20.1ns ± 6%		9.2ns ±13%		-54.12%			20.5ns ± 5%		9.2ns ±11%		-55.09%		1
BM_Sort_string_SingleElement_64			27.9ns ±10%		26.9ns ±20%		0.00%			28.2ns ± 9%		25.1ns ±16%		-11.04%		1
BM_Sort_string_SingleElement_256		25.9ns ± 8%		24.5ns ±23%		-5.43%			26.6ns ± 5%		24.5ns ± 8%		-7.90%		1
BM_Sort_string_SingleElement_1024		24.1ns ±17%		21.4ns ±20%		-11.23%			25.0ns ± 8%		21.6ns ± 6%		-13.53%		1
BM_Sort_string_SingleElement_16384		22.8ns ±16%		21.4ns ±26%		0.00%			24.0ns ±18%		21.7ns ± 9%		-9.38%		1
BM_Sort_string_SingleElement_262144		21.0ns ±23%		20.7ns ±28%		0.00%			22.5ns ±35%		21.7ns ±14%		0.00%		1
BM_Sort_string_PipeOrgan_1			5.10ns ± 2%		5.04ns ± 3%		-1.02%			5.07ns ± 2%		5.83ns ± 2%		14.89%		1
BM_Sort_string_PipeOrgan_4			9.89ns ±13%		9.61ns ±12%		0.00%			10.0ns ±22%		10.3ns ±15%		0.00%		1
BM_Sort_string_PipeOrgan_16			27.3ns ± 8%		18.8ns ±12%		-31.28%			28.4ns ±17%		21.1ns ± 7%		-25.66%		1
BM_Sort_string_PipeOrgan_64			39.1ns ±13%		34.3ns ±18%		-12.35%			40.3ns ±20%		47.8ns ±11%		18.65%		1
BM_Sort_string_PipeOrgan_256			49.4ns ±13%		27.9ns ±16%		-43.50%			49.4ns ± 6%		34.1ns ±15%		-30.98%		1
BM_Sort_string_PipeOrgan_1024			59.6ns ±13%		44.5ns ±20%		-25.30%			58.2ns ± 8%		48.6ns ±16%		-16.42%		1
BM_Sort_string_PipeOrgan_16384			80.8ns ±10%		65.0ns ±19%		-19.64%			82.8ns ±26%		76.8ns ±22%		-7.21%		1
BM_Sort_string_PipeOrgan_262144			126ns ±26%		92ns ±43%		-27.23%			122ns ±33%		106ns ±31%		-12.89%		1
BM_Sort_string_QuickSortAdversary_1		5.02ns ± 1%		5.00ns ± 1%		-0.40%			5.00ns ± 1%		5.82ns ± 1%		16.23%		1
BM_Sort_string_QuickSortAdversary_4		16.3ns ± 4%		16.9ns ±13%		0.00%			16.4ns ± 4%		18.0ns ± 4%		9.75%		1
BM_Sort_string_QuickSortAdversary_16		49.3ns ± 6%		40.3ns ±13%		-18.24%			50.1ns ± 5%		43.3ns ±15%		-13.41%		1
BM_Sort_string_QuickSortAdversary_64		79.1ns ±12%		68.6ns ±15%		-13.24%			77.2ns ± 5%		66.0ns ± 4%		-14.51%		1
BM_Sort_string_QuickSortAdversary_256		97.1ns ± 4%		86.0ns ± 5%		-11.42%			97.6ns ± 3%		86.3ns ± 2%		-11.57%		1
BM_Sort_string_QuickSortAdversary_1024		119ns ± 3%		106ns ± 8%		-11.30%			120ns ± 3%		107ns ± 1%		-10.91%		1
BM_Sort_string_QuickSortAdversary_16384		180ns ±13%		158ns ±12%		-12.06%			190ns ±17%		162ns ± 6%		-14.34%		1
BM_Sort_string_QuickSortAdversary_262144	252ns ±13%		220ns ±13%		-12.61%			272ns ±21%		227ns ± 7%		-16.38%		1
BM_Sort_float_Random_1				4.10ns ± 0%		4.41ns ± 0%		7.43%			4.34ns ±12%		3.63ns ± 2%		-16.37%		10
BM_Sort_float_Random_4				1.72ns ± 0%		1.76ns ± 1%		1.87%			1.83ns ±12%		6.87ns ± 1%		275.77%		100
BM_Sort_float_Random_16				11.0ns ± 1%		11.7ns ± 1%		6.85%			11.0ns ± 2%		12.6ns ± 1%		14.94%		1000
BM_Sort_float_Random_64				19.6ns ± 0%		18.3ns ± 1%		-6.60%			19.6ns ± 1%		19.0ns ± 2%		-3.13%		1000
BM_Sort_float_Random_256			28.1ns ± 0%		22.5ns ± 0%		-19.87%			28.1ns ± 1%		22.9ns ± 1%		-18.46%		1000
BM_Sort_float_Random_1024			36.6ns ± 1%		25.5ns ± 0%		-30.31%			36.7ns ± 1%		25.9ns ± 1%		-29.44%		1000
BM_Sort_float_Random_16384			53.2ns ± 0%		30.9ns ± 1%		-42.00%			53.2ns ± 0%		31.1ns ± 1%		-41.56%		100
BM_Sort_float_Random_262144			69.5ns ± 2%		36.2ns ± 1%		-47.84%			69.5ns ± 2%		36.4ns ± 1%		-47.59%		10
BM_Sort_float_Ascending_1			4.11ns ± 1%		4.41ns ± 1%		7.32%			4.11ns ± 1%		3.62ns ± 1%		-11.90%		1
BM_Sort_float_Ascending_4			1.73ns ± 0%		1.76ns ± 1%		1.77%			1.73ns ± 1%		2.04ns ± 2%		17.76%		1
BM_Sort_float_Ascending_16			0.94ns ± 1%		0.91ns ± 1%		-3.25%			0.94ns ± 0%		1.10ns ± 1%		17.31%		1
BM_Sort_float_Ascending_64			1.15ns ± 1%		1.80ns ± 0%		56.09%			1.15ns ± 0%		1.57ns ± 1%		36.45%		1
BM_Sort_float_Ascending_256			1.27ns ± 2%		1.81ns ± 1%		42.73%			1.27ns ± 1%		1.63ns ± 2%		28.86%		1
BM_Sort_float_Ascending_1024			1.11ns ± 1%		1.65ns ± 1%		49.39%			1.11ns ± 1%		1.44ns ± 3%		29.65%		1
BM_Sort_float_Ascending_16384			1.04ns ± 1%		1.59ns ± 1%		52.25%			1.04ns ± 0%		1.35ns ± 4%		29.89%		1
BM_Sort_float_Ascending_262144			1.03ns ± 1%		1.58ns ± 0%		52.92%			1.03ns ± 0%		1.22ns ± 2%		18.32%		1
BM_Sort_float_Descending_1			4.28ns ±14%		4.41ns ± 1%		2.89%			4.12ns ± 8%		3.62ns ± 1%		-12.15%		1
BM_Sort_float_Descending_4			1.73ns ± 1%		1.76ns ± 1%		1.66%			1.80ns ±14%		2.53ns ± 1%		40.19%		1
BM_Sort_float_Descending_16			5.04ns ± 1%		4.72ns ± 1%		-6.36%			5.26ns ±14%		4.76ns ± 1%		-9.44%		1
BM_Sort_float_Descending_64			2.07ns ± 1%		3.44ns ± 1%		66.02%			2.18ns ±13%		3.47ns ± 1%		59.20%		1
BM_Sort_float_Descending_256			2.02ns ± 1%		3.34ns ± 0%		65.55%			2.12ns ±13%		3.25ns ± 2%		53.09%		1
BM_Sort_float_Descending_1024			2.38ns ± 1%		3.18ns ± 1%		33.86%			2.48ns ±14%		2.83ns ± 1%		14.08%		1
BM_Sort_float_Descending_16384			2.12ns ± 1%		3.08ns ± 1%		45.43%			2.12ns ± 2%		2.57ns ± 2%		21.13%		1
BM_Sort_float_Descending_262144			2.09ns ± 1%		3.07ns ± 1%		46.51%			2.10ns ± 1%		2.57ns ± 1%		22.61%		1
BM_Sort_float_SingleElement_1			4.30ns ±13%		4.47ns ±11%		3.80%			4.11ns ± 1%		3.63ns ± 2%		-11.60%		1
BM_Sort_float_SingleElement_4			1.84ns ±11%		1.86ns ±12%		0.93%			1.73ns ± 1%		2.06ns ± 8%		19.13%		1
BM_Sort_float_SingleElement_16			1.02ns ±10%		1.56ns ±13%		53.04%			0.94ns ± 1%		1.18ns ±11%		25.23%		1
BM_Sort_float_SingleElement_64			1.24ns ±12%		2.09ns ±13%		68.70%			1.16ns ± 0%		1.58ns ±10%		35.98%		1
BM_Sort_float_SingleElement_256			1.34ns ±11%		1.91ns ± 3%		42.54%			1.26ns ± 1%		1.41ns ±10%		12.00%		1
BM_Sort_float_SingleElement_1024		1.26ns ±11%		1.80ns ± 3%		42.89%			1.19ns ± 1%		1.28ns ± 9%		0.00%		1
BM_Sort_float_SingleElement_16384		1.18ns ±14%		1.75ns ± 1%		48.21%			1.13ns ± 0%		1.20ns ±10%		0.00%		1
BM_Sort_float_SingleElement_262144		1.13ns ± 2%		1.75ns ± 8%		55.35%			1.12ns ± 0%		1.17ns ±10%		0.00%		1
BM_Sort_float_PipeOrgan_1			4.11ns ± 1%		4.42ns ± 1%		7.55%			4.11ns ± 1%		3.84ns ±12%		0.00%		1
BM_Sort_float_PipeOrgan_4			1.73ns ± 0%		1.78ns ±11%		3.07%			1.73ns ± 1%		2.04ns ± 1%		17.77%		1
BM_Sort_float_PipeOrgan_16			1.96ns ± 1%		2.05ns ±11%		0.00%			1.96ns ± 1%		2.08ns ± 1%		6.46%		1
BM_Sort_float_PipeOrgan_64			6.41ns ± 1%		3.95ns ±11%		-38.40%			6.41ns ± 0%		4.97ns ± 1%		-22.52%		1
BM_Sort_float_PipeOrgan_256			2.76ns ± 1%		3.56ns ±10%		28.91%			2.76ns ± 0%		4.13ns ± 2%		49.87%		1
BM_Sort_float_PipeOrgan_1024			3.67ns ± 1%		6.24ns ± 9%		70.06%			3.67ns ± 1%		5.72ns ± 1%		56.04%		1
BM_Sort_float_PipeOrgan_16384			4.33ns ± 1%		7.35ns ±10%		69.67%			4.33ns ± 1%		6.51ns ± 1%		50.30%		1
BM_Sort_float_PipeOrgan_262144			5.16ns ± 0%		8.17ns ±11%		58.39%			5.16ns ± 0%		7.33ns ± 1%		42.12%		1
BM_Sort_float_QuickSortAdversary_1		4.13ns ± 8%		4.69ns ±11%		13.50%			4.11ns ± 1%		3.61ns ± 1%		-12.03%		1
BM_Sort_float_QuickSortAdversary_4		1.73ns ± 0%		1.85ns ±13%		6.97%			1.73ns ± 1%		1.96ns ± 1%		13.01%		1
BM_Sort_float_QuickSortAdversary_16		0.94ns ± 1%		0.91ns ± 0%		-3.23%			0.99ns ±13%		1.06ns ± 2%		7.42%		1
BM_Sort_float_QuickSortAdversary_64		10.9ns ± 1%		15.8ns ± 1%		44.76%			11.5ns ±13%		13.2ns ± 1%		14.68%		1
BM_Sort_float_QuickSortAdversary_256		14.7ns ± 1%		22.9ns ± 0%		55.56%			15.5ns ±13%		16.7ns ± 1%		8.02%		1
BM_Sort_float_QuickSortAdversary_1024		34.1ns ± 3%		38.3ns ± 1%		12.36%			35.9ns ±13%		42.3ns ± 4%		18.04%		1
BM_Sort_float_QuickSortAdversary_16384		65.1ns ± 4%		73.6ns ± 2%		12.99%			68.4ns ±13%		70.1ns ± 1%		2.46%		1
BM_Sort_float_QuickSortAdversary_262144		69.8ns ± 1%		80.9ns ± 1%		15.87%			74.1ns ±11%		81.0ns ± 2%		0.00%		1
																
Weighted Average										-15.93%									-15.16%

[nilayvaish]

In D122780#3850519, @ldionne wrote:

As it stands, we basically have to decide whether to optimize for randomly sorted data or to also take into account common patterns IIUC. That's not a super easy call to make, since we're talking about 40-50% improvements and 40-50% regressions in each case. I remember @Morwenn had mentioned pdqsort previously, and that seemed to be an algorithm that would handle both random data and also patterns properly. Would that solve the problems of this algorithm?

@ldionne : if we collect and provide data on the relative change in cycles spent on std::sort for Google's data centers with the new implementation, would that be sufficient to land this diff in libcxx? How much improvement would you expect from the new implementation for tilting the balance in its favor?

[marcogelmi]

FWIW I think this would be a good change to accept for the following reasons:

1. random patterns are more likely than specific patterns, especially because some of these patterns are quite unrealistic (e.g. single element repeated 256k times)
2. these deterministic patterns tend to be much faster to sort anyway (e.g. ~1ns vs ~64ns for ascending vs random)
3. the fact that they are so fast also increases the measurement noise so the numbers might not be entirely reliable
4. for the reasons above, I see the benchmarks for these edge cases to be more of a sanity check (i.e. are we making ascending terrible? this does not seem to be the case here)
5. the numbers for strings are great and sorting strings is one of the most common use cases

[nilayvaish]

Pinging @ldionne. Can you comment on the data that would help you to make the decision? I am trying to convince folks at Google on trying out this diff. The main question being asked is what data you would like to see?

In D122780#3869112, @nilayvaish wrote:

In D122780#3850519, @ldionne wrote:

As it stands, we basically have to decide whether to optimize for randomly sorted data or to also take into account common patterns IIUC. That's not a super easy call to make, since we're talking about 40-50% improvements and 40-50% regressions in each case. I remember @Morwenn had mentioned pdqsort previously, and that seemed to be an algorithm that would handle both random data and also patterns properly. Would that solve the problems of this algorithm?

@ldionne : if we collect and provide data on the relative change in cycles spent on std::sort for Google's data centers with the new implementation, would that be sufficient to land this diff in libcxx? How much improvement would you expect from the new implementation for tilting the balance in its favor?

[ldionne]

In D122780#3869112, @nilayvaish wrote:

In D122780#3850519, @ldionne wrote:

@ldionne : if we collect and provide data on the relative change in cycles spent on std::sort for Google's data centers with the new implementation, would that be sufficient to land this diff in libcxx? How much improvement would you expect from the new implementation for tilting the balance in its favor?

Thanks for adding the weights to the benchmarks here, I think this was the missing link for me. You and @marcogelmi are right, the patterns that are the most important get an improvement, so I think this is good to go.

Let's rebase this, wait for the CI to be green, and merge this. Let me or another libc++ review group member know if you need help with merging this (if you do, please provide Author Name <email@domain> for commit attribution).

Is https://reviews.llvm.org/D93233 still relevant?

[ldionne]

As you rebase, it may be worth adding a release note explaining that we revised our implementation of std::sort, that it should be much faster in most cases now and that they can file a bug report in case they notice a notable performance regression.

[nilayvaish]

@ldionne : thanks for the accepting the change. We are trying to evaluate the effect of the change on Android APK's size. You might recall there were several comments about increased APK size in https://reviews.llvm.org/D113413 after it was submitted. I think it would be better if we are aware of the change in APK's size beforehand.

The evaluation is taking time, hopefully would get done soon.

[ldionne]

In D122780#3955083, @nilayvaish wrote:

@ldionne : thanks for the accepting the change. We are trying to evaluate the effect of the change on Android APK's size. You might recall there were several comments about increased APK size in https://reviews.llvm.org/D113413 after it was submitted. I think it would be better if we are aware of the change in APK's size beforehand.

The evaluation is taking time, hopefully would get done soon.

Thanks for the update. We'll be eager to hear about the results if you are allowed to share them. Hopefully there is no prohibitive code size regression. If so, it may be worth investigating if externally instantiating some of these templates in the dylib could mitigate the regression. IIRC this optimization was only enabled for integer types, right?

[nilayvaish]

In D122780#3955522, @ldionne wrote:

In D122780#3955083, @nilayvaish wrote:

@ldionne : thanks for the accepting the change. We are trying to evaluate the effect of the change on Android APK's size. You might recall there were several comments about increased APK size in https://reviews.llvm.org/D113413 after it was submitted. I think it would be better if we are aware of the change in APK's size beforehand.

The evaluation is taking time, hopefully would get done soon.

Thanks for the update. We'll be eager to hear about the results if you are allowed to share them. Hopefully there is no prohibitive code size regression. If so, it may be worth investigating if externally instantiating some of these templates in the dylib could mitigate the regression. IIRC this optimization was only enabled for integer types, right?

@ayzhao reported that this change would increase Chrome Android APK size by about 65.54 KB. The Chrome team is OK with this for now. For comparison, when we shifted to introsort, the increase was about 120 KB.

The optimization would be enabled for all arithmetic types.

[nilayvaish]

I would next rebase this change and redo the internal testing I did previously. Would post the rebased diff soon.

[smeenai]

Thanks for looking into the APK size impact. Could you give me a couple of days (I'll try my best to get to this tomorrow) to evaluate this on Meta's Android apps as well? I maintain the libc++ used by those, and we have some apps that are incredibly sensitive to APK size (increases of even a few KB are flagged), so I'd appreciate the chance to evaluate this before it lands. (If I haven't been able to get to this by Wednesday of next week, feel free to go ahead regardless.)

I don't know if the NDK folks are also interested in the size implications here, but CCing @rprichard just in case.

[smeenai]

Ah, I was hoping I'd be able to rebase the current version onto the 15.x release branch cleanly, but I'm running into conflicts that I'm not sure how to resolve. I'll wait for the rebased version and then try that.

[nilayvaish]

Rebase to the HEAD revision

[ldionne]

libcxx/include/__algorithm/sort.h

145

Your rebase is incorrect. You should be using _Ops::__iter_move(__k) instead of std::move(*__k) here and in a bunch of other places.

[nilayvaish]

Changed to use _Ops::__iter_move instead of std::move.

[nilayvaish]

Changed more std::move to _Ops::__iter_move

Passes tests on my machine.

[smeenai]

I'm not able to apply the latest version of the patch, and it looks like CI isn't either. Which revision is this patch based on top of?

Your stack still has D122858 in it, which is making arc patch unhappy locally, but even taking the raw patch and using git apply is failing for me.

[nilayvaish]

Properly update the diff

[nilayvaish]

In D122780#3978826, @smeenai wrote:

I'm not able to apply the latest version of the patch, and it looks like CI isn't either. Which revision is this patch based on top of?

Your stack still has D122858 in it, which is making arc patch unhappy locally, but even taking the raw patch and using git apply is failing for me.

@smeenai , can you try again? I think I don't understand the 'arc' tool that well.

[smeenai]

In D122780#3978947, @nilayvaish wrote:

In D122780#3978826, @smeenai wrote:

I'm not able to apply the latest version of the patch, and it looks like CI isn't either. Which revision is this patch based on top of?

Your stack still has D122858 in it, which is making arc patch unhappy locally, but even taking the raw patch and using git apply is failing for me.

@smeenai , can you try again? I think I don't understand the 'arc' tool that well.

It's a pretty hard tool to understand, to be fair :)

I'm able to apply this now, thanks. I'm working on the size evaluation today; I should have that today if I don't run into any unexpected snags.

[nilayvaish]

Corrected errors pointed out by the CI

[smeenai]

The size regressions from this are acceptably small for us, so we have no problems with that. Thanks for flagging it.

[nilayvaish]

Rebase to HEAD

[nilayvaish]

@ldionne : this diff is ready for submission. If you could do so, that would be great.

libcxx/include/__algorithm/sort.h

145

I have fixed all the places. std::move is being only used to move the value, not the iterator.

[ldionne]

@nilayvaish Can you follow these steps to get commit access? https://llvm.org/docs/DeveloperPolicy.html#obtaining-commit-access You can CC me on the email.

I would normally be happy to apply this for you, but I'm about to go OOO and I think it would be wise for you to have commit access in case this needs to be reverted (hopefully that does not happen).

[nilayvaish]

Rebase to head

[nilayvaish]

Rebase to HEAD

Buildkite seems to have been failing for unrelated reasons.

[ValZapod]

So this got reverted. Are you on planning on resubmitting?

[nilayvaish]

In D122780#4409544, @ValZapod wrote:

So this got reverted. Are you on planning on resubmitting?

This patch was reverted only in LLVM release 16. It is still there in the trunk. @ldionne , @danlark and others have been making changes to lower the danger of invalid comparators going out-of-bounds. I think LLVM release 17 will have this change.

libcxx/include/__algorithm/sort.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_SORT_H
 #define _LIBCPP___ALGORITHM_SORT_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
+#include <__algorithm/iter_swap.h>
 #include <__algorithm/min_element.h>
 #include <__algorithm/partial_sort.h>
 #include <__algorithm/unwrap_iter.h>
 #include <__config>
 #include <__utility/swap.h>
 #include <memory>
 
 #if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY)
for (++__i; __i != __last; ++__i) {
       value_type __t(_VSTD::move(*__j));
       for (_BidirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j)
         *__j = _VSTD::move(*__k);
       *__j = _VSTD::move(__t);
     }
   }
 }
 
+// Sort the iterator range [__first, __last) using the comparator __comp using
+// the insertion sort algorithm.
 template <class _Compare, class _RandomAccessIterator>
 void __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
-  _RandomAccessIterator __j = __first + difference_type(2);
-  _VSTD::__sort3<_Compare>(__first, __first + difference_type(1), __j, __comp);
-  for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) {
+  if (__first == __last)
+    return;
+  for (_RandomAccessIterator __i = __first + difference_type(1); __i != __last; ++__i) {
+    _RandomAccessIterator __j = __i - difference_type(1);
     if (__comp(*__i, *__j)) {
       value_type __t(_VSTD::move(*__i));
       _RandomAccessIterator __k = __j;
       __j = __i;
       do {
         *__j = _VSTD::move(*__k);
         __j = __k;
       } while (__j != __first && __comp(__t, *--__k));
       *__j = _VSTD::move(__t);
     }
+  }
+  __j = __i;
+}
+}
+
+// Sort the iterator range [__first, __last) using the comparator __comp using
+// the insertion sort algorithm.  Insertion sort has two loops, outer and inner.
+// The implementation below has not bounds check (unguarded) for the inner loop.
+// Assumes that there is an element in the position (__first - 1) and that each
+// element in the input range is greater or equal to the element at __first - 1.
+template <class _Compare, class _RandomAccessIterator>
+void __insertion_sort_3_unguarded(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+  typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
+  typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
+  if (__first == __last)
+    return;
+  for (_RandomAccessIterator __i = __first + difference_type(1); __i != __last; ++__i) {
+    _RandomAccessIterator __j = __i - difference_type(1);
+    if (__comp(*__i, *__j)) {
+      value_type __t(_VSTD::move(*__i));
+      _RandomAccessIterator __k = __j;
       __j = __i;
+      do {
+        *__j = _VSTD::move(*__k);
+        __j = __k;
+      } while (__comp(__t, *--__k)); // No need for bounds check due to the assumption stated above.
+      *__j = _VSTD::move(__t);
+    }
   }
 }
 
 template <class _Compare, class _RandomAccessIterator>
 bool __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   switch (__last - __first) {
   case 0:
if (__first1 != __last1) {
     __h.release();
   }
 }
 
 template <class _Compare, class _RandomAccessIterator>
 void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
                  typename iterator_traits<_RandomAccessIterator>::difference_type __depth) {
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
   const difference_type __limit =
       is_trivially_copy_constructible<value_type>::value && is_trivially_copy_assignable<value_type>::value ? 30 : 6;
   while (true) {
   __restart:
     difference_type __len = __last - __first;
     switch (__len) {
     case 0:
     case 1:
       return;
     case 2:
       if (__comp(*--__last, *__first))
         swap(*__first, *__last);
       return;
     case 3:
       _VSTD::__sort3<_Compare>(__first, __first + difference_type(1), --__last, __comp);
       return;
     case 4:
       _VSTD::__sort4<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), --__last, __comp);
       return;
     case 5:
       _VSTD::__sort5<_Compare>(__first, __first + difference_type(1), __first + difference_type(2),
                                __first + difference_type(3), --__last, __comp);
       return;
     }
     if (__len <= __limit) {
       _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
       return;
     }
     // __len > 5
     if (__depth == 0) {
       // Fallback to heap sort as Introsort suggests.
       _VSTD::__partial_sort<_Compare>(__first, __last, __last, __comp);
       return;
     }
-    --__depth;
-    _RandomAccessIterator __m = __first;
-    _RandomAccessIterator __lm1 = __last;
-    --__lm1;
-    unsigned __n_swaps;
-    {
-      difference_type __delta;
-      if (__len >= 1000) {
-        __delta = __len / 2;
-        __m += __delta;
-        __delta /= 2;
-        __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m + __delta, __lm1, __comp);
-      } else {
-        __delta = __len / 2;
-        __m += __delta;
-        __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
+  }
+
+  struct __64bit_set {
+    typedef uint64_t __storage_t;
+    enum { __block_size = 64 };
+    static __storage_t __blsr(__storage_t x) {
+      // _blsr_u64 can be used here but it did not make any performance
+      // difference in practice.
+      return x ^ (x & -x);
+    }
+    static int __clz(__storage_t x) { return __builtin_clzll(x); }
+    static int __ctz(__storage_t x) { return __builtin_ctzll(x); }
+    static int __popcount(__storage_t x) { return __builtin_popcountll(x); }
+  };
+
+  struct __32bit_set {
+    typedef uint32_t __storage_t;
+    enum { __block_size = 32 };
+    static __storage_t __blsr(__storage_t x) {
+      // _blsr_u32 can be used here but it did not make any performance
+      // difference in practice.
+      return x ^ (x & -x);
+    }
+    static int __clz(__storage_t x) { return __builtin_clzl(x); }
+    static int __ctz(__storage_t x) { return __builtin_ctzl(x); }
+    static int __popcount(__storage_t x) { return __builtin_popcountl(x); }
+  };
+
+  template <class _Bitset, class _RandomAccessIterator>
+  inline _LIBCPP_HIDE_FROM_ABI void __swap_bitmap_pos(_RandomAccessIterator __first, _RandomAccessIterator __last,
+                                                      typename _Bitset::__storage_t & __left_bitset,
+                                                      typename _Bitset::__storage_t & __right_bitset) {
+    typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
+    // Swap one pair on each iteration as long as both bitsets have at least one
+    // element for swapping.
+    while (__left_bitset != 0 && __right_bitset != 0) {
+      difference_type tz_left = _Bitset::__ctz(__left_bitset);
+      __left_bitset = _Bitset::__blsr(__left_bitset);
+      difference_type tz_right = _Bitset::__ctz(__right_bitset);
+      __right_bitset = _Bitset::__blsr(__right_bitset);
+      _VSTD::iter_swap(__first + tz_left, __last - tz_right);
+    }
+  }
+
+  // Partition [__first, __last) using the comparator __comp.  *__first has the
+  // chosen pivot.  Elements that are equivalent are kept to the left of the
+  // pivot.  Returns the iterator for the pivot and a bool value which is true if
+  // the provided range is already sorted, false otherwise.  We assume that the
+  // length of the range is at least three elements.
+  //
+  // We term the partitioning algorithm as bitset partitioning since the
+  // outcomes of the comparisons between the pivot and other elements are stored
+  // in the fixed size bitsets.
+  template <class _Bitset, class _RandomAccessIterator, class _Compare>
+  _LIBCPP_HIDE_FROM_ABI _VSTD::pair<_RandomAccessIterator, bool> __bitset_partition(
+      _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+    typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type;
+    typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type;
+    typedef typename _Bitset::__storage_t __storage_t;
+    _RandomAccessIterator __begin = __first;
+    value_type __pivot(_VSTD::move(*__first));
+    // Find the first element greater than the pivot.
+    if (__comp(__pivot, *(__last - difference_type(1)))) {
+      // Not guarded since we know the last element is greater than the pivot.
+      while (!__comp(__pivot, *++__first)) {
+      }
+      while (++__first < __last && !__comp(__pivot, *__first)) {
       }
     }
-    // *__m is median
-    // partition [__first, __m) < *__m and *__m <= [__m, __last)
-    // (this inhibits tossing elements equivalent to __m around unnecessarily)
-    _RandomAccessIterator __i = __first;
-    _RandomAccessIterator __j = __lm1;
-    // j points beyond range to be tested, *__m is known to be <= *__lm1
-    // The search going up is known to be guarded but the search coming down isn't.
-    // Prime the downward search with a guard.
-    if (!__comp(*__i, *__m)) // if *__first == *__m
-    {
-      // *__first == *__m, *__first doesn't go in first part
-      // manually guard downward moving __j against __i
-      while (true) {
-        if (__i == --__j) {
-          // *__first == *__m, *__m <= all other elements
-          // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
-          ++__i; // __first + 1
-          __j = __last;
-          if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
-          {
-            while (true) {
-              if (__i == __j)
-                return; // [__first, __last) all equivalent elements
-              if (__comp(*__first, *__i)) {
-                swap(*__i, *__j);
-                ++__n_swaps;
-                ++__i;
-                break;
-              }
-              ++__i;
-            }
-          }
-          // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
-          if (__i == __j)
-            return;
-          while (true) {
-            while (!__comp(*__first, *__i))
-              ++__i;
-            while (__comp(*__first, *--__j))
-              ;
-            if (__i >= __j)
-              break;
-            swap(*__i, *__j);
-            ++__n_swaps;
-            ++__i;
-          }
-          // [__first, __i) == *__first and *__first < [__i, __last)
-          // The first part is sorted, sort the second part
-          // _VSTD::__sort<_Compare>(__i, __last, __comp);
-          __first = __i;
-          goto __restart;
-        }
-        if (__comp(*__j, *__m)) {
-          swap(*__i, *__j);
-          ++__n_swaps;
-          break; // found guard for downward moving __j, now use unguarded partition
-        }
-      }
-    }
-    // It is known that *__i < *__m
-    ++__i;
-    // j points beyond range to be tested, *__m is known to be <= *__lm1
-    // if not yet partitioned...
-    if (__i < __j) {
-      // known that *(__i - 1) < *__m
-      // known that __i <= __m
-      while (true) {
-        // __m still guards upward moving __i
-        while (__comp(*__i, *__m))
-          ++__i;
-        // It is now known that a guard exists for downward moving __j
-        while (!__comp(*--__j, *__m))
-          ;
-        if (__i > __j)
-          break;
-        swap(*__i, *__j);
-        ++__n_swaps;
-        // It is known that __m != __j
-        // If __m just moved, follow it
-        if (__m == __i)
-          __m = __j;
-        ++__i;
+    // Find the last element less than or equal to the pivot.
+    if (__first < __last) {
+      // It will be always guarded because __introsort will do the median-of-three
+      // before calling this.
+      while (__comp(__pivot, *--__last)) {
+      }
+    }
+    // If the first element greater than the pivot is at or after the
+    // last element less than or equal to the pivot, then we have covered the
+    // entire range without swapping elements.  This implies the range is already
+    // partitioned.
+    bool __already_partitioned = __first >= __last;
+    if (!__already_partitioned) {
+      _VSTD::iter_swap(__first, __last);
+      ++__first;
+    }
+
+    // In [__first, __last) __last is not inclusive. From now on, it uses last
+    // minus one to be inclusive on both sides.
+    _RandomAccessIterator __lm1 = __last - difference_type(1);
+    __storage_t __left_bitset = 0;
+    __storage_t __right_bitset = 0;
+
+    // Reminder: length = __lm1 - __first + 1.
+    while (__lm1 - __first >= 2 * _Bitset::__block_size - 1) {
+      // Record the comparion outcomes for the elements currently on the left
+      // side.
+      if (__left_bitset == 0) {
+        // Possible vectorization. With a proper "-march" flag, the following loop
+        // will be compiled into a set of SIMD instructions.
+        _RandomAccessIterator __iter = __first;
+        for (int __j = 0; __j < _Bitset::__block_size;) {
+          bool __comp_result = !__comp(*__iter, __pivot);
+          __left_bitset |= (static_cast<__storage_t>(__comp_result) << __j);
+          __j++;
+          ++__iter;
+        }
+      }
+      // Record the comparion outcomes for the elements currently on the right
+      // side.
+      if (__right_bitset == 0) {
+        // Possible vectorization. With a proper "-march" flag, the following loop
+        // will be compiled into a set of SIMD instructions.
+        _RandomAccessIterator __iter = __lm1;
+        for (int __j = 0; __j < _Bitset::__block_size;) {
+          bool __comp_result = __comp(*__iter, __pivot);
+          __right_bitset |= (static_cast<__storage_t>(__comp_result) << __j);
+          __j++;
+          --__iter;
+        }
+      }
+      // Swap the elements recorded to be the candidates for swapping in the
+      // bitsets.
+      __swap_bitmap_pos<_Bitset>(__first, __lm1, __left_bitset, __right_bitset);
+      // Only advance the iterator if all the elements that need to be moved to
+      // other side were moved.
+      __first += (__left_bitset == 0) ? difference_type(_Bitset::__block_size) : difference_type(0);
+      __lm1 -= (__right_bitset == 0) ? difference_type(_Bitset::__block_size) : difference_type(0);
+    }
+    // Now, we have a less-than a block worth of elements on at least one of the
+    // sides.
+    difference_type __remaining_len = __lm1 - __first + 1;
+    difference_type __l_size;
+    difference_type __r_size;
+    if (__left_bitset == 0 && __right_bitset == 0) {
+      __l_size = __remaining_len / 2;
+      __r_size = __remaining_len - __l_size;
+    } else if (__left_bitset == 0) {
+      // We know at least one side is a full block.
+      __l_size = __remaining_len - _Bitset::__block_size;
+      __r_size = _Bitset::__block_size;
+    } else { // if (__right_bitset == 0)
+      __l_size = _Bitset::__block_size;
+      __r_size = __remaining_len - _Bitset::__block_size;
+    }
+    // Record the comparion outcomes for the elements currently on the left side.
+    if (__left_bitset == 0) {
+      _RandomAccessIterator __iter = __first;
+      for (int j = 0; j < __l_size; j++) {
+        bool __comp_result = !__comp(*__iter, __pivot);
+        __left_bitset |= (static_cast<__storage_t>(__comp_result) << j);
+        ++__iter;
+      }
+    }
+    // Record the comparion outcomes for the elements currently on the right side.
+    if (__right_bitset == 0) {
+      _RandomAccessIterator __iter = __lm1;
+      for (int j = 0; j < __r_size; j++) {
+        bool __comp_result = __comp(*__iter, __pivot);
+        __right_bitset |= (static_cast<__storage_t>(__comp_result) << j);
+        --__iter;
+      }
+    }
+    __swap_bitmap_pos<_Bitset>(__first, __lm1, __left_bitset, __right_bitset);
+    __first += (__left_bitset == 0) ? __l_size : 0;
+    __lm1 -= (__right_bitset == 0) ? __r_size : 0;
+    // At least one the bitsets would be empty.  For the non-empty one, we need to
+    // properly partition the elements that appear within that bitset.
+    if (__left_bitset) {
+      // Swap within the left side.  Need to find set positions in the reverse
+      // order.
+      while (__left_bitset != 0) {
+        difference_type __tz_left = _Bitset::__block_size - 1 - _Bitset::__clz(__left_bitset);
+        __left_bitset &= (static_cast<__storage_t>(1) << __tz_left) - 1;
+        _RandomAccessIterator it = __first + __tz_left;
+        if (it != __lm1) {
+          _VSTD::iter_swap(it, __lm1);
+        --__lm1;
+      __first = __lm1 + difference_type(1);
+    } else if (__right_bitset) {
+      // Swap within the right side.  Need to find set positions in the reverse
+      // order.
+      while (__right_bitset != 0) {
+        difference_type __tz_right = _Bitset::__block_size - 1 - _Bitset::__clz(__right_bitset);
+        __right_bitset &= (static_cast<__storage_t>(1) << __tz_right) - 1;
+        _RandomAccessIterator it = __lm1 - __tz_right;
+        if (it != __first) {
+          _VSTD::iter_swap(it, __first);
+        }
+        ++__first;
+      }
+    }
+    // Move the pivot to its correct position.
+    _RandomAccessIterator __pivot_pos = __first - difference_type(1);
+    if (__begin != __pivot_pos) {
+      *__begin = _VSTD::move(*__pivot_pos);
+    }
+    *__pivot_pos = _VSTD::move(__pivot);
+    return _VSTD::make_pair(__pivot_pos, __already_partitioned);
+  }
+
+  // Partition [__first, __last) using the comparator __comp.  *__first has the
+  // chosen pivot.  Elements that are equivalent are kept to the right of the
+  // pivot.  Returns the iterator for the pivot and a bool value which is true if
+  // the provided range is already sorted, false otherwise.  We assume that the
+  // length of the range is at least three elements.
+  template <class _RandomAccessIterator, class _Compare>
+  _LIBCPP_HIDE_FROM_ABI _VSTD::pair<_RandomAccessIterator, bool> __partition_with_equals_on_right(
+      _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
+    typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type;
+    _RandomAccessIterator __begin = __first;
+    value_type __pivot(_VSTD::move(*__first));
+    // Find the first element greater or equal to the pivot.  It will be always
+    // guarded because __introsort will do the median-of-three before calling
+    // this.
+    while (__comp(*++__first, __pivot))
+      ;
+
+    // Find the last element less than the pivot.
+    if (__begin == __first - difference_type(1)) {
+      while (__first < __last && !__comp(*--__last, __pivot))
+        ;
+    } else {
+      // Guarded.
+      while (!__comp(*--__last, __pivot))
+        ;
+
+    // If the first element greater than or equal to the pivot is at or after the
+    // last element less than the pivot, then we have covered the entire range
+    // without swapping elements.  This implies the range is already partitioned.
+    bool __already_partitioned = __first >= __last;
+    // Go through the remaining elements.  Swap pairs of elements (one to the
+    // right of the pivot and the other to left of the pivot) that are not on the
+    // correct side of the pivot.
+    while (__first < __last) {
+      _VSTD::iter_swap(__first, __last);
+      while (__comp(*++__first, __pivot))
+        ;
+      while (!__comp(*--__last, __pivot))
+    // Move the pivot to its correct position.
+    _RandomAccessIterator __pivot_pos = __first - difference_type(1);
+    if (__begin != __pivot_pos) {
+      *__begin = _VSTD::move(*__pivot_pos);
+    *__pivot_pos = _VSTD::move(__pivot);
+    return _VSTD::make_pair(__pivot_pos, __already_partitioned);
+
+  // Similar to the above function.  Elements equivalent to the pivot are put to
+  // the left of the pivot.  Returns the iterator to the pivot element.
+  template <class _RandomAccessIterator, class _Compare>
+  _LIBCPP_HIDE_FROM_ABI _RandomAccessIterator __partition_with_equals_on_left(
+      _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
+    typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type;
+    _RandomAccessIterator __begin = __first;
+    value_type __pivot(_VSTD::move(*__first));
+    if (__comp(__pivot, *(__last - difference_type(1)))) {
+      // Guarded.
+      while (!__comp(__pivot, *++__first)) {
+      }
+    } else {
+      while (++__first < __last && !__comp(__pivot, *__first)) {
+      }
+    }
+
+    if (__first < __last) {
+      // It will be always guarded because __introsort will do the
+      // median-of-three before calling this.
+      while (__comp(__pivot, *--__last)) {
+      }
+    }
+    while (__first < __last) {
+      _VSTD::iter_swap(__first, __last);
+      while (!__comp(__pivot, *++__first))
+      while (__comp(__pivot, *--__last))
+        ;
+    }
+    _RandomAccessIterator __pivot_pos = __first - difference_type(1);
+    if (__begin != __pivot_pos) {
+      *__begin = _VSTD::move(*__pivot_pos);
+    }
+    *__pivot_pos = _VSTD::move(__pivot);
+    return __first;
+  }
+
+  // The main sorting function.  Implements introsort combined with other ideas:
+  //  - option of using block quick sort for partitioning,
+  //  - guarded and unguarded insertion sort for small lengths,
+  //  - Tuckey's ninther technique for computing the pivot,
+  //  - check on whether partition was not required.
+  // The implementation is partly based on Orson Peters' pattern-defeating
+  // quicksort, published at: <https://github.com/orlp/pdqsort>
+  template <class _Compare, class _RandomAccessIterator, bool _UseBitSetPartition>
+  void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
+                   typename iterator_traits<_RandomAccessIterator>::difference_type __depth, bool __leftmost = true) {
+    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
+    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+    // Upper bound for using insertion sort for sorting.
+    _LIBCPP_CONSTEXPR_AFTER_CXX11 difference_type __limit = 24;
+    // Lower bound for using Tuckey's ninther technique for median computation.
+    _LIBCPP_CONSTEXPR_AFTER_CXX11 difference_type __ninther_threshold = 128;
+    while (true) {
+      difference_type __len = __last - __first;
+      switch (__len) {
+      case 0:
+      case 1:
+        return;
+      case 2:
+        if (__comp(*--__last, *__first))
+          swap(*__first, *__last);
+        return;
+      case 3:
+        _VSTD::__sort3<_Compare>(__first, __first + difference_type(1), --__last, __comp);
+        return;
+      case 4:
+        _VSTD::__sort4<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), --__last, __comp);
+        return;
+      case 5:
+        _VSTD::__sort5<_Compare>(__first, __first + difference_type(1), __first + difference_type(2),
+                                 __first + difference_type(3), --__last, __comp);
+        return;
       }
+      // Use insertion sort if the length of the range is below the specified
+      // limit.
+      if (__len < __limit) {
+        if (__leftmost) {
+          _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
+        } else {
+          _VSTD::__insertion_sort_3_unguarded<_Compare>(__first, __last, __comp);
         }
-    // [__first, __i) < *__m and *__m <= [__i, __last)
-    if (__i != __m && __comp(*__m, *__i)) {
-      swap(*__i, *__m);
-      ++__n_swaps;
+        return;
       }
+      if (__depth == 0) {
+        // Fallback to heap sort as Introsort suggests.
+        _VSTD::__partial_sort<_Compare>(__first, __last, __last, __comp);
+        return;
+      }
+      --__depth;
+      {
+        difference_type __half_len = __len / 2;
+        // Use Tuckey's ninther technique or median of 3 for pivot selection
+        // depending on the length of the range being sorted.
+        if (__len > __ninther_threshold) {
+          _VSTD::__sort3<_Compare>(__first, __first + __half_len, __last - difference_type(1), __comp);
+          _VSTD::__sort3<_Compare>(__first + difference_type(1), __first + (__half_len - 1),
+                                   __last - difference_type(2), __comp);
+          _VSTD::__sort3<_Compare>(__first + difference_type(2), __first + (__half_len + 1),
+                                   __last - difference_type(3), __comp);
+          _VSTD::__sort3<_Compare>(__first + (__half_len - 1), __first + __half_len, __first + (__half_len + 1),
+                                   __comp);
+          _VSTD::iter_swap(__first, __first + __half_len);
+        } else {
+          _VSTD::__sort3<_Compare>(__first + __half_len, __first, __last - difference_type(1), __comp);
+        }
+      }
+      // The elements to the left of the current iterator range are already
+      // sorted.  If the current iterator range to be sorted is not the
+      // leftmost part of the entire iterator range and the pivot is same as
+      // the highest element in the range to the left, then we know that all
+      // the elements in the range [first, pivot] would be equal to the pivot,
+      // assuming the equal elements are put on the left side when
+      // partitioned.  This also means that we do not need to sort the left
+      // side of the partition.
+      if (!__leftmost && !__comp(*(__first - difference_type(1)), *__first)) {
+        __first = __partition_with_equals_on_left<_RandomAccessIterator, _Comp_ref>(__first, __last, _Comp_ref(__comp));
+        continue;
+      }
+      // Use bitset partition only if asked for.
+      auto __ret = _UseBitSetPartition
+                       ? __bitset_partition<__64bit_set, _RandomAccessIterator, _Compare>(__first, __last, __comp)
+                       : __partition_with_equals_on_right<_RandomAccessIterator, _Compare>(__first, __last, __comp);
+      _RandomAccessIterator __i = __ret.first;
       // [__first, __i) < *__i and *__i <= [__i+1, __last)
       // If we were given a perfect partition, see if insertion sort is quick...
-    if (__n_swaps == 0) {
+      if (__ret.second) {
         bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
         if (_VSTD::__insertion_sort_incomplete<_Compare>(__i + difference_type(1), __last, __comp)) {
           if (__fs)
             return;
           __last = __i;
           continue;
         } else {
           if (__fs) {
             __first = ++__i;
             continue;
           }
         }
       }
-    // sort smaller range with recursive call and larger with tail recursion elimination
-    if (__i - __first < __last - __i) {
-      _VSTD::__introsort<_Compare>(__first, __i, __comp, __depth);
+      // Sort the left partiton recursively and the right partition with tail
+      // recursion elimination.
+      _VSTD::__introsort<_Compare, _RandomAccessIterator, _UseBitSetPartition>(__first, __i, __comp, __depth,
+                                                                               __leftmost);
+      __leftmost = false;
       __first = ++__i;
-    } else {
-      _VSTD::__introsort<_Compare>(__i + difference_type(1), __last, __comp, __depth);
-      __last = __i;
-    }
     }
   }
 
 template <typename _Number>
 inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) {
   _Number __log2 = 0;
   while (__n > 1) {
     __log2++;
     __n >>= 1;
   }
   return __log2;
 }
 
 template <class _Compare, class _RandomAccessIterator>
 void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
   typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
   difference_type __depth_limit = 2 * __log2i(__last - __first);
-  _VSTD::__introsort<_Compare>(__first, __last, __comp, __depth_limit);
+  // Only use bitset partitioning for arithmetic types.  We should also check
+  // that the default comparator is in use so that we are sure that there are no
+  // branches in the comparator.
+  _VSTD::__introsort<_Compare, _RandomAccessIterator,
+                     _VSTD::is_arithmetic<typename iterator_traits<_RandomAccessIterator>::value_type>::value>(
+      __first, __last, __comp, __depth_limit);
 }
 
 template <class _Compare, class _Tp>
 inline _LIBCPP_INLINE_VISIBILITY void __sort(_Tp** __first, _Tp** __last, __less<_Tp*>&) {
   __less<uintptr_t> __comp;
   _VSTD::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp);
 }
 
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&))