Вопросы Теги

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

http://someurl.com?key=value&keynovalue&keyemptyvalue=&&keynovalue=nowhasvalue#somehash
  • Параллельная пара ключ / значение (?param=value)
  • Клавиши без значения (?param: знак равенства или значение)
  • Клавиши w / пустое значение (?param=: знак равенства, но нет значения справа от знака равенства)
  • Повторные клавиши (?param=1&param=2)
  • Удаляет пустые ключи (?&&: нет ключа или значения)

Код: 

  • var queryString = window.location.search || '';
var keyValPairs = [];
var params      = {};
queryString     = queryString.substr(1);

if (queryString.length)
{
   keyValPairs = queryString.split('&');
   for (pairNum in keyValPairs)
   {
      var key = keyValPairs[pairNum].split('=')[0];
      if (!key.length) continue;
      if (typeof params[key] === 'undefined')
         params[key] = [];
      params[key].push(keyValPairs[pairNum].split('=')[1]);
   }
}

Как позвонить: 

  • params['key'];  // returns an array of values (1..n)

Выход: 

  • key            ["value"]
keyemptyvalue  [""]
keynovalue     [undefined, "nowhasvalue"]
64
задан ilkkachu 30 September 2019 в 08:57
поделиться

2 ответа

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

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

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

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

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

newArray

newArray2

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

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

РЕДАКТИРОВАНИЕ

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

81
ответ дан 24 November 2019 в 12:44
поделиться

В примечании в Документы Oracle под multianewarray инструкция говорится:

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

Далее:

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

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

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

Для эти 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)
17
ответ дан 24 November 2019 в 12:44
поделиться
Другие вопросы по тегам:

Похожие вопросы: