Warum dauert das Zuweisen eines einzelnen 2D-Arrays länger als das Zuweisen mehrerer 1D-Arrays mit derselben Gesamtgröße und -form?

Question 1

Ich dachte, es wäre schneller, direkt zu erstellen, aber das Hinzufügen von Schleifen dauert nur die Hälfte der Zeit. Was ist passiert, das sich so verlangsamt hat?

Hier ist der Testcode

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public class Test_newArray {
    private static int num = 10000;
    private static int length = 10;

    @Benchmark
    public static int[][] newArray() {
        return new int[num][length];
    }

    @Benchmark
    public static int[][] newArray2() {
        int[][] temps = new int[num][];
        for (int i = 0; i < temps.length; i++) {
            temps[i] = new int[length];
        }
        return temps;
    }

}

Die Testergebnisse sind wie folgt.

Benchmark                Mode  Cnt    Score   Error  Units
Test_newArray.newArray   avgt   25  289.254 ± 4.982  us/op
Test_newArray.newArray2  avgt   25  114.364 ± 1.446  us/op

Die Testumgebung ist wie folgt

JMH-Version: 1.21

VM-Version: JDK 1.8.0_212, OpenJDK 64-Bit-Server-VM, 25.212-b04

Question 2

In Java gibt es einen separaten Bytecode-Befehl zum Zuweisen mehrdimensionaler Arrays - multianewarray.

newArrayBenchmark verwendet multianewarrayBytecode;
newArray2ruft einfach newarrayin der Schleife auf.

Das Problem ist, dass HotSpot JVM keinen schnellen Pfad ^* für multianewarrayBytecode hat. Diese Anweisung wird immer zur VM-Laufzeit ausgeführt. Daher ist die Zuordnung im kompilierten Code nicht enthalten.

Der erste Benchmark muss die Leistung beim Umschalten zwischen Java- und VM-Laufzeitkontexten beeinträchtigen. Außerdem ist der allgemeine Zuordnungscode in der VM-Laufzeit (in C ++ geschrieben) nicht so optimiert wie die Inline-Zuweisung in JIT-kompiliertem Code, nur weil er generisch ist , dh nicht für den bestimmten Objekttyp oder für den bestimmten Aufrufstandort optimiert ist führt zusätzliche Laufzeitprüfungen usw. durch.

Hier sind die Ergebnisse der Profilerstellung beider Benchmarks mit dem Async-Profiler . Ich habe JDK 11.0.4 verwendet, aber für JDK 8 sieht das Bild ähnlich aus.

Im ersten Fall werden 99% der Zeit OptoRuntime::multianewarray2_Cim C ++ - Code der VM-Laufzeit verbracht.

Im zweiten Fall ist der größte Teil des Diagramms grün, was bedeutet, dass das Programm hauptsächlich im Java-Kontext ausgeführt wird und tatsächlich JIT-kompilierten Code ausführt, der speziell für den angegebenen Benchmark optimiert wurde.

BEARBEITEN

^* Nur zur Verdeutlichung: In HotSpot multianewarrayist das Design nicht sehr gut optimiert. Es ist ziemlich kostspielig, eine derart komplexe Operation in beiden JIT-Compilern ordnungsgemäß zu implementieren, während die Vorteile einer solchen Optimierung fraglich wären: Die Zuweisung von multidimentionalen Arrays ist in einer typischen Anwendung selten ein Leistungsengpass.

Question 3

Ein Hinweis in den Oracle-Dokumenten unter der multianewarrayAnweisung lautet:

Es kann effizienter sein, newarrayoder zu verwendenanewarray ( §newarray , §anewarray ) , wenn eine Anordnung von einer einzigen Dimension zu schaffen.

Des Weiteren:

newArrayDer Benchmark verwendet eine multianewarrayBytecode-Anweisung.

newArray2Der Benchmark verwendet eine anewarrayBytecode-Anweisung.

Und das macht den Unterschied. Sehen wir uns die Statistiken an, die mit dem perfLinux-Profiler erstellt wurden.

