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

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

72 голосов
/ 29 сентября 2019

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

Вот код теста 

@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

Ответы [ 2 ]

81 голосов
/ 30 сентября 2019

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

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

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

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

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

newArray

newArray2

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

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

EDIT

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

17 голосов
/ 29 сентября 2019

Примечание в Oracle Docs по инструкции 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  __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>

И для 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)
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...