Разбираемся с копированием и клонированием

в 13:21, , рубрики: clone, copy, java, Анализ и проектирование систем, Блог компании Mail.Ru Group, высокая производительность, никто не читает теги, отладка

Разбираемся с копированием и клонированием - 1

Я наткнулся на статью Нареша Джоши о копировании и клонировании и был удивлён ситуацией с производительностью. У клонирования есть проблемы с финальными полями. А учитывая тот факт, что интерфейс Cloneable не предоставляет метод clone, то для вызова clone вам необходимо будет знать конкретный тип класса.

Вы можете написать такой код:

    ((Cloneable)o).clone(); // не работает

Если интерфейс Cloneable сломан, то у механизма клонирования могут быть некоторые преимущества. При копировании памяти он может оказаться эффективнее, чем копирование поля за полем. Это подчёркивает Джош Блох, автор Effective Java:

Даг Ли пошёл ещё дальше. Он сказал мне, что теперь клонирует только при копировании массивов. Вам следует использовать клонирование копирования массивов, потому что в целом это самый быстрый способ. Но у Дага типы больше не реализуют Cloneable. Он с ним завязал. И я не считаю это необоснованным.

Но это было в 2002-м, разве ситуация не изменилась? Со времён Java 6 у нас есть Arrays.copyOf, что насчёт него? Какова производительность копирования объекта?
Есть только один способ выяснить: прогнать бенчмарки.

TL;DR

  • Клонирование работает быстрее при копировании массива, это заметно на маленьких массивах.
  • Клонирование работает медленнее для маленьких объектов, меньше восьми полей, но в любом случае быстрее.
  • При клонировании не работает escape analysis, и потенциально оно может помешать применению других оптимизаций.

image

Массивы

Давайте быстро рассмотрим clone и Arrays.copyOf применительно к массивам.

Бенчмарк int array выглядит так:

    @Benchmark
    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
    public int[] testCopy() {
        return Arrays.copyOf(original, size);
    }

    @Benchmark
    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
    public int[] testClone() {
        return original.clone();
    }

Мы создали массив из случайных числовых значений, затем выполнили clone или Arrays.copyOf. Обратите внимание: мы вернули результат копирования, чтобы гарантировать, что код будет выполнен. В главе про escape analysis мы увидим, как невозвращение массива может радикально повлиять на бенчмарк.

Наряду с int array есть версия для byte array, long array и Object array. Я использую флаг DONT_INLINE, чтобы при необходимости легче было анализировать сгенерированный asm.

mvn clean install
java -jar target/benchmark.jar -bm avgt -tu ns -rf csv

Это даёт нам следующие значения средней продолжительности в наносекундах.

На графиках я отобразил одновременно total time/array size. Чем меньше, тем лучше.

image image

image image

Как видите, clone по сравнению с Arrays.copyOf обходится примерно на 10 % дешевле при маленьких массивах, так что это всё ещё хороший вариант. Несколько удивительно, что оба они используют один и тот же механизм копирования.

Давайте рассмотрим сгенерированный asm.

Клонирование asm

Для testClone есть код выделения памяти, идущий за копированием массива со строки 41 по 47.

0x0000000116972e4c: mov 0x10(%rsi),%r9d  ;*getfield original
                                         ; - com.github.arnaudroger.ArrayByteCopyVsCloneBenchmark::testClone@1 (line 68)
0x0000000116972e50: mov 0xc(%r12,%r9,8),%r8d  ;*invokevirtual clone
                                              ; - com.github.arnaudroger.ArrayByteCopyVsCloneBenchmark::testClone@4 (line 68)
                                              ; implicit exception: dispatches to 0x0000000116972f0e
0x0000000116972e55: lea (%r12,%r9,8),%rbp  ;*getfield original
                                           ; - com.github.arnaudroger.ArrayByteCopyVsCloneBenchmark::testClone@1 (line 68)
