RFR: 8320448: Accelerate IndexOf using AVX2 [v19]

[Sandhya Viswanathan]

On Sat, 4 May 2024 19:35:21 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 incrementally with one additional commit since the last revision:
> 
>   Rearrange; add lambdas for clarity

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

> 1081: // haystack - the address of the first byte of the haystack
> 1082: // hsLen - the sizeof the haystack
> 1083: // isU - true if argument encoding is either UU or UL

We need to list needleLen here as well?

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

> 1094:                                            MacroAssembler *_masm) {
> 1095: 
> 1096:   assert_different_registers(eq_mask, haystack, needleLen, rTmp, hsLen, r10);

r10 kind of stands out here. You could say nMinusK in this assert.
The assert following to this one is checking for nMinusK==r10 so that should suffice.
BTW, didn't see anything in the code below that needs nMinuxK to be r10.

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

> 1118: #define cmp_0 XMM_TMP3
> 1119: #undef cmp_k
> 1120: #define cmp_k XMM_TMP4

XMM_TMP4 is not reused so cmp_k could be declared as const. In general limiting undef/define pair only to reused registers would make the review easier.

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

> 1123: #undef lastMask
> 1124: 
> 1125:   int sizeIncr = isU ? 2 : 1;

sizeIncr and scale seems to be same, we could just use one of them in this function.

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

> 1176:     __ andq(eq_mask, lastMask);
> 1177:     if (needToSaveRCX) {
> 1178:       __ movdq(rcx, saveRCX);

movdq is an expensive instruction (about 3 cycle). If we have another gpr temporary available here for shiftVal, then we dont need to do save/restore rcx.

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

> 1181: 
> 1182:     if (bytesToCompare > 2) {
> 1183:       if (size > (isU ? 4 : 2)) {

this and other usages could be simplified to: size > 2 * scale

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

PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1599201163
PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1599203881
PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1599211645
PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1599202848
PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1599242323
PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1599228299