RFR: 8266431: Dual-Pivot Quicksort improvements (Radix sort)
Vladimir Yaroslavskiy
duke at openjdk.org
Sun Sep 21 20:35:53 UTC 2025
On Sun, 21 Sep 2025 19:47:14 GMT, Vladimir Yaroslavskiy <duke at openjdk.org> 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
More information about the core-libs-dev
mailing list