Für den newArrayBenchmark sind die heißesten Methoden nach dem Inlining:

....[Hottest Methods (after inlining)]..............................................................
 22.58%           libjvm.so  MemAllocator::allocate
 14.80%           libjvm.so  ObjArrayAllocator::initialize
 12.92%           libjvm.so  TypeArrayKlass::multi_allocate
 10.98%           libjvm.so  AccessInternal::PostRuntimeDispatch<G1BarrierSet::AccessBarrier<2670710ul, G1BarrierSet>, (AccessInternal::BarrierType)1, 2670710ul>::oop_access_barrier
  7.38%           libjvm.so  ObjArrayKlass::multi_allocate
  6.02%           libjvm.so  MemAllocator::Allocation::notify_allocation_jvmti_sampler
  5.84%          ld-2.27.so  __tls_get_addr
  5.66%           libjvm.so  CollectedHeap::array_allocate
  5.39%           libjvm.so  Klass::check_array_allocation_length
  4.76%        libc-2.27.so  __memset_avx2_unaligned_erms
  0.75%        libc-2.27.so  __memset_avx2_erms
  0.38%           libjvm.so  __tls_get_addr@plt
  0.17%           libjvm.so  memset@plt
  0.10%           libjvm.so  G1ParScanThreadState::copy_to_survivor_space
  0.10%   [kernel.kallsyms]  update_blocked_averages
  0.06%   [kernel.kallsyms]  native_write_msr
  0.05%           libjvm.so  G1ParScanThreadState::trim_queue
  0.05%           libjvm.so  Monitor::lock_without_safepoint_check
  0.05%           libjvm.so  G1FreeCollectionSetTask::G1SerialFreeCollectionSetClosure::do_heap_region
  0.05%           libjvm.so  OtherRegionsTable::occupied
  1.92%  <...other 288 warm methods...>

....[Distribution by Source]....
 87.61%           libjvm.so
  5.84%          ld-2.27.so
  5.56%        libc-2.27.so
  0.92%   [kernel.kallsyms]
  0.03%      perf-27943.map
  0.03%              [vdso]
  0.01%  libpthread-2.27.so
................................
100.00%  <totals>

Und für die newArray2:

....[Hottest Methods (after inlining)]..............................................................
 93.45%      perf-28023.map  [unknown]
  0.26%           libjvm.so  G1ParScanThreadState::copy_to_survivor_space
  0.22%   [kernel.kallsyms]  update_blocked_averages
  0.19%           libjvm.so  OtherRegionsTable::is_empty
  0.17%        libc-2.27.so  __memset_avx2_erms
  0.16%        libc-2.27.so  __memset_avx2_unaligned_erms
  0.14%           libjvm.so  OptoRuntime::new_array_C
  0.12%           libjvm.so  G1ParScanThreadState::trim_queue
  0.11%           libjvm.so  G1FreeCollectionSetTask::G1SerialFreeCollectionSetClosure::do_heap_region
  0.11%           libjvm.so  MemAllocator::allocate_inside_tlab_slow
  0.11%           libjvm.so  ObjArrayAllocator::initialize
  0.10%           libjvm.so  OtherRegionsTable::occupied
  0.10%           libjvm.so  MemAllocator::allocate
  0.10%           libjvm.so  Monitor::lock_without_safepoint_check
  0.10%   [kernel.kallsyms]  rt2800pci_rxdone_tasklet
  0.09%           libjvm.so  G1Allocator::unsafe_max_tlab_alloc
  0.08%           libjvm.so  ThreadLocalAllocBuffer::fill
  0.08%          ld-2.27.so  __tls_get_addr
  0.07%           libjvm.so  G1CollectedHeap::allocate_new_tlab
  0.07%           libjvm.so  TypeArrayKlass::allocate_common
  4.15%  <...other 411 warm methods...>