0x0000000116972e59: movslq %r8d,%rdx
0x0000000116972e5c: add $0x17,%rdx
0x0000000116972e60: and $0xfffffffffffffff8,%rdx
0x0000000116972e64: cmp $0x100000,%r8d
0x0000000116972e6b: ja L0001
0x0000000116972e6d: mov 0x60(%r15),%rbx
0x0000000116972e71: mov %rbx,%r10
0x0000000116972e74: add %rdx,%r10
0x0000000116972e77: cmp 0x70(%r15),%r10
0x0000000116972e7b: jae L0001
0x0000000116972e7d: mov %r10,0x60(%r15)
0x0000000116972e81: prefetchnta 0xc0(%r10)
0x0000000116972e89: movq $0x1,(%rbx)
0x0000000116972e90: prefetchnta 0x100(%r10)
0x0000000116972e98: movl $0xf80000f5,0x8(%rbx)  ;   {metadata({type array byte})}
0x0000000116972e9f: mov %r8d,0xc(%rbx)
0x0000000116972ea3: prefetchnta 0x140(%r10)
0x0000000116972eab: prefetchnta 0x180(%r10)
             L0000: lea 0x10(%r12,%r9,8),%rdi
0x0000000116972eb8: mov %rbx,%rsi
0x0000000116972ebb: add $0x10,%rsi
0x0000000116972ebf: add $0xfffffffffffffff0,%rdx
0x0000000116972ec3: shr $0x3,%rdx
0x0000000116972ec7: movabs $0x1167e5780,%r10
0x0000000116972ed1: callq *%r10  ;*invokevirtual clone
                                 ; - com.github.arnaudroger.ArrayByteCopyVsCloneBenchmark::testClone@4 (line 68)
0x0000000116972ed4: mov %rbx,%rax
0x0000000116972ed7: add $0x20,%rsp
0x0000000116972edb: pop %rbp
0x0000000116972edc: test %eax,-0xdf73ee2(%rip)  # 0x00000001089ff000
                                                ;   {poll_return} *** SAFEPOINT POLL ***
0x0000000116972ee2: retq

Копирование asm

В testCopy есть код выделения памяти, но со строки 47 идёт гораздо больше кода для работы с длиной копии. Реальное копирование выполняется в строках 79—80.

0x000000010b1639cc: mov 0xc(%rsi),%r10d  ;*getfield size
                                         ; - com.github.arnaudroger.ArrayByteCopyVsCloneBenchmark::testCopy@5 (line 62)
0x000000010b1639d0: cmp $0x100000,%r10d
0x000000010b1639d7: ja L0005
0x000000010b1639dd: movslq %r10d,%r8  ;*newarray
                                      ; - java.util.Arrays::copyOf@1 (line 3236)
                                      ; - com.github.arnaudroger.ArrayByteCopyVsCloneBenchmark::testCopy@8 (line 62)
             L0000: mov 0x10(%rsi),%r9d  ;*getfield original
                                         ; - com.github.arnaudroger.ArrayByteCopyVsCloneBenchmark::testCopy@1 (line 62)
0x000000010b1639e4: mov %r9d,0x10(%rsp)
0x000000010b1639e9: add $0x17,%r8
0x000000010b1639ed: mov %r8,%rdx
0x000000010b1639f0: and $0xfffffffffffffff8,%rdx
0x000000010b1639f4: cmp $0x100000,%r10d
0x000000010b1639fb: ja L0004
0x000000010b163a01: mov 0x60(%r15),%rbp
0x000000010b163a05: mov %rbp,%r11
0x000000010b163a08: add %rdx,%r11
0x000000010b163a0b: cmp 0x70(%r15),%r11
0x000000010b163a0f: jae L0004
0x000000010b163a15: mov %r11,0x60(%r15)
0x000000010b163a19: prefetchnta 0xc0(%r11)
0x000000010b163a21: movq $0x1,0x0(%rbp)
0x000000010b163a29: prefetchnta 0x100(%r11)
0x000000010b163a31: movl $0xf80000f5,0x8(%rbp)  ;   {metadata({type array byte})}
0x000000010b163a38: mov %r10d,0xc(%rbp)
0x000000010b163a3c: prefetchnta 0x140(%r11)
0x000000010b163a44: prefetchnta 0x180(%r11)  ;*newarray
                                             ; - java.util.Arrays::copyOf@1 (line 3236)
                                             ; - com.github.arnaudroger.ArrayByteCopyVsCloneBenchmark::testCopy@8 (line 62)
             L0001: mov 0x10(%rsp),%r11d
