RFR: JDK-8320448 Accelerate IndexOf using AVX2 [v7]

[Jatin Bhateja]

On Thu, 11 Jan 2024 23:06:32 GMT, Scott Gibbons <sgibbons at openjdk.org> wrote:

>> Re-write the IndexOf code without the use of the pcmpestri instruction, only using AVX2 instructions.  This change accelerates String.IndexOf on average 1.3x for AVX2.  The benchmark numbers:
>> 
>> 
>> Benchmark	                                               Score		Latest		
>> StringIndexOf.advancedWithMediumSub   343.573		317.934		0.925375393x
>> StringIndexOf.advancedWithShortSub1	  1039.081		1053.96		1.014319384x
>> StringIndexOf.advancedWithShortSub2	      55.828		110.541		1.980027943x
>> StringIndexOf.constantPattern	                9.361		11.906		1.271872663x
>> StringIndexOf.searchCharLongSuccess	        4.216		4.218		1.000474383x
>> StringIndexOf.searchCharMediumSuccess	3.133		3.216		1.02649218x
>> StringIndexOf.searchCharShortSuccess	3.76		        3.761		1.000265957x
>> StringIndexOf.success	                                9.186		9.713		1.057369911x
>> StringIndexOf.successBig	                      14.341		46.343		3.231504079x
>> StringIndexOfChar.latin1_AVX2_String	  6220.918		12154.52		1.953814533x
>> StringIndexOfChar.latin1_AVX2_char	  5503.556		5540.044		1.006629895x
>> StringIndexOfChar.latin1_SSE4_String	  6978.854		6818.689		0.977049957x
>> StringIndexOfChar.latin1_SSE4_char	  5657.499		5474.624		0.967675646x
>> StringIndexOfChar.latin1_Short_String	  7132.541		6863.359		0.962260014x
>> StringIndexOfChar.latin1_Short_char	16013.389	      16162.437		1.009307711x
>> StringIndexOfChar.latin1_mixed_String	  7386.123	      14771.622		1.999915517x
>> StringIndexOfChar.latin1_mixed_char	  9901.671		9782.245		0.987938803
>
> Scott Gibbons has updated the pull request with a new target base due to a merge or a rebase. The pull request now contains 22 commits:
> 
>  - Merge branch 'openjdk:master' into indexof
>  - Merge branch 'openjdk:master' into indexof
>  - Addressing review comments.
>  - Fix for JDK-8321599
>  - Support UU IndexOf
>  - Only use optimization when EnableX86ECoreOpts is true
>  - Fix whitespace
>  - Merge branch 'openjdk:master' into indexof
>  - Comments; added exhaustive-ish test
>  - Subtracting 0x10 twice.
>  - ... and 12 more: https://git.openjdk.org/jdk/compare/8e12053e...3e58d0c2

src/hotspot/cpu/x86/stubGenerator_x86_64_string.cpp line 197:

> 195:     __ bind(L_small_string);
> 196:     __ cmpq(r15, 0x20);
> 197:     __ ja(L_small_string2);

ja should replaced by jg.

src/hotspot/cpu/x86/stubGenerator_x86_64_string.cpp line 1526:

> 1524:     __ movq(rdx, r8);
> 1525:     __ movq(rcx, r9);
> 1526: #endif

Can we spill them into XXMs, to save costly stack operations.

src/hotspot/cpu/x86/stubGenerator_x86_64_string.cpp line 1545:

> 1543:     //   return 0;
> 1544:     // }
> 1545:     __ movq(r12, rcx);

Kindly use meaningful variable and label names. It will ease the review process and maintenance.

src/hotspot/cpu/x86/stubGenerator_x86_64_string.cpp line 1551:

> 1549:     __ movq(r15, rsi);
> 1550:     __ movq(r11, rdi);
> 1551:     __ cmpq(rsi, 0x20);

All comparisons are with 32 bit int value , cmpq -> cmpl, may save emitting REX encoding prefix (no need for setting REX.W).

src/hotspot/cpu/x86/stubGenerator_x86_64_string.cpp line 1552:

> 1550:     __ movq(r11, rdi);
> 1551:     __ cmpq(rsi, 0x20);
> 1552:     __ jb(L_small_string);

All the comparisons against needle length are signed integer comparisons, so jb should be replaced by jl

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

> 1204: 
> 1205:   Node* result = nullptr;
> 1206:   bool do_intrinsic =

Name change suggestion: do_intrinsic -> call_opt_stub

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

> 1227:   } else {
> 1228:     result = make_indexOf_node(src_start, src_count, tgt_start, tgt_count,
> 1229:                                result_rgn, result_phi, ae);

Existing routines emits IR to handle following special cases.

tgt_cnt > src_cnt return -1
tgt_cnt == 0 return 0.

Should we not be preserving those check before calling stub ?

As of now these checks are part of stub and doing them in JIT code will save call overhead.

src/hotspot/share/opto/runtime.cpp line 1347:

> 1345:   fields[argp++] = TypeInt::INT;        // needle length
> 1346:   fields[argp++] = TypePtr::NOTNULL;    // haystack array
> 1347:   fields[argp++] = TypeInt::INT;        // haystack length

Do we need to swap the comments? first two arguments corresponds to value (haystack) as per java side intrinsic signature.
https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/lang/StringLatin1.java#L348

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

PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1453304911
PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1453332647
PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1453333045
PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1453333555
PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1453333878
PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1453338427
PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1453338718
PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1453329079