java - ¿Por qué la asignación de una sola matriz 2D tarda más que un bucle que asigna múltiples matrices 1D del mismo tamaño y forma total?

performance

Question

Pensé que sería más rápido crear directamente, pero de hecho, agregar bucles lleva solo la mitad del tiempo. ¿Qué pasó que disminuyó tanto?

Aquí está el código de prueba

@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;
    }

}

Los resultados de la prueba son los siguientes.

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

El entorno de prueba es el siguiente

Versión JMH: 1.21

Versión de VM: JDK 1.8.0_212, OpenJDK 64-Bit Server VM, 25.212-b04

Answer 1

En Java hay una instrucción de multianewarray separada para asignar matrices multidimensionales: multianewarray .

• newArray benchmark utiliza multianewarray bytecode;
• newArray2 invoca newArray2 simple en el bucle.

El problema es que HotSpot JVM no tiene una ruta rápida ^* para el bytecode multianewarray . Esta instrucción siempre se ejecuta en tiempo de ejecución de VM. Por lo tanto, la asignación no está incorporada en el código compilado.

El primer punto de referencia tiene que pagar una penalización de rendimiento por cambiar entre contextos Java y VM Runtime. Además, el código de asignación común en el tiempo de ejecución de VM (escrito en C ++) no está tan optimizado como la asignación en línea en el código compilado JIT, simplemente porque es genérico , es decir, no está optimizado para el tipo de objeto en particular o para el sitio de llamada en particular. realiza verificaciones de tiempo de ejecución adicionales, etc.

Aquí están los resultados de perfilar ambos puntos de referencia con async-profiler . Utilicé JDK 11.0.4, pero para JDK 8 la imagen se ve similar.

En el primer caso, se pasa el 99% del tiempo dentro de OptoRuntime::multianewarray2_C , el código C ++ en el tiempo de ejecución de VM.

En el segundo caso, la mayor parte del gráfico es verde, lo que significa que el programa se ejecuta principalmente en el contexto de Java, en realidad ejecuta código compilado JIT optimizado específicamente para el punto de referencia dado.

EDITAR

^* Solo para aclarar: en HotSpot multianewarray no está optimizado muy bien por diseño. Implementar una operación tan compleja en ambos compiladores JIT es bastante costoso, mientras que los beneficios de dicha optimización serían cuestionables: la asignación de matrices multidimensionales rara vez es un cuello de botella en el rendimiento de una aplicación típica.

Answer 2

Una nota en los documentos de Oracle bajo la instrucción multianewarray dice:

Puede ser más eficiente usar newarray o anewarray ( §newarray , §anewarray ) al crear una matriz de una sola dimensión.

Promover, adicional:

newArray benchmark newArray utiliza una anewarray instrucción bytecode de anewarray .

newArray2 benchmark newArray2 usa instrucciones de bytecode multianewarray .

Y eso es lo que hace la diferencia. Veamos las estadísticas obtenidas usando el perfilador Linux perf .

Para el newArray benchmark newArray , las regiones más populares ¹ en el código generado son:

....[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...>

Y para el nuevo 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...>

Como podemos ver, para el newArray benchmark newArray más lento, la newArray parte del tiempo se dedica a:

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

Mientras que newArray2 usa OptoRuntime::new_array_C , OptoRuntime::new_array_C mucho menos tiempo a asignar la memoria a las matrices.

Estadísticas de bonificación obtenidas utilizando el perfilador de perfnorm :

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
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

Tenga en cuenta la diferencia en el número de ciclos e instrucciones.

^{1 - Las regiones de código que toman más tiempo de ejecución.}