0x000000010b163a51: mov 0xc(%r12,%r11,8),%r11d  ;*arraylength
                                                ; - java.util.Arrays::copyOf@9 (line 3237)
                                                ; - com.github.arnaudroger.ArrayByteCopyVsCloneBenchmark::testCopy@8 (line 62)
                                                ; implicit exception: dispatches to 0x000000010b163b77
0x000000010b163a56: cmp %r10d,%r11d
0x000000010b163a59: mov %r10d,%r9d
0x000000010b163a5c: cmovl %r11d,%r9d  ;*invokestatic min
                                      ; - java.util.Arrays::copyOf@11 (line 3238)
                                      ; - com.github.arnaudroger.ArrayByteCopyVsCloneBenchmark::testCopy@8 (line 62)
0x000000010b163a60: mov %rbp,%rbx
0x000000010b163a63: add $0x10,%rbx
0x000000010b163a67: shr $0x3,%r8  ;*invokestatic arraycopy
                                  ; - java.util.Arrays::copyOf@14 (line 3237)
                                  ; - com.github.arnaudroger.ArrayByteCopyVsCloneBenchmark::testCopy@8 (line 62)
0x000000010b163a6b: mov 0x10(%rsp),%edi
0x000000010b163a6f: lea (%r12,%rdi,8),%rsi  ;*getfield original
                                            ; - com.github.arnaudroger.ArrayByteCopyVsCloneBenchmark::testCopy@1 (line 62)
0x000000010b163a73: mov %r8,%rcx
0x000000010b163a76: add $0xfffffffffffffffe,%rcx
0x000000010b163a7a: cmp %r9d,%r11d
0x000000010b163a7d: jb L0006
0x000000010b163a83: cmp %r9d,%r10d
0x000000010b163a86: jb L0006
0x000000010b163a8c: test %r9d,%r9d
0x000000010b163a8f: jle L0007
0x000000010b163a95: lea 0x10(%r12,%rdi,8),%r11
0x000000010b163a9a: cmp %r10d,%r9d
0x000000010b163a9d: jl L0003
0x000000010b163a9f: add $0xfffffffffffffff0,%rdx
0x000000010b163aa3: shr $0x3,%rdx
0x000000010b163aa7: mov %r11,%rdi
0x000000010b163aaa: mov %rbx,%rsi
0x000000010b163aad: movabs $0x10afd5780,%r10
0x000000010b163ab7: callq *%r10
             L0002: mov %rbp,%rax
0x000000010b163abd: add $0x30,%rsp
0x000000010b163ac1: pop %rbp
0x000000010b163ac2: test %eax,-0x5b6aac8(%rip)  # 0x00000001055f9000
                                                ;   {poll_return} *** SAFEPOINT POLL ***
0x000000010b163ac8: retq

clone сделает копию точно такой же длины, но Arrays.copyOf позволяет нам копировать массив в массив другой длины, что усложняет обработку разных ситуаций и увеличивает стоимость, особенно на маленьких массивах. Похоже, jit никак не смирится с тем фактом, что мы передаём original.length как newLength. Будь это не так, он мог бы упростить код и производительность стала бы на уровне.

Объекты

Теперь разберёмся с клонированием объектов с 4, 8, 16 и 32 полями. Бенчмарки ищут объекты с 4 полями:

    @Benchmark
    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
    public Object4 testCopy4() {
        return new Object4(original);
    }

    @Benchmark
    @CompilerControl(CompilerControl.Mode.DONT_INLINE)
    public Object4 testClone4() {
        return original.clone();
    }

С 8, 16 и 32 полями.

Нормализованные результаты:

image

Как видите, для маленьких/средних объектов — меньше 8 полей — клонирование не столь эффективно, как копирование, но его преимущества раскрываются на более крупных объектах.
Это неудивительно и следует из комментария к коду JVM:

// TODO: вместо этого сгенерировать копии полей для маленьких объектов.

Кто-то должен был отработать этот комментарий, но так и не сделал этого.

Давайте внимательнее проанализируем asm применительно к копированию и клонированию объектов с 4 полями.

Asm и 4 поля

