[libc++] Improve the performance of std::make_heap a bit (#154092)

2025-09-08T10:00:04+00:00

```
Apple M4:
-----------------------------------------------------------------------------------------------------
Benchmark                                                                         old             new
-----------------------------------------------------------------------------------------------------
BM_MakeHeap_uint32_Random_1                                                  0.285 ns        0.271 ns
BM_MakeHeap_uint32_Random_4                                                   2.09 ns         1.80 ns
BM_MakeHeap_uint32_Random_16                                                  1.85 ns         1.83 ns
BM_MakeHeap_uint32_Random_64                                                  1.92 ns         1.50 ns
BM_MakeHeap_uint32_Random_256                                                 2.10 ns         1.87 ns
BM_MakeHeap_uint32_Random_1024                                                1.73 ns         1.86 ns
BM_MakeHeap_uint32_Random_16384                                               2.17 ns         2.05 ns
BM_MakeHeap_uint32_Random_262144                                              1.77 ns         1.77 ns
BM_MakeHeap_uint32_Ascending_1                                               0.288 ns        0.277 ns
BM_MakeHeap_uint32_Ascending_4                                               0.658 ns        0.481 ns
BM_MakeHeap_uint32_Ascending_16                                              0.636 ns        0.637 ns
BM_MakeHeap_uint32_Ascending_64                                              0.643 ns        0.601 ns
BM_MakeHeap_uint32_Ascending_256                                             0.710 ns        0.636 ns
BM_MakeHeap_uint32_Ascending_1024                                            0.747 ns        0.660 ns
BM_MakeHeap_uint32_Ascending_16384                                           0.713 ns        0.633 ns
BM_MakeHeap_uint32_Ascending_262144                                          0.769 ns        0.731 ns
BM_MakeHeap_uint32_Descending_1                                              0.294 ns        0.280 ns
BM_MakeHeap_uint32_Descending_4                                              0.379 ns        0.305 ns
BM_MakeHeap_uint32_Descending_16                                             0.376 ns        0.268 ns
BM_MakeHeap_uint32_Descending_64                                             0.358 ns        0.271 ns
BM_MakeHeap_uint32_Descending_256                                            0.377 ns        0.284 ns
BM_MakeHeap_uint32_Descending_1024                                           0.355 ns        0.267 ns
BM_MakeHeap_uint32_Descending_16384                                          0.348 ns        0.248 ns
BM_MakeHeap_uint32_Descending_262144                                         0.349 ns        0.247 ns
BM_MakeHeap_uint32_SingleElement_1                                           0.292 ns        0.280 ns
BM_MakeHeap_uint32_SingleElement_4                                           0.570 ns        0.332 ns
BM_MakeHeap_uint32_SingleElement_16                                          0.635 ns        0.604 ns
BM_MakeHeap_uint32_SingleElement_64                                          0.653 ns        0.567 ns
BM_MakeHeap_uint32_SingleElement_256                                         0.703 ns        0.609 ns
BM_MakeHeap_uint32_SingleElement_1024                                        0.737 ns        0.604 ns
BM_MakeHeap_uint32_SingleElement_16384                                       0.699 ns        0.574 ns
BM_MakeHeap_uint32_SingleElement_262144                                      0.803 ns        0.684 ns
BM_MakeHeap_uint32_PipeOrgan_1                                               0.291 ns        0.284 ns
BM_MakeHeap_uint32_PipeOrgan_4                                               0.588 ns        0.399 ns
BM_MakeHeap_uint32_PipeOrgan_16                                              0.648 ns         1.12 ns
BM_MakeHeap_uint32_PipeOrgan_64                                              0.662 ns        0.771 ns
BM_MakeHeap_uint32_PipeOrgan_256                                             0.723 ns        0.672 ns
BM_MakeHeap_uint32_PipeOrgan_1024                                            0.749 ns        0.674 ns
BM_MakeHeap_uint32_PipeOrgan_16384                                           0.708 ns        0.638 ns
BM_MakeHeap_uint32_PipeOrgan_262144                                          0.786 ns        0.743 ns
BM_MakeHeap_uint32_Heap_1                                                    0.298 ns        0.282 ns
BM_MakeHeap_uint32_Heap_4                                                    0.396 ns        0.308 ns
BM_MakeHeap_uint32_Heap_16                                                   0.377 ns        0.268 ns
BM_MakeHeap_uint32_Heap_64                                                   0.356 ns        0.271 ns
BM_MakeHeap_uint32_Heap_256                                                  0.378 ns        0.290 ns
BM_MakeHeap_uint32_Heap_1024                                                 0.356 ns        0.275 ns
BM_MakeHeap_uint32_Heap_16384                                                0.348 ns        0.252 ns
BM_MakeHeap_uint32_Heap_262144                                               0.347 ns        0.250 ns
BM_MakeHeap_uint32_QuickSortAdversary_1                                      0.290 ns        0.284 ns
BM_MakeHeap_uint32_QuickSortAdversary_4                                      0.627 ns        0.409 ns
BM_MakeHeap_uint32_QuickSortAdversary_16                                     0.640 ns        0.653 ns
BM_MakeHeap_uint32_QuickSortAdversary_64                                     0.577 ns        0.484 ns
BM_MakeHeap_uint32_QuickSortAdversary_256                                    0.613 ns        0.521 ns
BM_MakeHeap_uint32_QuickSortAdversary_1024                                   0.652 ns        0.514 ns
BM_MakeHeap_uint32_QuickSortAdversary_16384                                  0.428 ns        0.308 ns
BM_MakeHeap_uint32_QuickSortAdversary_262144                                 0.373 ns        0.261 ns
BM_MakeHeap_uint64_Random_1                                                  0.291 ns        0.281 ns
BM_MakeHeap_uint64_Random_4                                                   2.20 ns         1.97 ns
BM_MakeHeap_uint64_Random_16                                                  1.93 ns         1.70 ns
BM_MakeHeap_uint64_Random_64                                                  1.89 ns         1.48 ns
BM_MakeHeap_uint64_Random_256                                                 2.10 ns         1.99 ns
BM_MakeHeap_uint64_Random_1024                                                1.41 ns         2.04 ns
BM_MakeHeap_uint64_Random_16384                                               2.12 ns         1.83 ns
BM_MakeHeap_uint64_Random_262144                                              1.83 ns         1.63 ns
BM_MakeHeap_uint64_Ascending_1                                               0.288 ns        0.283 ns
BM_MakeHeap_uint64_Ascending_4                                               0.624 ns        0.493 ns
BM_MakeHeap_uint64_Ascending_16                                              0.648 ns        0.688 ns
BM_MakeHeap_uint64_Ascending_64                                              0.671 ns        0.634 ns
BM_MakeHeap_uint64_Ascending_256                                             0.739 ns        0.680 ns
BM_MakeHeap_uint64_Ascending_1024                                            0.761 ns        0.698 ns
BM_MakeHeap_uint64_Ascending_16384                                           0.740 ns        0.685 ns
BM_MakeHeap_uint64_Ascending_262144                                          0.849 ns        0.837 ns
BM_MakeHeap_uint64_Descending_1                                              0.304 ns        0.287 ns
BM_MakeHeap_uint64_Descending_4                                              0.395 ns        0.312 ns
BM_MakeHeap_uint64_Descending_16                                             0.374 ns        0.276 ns
BM_MakeHeap_uint64_Descending_64                                             0.358 ns        0.272 ns
BM_MakeHeap_uint64_Descending_256                                            0.389 ns        0.303 ns
BM_MakeHeap_uint64_Descending_1024                                           0.361 ns        0.278 ns
BM_MakeHeap_uint64_Descending_16384                                          0.352 ns        0.253 ns
BM_MakeHeap_uint64_Descending_262144                                         0.350 ns        0.251 ns
BM_MakeHeap_uint64_SingleElement_1                                           0.295 ns        0.285 ns
BM_MakeHeap_uint64_SingleElement_4                                           0.569 ns        0.358 ns
BM_MakeHeap_uint64_SingleElement_16                                          0.649 ns        0.652 ns
BM_MakeHeap_uint64_SingleElement_64                                          0.673 ns        0.565 ns
BM_MakeHeap_uint64_SingleElement_256                                         0.732 ns        0.651 ns
BM_MakeHeap_uint64_SingleElement_1024                                        0.759 ns        0.632 ns
BM_MakeHeap_uint64_SingleElement_16384                                       0.748 ns        0.614 ns
BM_MakeHeap_uint64_SingleElement_262144                                      0.947 ns        0.797 ns
BM_MakeHeap_uint64_PipeOrgan_1                                               0.295 ns        0.284 ns
BM_MakeHeap_uint64_PipeOrgan_4                                               0.601 ns        0.496 ns
BM_MakeHeap_uint64_PipeOrgan_16                                              0.655 ns         1.18 ns
BM_MakeHeap_uint64_PipeOrgan_64                                              0.682 ns        0.803 ns
BM_MakeHeap_uint64_PipeOrgan_256                                             0.759 ns        0.710 ns
BM_MakeHeap_uint64_PipeOrgan_1024                                            0.759 ns        0.713 ns
BM_MakeHeap_uint64_PipeOrgan_16384                                           0.739 ns        0.696 ns
BM_MakeHeap_uint64_PipeOrgan_262144                                          0.870 ns        0.849 ns
BM_MakeHeap_uint64_Heap_1                                                    0.290 ns        0.284 ns
BM_MakeHeap_uint64_Heap_4                                                    0.413 ns        0.314 ns
BM_MakeHeap_uint64_Heap_16                                                   0.378 ns        0.277 ns
BM_MakeHeap_uint64_Heap_64                                                   0.362 ns        0.272 ns
BM_MakeHeap_uint64_Heap_256                                                  0.389 ns        0.303 ns
BM_MakeHeap_uint64_Heap_1024                                                 0.362 ns        0.283 ns
BM_MakeHeap_uint64_Heap_16384                                                0.352 ns        0.253 ns
BM_MakeHeap_uint64_Heap_262144                                               0.350 ns        0.251 ns
BM_MakeHeap_uint64_QuickSortAdversary_1                                      0.293 ns        0.284 ns
BM_MakeHeap_uint64_QuickSortAdversary_4                                      0.606 ns        0.494 ns
BM_MakeHeap_uint64_QuickSortAdversary_16                                     0.645 ns        0.691 ns
BM_MakeHeap_uint64_QuickSortAdversary_64                                     0.607 ns        0.511 ns
BM_MakeHeap_uint64_QuickSortAdversary_256                                    0.641 ns        0.537 ns
BM_MakeHeap_uint64_QuickSortAdversary_1024                                   0.657 ns        0.529 ns
BM_MakeHeap_uint64_QuickSortAdversary_16384                                  0.435 ns        0.316 ns
BM_MakeHeap_uint64_QuickSortAdversary_262144                                 0.382 ns        0.266 ns
BM_MakeHeap_pair_Random_1                                    0.297 ns        0.378 ns
BM_MakeHeap_pair_Random_4                                     2.80 ns        0.765 ns
BM_MakeHeap_pair_Random_16                                    2.92 ns         2.20 ns
BM_MakeHeap_pair_Random_64                                    3.17 ns         3.64 ns
BM_MakeHeap_pair_Random_256                                   3.44 ns         3.20 ns
BM_MakeHeap_pair_Random_1024                                  3.35 ns         3.64 ns
BM_MakeHeap_pair_Random_16384                                 3.22 ns         3.50 ns
BM_MakeHeap_pair_Random_262144                                3.61 ns         3.46 ns
BM_MakeHeap_pair_Ascending_1                                 0.291 ns        0.379 ns
BM_MakeHeap_pair_Ascending_4                                 0.779 ns        0.436 ns
BM_MakeHeap_pair_Ascending_16                                0.943 ns         1.01 ns
BM_MakeHeap_pair_Ascending_64                                 1.17 ns         1.26 ns
BM_MakeHeap_pair_Ascending_256                                1.38 ns         1.44 ns
BM_MakeHeap_pair_Ascending_1024                               1.37 ns         1.43 ns
BM_MakeHeap_pair_Ascending_16384                              1.29 ns         1.31 ns
BM_MakeHeap_pair_Ascending_262144                             1.37 ns         1.40 ns
BM_MakeHeap_pair_Descending_1                                0.292 ns        0.382 ns
BM_MakeHeap_pair_Descending_4                                0.440 ns        0.347 ns
BM_MakeHeap_pair_Descending_16                               0.529 ns        0.520 ns
BM_MakeHeap_pair_Descending_64                               0.540 ns        0.527 ns
BM_MakeHeap_pair_Descending_256                              0.637 ns        0.583 ns
BM_MakeHeap_pair_Descending_1024                             0.552 ns        0.513 ns
BM_MakeHeap_pair_Descending_16384                            0.522 ns        0.488 ns
BM_MakeHeap_pair_Descending_262144                           0.515 ns        0.492 ns
BM_MakeHeap_pair_SingleElement_1                             0.299 ns        0.377 ns
BM_MakeHeap_pair_SingleElement_4                             0.787 ns        0.474 ns
BM_MakeHeap_pair_SingleElement_16                             1.07 ns        0.921 ns
BM_MakeHeap_pair_SingleElement_64                             1.20 ns         1.15 ns
BM_MakeHeap_pair_SingleElement_256                            1.30 ns         1.27 ns
BM_MakeHeap_pair_SingleElement_1024                           1.30 ns         1.31 ns
BM_MakeHeap_pair_SingleElement_16384                          1.29 ns         1.28 ns
BM_MakeHeap_pair_SingleElement_262144                         1.37 ns         1.38 ns
BM_MakeHeap_pair_PipeOrgan_1                                 0.293 ns        0.385 ns
BM_MakeHeap_pair_PipeOrgan_4                                 0.677 ns        0.438 ns
BM_MakeHeap_pair_PipeOrgan_16                                 1.04 ns         1.00 ns
BM_MakeHeap_pair_PipeOrgan_64                                 1.20 ns         1.27 ns
BM_MakeHeap_pair_PipeOrgan_256                                1.40 ns         1.43 ns
BM_MakeHeap_pair_PipeOrgan_1024                               1.36 ns         1.43 ns
BM_MakeHeap_pair_PipeOrgan_16384                              1.27 ns         1.31 ns
BM_MakeHeap_pair_PipeOrgan_262144                             1.37 ns         1.41 ns
BM_MakeHeap_pair_Heap_1                                      0.292 ns        0.378 ns
BM_MakeHeap_pair_Heap_4                                      0.440 ns        0.380 ns
BM_MakeHeap_pair_Heap_16                                     0.560 ns        0.606 ns
BM_MakeHeap_pair_Heap_64                                     0.588 ns        0.573 ns
BM_MakeHeap_pair_Heap_256                                    0.632 ns        0.607 ns
BM_MakeHeap_pair_Heap_1024                                   0.598 ns        0.580 ns
BM_MakeHeap_pair_Heap_16384                                  0.576 ns        0.563 ns
BM_MakeHeap_pair_Heap_262144                                 0.572 ns        0.561 ns
BM_MakeHeap_pair_QuickSortAdversary_1                        0.304 ns        0.379 ns
BM_MakeHeap_pair_QuickSortAdversary_4                        0.823 ns        0.430 ns
BM_MakeHeap_pair_QuickSortAdversary_16                        1.08 ns         1.03 ns
BM_MakeHeap_pair_QuickSortAdversary_64                        1.18 ns         1.23 ns
BM_MakeHeap_pair_QuickSortAdversary_256                       1.39 ns         1.43 ns
BM_MakeHeap_pair_QuickSortAdversary_1024                      1.36 ns         1.42 ns
BM_MakeHeap_pair_QuickSortAdversary_16384                     1.28 ns         1.32 ns
BM_MakeHeap_pair_QuickSortAdversary_262144                    1.34 ns         1.37 ns
BM_MakeHeap_tuple_Random_1                           0.276 ns        0.511 ns
BM_MakeHeap_tuple_Random_4                            4.25 ns         1.96 ns
BM_MakeHeap_tuple_Random_16                           4.84 ns         3.77 ns
BM_MakeHeap_tuple_Random_64                           5.53 ns         4.93 ns
BM_MakeHeap_tuple_Random_256                          5.30 ns         5.06 ns
BM_MakeHeap_tuple_Random_1024                         5.29 ns         5.02 ns
BM_MakeHeap_tuple_Random_16384                        5.53 ns         5.31 ns
BM_MakeHeap_tuple_Random_262144                       5.49 ns         5.29 ns
BM_MakeHeap_tuple_Ascending_1                        0.275 ns        0.443 ns
BM_MakeHeap_tuple_Ascending_4                         1.22 ns        0.764 ns
BM_MakeHeap_tuple_Ascending_16                        1.39 ns         1.49 ns
BM_MakeHeap_tuple_Ascending_64                        1.66 ns         1.76 ns
BM_MakeHeap_tuple_Ascending_256                       1.85 ns         1.99 ns
BM_MakeHeap_tuple_Ascending_1024                      1.90 ns         2.02 ns
BM_MakeHeap_tuple_Ascending_16384                     2.15 ns         2.27 ns
BM_MakeHeap_tuple_Ascending_262144                    2.25 ns         2.37 ns
BM_MakeHeap_tuple_Descending_1                       0.274 ns        0.445 ns
BM_MakeHeap_tuple_Descending_4                       0.939 ns        0.520 ns
BM_MakeHeap_tuple_Descending_16                       1.02 ns        0.811 ns
BM_MakeHeap_tuple_Descending_64                       1.01 ns        0.941 ns
BM_MakeHeap_tuple_Descending_256                      1.03 ns         1.01 ns
BM_MakeHeap_tuple_Descending_1024                    0.969 ns        0.947 ns
BM_MakeHeap_tuple_Descending_16384                   0.882 ns        0.876 ns
BM_MakeHeap_tuple_Descending_262144                  0.893 ns        0.871 ns
BM_MakeHeap_tuple_SingleElement_1                    0.276 ns        0.443 ns
BM_MakeHeap_tuple_SingleElement_4                     1.34 ns        0.870 ns
BM_MakeHeap_tuple_SingleElement_16                    1.60 ns         1.59 ns
BM_MakeHeap_tuple_SingleElement_64                    1.91 ns         2.00 ns
BM_MakeHeap_tuple_SingleElement_256                   1.91 ns         2.08 ns
BM_MakeHeap_tuple_SingleElement_1024                  1.91 ns         2.10 ns
BM_MakeHeap_tuple_SingleElement_16384                 2.13 ns         2.35 ns
BM_MakeHeap_tuple_SingleElement_262144                2.25 ns         2.48 ns
BM_MakeHeap_tuple_PipeOrgan_1                        0.275 ns        0.446 ns
BM_MakeHeap_tuple_PipeOrgan_4                         1.07 ns        0.671 ns
BM_MakeHeap_tuple_PipeOrgan_16                        1.36 ns         1.44 ns
BM_MakeHeap_tuple_PipeOrgan_64                        1.70 ns         1.80 ns
BM_MakeHeap_tuple_PipeOrgan_256                       1.88 ns         2.05 ns
BM_MakeHeap_tuple_PipeOrgan_1024                      1.92 ns         2.06 ns
BM_MakeHeap_tuple_PipeOrgan_16384                     2.11 ns         2.26 ns
BM_MakeHeap_tuple_PipeOrgan_262144                    2.18 ns         2.34 ns
BM_MakeHeap_tuple_Heap_1                             0.274 ns        0.441 ns
BM_MakeHeap_tuple_Heap_4                             0.938 ns        0.587 ns
BM_MakeHeap_tuple_Heap_16                             1.01 ns        0.873 ns
BM_MakeHeap_tuple_Heap_64                             1.08 ns         1.00 ns
BM_MakeHeap_tuple_Heap_256                            1.21 ns         1.18 ns
BM_MakeHeap_tuple_Heap_1024                           1.37 ns         1.29 ns
BM_MakeHeap_tuple_Heap_16384                          1.31 ns         1.26 ns
BM_MakeHeap_tuple_Heap_262144                         1.29 ns         1.25 ns
BM_MakeHeap_tuple_QuickSortAdversary_1               0.275 ns        0.447 ns
BM_MakeHeap_tuple_QuickSortAdversary_4                1.22 ns        0.764 ns
BM_MakeHeap_tuple_QuickSortAdversary_16               1.35 ns         1.46 ns
BM_MakeHeap_tuple_QuickSortAdversary_64               1.63 ns         1.73 ns
BM_MakeHeap_tuple_QuickSortAdversary_256              1.83 ns         1.87 ns
BM_MakeHeap_tuple_QuickSortAdversary_1024             1.81 ns         1.94 ns
BM_MakeHeap_tuple_QuickSortAdversary_16384            2.06 ns         2.19 ns
BM_MakeHeap_tuple_QuickSortAdversary_262144           2.14 ns         2.31 ns
BM_MakeHeap_string_Random_1                                                  0.289 ns        0.446 ns
BM_MakeHeap_string_Random_4                                                   7.43 ns         4.84 ns
BM_MakeHeap_string_Random_16                                                  9.73 ns         8.92 ns
BM_MakeHeap_string_Random_64                                                  11.5 ns         11.5 ns
BM_MakeHeap_string_Random_256                                                 12.6 ns         12.4 ns
BM_MakeHeap_string_Random_1024                                                13.2 ns         13.2 ns
BM_MakeHeap_string_Random_16384                                               15.4 ns         15.4 ns
BM_MakeHeap_string_Random_262144                                              21.4 ns         21.5 ns
BM_MakeHeap_string_Ascending_1                                               0.287 ns        0.447 ns
BM_MakeHeap_string_Ascending_4                                                3.22 ns         2.44 ns
BM_MakeHeap_string_Ascending_16                                               3.77 ns         3.62 ns
BM_MakeHeap_string_Ascending_64                                               4.84 ns         5.17 ns
BM_MakeHeap_string_Ascending_256                                              5.79 ns         6.04 ns
BM_MakeHeap_string_Ascending_1024                                             5.93 ns         6.60 ns
BM_MakeHeap_string_Ascending_16384                                            6.84 ns         7.25 ns
BM_MakeHeap_string_Ascending_262144                                           13.5 ns         14.3 ns
BM_MakeHeap_string_Descending_1                                              0.293 ns        0.447 ns
BM_MakeHeap_string_Descending_4                                               2.61 ns         1.83 ns
BM_MakeHeap_string_Descending_16                                              2.64 ns         2.60 ns
BM_MakeHeap_string_Descending_64                                              2.75 ns         2.74 ns
BM_MakeHeap_string_Descending_256                                             3.78 ns         3.57 ns
BM_MakeHeap_string_Descending_1024                                            3.20 ns         3.51 ns
BM_MakeHeap_string_Descending_16384                                           3.57 ns         3.85 ns
BM_MakeHeap_string_Descending_262144                                          6.27 ns         6.39 ns
BM_MakeHeap_string_SingleElement_1                                           0.291 ns        0.448 ns
BM_MakeHeap_string_SingleElement_4                                            3.88 ns         2.71 ns
BM_MakeHeap_string_SingleElement_16                                           5.08 ns         4.96 ns
BM_MakeHeap_string_SingleElement_64                                           6.14 ns         6.29 ns
BM_MakeHeap_string_SingleElement_256                                          6.13 ns         6.46 ns
BM_MakeHeap_string_SingleElement_1024                                         5.98 ns         6.60 ns
BM_MakeHeap_string_SingleElement_16384                                        5.88 ns         6.39 ns
BM_MakeHeap_string_SingleElement_262144                                       9.95 ns         10.2 ns
BM_MakeHeap_string_PipeOrgan_1                                               0.292 ns        0.447 ns
BM_MakeHeap_string_PipeOrgan_4                                                2.97 ns         2.51 ns
BM_MakeHeap_string_PipeOrgan_16                                               3.76 ns         3.91 ns
BM_MakeHeap_string_PipeOrgan_64                                               4.89 ns         5.20 ns
BM_MakeHeap_string_PipeOrgan_256                                              5.77 ns         6.09 ns
BM_MakeHeap_string_PipeOrgan_1024                                             6.14 ns         6.40 ns
BM_MakeHeap_string_PipeOrgan_16384                                            6.83 ns         7.32 ns
BM_MakeHeap_string_PipeOrgan_262144                                           13.8 ns         14.6 ns
BM_MakeHeap_string_Heap_1                                                    0.288 ns        0.515 ns
BM_MakeHeap_string_Heap_4                                                     3.62 ns         4.20 ns
BM_MakeHeap_string_Heap_16                                                    5.36 ns         5.23 ns
BM_MakeHeap_string_Heap_64                                                    5.79 ns         5.38 ns
BM_MakeHeap_string_Heap_256                                                   5.70 ns         5.40 ns
BM_MakeHeap_string_Heap_1024                                                  5.78 ns         5.37 ns
BM_MakeHeap_string_Heap_16384                                                 6.09 ns         5.67 ns
BM_MakeHeap_string_Heap_262144                                                6.37 ns         5.96 ns
BM_MakeHeap_string_QuickSortAdversary_1                                      0.282 ns        0.448 ns
BM_MakeHeap_string_QuickSortAdversary_4                                       7.45 ns         5.60 ns
BM_MakeHeap_string_QuickSortAdversary_16                                      9.76 ns         8.85 ns
BM_MakeHeap_string_QuickSortAdversary_64                                      11.5 ns         11.2 ns
BM_MakeHeap_string_QuickSortAdversary_256                                     12.0 ns         11.8 ns
BM_MakeHeap_string_QuickSortAdversary_1024                                    12.2 ns         12.0 ns
BM_MakeHeap_string_QuickSortAdversary_16384                                   13.7 ns         13.6 ns
BM_MakeHeap_string_QuickSortAdversary_262144                                  14.1 ns         14.8 ns
BM_MakeHeap_float_Random_1                                                   0.287 ns        0.287 ns
BM_MakeHeap_float_Random_4                                                    2.29 ns         2.60 ns
BM_MakeHeap_float_Random_16                                                   4.00 ns         2.48 ns
BM_MakeHeap_float_Random_64                                                   4.41 ns         1.92 ns
BM_MakeHeap_float_Random_256                                                  4.73 ns         2.05 ns
BM_MakeHeap_float_Random_1024                                                 4.90 ns         2.27 ns
BM_MakeHeap_float_Random_16384                                                4.42 ns         2.27 ns
BM_MakeHeap_float_Random_262144                                               4.72 ns         1.39 ns
BM_MakeHeap_float_Ascending_1                                                0.291 ns        0.293 ns
BM_MakeHeap_float_Ascending_4                                                0.633 ns        0.428 ns
BM_MakeHeap_float_Ascending_16                                               0.638 ns        0.874 ns
BM_MakeHeap_float_Ascending_64                                               0.614 ns        0.698 ns
BM_MakeHeap_float_Ascending_256                                              0.663 ns        0.713 ns
BM_MakeHeap_float_Ascending_1024                                             0.660 ns        0.761 ns
BM_MakeHeap_float_Ascending_16384                                            0.628 ns        0.725 ns
BM_MakeHeap_float_Ascending_262144                                           0.629 ns        0.814 ns
BM_MakeHeap_float_Descending_1                                               0.290 ns        0.290 ns
BM_MakeHeap_float_Descending_4                                               0.421 ns        0.316 ns
BM_MakeHeap_float_Descending_16                                              0.302 ns        0.225 ns
BM_MakeHeap_float_Descending_64                                              0.293 ns        0.212 ns
BM_MakeHeap_float_Descending_256                                             0.314 ns        0.246 ns
BM_MakeHeap_float_Descending_1024                                            0.300 ns        0.231 ns
BM_MakeHeap_float_Descending_16384                                           0.308 ns        0.205 ns
BM_MakeHeap_float_Descending_262144                                          0.309 ns        0.203 ns
BM_MakeHeap_float_SingleElement_1                                            0.289 ns        0.292 ns
BM_MakeHeap_float_SingleElement_4                                            0.569 ns        0.347 ns
BM_MakeHeap_float_SingleElement_16                                           0.538 ns        0.825 ns
BM_MakeHeap_float_SingleElement_64                                           0.585 ns        0.727 ns
BM_MakeHeap_float_SingleElement_256                                          0.603 ns        0.708 ns
BM_MakeHeap_float_SingleElement_1024                                         0.618 ns        0.760 ns
BM_MakeHeap_float_SingleElement_16384                                        0.599 ns        0.726 ns
BM_MakeHeap_float_SingleElement_262144                                       0.723 ns        0.820 ns
BM_MakeHeap_float_PipeOrgan_1                                                0.289 ns        0.291 ns
BM_MakeHeap_float_PipeOrgan_4                                                0.457 ns        0.420 ns
BM_MakeHeap_float_PipeOrgan_16                                               0.670 ns         1.32 ns
BM_MakeHeap_float_PipeOrgan_64                                               0.764 ns        0.889 ns
BM_MakeHeap_float_PipeOrgan_256                                              0.793 ns        0.757 ns
BM_MakeHeap_float_PipeOrgan_1024                                             0.755 ns        0.764 ns
BM_MakeHeap_float_PipeOrgan_16384                                            0.723 ns        0.723 ns
BM_MakeHeap_float_PipeOrgan_262144                                           0.654 ns        0.817 ns
BM_MakeHeap_float_Heap_1                                                     0.291 ns        0.289 ns
BM_MakeHeap_float_Heap_4                                                     0.388 ns        0.316 ns
BM_MakeHeap_float_Heap_16                                                    0.317 ns        0.225 ns
BM_MakeHeap_float_Heap_64                                                    0.353 ns        0.213 ns
BM_MakeHeap_float_Heap_256                                                   0.361 ns        0.246 ns
BM_MakeHeap_float_Heap_1024                                                  0.381 ns        0.233 ns
BM_MakeHeap_float_Heap_16384                                                 0.390 ns        0.205 ns
BM_MakeHeap_float_Heap_262144                                                0.379 ns        0.202 ns
BM_MakeHeap_float_QuickSortAdversary_1                                       0.295 ns        0.289 ns
BM_MakeHeap_float_QuickSortAdversary_4                                       0.640 ns        0.422 ns
BM_MakeHeap_float_QuickSortAdversary_16                                      0.658 ns        0.871 ns
BM_MakeHeap_float_QuickSortAdversary_64                                      0.574 ns        0.659 ns
BM_MakeHeap_float_QuickSortAdversary_256                                     0.631 ns        0.550 ns
BM_MakeHeap_float_QuickSortAdversary_1024                                    0.617 ns        0.552 ns
BM_MakeHeap_float_QuickSortAdversary_16384                                   0.424 ns        0.283 ns
BM_MakeHeap_float_QuickSortAdversary_262144                                  0.386 ns        0.219 ns
```

Fixes #120752

[libc++][hardening] Categorize more assertions. (#75918)

2024-01-06T00:29:23+00:00

Also introduce `_LIBCPP_ASSERT_PEDANTIC` for assertions violating which
results in a no-op or other benign behavior, but which may nevertheless
indicate a bug in the invoking code.

[libc++] Format the code base (#74334)

2023-12-18T19:01:33+00:00

This patch runs clang-format on all of libcxx/include and libcxx/src, in
accordance with the RFC discussed at [1]. Follow-up patches will format
the benchmarks, the test suite and remaining parts of the code. I'm
splitting this one into its own patch so the diff is a bit easier to
review.

This patch was generated with:

   find libcxx/include libcxx/src -type f \
      | grep -v 'module.modulemap.in' \
      | grep -v 'CMakeLists.txt' \
      | grep -v 'README.txt' \
      | grep -v 'libcxx.imp' \
      | grep -v '__config_site.in' \
      | xargs clang-format -i

A Git merge driver is available in libcxx/utils/clang-format-merge-driver.sh
to help resolve merge and rebase issues across these formatting changes.

[1]: https://discourse.llvm.org/t/rfc-clang-formatting-all-of-libc-once-and-for-all

[libc++] Replace uses of _VSTD:: by std:: (#74331)

2023-12-05T16:19:15+00:00

As part of the upcoming clang-formatting of libc++, this patch performs
the long desired removal of the _VSTD macro.

See https://discourse.llvm.org/t/rfc-clang-formatting-all-of-libc-once-and-for-all
for the clang-format proposal.

Fixing conflicting macro definitions between curses.h and the standard library.

2023-07-06T17:21:08+00:00

POSIX allows certain macros to exist with generic names (i.e. refresh(), move(), and erase()) to exist in `curses.h` which conflict with functions found in std::filesystem, among others. This patch undefs the macros in question and adds them to LIBCPP_PUSH_MACROS and LIBCPP_POP_MACROS.

Reviewed By: #libc, philnik, ldionne

Differential Revision: https://reviews.llvm.org/D147356

[libc++][hardening][NFC] Introduce `_LIBCPP_ASSERT_UNCATEGORIZED`.

2023-06-28T22:10:31+00:00

Replace most uses of `_LIBCPP_ASSERT` with
`_LIBCPP_ASSERT_UNCATEGORIZED`.

This is done as a prerequisite to introducing hardened mode to libc++.
The idea is to make enabling assertions an opt-in with (somewhat)
fine-grained controls over which categories of assertions are enabled.
The vast majority of assertions are currently uncategorized; the new
macro will allow turning on `_LIBCPP_ASSERT` (the underlying mechanism
for all kinds of assertions) without enabling all the uncategorized
assertions (in the future; this patch preserves the current behavior).

Differential Revision: https://reviews.llvm.org/D153816

[libc++][NFC] Rename the constexpr macros

2022-08-19T13:35:02+00:00

This was discussed on Discord with the consensus that we should rename the macros.

Reviewed By: ldionne, Mordante, var-const, avogelsgesang, jloser, #libc

Spies: libcxx-commits

Differential Revision: https://reviews.llvm.org/D131498

[libc++] Add a bunch of missing _LIBCPP_HIDE_FROM_ABI

2022-08-13T20:41:22+00:00

Reviewed By: ldionne, Mordante, var-const, huixie90, #libc

Spies: jloser, libcxx-commits, arichardson, miyuki

Differential Revision: https://reviews.llvm.org/D129968

[libc++][ranges] Implement `std::ranges::partial_sort_copy`.

2022-07-30T09:42:18+00:00

Differential Revision: https://reviews.llvm.org/D130532

[libc++][ranges] Make range algorithms support proxy iterators

2022-07-18T01:12:06+00:00

Also test all the range algorithms to verify the support.

Differential Revision: https://reviews.llvm.org/D129823

llvm-project.git/libcxx/include/__algorithm/sift_down.h, branch users/mingmingl-llvm/samplefdo-profile-format