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 576:

> 574:       broadcast_additional_needles(false, 0 /* unknown */, NUMBER_OF_NEEDLE_BYTES_TO_COMPARE, needle, needleLen, rTmp3,
> 575:                                    isUU, isUL, _masm);
> 576: 

Good to pass output xmm registers to this method.

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

> 585:       //  firstNeedleCompare has address of second element of needle
> 586:       //  compLen has length of comparison to do
> 587: 

This is not clear. firstNeedleCompare gets needle + NUMBER_OF_NEEDLE_BYTES_TO_COMPARE - 1 which is not necessarily the second element of needle. If it helps let us fix the NUMBER_OF_NEEDLE_BYTES_TO_COMPARE to 3 and have comments and code versus that only.

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

> 588:       compare_haystack_to_needle(false, 0, NUMBER_OF_NEEDLE_BYTES_TO_COMPARE, L_returnRBP, haystack, isU,
> 589:                                  DO_EARLY_BAILOUT, mask, needleLen, rTmp3, _masm);
> 590: 

It is better to pass the broadcasted xmm registers to compare_haystack_to_nedle. Basically pass input, output, and temps to all the methods.

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

> 637:     __ movl(rax, r8);
> 638:     __ subq(rcx, rbx);
> 639:     __ addq(rcx, rax);

This could be:
    __ subq(rcx, rbx);
    __ addq(rcx, r8);

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

> 645:     __ cmpq(r11, r10);
> 646:     __ movq(rbp, -1);
> 647:     __ cmovq(Assembler::belowEqual, rbp, r11);

This could be directly computed in rax:
    __ movq(rax, -1);
    __ cmovq(Assembler::belowEqual, rax, r11);
Also is it possible to not do cmov on some paths? It is an expensive operation.

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

> 1008: static void broadcast_additional_needles(bool sizeKnown, int size, int bytesToCompare, Register needle,
> 1009:                                          Register needleLen, Register rTmp, bool isUU, bool isUL,
> 1010:                                          MacroAssembler *_masm) {

Good to add output XMM registers to the parameter list.

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

> 1038:         __ vpbroadcastb(byte_1, Address(needle, 1), Assembler::AVX_256bit);
> 1039:       }
> 1040:     }

It will be good to have a function which broadcasts a needle element from a given offset into a vector register.
That function could take (needle address, offset, outout vector register, temps).
Such a function could then be called twice from here and from main function for offset 0.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1593046499
PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1593057834
PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1593045710
PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1592989197
PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1592992225
PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1593023349
PR Review Comment: https://git.openjdk.org/jdk/pull/16753#discussion_r1593006539