java -jar target/benchmarks.jar -jvmArgs "-XX:+UnlockDiagnosticVMOptions -XX:+TraceClassLoading -XX:+LogCompilation -XX:+PrintAssembly "  -f 1 "Object4"

Копирование asm

В testCopy asm с 17-й по 32-ю строки мы видим код выделения памяти.

Я добавил в asm кое-какую аннотацию, начинающуюся с **.

0x000000010593d28f: mov 0x60(%r15),%rax
0x000000010593d293: mov %rax,%r10
0x000000010593d296: add $0x20,%r10         ;** allocation size
0x000000010593d29a: cmp 0x70(%r15),%r10
0x000000010593d29e: jae L0001
0x000000010593d2a0: mov %r10,0x60(%r15)
0x000000010593d2a4: prefetchnta 0xc0(%r10)
0x000000010593d2ac: mov $0xf8015eab,%r11d  ;   {metadata('com/github/arnaudroger/beans/Object4')}
0x000000010593d2b2: movabs $0x0,%r10
0x000000010593d2bc: lea (%r10,%r11,8),%r10
0x000000010593d2c0: mov 0xa8(%r10),%r10
0x000000010593d2c7: mov %r10,(%rax)
0x000000010593d2ca: movl $0xf8015eab,0x8(%rax)  ;   {metadata('com/github/arnaudroger/beans/Object4')}
0x000000010593d2d1: mov %r12d,0xc(%rax)
0x000000010593d2d5: mov %r12,0x10(%rax)
0x000000010593d2d9: mov %r12,0x18(%rax)  ;*new  ; - com.github.arnaudroger.Object4CopyVsCloneBenchmark::testCopy4@0 (line 60)

Строка 19 — это размер выделяемой памяти, 32 байта. Из них 16 байтов для свойств, 12 — для заголовков, 4 — для выравнивания (alignment). Проверить это можно с помощью jol.

com.github.arnaudroger.beans.Object4 object internals:
 OFFSET  SIZE   TYPE DESCRIPTION                               VALUE
      0    12        (object header)                           N/A
     12     4    int Object4.f1                                N/A
     16     4    int Object4.f2                                N/A
     20     4    int Object4.f3                                N/A
     24     4    int Object4.f4                                N/A
     28     4        (loss due to the next object alignment)
Instance size: 32 bytes
Space losses: 0 bytes internal + 4 bytes external = 4 bytes total

Копирование поля за полем выполняется в строках с 33-й по 48-ю.

             L0000: mov 0xc(%rbp),%r11d  ;*getfield original4
                                         ; - com.github.arnaudroger.Object4CopyVsCloneBenchmark::testCopy4@5 (line 60)
0x000000010593d2e1: mov 0xc(%r12,%r11,8),%r10d  ; implicit exception: dispatches to 0x000000010593d322
0x000000010593d2e6: mov %r10d,0xc(%rax)  ;*putfield f1
                                         ; - com.github.arnaudroger.beans.Object4::<init>@9 (line 12)
                                         ; - com.github.arnaudroger.Object4CopyVsCloneBenchmark::testCopy4@8 (line 60)
0x000000010593d2ea: mov 0x10(%r12,%r11,8),%r8d
0x000000010593d2ef: mov %r8d,0x10(%rax)  ;*putfield f2
                                         ; - com.github.arnaudroger.beans.Object4::<init>@17 (line 13)
                                         ; - com.github.arnaudroger.Object4CopyVsCloneBenchmark::testCopy4@8 (line 60)
0x000000010593d2f3: mov 0x14(%r12,%r11,8),%r10d
0x000000010593d2f8: mov %r10d,0x14(%rax)  ;*putfield f3
                                          ; - com.github.arnaudroger.beans.Object4::<init>@25 (line 14)
                                          ; - com.github.arnaudroger.Object4CopyVsCloneBenchmark::testCopy4@8 (line 60)
0x000000010593d2fc: mov 0x18(%r12,%r11,8),%r11d
0x000000010593d301: mov %r11d,0x18(%rax)

Клонирование asm

Для testClone asm можно также посмотреть код выделения памяти с 24-й по 37-ю строку.

