[aarch64-port-dev ] RFR: 8187472 - AARCH64: array_equals intrinsic doesn't use prefetch for large arrays

[Dmitrij Pochepko]

Thank you for review


On 06.04.2018 10:00, Dmitry Samersoff wrote:
> Dmitrij,
>
> This version looks good to me.
>
> -Dmitry\S
>
> On 16/03/2018 19:21, Dmitrij Pochepko wrote:
>> Hi Andrew, all,
>>
>> I modified patch according to your comments.
>>
>> First, regarding size statistics: I looked into string size statistics
>> which was measured for JEP254: Compact Strings
>> (http://docs.huihoo.com/javaone/2015/CON5483-Compact-Strings-A-Memory-Efficient-Internal-Representation-for-Strings.pdf).
>> Conclusions are that 75% of strings <= 32 symbols, so we can take this
>> number into account. This also means that changing string equals code to
>> be capable of prefetching(and thus adding branch for that) is not
>> practical. Arrays are another story. So, I split array equals and string
>> equals.
>>
>> String equals remains basically unchanged(the only noticeable change is
>> that I removed size calculations for UTF strings (asr to convert
>> length-in-bytes into length-in-characters, and than converting it back
>> via lsr). It save 2 instructions for this code path: about 5%
>> improvement on small sizes.
>>
>> Array equals was completely re-written.
>>
>> For array equals I have 2 algorithms, controlled by vm option:
>> UseSimpleArrayEquals. First algorithm(simple one) is basically the same
>> as original one with slightly another branch logic. It seems like Cortex
>> A7* series prefer shorter code, which fits better for speculative
>> execution. All other CPUs I was able to check(Cortex A53 and Cavium h/w)
>> prefer algorithm with large loop and possible prefetching.
>>
>> Regarding your comment about addresses at the end of memory page: you're
>> right. It is indeed possible in theory to use this code for some
>> substring, however, due to the nature of algorithm for array equals(it
>> reads array length from array header directly and then jump to first
>> array element), memory access will always be 8-byte aligned, then it's
>> safe to use 8-byte loads for array tails. So, I believe this issue is
>> now naturally resolved, since I left string equals logic unchanged.
>>
>>
>> Now, benchmarks:
>>
>> I modified benchmark to have better measurements accuracy by increasing
>> amount of data processed in each iteration
>> (http://cr.openjdk.java.net/~dpochepk/8187472/ArrayAltEquals.java) and
>> has following improvement average numbers for array equals:
>>
>> Cavium "ThunderX 2":
>> length 1..8: 10-20%
>> length 9..16: 1%
>> length 17..32: 5-10%
>> large(512+): almost 2 times
>>
>> Cavium "Thunder X":
>> length 1..8: 1%
>> length 9..16: 2-3%
>> length 17..32: 5%
>> large arrays(512+): up to 5 times
>>
>> Cortex A53 (R-Pi):
>> all ranges are about 5% average (note: large results dispersion (about
>> 10%) on R-PI)
>>
>> Cortex A73:
>> basically no changes because implementation is almost the same (better
>> by about 0.5% average, but dispersion is about 4%, so it's not a
>> statistically significant result)
>>
>>
>> More detailed benchmarking results can be found here:
>> http://cr.openjdk.java.net/~dpochepk/8187472/array_equals_total.xls
>>
>> updated webrev: http://cr.openjdk.java.net/~dpochepk/8187472/webrev.08/
>>
>> Testing: passed jtreg hotspot tests on AArch64 fastdebug build. no new
>> failures found in comparison with non-patched build.
>>
>> I also additionally used "brute-force" test which checks all array
>> equality combinations for any given length ranges:
>> http://cr.openjdk.java.net/~dpochepk/8187472/ArrayEqTest.java
>>
>>
>> Thanks,
>>
>> Dmitrij
>>
>> On 08.02.2018 13:11, Andrew Haley wrote:
>>> On 07/02/18 19:39, Dmitrij Pochepko wrote:
>>>> In general, this patch changes very short arrays handling(performing
>>>> 8-byte read instead of few smaller reads, using the fact of 8-byte
>>>> alignment) and jumping into stub with large 64-byte read loop for larger
>>>> arrays).
>>>>
>>>> Measurements(measured array length 7,64,128,256,512,1024,100000.
>>>> Improvement in %. 80% improvement means that new version is 80% faster,
>>>> i.e. 5 times.):
>>>>
>>>>
>>>> ThunderX: 2%, -4%, 0%, 2%, 32%, 55%, 80%
>>>>
>>>> ThunderX2: 0%, -3%, 17%, 19%, 29%, 31%, 47%
>>>>
>>>> Cortex A53 at 533MHz: 8%, -1%, -2%, 4%, 6%, 5%, 3%
>>>>
>>>> Cortex A73 at 903MHz: 8%, -3%, 0%, 7%, 8%, 9%, 8%
>>>>
>>>> Note: medium sizes are a bit slower because of additional branch
>>>> added(which checks size and jumps to stub).
>>> This indentation is messed up:
>>>
>>> @@ -5201,40 +5217,23 @@
>>>      // length == 4.
>>>      if (log_elem_size > 0)
>>>        lsl(cnt1, cnt1, log_elem_size);
>>> -  ldr(tmp1, Address(a1, cnt1));
>>> -  ldr(tmp2, Address(a2, cnt1));
>>> +    ldr(tmp1, Address(a1, cnt1));
>>> +    ldr(tmp2, Address(a2, cnt1));
>>>
>>> I'm not convinced that this works correctly if passed the address of a
>>> pair
>>> of arrays at the end of a page.  Maybe it isn't used on sub-arrays today
>>> in HotSpot, but one day it might be.
>>>
>>> It pessimizes a very common case of strings, those of about 32
>>> characters.
>>> Please think again.  Please also think about strings that are long enough
>>> for the SIMD loop but differ in their early substrings.
>>>
>