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