0x000000010b17da9d: mov 0x60(%r15),%rbx
0x000000010b17daa1: mov %rbx,%r10
0x000000010b17daa4: add $0x20,%r10         ;** allocation size
0x000000010b17daa8: cmp 0x70(%r15),%r10
0x000000010b17daac: jae L0001
0x000000010b17daae: mov %r10,0x60(%r15)
0x000000010b17dab2: prefetchnta 0xc0(%r10)
0x000000010b17daba: mov $0xf8015eab,%r11d  ;   {metadata('com/github/arnaudroger/beans/Object4')}
0x000000010b17dac0: movabs $0x0,%r10
0x000000010b17daca: lea (%r10,%r11,8),%r10
0x000000010b17dace: mov 0xa8(%r10),%r10
0x000000010b17dad5: mov %r10,(%rbx)
0x000000010b17dad8: movl $0xf8015eab,0x8(%rbx)  ;   {metadata('com/github/arnaudroger/beans/Object4')}

Это несколько удивляет, потому что в логе компилирования

image

        <klass name="java/lang/Object" flags="1" id="729"/>
        <method compile_kind="c2n" level="0" bytes="0" name="clone" flags="260" holder="729" id="838" compile_id="167" iicount="512" return="729"/>
        <call method="838" inline="1" count="16881" prof_factor="1"/>
        <inline_fail reason="native method"/>
        <dependency ctxk="833" type="leaf_type"/>
        <uncommon_trap reason="unhandled" bci="1" action="none"/>
        <intrinsic nodes="69" id="_clone"/>

Применительно к Object.clone указан сбой инлайнинга, потому что это «нативный метод».
clone является внутренним (intrinsic), он инлайнится с помощью inline_native_clone и copy_to_clone.

copy_to_clone генерирует выделение памяти (allocation), а затем копирование long array. Оно возможно, потому что объекты выравнены в памяти по 8 байтов.

             L0000: lea 0x8(%r12,%r8,8),%rdi ;** src 
0x000000010b17dae4: mov %rbx,%rsi ;** dst
0x000000010b17dae7: add $0x8,%rsi ;** add offset
0x000000010b17daeb: mov $0x3,%edx ;** length
0x000000010b17daf0: movabs $0x10aff4780,%r10
0x000000010b17dafa: callq *%r10  ;*invokespecial clone
                                 ; - com.github.arnaudroger.beans.Object4::clone@1 (line 28)
                                 ; - com.github.arnaudroger.Object4CopyVsCloneBenchmark::testClone4@4 (line 66)

Так что, несмотря на пометку о сбое, инлайнинг полностью выполнен. Выполняется копирование со смещением (offset) в 8 байтов, а также копируется три long или 24 байта, включая 4 байта метаданных класса, 16 байтов на 4 целочисленных значения, а остальное — на выравнивание.

Влияние escape analysis

Но поскольку клонирование использует копию памяти, экземпляр не пройдёт escape analysis, что приведёт к отключению некоторых оптимизаций. В следующем бенчмарке мы создадим копию и вернём только одно поле из свежесозданного Object32.

     @Benchmark
     @CompilerControl(CompilerControl.Mode.DONT_INLINE)
     public int testCopy() {
         return new Object32(original).f29;
     }

     @Benchmark
     @CompilerControl(CompilerControl.Mode.DONT_INLINE)
     public int testClone() {
         return original.clone().f29;
     }

Результаты таковы, что, даже хотя clone более эффективно для объектов с 32 полями...

image

… бенчмарк клонирования работает более чем вчетверо медленнее! Что произошло?

Посмотрим, что находится под капотом asm.

asm клонирование

В asm для testClone всё аналогично варианту для Object4CopyVsCloneBenchmark.testClone. В строке 26 выделяется 144 байта — 90 в шестнадцатеричном виде, — из которых 12 байтов на заголовок, 32 × 4 = 128 байтов на поля, 4 байта потеряно на выравнивание.

0x000000010ceebe8c: mov 0xc(%rsi),%r9d  ;*getfield original
                                        ; - com.github.arnaudroger.Object32CopyVsCloneEABenchmark::testClone@1 (line 69)
0x000000010ceebe90: test %r9d,%r9d
0x000000010ceebe93: je L0002  ;*invokespecial clone
                              ; - com.github.arnaudroger.beans.Object32::clone@1 (line 111)
                              ; - com.github.arnaudroger.Object32CopyVsCloneEABenchmark::testClone@4 (line 69)
