On Sun, 21 Sep 2025 19:47:14 GMT, Vladimir Yaroslavskiy <[email protected]> wrote:
> The goal of the PR is to improve both, sequential and parallel, sorting of > primitives. > > **The main achievements** > > - introduced Radix in parallel sorting which shows several times boost of > performance and has linear complexity instead of n*ln(n) > - improved mixed insertion sort (makes whole sorting faster) > - improved merging sort for almost sorted data > - optimized parallel sorting > - improved step for pivot candidates and pivot partitioning > - suggested better buffer allocation: if no memory, it is switched to > in-place sorting with no OutOfMemoryError > - minor javadoc and comment changes > > - extended existing tests > - added tests for radix sort, heap sort, insertion sort > - added benchmarking JMH tests > - improved test coverage > > **The summary of benchmarking:** > > **Sequential sorting (Arrays.sort)** > > byte: up to 50% faster > char: 4-7 times faster > short: 2-6 times faster > int: 1.2-5 times faster > long: 1.2-5 times faster > float: 1.2-5 times faster > double: 1.2-4 times faster > > **Parallel sorting (Arrays.parallelSort)** > > int: 1.2-9 times faster > long: 1.2-9 times faster > float: 1.2-4 times faster > double: 1.2-4 times faster > > **AVX512 support** > > Vamsi Parasa suggested faster sort routines by taking advantage of AVX512 > instructions, see https://github.com/openjdk/jdk/pull/14227, sources of > sorting were modified. Therefore, I performed benchmarking of the final > version (which includes optimizations by Vamsi Parasa and optimizations from > my side) on a server with CPUs supported AVX512 instructions, no regression > of performance was found, see detailed benchmarking results. > > I'm going on previous PRs https://github.com/openjdk/jdk/pull/3938 and > https://github.com/openjdk/jdk/pull/13568 **Sorting on a server with AVX512 instructions** OS name: Fedora Linux 38 (Workstation Edition) Model name: Intel(R) Xeon(R) Gold 6338 CPU @ 2.00GHz CPU family: 6 Model: 106 Thread(s) per core: 2 Core(s) per socket: 32 Socket(s): 2 OpenJDK version "24-beta" 2025-03-18 OpenJDK Runtime Environment Zulu24+53-CA (build 24-beta+22) OpenJDK 64-Bit Server VM Zulu24+53-CA (build 24-beta+22, mixed mode, sharing) **Sequential sorting** Benchmark | Data Type | Array Size | Baseline (us/op) | New version (us/op) | Speedup -- | -- | -- | -- | -- | -- byte | RANDOM | 600 | 1,105 | 1,096 | **1.01** byte | RANDOM | 3000 | 3,315 | 3,015 | **1.10** byte | RANDOM | 40000 | 41,283 | 36,735 | **1.12** byte | RANDOM | 800000 | 472,986 | 371,946 | **1.27** byte | RANDOM | 5000000 | 2958,884 | 2359,100 | **1.25** byte | SHUFFLE | 600 | 1,025 | 1,025 | **1.00** byte | SHUFFLE | 3000 | 3,110 | 2,995 | **1.04** byte | SHUFFLE | 40000 | 37,507 | 34,698 | **1.08** byte | SHUFFLE | 800000 | 440,601 | 353,063 | **1.25** byte | SHUFFLE | 5000000 | 2645,334 | 2220,906 | **1.19** byte | STAGGER | 600 | 0,682 | 0,696 | **0.98** byte | STAGGER | 3000 | 2,473 | 2,498 | **0.99** byte | STAGGER | 40000 | 16,892 | 17,167 | **0.98** byte | STAGGER | 800000 | 340,018 | 334,596 | **1.02** byte | STAGGER | 5000000 | 2171,872 | 2180,550 | **1.00** byte | REPEATED | 600 | 0,824 | 0,840 | **0.98** byte | REPEATED | 3000 | 2,435 | 2,448 | **0.99** byte | REPEATED | 40000 | 29,167 | 29,168 | **1.00** byte | REPEATED | 800000 | 592,413 | 592,667 | **1.00** byte | REPEATED | 5000000 | 3792,008 | 3791,389 | **1.00** --- | --- | --- | --- | --- | --- char | RANDOM | 600 | 8,076 | 5,811 | **1.39** char | RANDOM | 3000 | 127,738 | 18,471 | **6.92** char | RANDOM | 40000 | 466,992 | 464,783 | **1.00** char | RANDOM | 800000 | 1962,639 | 2007,212 | **0.98** char | RANDOM | 5000000 | 6608,751 | 6730,025 | **0.98** char | SHUFFLE | 600 | 4,713 | 3,574 | **1.32** char | SHUFFLE | 3000 | 86,595 | 10,962 | **7.90** char | SHUFFLE | 40000 | 116,087 | 103,458 | **1.12** char | SHUFFLE | 800000 | 802,059 | 747,908 | **1.07** char | SHUFFLE | 5000000 | 3527,583 | 3273,802 | **1.08** char | STAGGER | 600 | 9,146 | 5,651 | **1.62** char | STAGGER | 3000 | 88,480 | 9,888 | **8.95** char | STAGGER | 40000 | 140,569 | 129,855 | **1.08** char | STAGGER | 800000 | 694,116 | 701,170 | **0.99** char | STAGGER | 5000000 | 3685,380 | 3667,346 | **1.00** char | REPEATED | 600 | 1,775 | 1,745 | **1.02** char | REPEATED | 3000 | 87,272 | 17,176 | **5.08** char | REPEATED | 40000 | 116,472 | 88,054 | **1.32** char | REPEATED | 800000 | 789,963 | 660,936 | **1.20** char | REPEATED | 5000000 | 4373,931 | 3907,108 | **1.12** --- | --- | --- | --- | --- | --- short | RANDOM | 600 | 8,433 | 5,455 | **1.55** short | RANDOM | 3000 | 95,889 | 9,871 | **9.71** short | RANDOM | 40000 | 526,723 | 457,268 | **1.15** short | RANDOM | 800000 | 1991,657 | 2011,202 | **0.99** short | RANDOM | 5000000 | 6592,367 | 6745,836 | **0.98** short | SHUFFLE | 600 | 4,706 | 3,597 | **1.31** short | SHUFFLE | 3000 | 44,413 | 11,895 | **3.73** short | SHUFFLE | 40000 | 137,088 | 139,490 | **0.98** short | SHUFFLE | 800000 | 851,142 | 813,856 | **1.05** short | SHUFFLE | 5000000 | 3605,340 | 3642,393 | **0.99** short | STAGGER | 600 | 8,932 | 5,088 | **1.76** short | STAGGER | 3000 | 54,740 | 11,432 | **4.79** short | STAGGER | 40000 | 141,403 | 104,327 | **1.36** short | STAGGER | 800000 | 739,105 | 755,126 | **0.98** short | STAGGER | 5000000 | 3613,685 | 3649,485 | **0.99** short | REPEATED | 600 | 1,787 | 1,646 | **1.09** short | REPEATED | 3000 | 41,117 | 17,711 | **2.32** short | REPEATED | 40000 | 67,597 | 62,072 | **1.09** short | REPEATED | 800000 | 725,665 | 635,773 | **1.14** short | REPEATED | 5000000 | 3961,620 | 3910,409 | **1.01** --- | --- | --- | --- | --- | --- int | RANDOM | 600 | 10,062 | 6,263 | **1.61** int | RANDOM | 3000 | 106,288 | 81,867 | **1.30** int | RANDOM | 40000 | 2706,821 | 2409,536 | **1.12** int | RANDOM | 800000 | 70786,294 | 63018,686 | **1.12** int | RANDOM | 5000000 | 513654,721 |448534,136 | **1.15** int | SHUFFLE | 600 | 5,554 | 3,832 | **1.45** int | SHUFFLE | 3000 | 34,681 | 23,799 | **1.46** int | SHUFFLE | 40000 | 810,646 | 675,154 | **1.20** int | SHUFFLE | 800000 | 17786,842 | 13394,929 | **1.33** int | SHUFFLE | 5000000 | 103972,483 | 89292,885 | **1.16** int | STAGGER | 600 | 10,912 | 1,919 | **5.69** int | STAGGER | 3000 | 16,805 | 8,743 | **1.92** int | STAGGER | 40000 | 221,680 | 119,119 | **1.86** int | STAGGER | 800000 | 4439,270 | 2646,225 | **1.68** int | STAGGER | 5000000 | 28206,856 | 18989,937 | **1.49** int | REPEATED | 600 | 1,600 | 1,401 | **1.14** int | REPEATED | 3000 | 8,333 | 8,166 | **1.02** int | REPEATED | 40000 | 366,056 | 338,253 | **1.08** int | REPEATED | 800000 | 8381,340 | 7163,611 | **1.17** int | REPEATED | 5000000 | 57009,039 | 49579,605 | **1.15** --- | --- | --- | --- | --- | --- long | RANDOM | 600 | 9,526 | 5,500 | **1.73** long | RANDOM | 3000 | 106,262 | 81,212 | **1.31** long | RANDOM | 40000 | 2642,178 | 2380,290 | **1.11** long | RANDOM | 800000 | 71082,533 | 60574,668 | **1.17** long | RANDOM | 5000000 | 497591,181 |441894,477 | **1.13** long | SHUFFLE | 600 | 5,003 | 3,666 | **1.36** long | SHUFFLE | 3000 | 39,157 | 24,116 | **1.62** long | SHUFFLE | 40000 | 731,785 | 653,146 | **1.12** long | SHUFFLE | 800000 | 18055,584 | 14313,625 | **1.26** long | SHUFFLE | 5000000 | 122763,113 | 85477,515 | **1.44** long | STAGGER | 600 | 8,668 | 2,020 | **4.29** long | STAGGER | 3000 | 59,460 | 9,874 | **6.02** long | STAGGER | 40000 | 888,697 | 142,874 | **6.22** long | STAGGER | 800000 | 19205,162 | 3480,767 | **5.52** long | STAGGER | 5000000 | 123337,211 | 26088,945 | **4.73** long | REPEATED | 600 | 1,764 | 1,618 | **1.09** long | REPEATED | 3000 | 9,284 | 8,147 | **1.14** long | REPEATED | 40000 | 370,378 | 320,390 | **1.16** long | REPEATED | 800000 | 8546,204 | 7641,426 | **1.12** long | REPEATED | 5000000 | 57714,600 | 50890,207 | **1.13** --- | --- | --- | --- | --- | --- float | RANDOM | 600 | 9,229 | 6,824 | **1.35** float | RANDOM | 3000 | 98,336 | 94,386 | **1.04** float | RANDOM | 40000 | 2737,466 | 2626,643 | **1.04** float | RANDOM | 800000 | 71064,995 | 67788,935 | **1.05** float | RANDOM | 5000000 | 511617,741 |483790,193 | **1.06** float | SHUFFLE | 600 | 5,356 | 4,482 | **1.20** float | SHUFFLE | 3000 | 32,069 | 27,485 | **1.17** float | SHUFFLE | 40000 | 803,721 | 786,535 | **1.02** float | SHUFFLE | 800000 | 17475,458 | 15571,843 | **1.12** float | SHUFFLE | 5000000 | 104055,032 |103707,582 | **1.00** float | STAGGER | 600 | 9,823 | 2,259 | **4.35** float | STAGGER | 3000 | 21,148 | 10,721 | **1.97** float | STAGGER | 40000 | 280,128 | 145,725 | **1.92** float | STAGGER | 800000 | 5625,923 | 3227,219 | **1.74** float | STAGGER | 5000000 | 35646,533 | 22611,370 | **1.58** float | REPEATED | 600 | 2,489 | 2,273 | **1.10** float | REPEATED | 3000 | 14,390 | 11,444 | **1.26** float | REPEATED | 40000 | 537,690 | 456,280 | **1.18** float | REPEATED | 800000 | 11733,707 | 10678,972 | **1.10** float | REPEATED | 5000000 | 78247,675 | 58791,233 | **1.33** --- | --- | --- | --- | --- | --- double| RANDOM | 600 | 9,209 | 6,879 | **1.34** double| RANDOM | 3000 | 100,158 | 89,748 | **1.12** double| RANDOM | 40000 | 2744,205 | 2589,135 | **1.06** double| RANDOM | 800000 | 71450,447 | 67051,035 | **1.07** double| RANDOM | 5000000 | 518599,968 |482903,685 | **1.07** double| SHUFFLE | 600 | 5,424 | 4,574 | **1.19** double| SHUFFLE | 3000 | 31,738 | 27,942 | **1.14** double| SHUFFLE | 40000 | 787,763 | 776,840 | **1.01** double| SHUFFLE | 800000 | 17492,549 | 16081,350 | **1.09** double| SHUFFLE | 5000000 | 107874,866 |107086,811 | **1.01** double| STAGGER | 600 | 9,883 | 2,206 | **4.48** double| STAGGER | 3000 | 19,615 | 10,908 | **1.80** double| STAGGER | 40000 | 270,368 | 151,057 | **1.79** double| STAGGER | 800000 | 5504,383 | 3658,210 | **1.50** double| STAGGER | 5000000 | 37996,995 | 29044,386 | **1.31** double| REPEATED | 600 | 2,548 | 2,260 | **1.13** double| REPEATED | 3000 | 14,333 | 12,515 | **1.15** double| REPEATED | 40000 | 544,588 | 459,425 | **1.19** double| REPEATED | 800000 | 11791,047 | 10734,706 | **1.10** double| REPEATED | 5000000 | 79668,645 | 62098,296 | **1.28** **Parallel sorting** Benchmark | Data Type | Array Size | Baseline (us/op) | New version (us/op) | Speedup -- | -- | -- | -- | -- | -- int | RANDOM | 600 | 9,724 | 6,154 | **1.58** int | RANDOM | 3000 | 96,070 | 85,794 | **1.12** int | RANDOM | 40000 | 414,904 | 282,580 | **1.47** int | RANDOM | 800000 | 4743,790 | 1429,808 | **3.32** int | RANDOM | 5000000 | 23981,879 | 13549,869 | **1.77** int | SHUFFLE | 600 | 6,029 | 3,632 | **1.66** int | SHUFFLE | 3000 | 37,097 | 22,772 | **1.63** int | SHUFFLE | 40000 | 193,044 | 97,703 | **1.98** int | SHUFFLE | 800000 | 1769,768 | 900,230 | **1.97** int | SHUFFLE | 5000000 | 11040,155 | 7635,319 | **1.45** int | STAGGER | 600 | 10,948 | 2,366 | **4.63** int | STAGGER | 3000 | 15,728 | 11,559 | **1.36** int | STAGGER | 40000 | 76,648 | 65,278 | **1.17** int | STAGGER | 800000 | 912,780 | 532,419 | **1.71** int | STAGGER | 5000000 | 5528,946 | 2886,539 | **1.92** int | REPEATED | 600 | 2,000 | 1,588 | **1.26** int | REPEATED | 3000 | 10,518 | 8,022 | **1.31** int | REPEATED | 40000 | 153,249 | 101,689 | **1.51** int | REPEATED | 800000 | 2564,321 | 1102,722 | **2.33** int | REPEATED | 5000000 | 16141,658 | 6440,913 | **2.51** --- | --- | --- | --- | --- | --- long | RANDOM | 600 | 9,392 | 5,974 | **1.57** long | RANDOM | 3000 | 119,022 | 72,486 | **1.64** long | RANDOM | 40000 | 446,894 | 327,094 | **1.37** long | RANDOM | 800000 | 4618,046 | 2157,313 | **2.14** long | RANDOM | 5000000 | 26806,347 | 17064,431 | **1.57** long | SHUFFLE | 600 | 5,037 | 3,991 | **1.26** long | SHUFFLE | 3000 | 39,226 | 28,969 | **1.35** long | SHUFFLE | 40000 | 188,613 | 117,552 | **1.60** long | SHUFFLE | 800000 | 2203,806 | 1436,670 | **1.53** long | SHUFFLE | 5000000 | 15363,291 | 10869,309 | **1.41** long | STAGGER | 600 | 10,616 | 2,506 | **4.24** long | STAGGER | 3000 | 15,545 | 13,073 | **1.19** long | STAGGER | 40000 | 94,714 | 71,397 | **1.33** long | STAGGER | 800000 | 1263,737 | 933,039 | **1.35** long | STAGGER | 5000000 | 8534,961 | 5804,477 | **1.47** long | REPEATED | 600 | 1,726 | 1,640 | **1.05** long | REPEATED | 3000 | 10,035 | 7,876 | **1.27** long | REPEATED | 40000 | 168,700 | 110,725 | **1.52** long | REPEATED | 800000 | 2845,738 | 1504,553 | **1.89** long | REPEATED | 5000000 | 18759,763 | 9377,812 | **2.00** --- | --- | --- | --- | --- | --- float | RANDOM | 600 | 9,931 | 6,936 | **1.43** float | RANDOM | 3000 | 119,779 | 99,573 | **1.20** float | RANDOM | 40000 | 476,756 | 392,104 | **1.22** float | RANDOM | 800000 | 4930,482 | 2919,610 | **1.69** float | RANDOM | 5000000 | 29463,322 | 17644,605 | **1.67** float | SHUFFLE | 600 | 5,459 | 4,543 | **1.20** float | SHUFFLE | 3000 | 32,297 | 27,887 | **1.16** float | SHUFFLE | 40000 | 235,827 | 181,163 | **1.30** float | SHUFFLE | 800000 | 2428,839 | 1791,028 | **1.36** float | SHUFFLE | 5000000 | 15353,423 | 10433,192 | **1.47** float | STAGGER | 600 | 9,779 | 2,415 | **4.05** float | STAGGER | 3000 | 18,693 | 11,581 | **1.61** float | STAGGER | 40000 | 117,526 | 79,751 | **1.47** float | STAGGER | 800000 | 1744,397 | 1160,997 | **1.50** float | STAGGER | 5000000 | 10651,683 | 7002,571 | **1.52** float | REPEATED | 600 | 2,651 | 2,262 | **1.17** float | REPEATED | 3000 | 15,812 | 11,984 | **1.32** float | REPEATED | 40000 | 270,629 | 155,697 | **1.74** float | REPEATED | 800000 | 5450,441 | 1741,966 | **3.13** float | REPEATED | 5000000 | 34499,266 | 10705,402 | **3.22** --- | --- | --- | --- | --- | --- double | RANDOM | 600 | 9,183 | 6,965 | **1.32** double | RANDOM | 3000 | 97,578 | 94,393 | **1.03** double | RANDOM | 40000 | 468,966 | 410,451 | **1.14** double | RANDOM | 800000 | 5202,712 | 3569,054 | **1.46** double | RANDOM | 5000000 | 32081,048 | 22927,051 | **1.40** double | SHUFFLE | 600 | 5,462 | 4,438 | **1.23** double | SHUFFLE | 3000 | 31,924 | 27,371 | **1.17** double | SHUFFLE | 40000 | 263,423 | 199,992 | **1.32** double | SHUFFLE | 800000 | 2826,594 | 2387,148 | **1.18** double | SHUFFLE | 5000000 | 19212,580 | 16573,293 | **1.16** double | STAGGER | 600 | 9,803 | 2,558 | **3.83** double | STAGGER | 3000 | 19,258 | 13,093 | **1.47** double | STAGGER | 40000 | 133,250 | 107,261 | **1.24** double | STAGGER | 800000 | 2027,997 | 1561,934 | **1.30** double | STAGGER | 5000000 | 14387,512 | 10943,813 | **1.31** double | REPEATED | 600 | 2,553 | 2,266 | **1.13** double | REPEATED | 3000 | 14,479 | 11,995 | **1.21** double | REPEATED | 40000 | 274,235 | 167,220 | **1.64** double | REPEATED | 800000 | 5378,801 | 2182,560 | **2.46** double | REPEATED | 5000000 | 35181,974 | 14323,815 | **2.46** **Sorting on a computer without AVX512 support** OS name: Edition Windows 10 Pro Processor: Intel(R) Core(TM) i7-10850H CPU @ 2.70GHz System type: 64-bit operating system, x64-based processor Version: 22H2 OpenJDK 26-ea 2026-03-17 OpenJDK Runtime Environment (build 26-ea+13-1333) OpenJDK 64-Bit Server VM (build 26-ea+13-1333, mixed mode, sharing) **Sequential sorting** Benchmark | Data Type | Array Size | Baseline (us/op) | New version (us/op) | Speedup -- | -- | -- | -- | -- | -- byte | RANDOM | 600 | 1,336 | 1,341 | **1.00** byte | RANDOM | 3000 | 3,775 | 3,813 | **0.99** byte | RANDOM | 40000 | 30,852 | 31,590 | **0.98** byte | RANDOM | 800000 | 526,780 | 526,931 | **1.00** byte | RANDOM | 5000000 | 3427,225 | 3466,470 | **0.99** byte | SHUFFLE | 600 | 1,253 | 1,260 | **0.99** byte | SHUFFLE | 3000 | 3,456 | 3,526 | **0.98** byte | SHUFFLE | 40000 | 30,739 | 31,153 | **0.99** byte | SHUFFLE | 800000 | 506,622 | 507,776 | **1.00** byte | SHUFFLE | 5000000 | 3358,144 | 3340,962 | **1.01** byte | STAGGER | 600 | 0,926 | 0,903 | **1.03** byte | STAGGER | 3000 | 2,463 | 2,489 | **0.99** byte | STAGGER | 40000 | 26,155 | 25,906 | **1.01** byte | STAGGER | 800000 | 501,954 | 504,353 | **1.00** byte | STAGGER | 5000000 | 3264,418 | 3268,509 | **1.00** byte | REPEATED | 600 | 0,978 | 0,634 | **1.54** byte | REPEATED | 3000 | 2,870 | 2,532 | **1.13** byte | REPEATED | 40000 | 30,026 | 28,714 | **1.05** byte | REPEATED | 800000 | 571,674 | 571,686 | **1.00** byte | REPEATED | 5000000 | 3740,136 | 3744,403 | **1.00** --- | --- | --- | --- | --- | --- char | RANDOM | 600 | 11,029 | 6,696 | **1.65** char | RANDOM | 3000 | 106,682 | 11,737 | **9.09** char | RANDOM | 40000 | 518,084 | 509,866 | **1.02** char | RANDOM | 800000 | 2251,095 | 2296,499 | **0.98** char | RANDOM | 5000000 | 8126,281 | 8208,779 | **0.99** char | SHUFFLE | 600 | 6,646 | 4,382 | **1.52** char | SHUFFLE | 3000 | 91,039 | 12,664 | **7.19** char | SHUFFLE | 40000 | 163,862 | 162,688 | **1.01** char | SHUFFLE | 800000 | 991,965 | 981,299 | **1.01** char | SHUFFLE | 5000000 | 4388,959 | 4477,596 | **0.98** char | STAGGER | 600 | 11,344 | 6,691 | **1.70** char | STAGGER | 3000 | 74,156 | 12,469 | **5.95** char | STAGGER | 40000 | 138,021 | 138,125 | **1.00** char | STAGGER | 800000 | 905,072 | 869,419 | **1.04** char | STAGGER | 5000000 | 5075,574 | 5076,498 | **1.00** char | REPEATED | 600 | 1,796 | 1,675 | **1.07** char | REPEATED | 3000 | 72,315 | 17,109 | **4.23** char | REPEATED | 40000 | 100,150 | 99,830 | **1.00** char | REPEATED | 800000 | 788,861 | 728,818 | **1.08** char | REPEATED | 5000000 | 4534,875 | 4417,603 | **1.03** --- | --- | --- | --- | --- | --- short | RANDOM | 600 | 11,147 | 6,657 | **1.67** short | RANDOM | 3000 | 97,153 | 14,013 | **6.93** short | RANDOM | 40000 | 536,996 | 533,115 | **1.01** short | RANDOM | 800000 | 2214,721 | 2236,256 | **0.99** short | RANDOM | 5000000 | 8129,979 | 8305,536 | **0.98** short | SHUFFLE | 600 | 6,466 | 4,328 | **1.49** short | SHUFFLE | 3000 | 37,262 | 14,628 | **2.55** short | SHUFFLE | 40000 | 151,558 | 151,465 | **1.00** short | SHUFFLE | 800000 | 952,759 | 961,413 | **0.99** short | SHUFFLE | 5000000 | 4392,945 | 4481,849 | **0.98** short | STAGGER | 600 | 11,456 | 6,737 | **1.70** short | STAGGER | 3000 | 42,934 | 14,630 | **2.93** short | STAGGER | 40000 | 122,307 | 120,126 | **1.02** short | STAGGER | 800000 | 837,886 | 858,188 | **0.98** short | STAGGER | 5000000 | 5099,399 | 5063,530 | **1.01** short | REPEATED | 600 | 1,797 | 1,673 | **1.07** short | REPEATED | 3000 | 36,409 | 18,124 | **2.01** short | REPEATED | 40000 | 68,712 | 64,305 | **1.07** short | REPEATED | 800000 | 748,089 | 676,263 | **1.11** short | REPEATED | 5000000 | 4509,726 | 4354,061 | **1.04** --- | --- | --- | --- | --- | --- int | RANDOM | 600 | 12,799 | 8,529 | **1.50** int | RANDOM | 3000 | 168,717 | 151,504 | **1.11** int | RANDOM | 40000 | 3053,482 | 2663,760 | **1.15** int | RANDOM | 800000 | 77058,078 | 68039,633 | **1.13** int | RANDOM | 5000000 | 553486,331 |483191,027 | **1.15** int | SHUFFLE | 600 | 7,091 | 5,090 | **1.39** int | SHUFFLE | 3000 | 57,823 | 37,976 | **1.52** int | SHUFFLE | 40000 | 982,797 | 804,192 | **1.22** int | SHUFFLE | 800000 | 20170,567 | 15124,860 | **1.33** int | SHUFFLE | 5000000 | 119944,448 |101314,175 | **1.18** int | STAGGER | 600 | 12,372 | 2,332 | **5.31** int | STAGGER | 3000 | 18,185 | 11,073 | **1.64** int | STAGGER | 40000 | 263,148 | 149,947 | **1.75** int | STAGGER | 800000 | 5206,958 | 3003,595 | **1.73** int | STAGGER | 5000000 | 33070,195 | 20196,353 | **1.64** int | REPEATED | 600 | 1,850 | 1,689 | **1.10** int | REPEATED | 3000 | 19,935 | 16,725 | **1.19** int | REPEATED | 40000 | 427,379 | 426,491 | **1.00** int | REPEATED | 800000 | 8780,449 | 8693,568 | **1.01** int | REPEATED | 5000000 | 59041,332 | 53085,389 | **1.11** --- | --- | --- | --- | --- | --- long | RANDOM | 600 | 12,759 | 8,332 | **1.53** long | RANDOM | 3000 | 170,641 | 153,686 | **1.11** long | RANDOM | 40000 | 3102,722 | 2702,462 | **1.15** long | RANDOM | 800000 | 76062,436 | 68565,859 | **1.11** long | RANDOM | 5000000 | 550540,619 | 488863,464 | **1.13** long | SHUFFLE | 600 | 7,482 | 5,153 | **1.45** long | SHUFFLE | 3000 | 53,436 | 39,168 | **1.36** long | SHUFFLE | 40000 | 980,789 | 803,654 | **1.22** long | SHUFFLE | 800000 | 20833,103 | 15763,843 | **1.32** long | SHUFFLE | 5000000 | 122366,475 | 104073,072 | **1.18** long | STAGGER | 600 | 12,709 | 2,299 | **5.53** long | STAGGER | 3000 | 19,001 | 11,054 | **1.72** long | STAGGER | 40000 | 275,147 | 165,269 | **1.66** long | STAGGER | 800000 | 5466,681 | 3912,351 | **1.40** long | STAGGER | 5000000 | 37297,708 | 29582,068 | **1.26** long | REPEATED | 600 | 2,107 | 1,681 | **1.25** long | REPEATED | 3000 | 16,612 | 9,562 | **1.74** long | REPEATED | 40000 | 426,694 | 421,148 | **1.01** long | REPEATED | 800000 | 8904,279 | 8561,931 | **1.04** long | REPEATED | 5000000 | 60695,788 | 54597,570 | **1.11** --- | --- | --- | --- | --- | --- float | RANDOM | 600 | 12,991 | 9,693 | **1.34** float | RANDOM | 3000 | 175,275 | 167,552 | **1.05** float | RANDOM | 40000 | 3138,437 | 2962,572 | **1.06** float | RANDOM | 800000 | 79635,198 | 75467,573 | **1.06** float | RANDOM | 5000000 | 572424,359 | 536613,819 | **1.07** float | SHUFFLE | 600 | 7,568 | 6,270 | **1.21** float | SHUFFLE | 3000 | 54,735 | 43,874 | **1.25** float | SHUFFLE | 40000 | 992,473 | 912,560 | **1.09** float | SHUFFLE | 800000 | 20273,495 | 17291,888 | **1.17** float | SHUFFLE | 5000000 | 120219,159 | 113983,042 | **1.05** float | STAGGER | 600 | 13,936 | 2,911 | **4.79** float | STAGGER | 3000 | 23,105 | 13,149 | **1.76** float | STAGGER | 40000 | 307,735 | 179,749 | **1.71** float | STAGGER | 800000 | 22328,783 | 3838,253 | **5.82** float | STAGGER | 5000000 | 143354,475 | 27434,381 | **5.23** float | REPEATED | 600 | 2,952 | 2,551 | **1.16** float | REPEATED | 3000 | 41,605 | 16,208 | **2.57** float | REPEATED | 40000 | 650,424 | 530,244 | **1.23** float | REPEATED | 800000 | 13124,335 | 11077,583 | **1.18** float | REPEATED | 5000000 | 85949,114 | 64994,047 | **1.32** --- | --- | --- | --- | --- | --- double | RANDOM | 600 | 13,226 | 9,674 | **1.37** double | RANDOM | 3000 | 174,235 | 168,003 | **1.04** double | RANDOM | 40000 | 3143,176 | 2969,988 | **1.06** double | RANDOM | 800000 | 80122,032 | 75624,728 | **1.06** double | RANDOM | 5000000 | 574170,519 | 541634,681 | **1.06** double | SHUFFLE | 600 | 7,350 | 6,258 | **1.17** double | SHUFFLE | 3000 | 54,996 | 47,801 | **1.15** double | SHUFFLE | 40000 | 997,654 | 910,188 | **1.10** double | SHUFFLE | 800000 | 20885,588 | 17842,091 | **1.17** double | SHUFFLE | 5000000 | 124954,149 | 117951,053 | **1.06** double | STAGGER | 600 | 13,905 | 3,104 | **4.48** double | STAGGER | 3000 | 24,836 | 14,530 | **1.71** double | STAGGER | 40000 | 315,874 | 208,873 | **1.51** double | STAGGER | 800000 | 7174,689 | 4755,320 | **1.51** double | STAGGER | 5000000 | 48635,918 | 34536,380 | **1.41** double | REPEATED | 600 | 2,963 | 2,577 | **1.15** double | REPEATED | 3000 | 29,148 | 16,343 | **1.78** double | REPEATED | 40000 | 634,175 | 525,211 | **1.21** double | REPEATED | 800000 | 13132,082 | 11342,063 | **1.16** double | REPEATED | 5000000 | 88391,737 | 67412,676 | **1.31** **Parallel sorting** Benchmark | Data Type | Array Size | Baseline (us/op) | New version (us/op) | Speedup -- | -- | -- | -- | -- | -- int | RANDOM | 600 | 12,794 | 8,505 | **1.50** int | RANDOM | 3000 | 168,675 | 151,334 | **1.11** int | RANDOM | 40000 | 987,834 | 425,065 | **2.32** int | RANDOM | 800000 | 19055,172 | 6019,487 | **3.17** int | RANDOM | 5000000 | 138748,345 | 37177,898 | **3.73** int | SHUFFLE | 600 | 7,072 | 5,122 | **1.38** int | SHUFFLE | 3000 | 55,693 | 39,086 | **1.42** int | SHUFFLE | 40000 | 448,901 | 210,483 | **2.13** int | SHUFFLE | 800000 | 7086,518 | 1789,933 | **3.96** int | SHUFFLE | 5000000 | 33432,965 | 17881,627 | **1.87** int | STAGGER | 600 | 12,467 | 2,348 | **5.31** int | STAGGER | 3000 | 18,100 | 11,108 | **1.63** int | STAGGER | 40000 | 185,856 | 91,566 | **2.03** int | STAGGER | 800000 | 4237,095 | 1092,863 | **3.88** int | STAGGER | 5000000 | 91703,510 | 9672,080 | **9.48** int | REPEATED | 600 | 2,039 | 1,693 | **1.20** int | REPEATED | 3000 | 19,928 | 16,955 | **1.18** int | REPEATED | 40000 | 435,095 | 179,503 | **2.42** int | REPEATED | 800000 | 8667,204 | 2280,028 | **3.80** int | REPEATED | 5000000 | 46503,601 | 16295,285 | **2.85** --- | --- | --- | --- | --- | --- long | RANDOM | 600 | 12,683 | 8,324 | **1.52** long | RANDOM | 3000 | 170,779 | 151,285 | **1.13** long | RANDOM | 40000 | 1049,755 | 517,177 | **2.03** long | RANDOM | 800000 | 19114,558 | 8186,756 | **2.33** long | RANDOM | 5000000 | 136592,625 | 50122,188 | **2.73** long | SHUFFLE | 600 | 7,507 | 5,317 | **1.41** long | SHUFFLE | 3000 | 53,452 | 38,660 | **1.38** long | SHUFFLE | 40000 | 456,876 | 235,079 | **1.94** long | SHUFFLE | 800000 | 7104,711 | 3026,515 | **2.35** long | SHUFFLE | 5000000 | 36215,812 | 31943,545 | **1.13** long | STAGGER | 600 | 12,726 | 2,314 | **5.50** long | STAGGER | 3000 | 19,204 | 11,076 | **1.73** long | STAGGER | 40000 | 188,118 | 117,579 | **1.60** long | STAGGER | 800000 | 15883,497 | 1604,405 | **9.90** long | STAGGER | 5000000 | 30772,348 | 19823,240 | **1.55** long | REPEATED | 600 | 1,958 | 1,681 | **1.16** long | REPEATED | 3000 | 19,457 | 9,782 | **1.99** long | REPEATED | 40000 | 447,956 | 201,816 | **2.22** long | REPEATED | 800000 | 8709,853 | 2817,039 | **3.09** long | REPEATED | 5000000 | 47701,874 | 27042,182 | **1.76** --- | --- | --- | --- | --- | --- float | RANDOM | 600 | 12,957 | 9,760 | **1.33** float | RANDOM | 3000 | 174,859 | 168,011 | **1.04** float | RANDOM | 40000 | 1088,187 | 593,148 | **1.83** float | RANDOM | 800000 | 19946,194 | 8786,492 | **2.27** float | RANDOM | 5000000 | 143259,840 | 52053,455 | **2.75** float | SHUFFLE | 600 | 7,524 | 6,261 | **1.20** float | SHUFFLE | 3000 | 55,272 | 49,120 | **1.13** float | SHUFFLE | 40000 | 475,746 | 263,484 | **1.81** float | SHUFFLE | 800000 | 7241,135 | 2634,484 | **2.75** float | SHUFFLE | 5000000 | 35411,419 | 21196,612 | **1.67** float | STAGGER | 600 | 13,950 | 2,942 | **4.74** float | STAGGER | 3000 | 23,098 | 13,183 | **1.75** float | STAGGER | 40000 | 237,012 | 128,761 | **1.84** float | STAGGER | 800000 | 4591,090 | 1751,410 | **2.62** float | STAGGER | 5000000 | 32436,076 | 14446,905 | **2.25** float | REPEATED | 600 | 2,885 | 2,549 | **1.13** float | REPEATED | 3000 | 40,168 | 16,392 | **2.45** float | REPEATED | 40000 | 660,494 | 237,183 | **2.78** float | REPEATED | 800000 | 12950,842 | 3223,258 | **4.02** float | REPEATED | 5000000 | 72413,630 | 22049,544 | **3.28** --- | --- | --- | --- | --- | --- double | RANDOM | 600 | 13,141 | 9,722 | **1.35** double | RANDOM | 3000 | 173,583 | 167,573 | **1.04** double | RANDOM | 40000 | 1094,277 | 693,851 | **1.58** double | RANDOM | 800000 | 20258,598 | 11422,502 | **1.77** double | RANDOM | 5000000 | 149441,199 | 66982,876 | **2.23** double | SHUFFLE | 600 | 7,350 | 6,198 | **1.19** double | SHUFFLE | 3000 | 54,795 | 48,204 | **1.14** double | SHUFFLE | 40000 | 486,034 | 292,594 | **1.66** double | SHUFFLE | 800000 | 7493,063 | 3994,888 | **1.88** double | SHUFFLE | 5000000 | 38662,773 | 38459,203 | **1.01** double | STAGGER | 600 | 14,004 | 3,095 | **4.52** double | STAGGER | 3000 | 24,786 | 14,442 | **1.72** double | STAGGER | 40000 | 265,910 | 166,051 | **1.60** double | STAGGER | 800000 | 5161,371 | 2329,184 | **2.22** double | STAGGER | 5000000 | 37595,716 | 25195,029 | **1.49** double | REPEATED | 600 | 2,958 | 2,575 | **1.15** double | REPEATED | 3000 | 24,794 | 16,353 | **1.52** double | REPEATED | 40000 | 645,872 | 257,590 | **2.51** double | REPEATED | 800000 | 13011,569 | 3817,908 | **3.41** double | REPEATED | 5000000 | 73640,263 | 33488,503 | **2.20** ------------- PR Comment: https://git.openjdk.org/jdk/pull/27411#issuecomment-3316224966 PR Comment: https://git.openjdk.org/jdk/pull/27411#issuecomment-3316226941
