[9] RFR(S): 6941938: Improve array equals intrinsic on SPARC

Tobias Hartmann tobias.hartmann at oracle.com
Tue Apr 19 17:13:05 UTC 2016

Thanks, Vladimir!

On 19.04.2016 18:06, Vladimir Kozlov wrote:
> Very good. Go with basic. We can do SPU special improvements later if needed.

Okay, I'll push the basic version.

For reference, here are the results on a SPARC T4:

> "I also noticed that we don't use prefetching for arraycopy and other intrinsics on SPARC."
> We do have arraycopy code for it but by default we don't use it:
>   product(uintx,  ArraycopySrcPrefetchDistance, 0,
>   product(uintx,  ArraycopyDstPrefetchDistance, 0,
> Experiments back then did not show improvement on JBB benchmarks but some workloads may have benefit. that is why we keep the code.

Right but currently it's not possible to enable prefetching, because "ArraycopySrcPrefetchDistanceConstraintFunc" enforces the prefetch distance to be 0:

java -XX:ArraycopySrcPrefetchDistance=42 -version
ArraycopySrcPrefetchDistance (42) must be 0
Error: Could not create the Java Virtual Machine.
Error: A fatal exception has occurred. Program will exit


> Thanks,
> Vladimir
> On 4/19/16 5:35 AM, Tobias Hartmann wrote:
>> Hi,
>> please review the following enhancement:
>> https://bugs.openjdk.java.net/browse/JDK-6941938
>> MacroAssembler::array_equals() currently emits a 4-byte array comparison loop on SPARC but we can do a 8-byte comparison if the array addresses are doubleword aligned. The intrinsic is used for byte/char Arrays.equals() and String.equals().
>> I added the method MacroAssembler::array_equals_loop() that loads and compares array elements of size 'byte_width' until the elements are not equal or we reached the end of the arrays. Instead of first comparing trailing characters if the array sizes are not a multiple of 'byte_width', we simply read over the end of the arrays, bail out and compare the remaining elements by shifting out the garbage bits.
>> We use a width of 8 bytes if the array addresses are doubleword aligned, or fall back to 4 bytes if they are only word aligned (which is always guaranteed). I also refactored MacroAssembler::string_compare() to use load_sized_value().
>> Performance evaluation showed an improvement of up to 65% with the microbenchmarks on a SPARC M7. I used a slightly modified version of the "EqualsBench" [1] from Aleksey's compact string microbenchmark suite [2] that exercises the intrinsic on two equal/unequal char/byte arrays. Larger benchmarks (SPECjbb, SPECjvm) show no significant difference in performance.
>> I evaluated the following three versions of the patch.
>> -- Basic --
>> http://cr.openjdk.java.net/~thartmann/6941938/webrev.basic/
>> The basic version implements the algorithm described above. Microbenchmark evaluation [3] shows a great improvement for all array sizes except for size 16 where the performance suddenly drops: http://cr.openjdk.java.net/~thartmann/6941938/benchmarks/char_equal_basic.png
>> I figured out that this is due to caching. It seems that with 8 byte steps, the processor notices later in the loop that we are going to access the subsequent array elements, causing the reads to trigger costly cache misses that degrade overall performance. With 4 byte reads, fetching is triggered earlier and the subsequent reads are very fast. I executed the same benchmark on a SPARC T4 and there is no performance problem. Version "prefetching" tries to improve this.
>> There is also a regression for sizes 1 and 2 if the arrays are not equal because the baseline version explicitly checks those sizes before the loop: http://cr.openjdk.java.net/~thartmann/6941938/benchmarks/char_unequal_basic.png
>> Version "small" tries to improve this.
>> -- Prefetching --
>> http://cr.openjdk.java.net/~thartmann/6941938/webrev.prefetch/
>> This version adds explicit prefetching before the loop to make sure the first array elements are always in the cache. This helps to avoid the cache misses with 16 bytes: http://cr.openjdk.java.net/~thartmann/6941938/benchmarks/byte_unequal_prefetch.png
>> However, prefetching negatively affects overall performance in the other cases (see [4]). Zoltan suggested that this may be because software prefetching temporarily disables or affects the hardware prefetcher. I also experimented with adding incremental prefetching to the loop body but this does not improve performance.
>> -- Small --
>> http://cr.openjdk.java.net/~thartmann/6941938/webrev.small/
>> This version includes special handling of arrays of size <= 4 by emitting a single load without a loop and the corresponding checks. Performance evaluation showed that this does not pay off because the additional check induces an overhead for small arrays > 4 elements (see sheet "small arrays").
>> The numbers can be found here:
>> http://cr.openjdk.java.net/~thartmann/6941938/benchmarks/microbenchmark_results_6941938.xlsx
>> I would prefer to use the basic version because explicit prefetching is highly dependent on the processor and behavior may change. I also noticed that we don't use prefetching for arraycopy and other intrinsics on SPARC.
>> What do you think?
>> Tested with all hotspot tests on RBT (-Xmixed/-Xcomp). Links are attached to the bug.
>> Thanks,
>> Tobias
>> [1] https://bugs.openjdk.java.net/secure/attachment/58697/EqualsBench.java
>> [2] http://cr.openjdk.java.net/~shade/density/string-density-bench.zip
>> [3] Microbenchmark results for the "basic" implementation
>> http://cr.openjdk.java.net/~thartmann/6941938/benchmarks/byte_equal_basic.png
>> http://cr.openjdk.java.net/~thartmann/6941938/benchmarks/byte_unequal_basic.png
>> http://cr.openjdk.java.net/~thartmann/6941938/benchmarks/char_unequal_basic.png
>> http://cr.openjdk.java.net/~thartmann/6941938/benchmarks/char_equal_basic.png
>> [4] Microbenchmark results for the "prefetching" implementation
>> http://cr.openjdk.java.net/~thartmann/6941938/benchmarks/byte_equal_prefetch.png
>> http://cr.openjdk.java.net/~thartmann/6941938/benchmarks/byte_unequal_prefetch.png
>> http://cr.openjdk.java.net/~thartmann/6941938/benchmarks/char_equal_prefetch.png
>> http://cr.openjdk.java.net/~thartmann/6941938/benchmarks/char_unequal_prefetch.png

More information about the hotspot-compiler-dev mailing list