0x000000010ceebe99: lea (%r12,%r9,8),%rbp  ;*getfield original
                                           ; - com.github.arnaudroger.Object32CopyVsCloneEABenchmark::testClone@1 (line 69)
0x000000010ceebe9d: mov 0x60(%r15),%rbx
0x000000010ceebea1: mov %rbx,%r10
0x000000010ceebea4: add $0x90,%r10 ;** object length
0x000000010ceebeab: cmp 0x70(%r15),%r10
0x000000010ceebeaf: jae L0001
0x000000010ceebeb1: mov %r10,0x60(%r15)
0x000000010ceebeb5: prefetchnta 0xc0(%r10)
0x000000010ceebebd: mov $0xf8015eab,%r11d  ;   {metadata('com/github/arnaudroger/beans/Object32')}
0x000000010ceebec3: movabs $0x0,%r10
0x000000010ceebecd: lea (%r10,%r11,8),%r10
0x000000010ceebed1: mov 0xa8(%r10),%r10
0x000000010ceebed8: mov %r10,(%rbx)
0x000000010ceebedb: movl $0xf8015eab,0x8(%rbx)  ;   {metadata('com/github/arnaudroger/beans/Object32')}
             L0000: lea 0x8(%r12,%r9,8),%rdi ;** src
0x000000010ceebee7: mov %rbx,%rsi ;** dest
0x000000010ceebeea: add $0x8,%rsi ;** add offset of 8
0x000000010ceebeee: mov $0x11,%edx ;** length to copy 0x11 * 8 = 136 bytes 
0x000000010ceebef3: movabs $0x10cd5d780,%r10
0x000000010ceebefd: callq *%r10  ;*invokespecial clone
                                 ; - com.github.arnaudroger.beans.Object32::clone@1 (line 111)
                                 ; - com.github.arnaudroger.Object32CopyVsCloneEABenchmark::testClone@4 (line 69)
0x000000010ceebf00: mov 0x7c(%rbx),%eax  ;*getfield f29 ** 7c is 124 bytes, minus the headers 112 that offset 28 ints 
                                         ; - com.github.arnaudroger.Object32CopyVsCloneEABenchmark::testClone@7 (line 69)
0x000000010ceebf03: add $0x20,%rsp
0x000000010ceebf07: pop %rbp
0x000000010ceebf08: test %eax,-0xb154f0e(%rip)  # 0x0000000101d97000
                                                ;   {poll_return} *** SAFEPOINT POLL ***
0x000000010ceebf0e: retq

asm копирование

В копии один даже не копируется объект, просто возвращается поле f29 из оригинального объекта. Поскольку копирование не эскейпится и создание копии не приводит к побочным эффектам, то можно безопасно полностью удалить код создания нового объекта.

Строки с 16-й по 26-ю.

0x0000000109c7b1cc: mov 0xc(%rsi),%r11d  ;*getfield original
                                         ; - com.github.arnaudroger.Object32CopyVsCloneEABenchmark::testCopy@5 (line 63)
0x0000000109c7b1d0: mov 0x7c(%r12,%r11,8),%eax  ;*getfield f29 ** 7c is 124 bytes, minus the headers 112 that offset 28 ints
                                                ; - com.github.arnaudroger.beans.Object32::<init>@230 (line 67)
                                                ; - com.github.arnaudroger.Object32CopyVsCloneEABenchmark::testCopy@8 (line 63)
                                                ; implicit exception: dispatches to 0x0000000109c7b1e1
0x0000000109c7b1d5: add $0x10,%rsp
0x0000000109c7b1d9: pop %rbp
0x0000000109c7b1da: test %eax,-0x47b81e0(%rip)  # 0x00000001054c3000
                                                ;   {poll_return} *** SAFEPOINT POLL ***
0x0000000109c7b1e0: retq

Итог

Метод clone работает быстрее при копировании массивов и больших объектов. Но удостоверьтесь, что ваш код не использует преимущества escape-анализа. В любом случае это может незначительно повлиять на весь ваш код, так что совет Дага Ли всё ещё актуален: избегайте копирования, за исключением копирования массивов.

Автор: AloneCoder

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js