Eliminate array copy

[Vladimir Kozlov]

Hi Radek,

Thank you for doing this experiment and sharing results with us. It is 
very impressive work.

We have several String construction related optimizations already which 
may offset improvement with your changes.

First is old optimization in C2 - strings concatenation, flag 
OptimizeStringConcat, which replaces sequence of StringBuilder calls 
with String object construction and population its char[] array with 
values from StringBuilder.append() calls.

And new more general changes in javac in jdk9: 
https://bugs.openjdk.java.net/browse/JDK-8085796

I see that your changes are more general and not only for String. But I 
don't know how many cases real world applications have with non-escaping 
new primitive arrays followed by arraycopy which duplicates an array at 
the same method.

Unfortunately changes are too big and I am not sure they will help to 
improve performance of real applications significantly. May be others 
can show what can be improved so we can consider these changes.

PS: I can't look on [4] "JMH tests" - it is asking for login.

Thanks,
Vladimir

On 11/16/16 8:09 AM, Radosław Smogura wrote:
> 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).
>
> Then:
> 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
>
> Resources:
> [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
>
>
>