....[Distribution by Source]....
 93.45%      perf-28023.map
  4.31%           libjvm.so
  1.64%   [kernel.kallsyms]
  0.42%        libc-2.27.so
  0.08%          ld-2.27.so
  0.06%              [vdso]
  0.04%  libpthread-2.27.so
................................
100.00%  <totals>

Wie wir sehen können, wird die newArraymeiste Zeit im JVM-Code verbracht (insgesamt 87,61%):

22.58%  libjvm.so  MemAllocator::allocate
14.80%  libjvm.so  ObjArrayAllocator::initialize
12.92%  libjvm.so  TypeArrayKlass::multi_allocate
 7.38%  libjvm.so  ObjArrayKlass::multi_allocate
   ...

Während der newArray2verwendet dieOptoRuntime::new_array_C , verbringen Sie viel weniger Zeit damit, den Speicher für Arrays zuzuweisen. Die Gesamtzeit im JVM-Code beträgt nur 4,31%.

Mit dem perfnormProfiler erhaltene Bonusstatistiken:

Benchmark                        Mode  Cnt        Score    Error  Units
newArray                         avgt    4      448.018 ± 80.029  us/op
newArray:CPI                     avgt             0.359            #/op
newArray:L1-dcache-load-misses   avgt         10399.712            #/op
newArray:L1-dcache-loads         avgt       1032985.924            #/op
newArray:L1-dcache-stores        avgt        590756.905            #/op
newArray:cycles                  avgt       1132753.204            #/op
newArray:instructions            avgt       3159465.006            #/op

Benchmark                        Mode  Cnt        Score    Error  Units
newArray2                        avgt    4      125.531 ± 50.749  us/op
newArray2:CPI                    avgt             0.532            #/op
newArray2:L1-dcache-load-misses  avgt         10345.720            #/op
newArray2:L1-dcache-loads        avgt         85185.726            #/op
newArray2:L1-dcache-stores       avgt        103096.223            #/op
newArray2:cycles                 avgt        346651.432            #/op
newArray2:instructions           avgt        652155.439            #/op

Beachten Sie den Unterschied in der Anzahl der Zyklen und Anweisungen.

Umgebung:

Ubuntu 18.04.3 LTS

java version "12.0.2" 2019-07-16
Java(TM) SE Runtime Environment (build 12.0.2+10)
Java HotSpot(TM) 64-Bit Server VM (build 12.0.2+10, mixed mode, sharing)

Answer 1

73

Ich dachte, es wäre schneller, direkt zu erstellen, aber das Hinzufügen von Schleifen dauert nur die Hälfte der Zeit. Was ist passiert, das sich so verlangsamt hat?

Hier ist der Testcode

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public class Test_newArray {
    private static int num = 10000;
    private static int length = 10;

    @Benchmark
    public static int[][] newArray() {
        return new int[num][length];
    }

    @Benchmark
    public static int[][] newArray2() {
        int[][] temps = new int[num][];
        for (int i = 0; i < temps.length; i++) {
            temps[i] = new int[length];
        }
        return temps;
    }

}

Die Testergebnisse sind wie folgt.

Benchmark                Mode  Cnt    Score   Error  Units
Test_newArray.newArray   avgt   25  289.254 ± 4.982  us/op
Test_newArray.newArray2  avgt   25  114.364 ± 1.446  us/op

Die Testumgebung ist wie folgt

JMH-Version: 1.21

VM-Version: JDK 1.8.0_212, OpenJDK 64-Bit-Server-VM, 25.212-b04

java performance user10339780
quelle

5

nur raten, vielleicht weil im Falle von int[num][length]der kontinuierliche Raum der Größe num x lengthzugewiesen werden sollte, während im Fall von int[num][]die Arrays willkürlich zugewiesen werden

Mangusta

Haben Sie Daten darüber, was in Ihrer Umgebung passiert, wenn Sie variieren numund length?

NPE

@mangusta Es gibt keine 2D-Arrays in Java, ich glaube, deine Vermutung ist falsch. stackoverflow.com/a/6631081/1570854

Lesiak

2

