Fields
| hardware | None |
| os | None |
Parameters
Fields
| Name | Value |
|---|
Parameters
| Name | Value |
|---|---|
| git_commit |
commit fd08af0a969a13d505c47a1f64e8f8def65a6aca Author: Peng Liu <winner245@hotmail.com> Date: Wed Oct 15 19:44:35 2025 -0400 [libc++] Optimize {std,ranges}::distance for segmented iterators (#133612) This patch enhances the performance of `std::distance` and `std::ranges::distance` for non-random-access segmented iterators, e.g., `std::join_view` iterators. The original implementation operates in linear time, `O(n)`, where `n` is the total number of elements. The optimized version reduces this to approximately `O(n / segment_size)` by leveraging segmented structure, where `segment_size` is the average size of each segment. The table below summarizes the peak performance improvements observed across different segment sizes, with the total element count `n` ranging up to `1 << 20` (1,048,576 elements), based on benchmark results. ``` ---------------------------------------------------------------------------------------- Container/n/segment_size std::distance std::ranges::distance ---------------------------------------------------------------------------------------- join_view(vector<vector<int>>)/1048576/256 401.6x 422.9x join_view(deque<deque<int>>)/1048576/256 112.1x 132.6x join_view(vector<vector<int>>)/1048576/1024 1669.2x 1559.1x join_view(deque<deque<int>>)/1048576/1024 487.7x 497.4x ``` ## Benchmarks #### Segment size = 1024 ``` ----------------------------------------------------------------------------------------- Benchmark Before After Speedup ----------------------------------------------------------------------------------------- std::distance(join_view(vector<vector<int>>))/50 38.8 ns 1.01 ns 38.4x std::distance(join_view(vector<vector<int>>))/1024 660 ns 1.02 ns 647.1x std::distance(join_view(vector<vector<int>>))/4096 2934 ns 1.98 ns 1481.8x std::distance(join_view(vector<vector<int>>))/8192 5751 ns 3.92 ns 1466.8x std::distance(join_view(vector<vector<int>>))/16384 11520 ns 7.06 ns 1631.7x std::distance(join_view(vector<vector<int>>))/65536 46367 ns 32.2 ns 1440.6x std::distance(join_view(vector<vector<int>>))/262144 182611 ns 114 ns 1601.9x std::distance(join_view(vector<vector<int>>))/1048576 737785 ns 442 ns 1669.2x std::distance(join_view(deque<deque<int>>))/50 53.1 ns 6.13 ns 8.7x std::distance(join_view(deque<deque<int>>))/1024 854 ns 7.53 ns 113.4x std::distance(join_view(deque<deque<int>>))/4096 3507 ns 14.7 ns 238.6x std::distance(join_view(deque<deque<int>>))/8192 7114 ns 17.6 ns 404.2x std::distance(join_view(deque<deque<int>>))/16384 13997 ns 30.7 ns 455.9x std::distance(join_view(deque<deque<int>>))/65536 55598 ns 114 ns 487.7x std::distance(join_view(deque<deque<int>>))/262144 214293 ns 480 ns 446.4x std::distance(join_view(deque<deque<int>>))/1048576 833000 ns 2183 ns 381.6x rng::distance(join_view(vector<vector<int>>))/50 39.1 ns 1.10 ns 35.5x rng::distance(join_view(vector<vector<int>>))/1024 689 ns 1.14 ns 604.4x rng::distance(join_view(vector<vector<int>>))/4096 2753 ns 2.15 ns 1280.5x rng::distance(join_view(vector<vector<int>>))/8192 5530 ns 4.61 ns 1199.6x rng::distance(join_view(vector<vector<int>>))/16384 10968 ns 7.97 ns 1376.2x rng::distance(join_view(vector<vector<int>>))/65536 46009 ns 35.3 ns 1303.4x rng::distance(join_view(vector<vector<int>>))/262144 190569 ns 124 ns 1536.9x rng::distance(join_view(vector<vector<int>>))/1048576 746724 ns 479 ns 1559.1x rng::distance(join_view(deque<deque<int>>))/50 51.6 ns 6.57 ns 7.9x rng::distance(join_view(deque<deque<int>>))/1024 826 ns 6.50 ns 127.1x rng::distance(join_view(deque<deque<int>>))/4096 3323 ns 12.5 ns 265.8x rng::distance(join_view(deque<deque<int>>))/8192 6619 ns 19.1 ns 346.5x rng::distance(join_view(deque<deque<int>>))/16384 13495 ns 33.2 ns 406.5x rng::distance(join_view(deque<deque<int>>))/65536 53668 ns 114 ns 470.8x rng::distance(join_view(deque<deque<int>>))/262144 236277 ns 475 ns 497.4x rng::distance(join_view(deque<deque<int>>))/1048576 914177 ns 2157 ns 423.8x ----------------------------------------------------------------------------------------- ``` #### Segment size = 256 ``` ----------------------------------------------------------------------------------------- Benchmark Before After Speedup ----------------------------------------------------------------------------------------- std::distance(join_view(vector<vector<int>>))/50 38.1 ns 1.02 ns 37.4x std::distance(join_view(vector<vector<int>>))/1024 689 ns 2.06 ns 334.5x std::distance(join_view(vector<vector<int>>))/4096 2815 ns 7.01 ns 401.6x std::distance(join_view(vector<vector<int>>))/8192 5507 ns 14.3 ns 385.1x std::distance(join_view(vector<vector<int>>))/16384 11050 ns 33.7 ns 327.9x std::distance(join_view(vector<vector<int>>))/65536 44197 ns 118 ns 374.6x std::distance(join_view(vector<vector<int>>))/262144 175793 ns 449 ns 391.5x std::distance(join_view(vector<vector<int>>))/1048576 703242 ns 2140 ns 328.7x std::distance(join_view(deque<deque<int>>))/50 50.2 ns 6.12 ns 8.2x std::distance(join_view(deque<deque<int>>))/1024 835 ns 11.4 ns 73.2x std::distance(join_view(deque<deque<int>>))/4096 3353 ns 32.9 ns 101.9x std::distance(join_view(deque<deque<int>>))/8192 6711 ns 64.2 ns 104.5x std::distance(join_view(deque<deque<int>>))/16384 13231 ns 118 ns 112.1x std::distance(join_view(deque<deque<int>>))/65536 53523 ns 556 ns 96.3x std::distance(join_view(deque<deque<int>>))/262144 219101 ns 2166 ns 101.2x std::distance(join_view(deque<deque<int>>))/1048576 880277 ns 15852 ns 55.5x rng::distance(join_view(vector<vector<int>>))/50 37.7 ns 1.13 ns 33.4x rng::distance(join_view(vector<vector<int>>))/1024 697 ns 2.14 ns 325.7x rng::distance(join_view(vector<vector<int>>))/4096 2804 ns 7.52 ns 373.0x rng::distance(join_view(vector<vector<int>>))/8192 5749 ns 15.2 ns 378.2x rng::distance(join_view(vector<vector<int>>))/16384 11742 ns 34.8 ns 337.4x rng::distance(join_view(vector<vector<int>>))/65536 47274 ns 116 ns 407.7x rng::distance(join_view(vector<vector<int>>))/262144 187774 ns 444 ns 422.9x rng::distance(join_view(vector<vector<int>>))/1048576 749724 ns 2109 ns 355.5x rng::distance(join_view(deque<deque<int>>))/50 53.0 ns 6.09 ns 8.7x rng::distance(join_view(deque<deque<int>>))/1024 895 ns 11.0 ns 81.4x rng::distance(join_view(deque<deque<int>>))/4096 3825 ns 30.6 ns 125.0x rng::distance(join_view(deque<deque<int>>))/8192 7550 ns 60.5 ns 124.8x rng::distance(join_view(deque<deque<int>>))/16384 14847 ns 112 ns 132.6x rng::distance(join_view(deque<deque<int>>))/65536 56888 ns 453 ns 125.6x rng::distance(join_view(deque<deque<int>>))/262144 231395 ns 2034 ns 113.8x rng::distance(join_view(deque<deque<int>>))/1048576 933093 ns 15012 ns 62.2x ----------------------------------------------------------------------------------------- ``` Addresses a subtask of #102817. --------- Co-authored-by: Louis Dionne <ldionne.2@gmail.com> Co-authored-by: A. Jiang <de34@live.cn> |
Filter
ldionne-old-macbook-results test results
| Run | Order | Start Time | Duration |
|---|---|---|---|
| Current | 556122 | 2025-12-16T16:40:01 | 0:00:00 |
| Previous | 555899 | 2025-12-16T16:40:01 | 0:00:00 |
| Baseline | 485288 | 2025-12-16T16:40:01 | 0:00:00 |
Tests Summary
| Status Group | # | # (B) |
|---|---|---|
| Performance Regressions | 10 | 0 |
| Added Tests | 0 | 16 |
| Unchanged Tests | 70 | 64 |
| Total Tests | 80 |
| Performance Regressions - execution_time | Δ | Previous | Current | σ | Δ (B) | σ (B) |
|---|---|---|---|---|---|---|
| 706_stockfish_r | 5.25% | 20.494 | 21.570 | - | 0.00% | - |
| 707_ntest_r | 3.06% | 16.044 | 16.536 | - | 0.00% | - |
| 709_cactus_r | 2.44% | 19.178 | 19.645 | - | 0.00% | - |
| 737_gmsh_r | 2.18% | 12.657 | 12.933 | - | 0.00% | - |
| 729_abc_r | 2.04% | 18.313 | 18.687 | - | 0.00% | - |
| 727_cppcheck_r | 1.99% | 24.484 | 24.971 | - | 0.00% | - |
| 735_gem5_r | 1.80% | 13.142 | 13.379 | - | 0.00% | - |
| 723_llvm_r | 1.43% | 11.398 | 11.561 | - | 0.00% | - |
| 721_gcc_r | 1.07% | 12.885 | 13.023 | - | 0.00% | - |
| 710_omnetpp_r | 1.06% | 8.414 | 8.503 | - | 0.00% | - |
| Added Tests - execution_time |
|---|
| 706_stockfish_r |
| 707_ntest_r |
| 709_cactus_r |
| 710_omnetpp_r |
| 721_gcc_r |
| 723_llvm_r |
| 727_cppcheck_r |
| 729_abc_r |
| 731_astcenc_r |
| 735_gem5_r |
| 736_ocio_r |
| 737_gmsh_r |
| 748_flightdm_r |
| 750_sealcrypto_r |
| 753_ns3_r |
| 766_femflow_r |
Report Time: 0.08s