RFR: 8319577: x86_64 AVX2 intrinsics for Arrays.sort methods (int, float arrays) [v2]

Tue Nov 28 13:14:13 UTC 2023

On Sat, 18 Nov 2023 01:21:09 GMT, Srinivas Vamsi Parasa <duke at openjdk.org> wrote:

>> The goal is to develop faster sort routines for x86_64 CPUs by taking advantage of AVX2 instructions. This enhancement provides an order of magnitude speedup for Arrays.sort() using int, long, float and double arrays.
>> 
>> For serial sort on random data, this PR shows upto ~7.5x improvement for 32-bit datatypes (int, float) on Intel TigerLake machine as shown in the performance data below.
>> 
>> For parallel sort on random data, this PR shows upto ~3.4x for 32-bit datatypes (int, float) as shown below.
>> 
>> **Note:** This PR also improves the performance of AVX512 sort by upto 35%.
>> 
>> <html xmlns:v="urn:schemas-microsoft-com:vml"
>> xmlns:o="urn:schemas-microsoft-com:office:office"
>> xmlns:x="urn:schemas-microsoft-com:office:excel"
>> xmlns="http://www.w3.org/TR/REC-html40">
>> 
>> <head>
>> 
>> <meta name=ProgId content=Excel.Sheet>
>> <meta name=Generator content="Microsoft Excel 15">
>> <link id=Main-File rel=Main-File
>> href="file:///C:/Users/sparasa/AppData/Local/Temp/msohtmlclip1/01/clip.htm">
>> <link rel=File-List
>> href="file:///C:/Users/sparasa/AppData/Local/Temp/msohtmlclip1/01/clip_filelist.xml">
>> 
>> 
>> </head>
>> 
>> <body link="#0563C1" vlink="#954F72">
>> 
>> 
>> 
>> Benchmark (Serial Sort) | Size | Baseline      (us/op) | AVX2     (us/op) | Speedup
>> -- | -- | -- | -- | --
>> ArraysSort.intSort | 10 | 0.034 | 0.029 | 1.2
>> ArraysSort.intSort | 25 | 0.088 | 0.044 | 2.0
>> ArraysSort.intSort | 50 | 0.239 | 0.159 | 1.5
>> ArraysSort.intSort | 75 | 0.417 | 0.27 | 1.5
>> ArraysSort.intSort | 100 | 0.572 | 0.265 | 2.2
>> ArraysSort.intSort | 1000 | 10.098 | 4.282 | 2.4
>> ArraysSort.intSort | 10000 | 330.065 | 43.383 | 7.6
>> ArraysSort.intSort | 100000 | 4099.527 | 778.943 | 5.3
>> ArraysSort.intSort | 1000000 | 49150.16 | 9634.335 | 5.1
>> ArraysSort.floatSort | 10 | 0.045 | 0.043 | 1.0
>> ArraysSort.floatSort | 25 | 0.105 | 0.073 | 1.4
>> ArraysSort.floatSort | 50 | 0.278 | 0.216 | 1.3
>> ArraysSort.floatSort | 75 | 0.476 | 0.241 | 2.0
>> ArraysSort.floatSort | 100 | 0.583 | 0.313 | 1.9
>> ArraysSort.floatSort | 1000 | 10.182 | 4.329 | 2.4
>> ArraysSort.floatSort | 10000 | 323.136 | 57.175 | 5.7
>> ArraysSort.floatSort | 100000 | 4299.519 | 862.63 | 5.0
>> ArraysSort.floatSort | 1000000 | 50889.4 | 10972.19 | 4.6
>> 
>> </body>
>> 
>> </html>
>> 
>> <html xmlns:v="urn:schemas-microsoft-com:vml"
>> xmlns:o="urn:schemas-microsoft-com:office:office"
>> xmlns:x="urn:schemas-microsoft-com:office:excel"
>> xmlns="http://www.w3.org/TR/REC-html40">
>> 
>> <head>
>> 
>> <meta name=ProgId cont...
>
> Srinivas Vamsi Parasa has updated the pull request with a new target base due to a merge or a rebase. The incremental webrev excludes the unrelated changes brought in by the merge/rebase. The pull request contains 11 additional commits since the last revision:
> 
>  - Disable AVX2 sort for 64-bit types
>  - Merge branch 'master' of https://git.openjdk.java.net/jdk into simdsort
>  - fix jcheck failures due to windows encoding
>  - fix carriage return and change insertion sort thresholds
>  - fix formatting and white spaces
>  - cleanup unused code
>  - fix insertion sort thresholds
>  - add insertion sort
>  - fix headers
>  - revert to xss-common-qsort
>  - ... and 1 more: https://git.openjdk.org/jdk/compare/a21d12ff...08307b6a

src/hotspot/share/opto/library_call.cpp line 5391:

> 5389:     BasicType bt = elem_type->basic_type();
> 5390:     // Disable the intrinsic for 64-bit types with AVX2
> 5391:     if ((bt == T_LONG || bt == T_DOUBLE) && UseAVX == 2) {

You can directly use convenience routine _is_double_word_type_

src/hotspot/share/opto/library_call.cpp line 5448:

> 5446:   BasicType bt = elem_type->basic_type();
> 5447:   // Disable the intrinsic for 64-bit types with AVX2
> 5448:   if ((bt == T_LONG || bt == T_DOUBLE) && UseAVX == 2) {

Same as above.

-------------

PR Review Comment: https://git.openjdk.org/jdk/pull/16534#discussion_r1407677897
PR Review Comment: https://git.openjdk.org/jdk/pull/16534#discussion_r1407678192