Wenn Sie JMH mit ausführen -prof perfasm, erhalten Sie möglicherweise einige hilfreiche Erkenntnisse. ZB kann ich ObjArrayKlass::multi_allocatein der Ausgabe der ersten Methode viel vorhanden sehen, in der zweiten jedoch nicht. Meine Vermutung: Reflexion über Kopf?

Knittl

3

@Bohemian Führt JMH nicht jeden Benchmark isoliert aus (dh in seiner eigenen JVM) und übernimmt das Aufwärmen für Sie? Ich glaube, dass standardmäßig 5 Gabeln pro Benchmark verwendet werden , wobei jede Gabel 5 Aufwärmiterationen und 5 Messiterationen ausführt.

Slaw

Answer 2

5

nur raten, vielleicht weil im Falle von int[num][length]der kontinuierliche Raum der Größe num x lengthzugewiesen werden sollte, während im Fall von int[num][]die Arrays willkürlich zugewiesen werden

Mangusta

Answer 3

Haben Sie Daten darüber, was in Ihrer Umgebung passiert, wenn Sie variieren numund length?

NPE

Answer 4

@mangusta Es gibt keine 2D-Arrays in Java, ich glaube, deine Vermutung ist falsch. stackoverflow.com/a/6631081/1570854

Lesiak

Answer 5

2

Wenn Sie JMH mit ausführen -prof perfasm, erhalten Sie möglicherweise einige hilfreiche Erkenntnisse. ZB kann ich ObjArrayKlass::multi_allocatein der Ausgabe der ersten Methode viel vorhanden sehen, in der zweiten jedoch nicht. Meine Vermutung: Reflexion über Kopf?

Knittl

Answer 6

3

@Bohemian Führt JMH nicht jeden Benchmark isoliert aus (dh in seiner eigenen JVM) und übernimmt das Aufwärmen für Sie? Ich glaube, dass standardmäßig 5 Gabeln pro Benchmark verwendet werden , wobei jede Gabel 5 Aufwärmiterationen und 5 Messiterationen ausführt.

Slaw

Answer 7

In Java gibt es einen separaten Bytecode-Befehl zum Zuweisen mehrdimensionaler Arrays - multianewarray.

newArrayBenchmark verwendet multianewarrayBytecode;
newArray2ruft einfach newarrayin der Schleife auf.

Das Problem ist, dass HotSpot JVM keinen schnellen Pfad ^* für multianewarrayBytecode hat. Diese Anweisung wird immer zur VM-Laufzeit ausgeführt. Daher ist die Zuordnung im kompilierten Code nicht enthalten.

Der erste Benchmark muss die Leistung beim Umschalten zwischen Java- und VM-Laufzeitkontexten beeinträchtigen. Außerdem ist der allgemeine Zuordnungscode in der VM-Laufzeit (in C ++ geschrieben) nicht so optimiert wie die Inline-Zuweisung in JIT-kompiliertem Code, nur weil er generisch ist , dh nicht für den bestimmten Objekttyp oder für den bestimmten Aufrufstandort optimiert ist führt zusätzliche Laufzeitprüfungen usw. durch.

Hier sind die Ergebnisse der Profilerstellung beider Benchmarks mit dem Async-Profiler . Ich habe JDK 11.0.4 verwendet, aber für JDK 8 sieht das Bild ähnlich aus.

Im ersten Fall werden 99% der Zeit OptoRuntime::multianewarray2_Cim C ++ - Code der VM-Laufzeit verbracht.

Im zweiten Fall ist der größte Teil des Diagramms grün, was bedeutet, dass das Programm hauptsächlich im Java-Kontext ausgeführt wird und tatsächlich JIT-kompilierten Code ausführt, der speziell für den angegebenen Benchmark optimiert wurde.

BEARBEITEN

^* Nur zur Verdeutlichung: In HotSpot multianewarrayist das Design nicht sehr gut optimiert. Es ist ziemlich kostspielig, eine derart komplexe Operation in beiden JIT-Compilern ordnungsgemäß zu implementieren, während die Vorteile einer solchen Optimierung fraglich wären: Die Zuweisung von multidimentionalen Arrays ist in einer typischen Anwendung selten ein Leistungsengpass.

