Eliminate array copy

Radosław Smogura mail at smogura.eu
Wed Nov 16 16:09:01 UTC 2016

Dear all,

I hope you are well.

I would like to share one brave experiment. It was driven by observation that in many places, like StringBuilder, the backing array is not used after final toString call. As it’s bigger or equal to destination it would be great to pass just it with correct size, but this affects heap and other places where source can be referenced.

To solve above problems I was thinking about following approach (prototyped in [1], [2]):

If array copy meets following criteria:
* the source and destination offsets are 0,
* the source is not used after copy,
* the destination size and copy size are equal,
* both have same element types,
* both are arrays or primitives (technical assumption).

1. If source and destination sizes are same pass source.
2. Otherwise, if destination array could fit same aligned space like source - change source size.
3. Otherwise, if source is big enough, before reducing size, in remaining space put header of new array to fill gap.
4. Substitute destination with source, by inserting Phi after allocation outcome, in such a way that copy node still gets params from allocation.

As, the dummy array header is put before new size (I hope with proper mem bar), if GC thread would go through the heap after size change, it will see two arrays in place of one, otherwise it would move to next bytes after source array, in both cases it will reach next oop in a same way as source would not be changed. In parallel thread GC doesn’t build list of found oops sizes (am I right?), so there is no risk related to changing oop size. Calculating new locations and copying oops takes place at safe point, so at the time when heap is properly filled up.

To check source array usage, the escape analyse is used. All nodes referenced from fields referenced from source java objects are checked if those require memory from array copy (gives false positives when array copy is in loop).

The required escape state for source array is not to escape at all, as in other cases array could be assigned to some field, and referenced later.

There are JMH benchmarks [3], [4], showing 0%-6% improvement - expected improvement was 25%. 

Additionally, I did some tests with elimination of allocation and those gave 50% improvement, but eliminating allocation and copy together is more complicated, i.e. there can be nodes other than array copy taking control from initialiser (see Arrays.copyOf, Math.min(original.length, newLength) is passed as an argument to System.arraycopy).

I wonder if you would find a bit of time to take look at it and pass all pros and cons? 

And off topic, during work I made some assertions and performance changes to IGVN - [5].

Thanks in advance,
Radek Smogura

[1] Source branch  https://bitbucket.org/radoslaw_smogura/jdk-experiments-hotspot/branch/eliminate-array-copy
[2] Webrev         http://smogura.eu/webrevs/eliminate-array-copy-1/
[3] JMH output     http://smogura.eu/webrevs/eliminate-array-copy-1/eliminate_array_copy_20161116_tag_benchmarks_v2.txt
[4] JMH tests      https://bitbucket.org/radoslaw_smogura/eliminate-array-copy-jmh  
[5] IGVN additions https://bitbucket.org/radoslaw_smogura/jdk-experiments-hotspot/branch/ideal-graph-visualiser-various

More information about the hotspot-compiler-dev mailing list