Почему выделение одного двумерного массива занимает больше времени, чем циклическое выделение нескольких одномерных массивов одинакового общего размера и формы? - программирование
Подтвердить что ты не робот

Почему выделение одного двумерного массива занимает больше времени, чем циклическое выделение нескольких одномерных массивов одинакового общего размера и формы?

Я думал, что будет быстрее создать напрямую, но на самом деле, добавление циклов занимает только половину времени. Что случилось, что так сильно замедлилось?

Вот тестовый код

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

}

Результаты теста следующие.

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

Тестовая среда выглядит следующим образом

Версия JMH: 1.21

Версия виртуальной машины: JDK 1.8.0_212, 64-разрядная серверная виртуальная машина OpenJDK, 25.212-b04

4b9b3361

ОТВЕТЫ

Ответ 1

В Java есть отдельная инструкция для выделения многомерных массивов байт-кода - multianewarray.

  • В тесте newArray используется байт-код multianewarray;
  • newArray2 вызывает простой newarray в цикле.

Проблема в том, что у HotSpot JVM нет быстрого пути* для байт-кода multianewarray. Эта инструкция всегда выполняется во время выполнения виртуальной машины. Поэтому выделение не встроено в скомпилированный код.

Первый тест должен платить за снижение производительности при переключении между контекстами Java и VM Runtime. Кроме того, общий код распределения во время выполнения виртуальной машины (записанный в C++) не так оптимизирован, как встроенное распределение в JIT-скомпилированном коде, просто потому, что он универсальный, то есть не оптимизирован для конкретного типа объекта или для конкретного сайта вызова выполняет дополнительные проверки во время выполнения и т.д.

Вот результаты профилирования обоих тестов с помощью async-profiler. Я использовал JDK 11.0.4, но для JDK 8 картина выглядит аналогично.

newArray

newArray2

В первом случае 99% времени тратится внутри OptoRuntime::multianewarray2_C - кода C++ во время выполнения виртуальной машины.

Во втором случае большая часть графика зеленого цвета, что означает, что программа работает в основном в контексте Java, фактически выполняя JIT-скомпилированный код, оптимизированный специально для данного теста.

EDIT

* Просто для уточнения: в HotSpot multianewarray не очень хорошо оптимизирован по дизайну. Достаточно дорого реализовать такую сложную операцию в обоих JIT-компиляторах должным образом, в то время как преимущества такой оптимизации были бы сомнительными: распределение многомерных массивов редко является узким местом производительности в типичном приложении.

Ответ 2

Примечание в Документах Oracle согласно инструкции multianewarray гласит:

Может быть более эффективно использовать newarray или anewarray (§newarray, §anewarray) при создании массива одного измерения.

Далее:

В тесте newArray используется инструкция байт-кода multianewarray.

В тесте newArray2 используется инструкция байт-кода anewarray.

И это то, что имеет значение. Давайте посмотрим статистику, полученную с помощью perf Linux profiler.

Для эталонного теста newArray самые горячие методы после встраивания:

....[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  [email protected]
  0.17%           libjvm.so  [email protected]
  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>

А для 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>

Как мы видим, для более медленного newArray большую часть времени тратится на код jvm (всего 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
   ...

В то время как newArray2 использует OptoRuntime::new_array_C, тратит гораздо меньше времени на выделение памяти для массивов. Общее время, проведенное в коде jvm, составляет всего 4,31%.

Бонусная статистика, полученная с помощью профилировщика 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

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

Обратите внимание на разницу в количестве циклов и инструкций.

Окружающая среда:

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)