Answer 8

7

Gute Antwort, insbesondere mit einem Flammengraphen - ich wünschte, sie wären häufiger.

Kaan

Answer 9

1

Vielen Dank für Ihre Antwort. Es ist eine gute Antwort auf meine Zweifel. Das Problem ist die Unterhaltung der Ruhezeit. Es geht nicht wirklich darum, die Details zu optimieren.

user10339780

Answer 10

Ein Hinweis in den Oracle-Dokumenten unter der multianewarrayAnweisung lautet:

Es kann effizienter sein, newarrayoder zu verwendenanewarray ( §newarray , §anewarray ) , wenn eine Anordnung von einer einzigen Dimension zu schaffen.

Des Weiteren:

newArrayDer Benchmark verwendet eine multianewarrayBytecode-Anweisung.

newArray2Der Benchmark verwendet eine anewarrayBytecode-Anweisung.

Und das macht den Unterschied. Sehen wir uns die Statistiken an, die mit dem perfLinux-Profiler erstellt wurden.

Für den newArrayBenchmark sind die heißesten Methoden nach dem Inlining:

....[Hottest Methods (after inlining)]..............................................................
 22.58%           libjvm.so  MemAllocator::allocate
 14.80%           libjvm.so  ObjArrayAllocator::initialize
 12.92%           libjvm.so  TypeArrayKlass::multi_allocate
 10.98%           libjvm.so  AccessInternal::PostRuntimeDispatch<G1BarrierSet::AccessBarrier<2670710ul, G1BarrierSet>, (AccessInternal::BarrierType)1, 2670710ul>::oop_access_barrier
  7.38%           libjvm.so  ObjArrayKlass::multi_allocate
  6.02%           libjvm.so  MemAllocator::Allocation::notify_allocation_jvmti_sampler
  5.84%          ld-2.27.so  __tls_get_addr
  5.66%           libjvm.so  CollectedHeap::array_allocate
  5.39%           libjvm.so  Klass::check_array_allocation_length
  4.76%        libc-2.27.so  __memset_avx2_unaligned_erms
  0.75%        libc-2.27.so  __memset_avx2_erms
  0.38%           libjvm.so  __tls_get_addr@plt
  0.17%           libjvm.so  memset@plt
  0.10%           libjvm.so  G1ParScanThreadState::copy_to_survivor_space
  0.10%   [kernel.kallsyms]  update_blocked_averages
  0.06%   [kernel.kallsyms]  native_write_msr
  0.05%           libjvm.so  G1ParScanThreadState::trim_queue
  0.05%           libjvm.so  Monitor::lock_without_safepoint_check
  0.05%           libjvm.so  G1FreeCollectionSetTask::G1SerialFreeCollectionSetClosure::do_heap_region
  0.05%           libjvm.so  OtherRegionsTable::occupied
  1.92%  <...other 288 warm methods...>

....[Distribution by Source]....
 87.61%           libjvm.so
  5.84%          ld-2.27.so
  5.56%        libc-2.27.so
  0.92%   [kernel.kallsyms]
  0.03%      perf-27943.map
  0.03%              [vdso]
  0.01%  libpthread-2.27.so
................................
100.00%  <totals>

Und für die newArray2:

