RFR: 8189103 - AARCH64: optimize String indexOf intrinsic

[Dmitrij Pochepko]

Hi all,

please review patch for JDK-8189103: AARCH64: optimize String indexOf 
intrinsic

indexOf instrinsic initially had 6 different algorithms(selected 
depending on strings length): pattern length 1, 2, 3, 4, <generic linear 
search>, Boyer Moore algorithm.

This patch consists of few several improvement ideas:

1) minimally updated algorithms for pattern length 1,2,3,4, <generic 
linear search> by removing 1 unnecessary dependent instruction and 
moving 1 common instruction into common part for length 2,3,4, <generic 
linear search>. It slightly improves performance for these cases(about 1%).

2) large update of Boyer Moore algorithm implementation by increasing 
search table size from 128 to 256 to remove few branches for Latin1 
encoding cases and also improve performance for cases when Latin1 
symbols with values >128 are met. This patch also significantly improves 
search of Latin1 string inside UTF string by upgrading algorithm 
logic(the idea is to skip <pattern length> symbols in case pure UTF 
symbol is met in source string).

3) separate implementation for generic linear search is added(moved to 
stub). It requires more time for initialization, but is faster after 
initialization is done, which allows to improve performance for long strings

4) removed dead code in .ad file. LU case (search of UTF string inside 
Latin1 string) always return -1 and handled in java before calling this 
instrinsic


Benchmarking and results(used Cavium ThunderX (T88), Cavium ThunderX2 
(T99) and Cortex A73):

I created microbenchmark, which measures different pattern size search 
in different source size string: 
http://cr.openjdk.java.net/~dpochepk/8189103/IndexOfBench.java

Overall results:

- about same results for minimally updated algorithm paths

- large difference for Boyer Moore algorithm: up to x40 improvement for 
large string with variety of different characters

- significant difference for sizes affected by new linear search in 
stub: up to 30% improvement


Results matrix is large: 
http://cr.openjdk.java.net/~dpochepk/8189103/str_indexof_result.xls

Raw results: *.txt files in http://cr.openjdk.java.net/~dpochepk/8189103/


webrev: http://cr.openjdk.java.net/%7Edpochepk/8189103/webrev.01/

CR: https://bugs.openjdk.java.net/browse/JDK-8189103

Testing:

- run hotspot jtreg tests(compiler, runtime, gc) over patched release 
build and found no new failures.

- run additional "brute force" tests which checks all index combinations 
for specified lengths(takes much time to run): 
http://cr.openjdk.java.net/~dpochepk/8189103/IndexOfTest.java using both 
release and fastdebug builds
Thanks,

Dmitrij

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20180418/90609fe1/attachment.html>