....[Hottest Methods (after inlining)]..............................................................
 93.45%      perf-28023.map  [unknown]
  0.26%           libjvm.so  G1ParScanThreadState::copy_to_survivor_space
  0.22%   [kernel.kallsyms]  update_blocked_averages
  0.19%           libjvm.so  OtherRegionsTable::is_empty
  0.17%        libc-2.27.so  __memset_avx2_erms
  0.16%        libc-2.27.so  __memset_avx2_unaligned_erms
  0.14%           libjvm.so  OptoRuntime::new_array_C
  0.12%           libjvm.so  G1ParScanThreadState::trim_queue
  0.11%           libjvm.so  G1FreeCollectionSetTask::G1SerialFreeCollectionSetClosure::do_heap_region
  0.11%           libjvm.so  MemAllocator::allocate_inside_tlab_slow
  0.11%           libjvm.so  ObjArrayAllocator::initialize
  0.10%           libjvm.so  OtherRegionsTable::occupied
  0.10%           libjvm.so  MemAllocator::allocate
  0.10%           libjvm.so  Monitor::lock_without_safepoint_check
  0.10%   [kernel.kallsyms]  rt2800pci_rxdone_tasklet
  0.09%           libjvm.so  G1Allocator::unsafe_max_tlab_alloc
  0.08%           libjvm.so  ThreadLocalAllocBuffer::fill
  0.08%          ld-2.27.so  __tls_get_addr
  0.07%           libjvm.so  G1CollectedHeap::allocate_new_tlab
  0.07%           libjvm.so  TypeArrayKlass::allocate_common
  4.15%  <...other 411 warm methods...>

....[Distribution by Source]....
 93.45%      perf-28023.map
  4.31%           libjvm.so
  1.64%   [kernel.kallsyms]
  0.42%        libc-2.27.so
  0.08%          ld-2.27.so
  0.06%              [vdso]
  0.04%  libpthread-2.27.so
................................
100.00%  <totals>

Wie wir sehen können, wird die newArraymeiste Zeit im JVM-Code verbracht (insgesamt 87,61%):

22.58%  libjvm.so  MemAllocator::allocate
14.80%  libjvm.so  ObjArrayAllocator::initialize
12.92%  libjvm.so  TypeArrayKlass::multi_allocate
 7.38%  libjvm.so  ObjArrayKlass::multi_allocate
   ...

Während der newArray2verwendet dieOptoRuntime::new_array_C , verbringen Sie viel weniger Zeit damit, den Speicher für Arrays zuzuweisen. Die Gesamtzeit im JVM-Code beträgt nur 4,31%.

Mit dem perfnormProfiler erhaltene Bonusstatistiken:

Benchmark                        Mode  Cnt        Score    Error  Units
newArray                         avgt    4      448.018 ± 80.029  us/op
newArray:CPI                     avgt             0.359            #/op
newArray:L1-dcache-load-misses   avgt         10399.712            #/op
newArray:L1-dcache-loads         avgt       1032985.924            #/op
newArray:L1-dcache-stores        avgt        590756.905            #/op
newArray:cycles                  avgt       1132753.204            #/op
newArray:instructions            avgt       3159465.006            #/op

Benchmark                        Mode  Cnt        Score    Error  Units
newArray2                        avgt    4      125.531 ± 50.749  us/op
newArray2:CPI                    avgt             0.532            #/op
newArray2:L1-dcache-load-misses  avgt         10345.720            #/op
newArray2:L1-dcache-loads        avgt         85185.726            #/op
newArray2:L1-dcache-stores       avgt        103096.223            #/op
newArray2:cycles                 avgt        346651.432            #/op
newArray2:instructions           avgt        652155.439            #/op

Beachten Sie den Unterschied in der Anzahl der Zyklen und Anweisungen.

Umgebung:

Ubuntu 18.04.3 LTS

java version "12.0.2" 2019-07-16
Java(TM) SE Runtime Environment (build 12.0.2+10)
Java HotSpot(TM) 64-Bit Server VM (build 12.0.2+10, mixed mode, sharing)

Answer 11

8

Es wäre schön, wenn Sie diese Ergebnisse

näher erläutern

Answer 12

3

@ Andrew Danke für den Kommentar. Ich habe meine Antwort mit einigen zusätzlichen Details aktualisiert. Wenn Sie noch spezielle Fragen haben, zögern Sie bitte nicht zu fragen.

Oleksandr Pyrohov

Warum dauert das Zuweisen eines einzelnen 2D-Arrays länger als das Zuweisen mehrerer 1D-Arrays mit derselben Gesamtgröße und -form?

Antworten: