Почему Java переключается на смежные целые, кажется, работает быстрее с добавленными случаями?

Я работаю над некоторым Java-кодом, который должен быть сильно оптимизирован, так как он будет выполняться в горячих функциях, которые вызываются во многих точках моей основной логики программы. Часть этого кода включает в себя умножение double переменные по 10 возводится в произвольный неотрицательный intexponents. Один быстрый способ (изменить: но не самый быстрый из возможных, см. Обновление 2 ниже), чтобы получить умноженное значение, заключается в switch на exponent:

double multiplyByPowerOfTen(final double d, final int exponent) {
   switch (exponent) {
      case 0:
         return d;
      case 1:
         return d*10;
      case 2:
         return d*100;
      // ... same pattern
      case 9:
         return d*1000000000;
      case 10:
         return d*10000000000L;
      // ... same pattern with long literals
      case 18:
         return d*1000000000000000000L;
      default:
         throw new ParseException("Unhandled power of ten " + power, 0);
   }
}

Прокомментированные эллипсы выше указывают на то, что caseint константы продолжают увеличиваться на 1, так что на самом деле есть 19 cases в приведенном фрагменте кода. Так как я не был уверен, понадобятся ли мне все силы 10 в case заявления 10 через 18Я запустил несколько микробенчмарков, сравнивая время для выполнения 10 миллионов операций с этим switch заявление против switch только с cases 0 через 9exponent ограничено 9 или меньше, чтобы избежать поломки урезанного switch). Я получил довольно неожиданный (для меня, по крайней мере!) Результат, чем дольше switch с более case заявления на самом деле бежали быстрее

На жаворонке я попытался добавить еще больше cases, которые только что вернули фиктивные значения, и обнаружили, что я могу заставить переключатель работать еще быстрее с объявленным 22-27 cases (даже если эти фиктивные случаи никогда не выполняются, пока выполняется код). (Снова, cases были добавлены непрерывным способом, увеличивая предыдущий case постоянный 1.) Эти различия во времени выполнения не очень значительны: для случайного exponent между 0 а также 10манекен проложен switch оператор завершает 10 миллионов выполнений за 1,49 с против 1,54 с для незакрепленной версии, что дает общую экономию в 5 нс на выполнение. Таким образом, не та вещь, которая делает одержимость из-за switch Заявление стоит усилий с точки зрения оптимизации. Но я все еще нахожу любопытным и нелогичным, что switch не становится медленнее (или, возможно, в лучшем случае поддерживает постоянное время O(1)) для выполнения как более cases добавлены к этому.

переключить результаты тестирования

Это результаты, которые я получил от работы с различными ограничениями на случайно сгенерированные exponent ценности. Я не включил результаты вплоть до 1 для exponent предел, но общая форма кривой остается той же, с гребнем вокруг отметки 12-17 и долиной между 18-28. Все тесты выполнялись в JUnitBenchmarks с использованием общих контейнеров для случайных значений, чтобы обеспечить идентичные входные данные тестирования. Я также выполнил тесты в порядке от самого длинного switch заявление в кратчайшие сроки, и наоборот, чтобы попытаться исключить возможность проблем, связанных с заказом теста. Я поместил свой тестовый код в репозиторий github, если кто-то хочет попытаться воспроизвести эти результаты.

Итак, что здесь происходит? Некоторые капризы моей архитектуры или микростандартной конструкции? Или это Java switch действительно немного быстрее, чтобы выполнить в 18 в 28case диапазон, чем это от 11 вплоть до 17?

github тест репо "коммутатор-эксперимент"

ОБНОВЛЕНИЕ: Я немного очистил библиотеку сравнительного анализа и добавил текстовый файл в / results с некоторым выводом в более широком диапазоне. exponent ценности. Я также добавил опцию в коде тестирования, чтобы не бросать Exception от default, но это не влияет на результаты.

ОБНОВЛЕНИЕ 2: нашел довольно хорошее обсуждение этой проблемы еще в 2009 году на форуме xkcd здесь: http://forums.xkcd.com/viewtopic.php?f=11&t=33524. Обсуждение использования ОП Array.binarySearch() дал мне идею простой реализации на основе массива шаблона возведения в степень выше. Там нет необходимости для двоичного поиска, так как я знаю, что записи в array являются. Кажется, он работает примерно в 3 раза быстрее, чем при использовании switchочевидно, за счет некоторого потока управления, который switch дает. Этот код был также добавлен в репозиторий github.

5 ответов

Решение

Как указано в другом ответе, поскольку значения регистра являются смежными (в отличие от разреженных), сгенерированный байт-код для ваших различных тестов использует таблицу переключателей (инструкция байт-кода) tableswitch).

Однако, как только JIT начинает свою работу и компилирует байт-код в сборку, tableswitch инструкция не всегда приводит к массиву указателей: иногда таблица переключателей преобразуется в нечто похожее на lookupswitch (похоже на if / else if состав).

Декомпиляция сборки, сгенерированной JIT (горячая точка JDK 1.7), показывает, что она использует последовательность if/else, если при наличии 17 случаев или менее, массив указателей, когда их больше 18 (более эффективно).

Причина, по которой используется это магическое число 18, сводится к значению по умолчанию MinJumpTableSize Флаг JVM (около строки 352 в коде).

Я поднял проблему в списке компиляторов горячей точки, и это, кажется, наследие прошлого тестирования. Обратите внимание, что это значение по умолчанию было удалено в JDK 8 после того, как был проведен дополнительный сравнительный анализ.

Наконец, когда метод становится слишком длинным (> 25 случаев в моих тестах), он больше не связан с настройками JVM по умолчанию, что является наиболее вероятной причиной снижения производительности в этот момент.


В 5 случаях декомпилированный код выглядит следующим образом (обратите внимание на инструкции cmp/je/jg/jmp, сборка для if/goto):

[Verified Entry Point]
  # {method} 'multiplyByPowerOfTen' '(DI)D' in 'javaapplication4/Test1'
  # parm0:    xmm0:xmm0   = double
  # parm1:    rdx       = int
  #           [sp+0x20]  (sp of caller)
  0x00000000024f0160: mov    DWORD PTR [rsp-0x6000],eax
                                                ;   {no_reloc}
  0x00000000024f0167: push   rbp
  0x00000000024f0168: sub    rsp,0x10           ;*synchronization entry
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@-1 (line 56)
  0x00000000024f016c: cmp    edx,0x3
  0x00000000024f016f: je     0x00000000024f01c3
  0x00000000024f0171: cmp    edx,0x3
  0x00000000024f0174: jg     0x00000000024f01a5
  0x00000000024f0176: cmp    edx,0x1
  0x00000000024f0179: je     0x00000000024f019b
  0x00000000024f017b: cmp    edx,0x1
  0x00000000024f017e: jg     0x00000000024f0191
  0x00000000024f0180: test   edx,edx
  0x00000000024f0182: je     0x00000000024f01cb
  0x00000000024f0184: mov    ebp,edx
  0x00000000024f0186: mov    edx,0x17
  0x00000000024f018b: call   0x00000000024c90a0  ; OopMap{off=48}
                                                ;*new  ; - javaapplication4.Test1::multiplyByPowerOfTen@72 (line 83)
                                                ;   {runtime_call}
  0x00000000024f0190: int3                      ;*new  ; - javaapplication4.Test1::multiplyByPowerOfTen@72 (line 83)
  0x00000000024f0191: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffffa7]        # 0x00000000024f0140
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@52 (line 62)
                                                ;   {section_word}
  0x00000000024f0199: jmp    0x00000000024f01cb
  0x00000000024f019b: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffff8d]        # 0x00000000024f0130
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@46 (line 60)
                                                ;   {section_word}
  0x00000000024f01a3: jmp    0x00000000024f01cb
  0x00000000024f01a5: cmp    edx,0x5
  0x00000000024f01a8: je     0x00000000024f01b9
  0x00000000024f01aa: cmp    edx,0x5
  0x00000000024f01ad: jg     0x00000000024f0184  ;*tableswitch
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56)
  0x00000000024f01af: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffff81]        # 0x00000000024f0138
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@64 (line 66)
                                                ;   {section_word}
  0x00000000024f01b7: jmp    0x00000000024f01cb
  0x00000000024f01b9: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffff67]        # 0x00000000024f0128
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@70 (line 68)
                                                ;   {section_word}
  0x00000000024f01c1: jmp    0x00000000024f01cb
  0x00000000024f01c3: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffff55]        # 0x00000000024f0120
                                                ;*tableswitch
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56)
                                                ;   {section_word}
  0x00000000024f01cb: add    rsp,0x10
  0x00000000024f01cf: pop    rbp
  0x00000000024f01d0: test   DWORD PTR [rip+0xfffffffffdf3fe2a],eax        # 0x0000000000430000
                                                ;   {poll_return}
  0x00000000024f01d6: ret    

В 18 случаях сборка выглядит следующим образом (обратите внимание на массив указателей, который используется и устраняет необходимость во всех сравнениях: jmp QWORD PTR [r8+r10*1] переходит прямо к правильному умножению) - вот вероятная причина повышения производительности:

[Verified Entry Point]
  # {method} 'multiplyByPowerOfTen' '(DI)D' in 'javaapplication4/Test1'
  # parm0:    xmm0:xmm0   = double
  # parm1:    rdx       = int
  #           [sp+0x20]  (sp of caller)
  0x000000000287fe20: mov    DWORD PTR [rsp-0x6000],eax
                                                ;   {no_reloc}
  0x000000000287fe27: push   rbp
  0x000000000287fe28: sub    rsp,0x10           ;*synchronization entry
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@-1 (line 56)
  0x000000000287fe2c: cmp    edx,0x13
  0x000000000287fe2f: jae    0x000000000287fe46
  0x000000000287fe31: movsxd r10,edx
  0x000000000287fe34: shl    r10,0x3
  0x000000000287fe38: movabs r8,0x287fd70       ;   {section_word}
  0x000000000287fe42: jmp    QWORD PTR [r8+r10*1]  ;*tableswitch
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56)
  0x000000000287fe46: mov    ebp,edx
  0x000000000287fe48: mov    edx,0x31
  0x000000000287fe4d: xchg   ax,ax
  0x000000000287fe4f: call   0x00000000028590a0  ; OopMap{off=52}
                                                ;*new  ; - javaapplication4.Test1::multiplyByPowerOfTen@202 (line 96)
                                                ;   {runtime_call}
  0x000000000287fe54: int3                      ;*new  ; - javaapplication4.Test1::multiplyByPowerOfTen@202 (line 96)
  0x000000000287fe55: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe8b]        # 0x000000000287fce8
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@194 (line 92)
                                                ;   {section_word}
  0x000000000287fe5d: jmp    0x000000000287ff16
  0x000000000287fe62: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe86]        # 0x000000000287fcf0
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@188 (line 90)
                                                ;   {section_word}
  0x000000000287fe6a: jmp    0x000000000287ff16
  0x000000000287fe6f: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe81]        # 0x000000000287fcf8
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@182 (line 88)
                                                ;   {section_word}
  0x000000000287fe77: jmp    0x000000000287ff16
  0x000000000287fe7c: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe7c]        # 0x000000000287fd00
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@176 (line 86)
                                                ;   {section_word}
  0x000000000287fe84: jmp    0x000000000287ff16
  0x000000000287fe89: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe77]        # 0x000000000287fd08
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@170 (line 84)
                                                ;   {section_word}
  0x000000000287fe91: jmp    0x000000000287ff16
  0x000000000287fe96: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe72]        # 0x000000000287fd10
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@164 (line 82)
                                                ;   {section_word}
  0x000000000287fe9e: jmp    0x000000000287ff16
  0x000000000287fea0: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe70]        # 0x000000000287fd18
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@158 (line 80)
                                                ;   {section_word}
  0x000000000287fea8: jmp    0x000000000287ff16
  0x000000000287feaa: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe6e]        # 0x000000000287fd20
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@152 (line 78)
                                                ;   {section_word}
  0x000000000287feb2: jmp    0x000000000287ff16
  0x000000000287feb4: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe24]        # 0x000000000287fce0
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@146 (line 76)
                                                ;   {section_word}
  0x000000000287febc: jmp    0x000000000287ff16
  0x000000000287febe: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe6a]        # 0x000000000287fd30
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@140 (line 74)
                                                ;   {section_word}
  0x000000000287fec6: jmp    0x000000000287ff16
  0x000000000287fec8: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe68]        # 0x000000000287fd38
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@134 (line 72)
                                                ;   {section_word}
  0x000000000287fed0: jmp    0x000000000287ff16
  0x000000000287fed2: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe66]        # 0x000000000287fd40
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@128 (line 70)
                                                ;   {section_word}
  0x000000000287feda: jmp    0x000000000287ff16
  0x000000000287fedc: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe64]        # 0x000000000287fd48
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@122 (line 68)
                                                ;   {section_word}
  0x000000000287fee4: jmp    0x000000000287ff16
  0x000000000287fee6: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe62]        # 0x000000000287fd50
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@116 (line 66)
                                                ;   {section_word}
  0x000000000287feee: jmp    0x000000000287ff16
  0x000000000287fef0: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe60]        # 0x000000000287fd58
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@110 (line 64)
                                                ;   {section_word}
  0x000000000287fef8: jmp    0x000000000287ff16
  0x000000000287fefa: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe5e]        # 0x000000000287fd60
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@104 (line 62)
                                                ;   {section_word}
  0x000000000287ff02: jmp    0x000000000287ff16
  0x000000000287ff04: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe5c]        # 0x000000000287fd68
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@98 (line 60)
                                                ;   {section_word}
  0x000000000287ff0c: jmp    0x000000000287ff16
  0x000000000287ff0e: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe12]        # 0x000000000287fd28
                                                ;*tableswitch
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56)
                                                ;   {section_word}
  0x000000000287ff16: add    rsp,0x10
  0x000000000287ff1a: pop    rbp
  0x000000000287ff1b: test   DWORD PTR [rip+0xfffffffffd9b00df],eax        # 0x0000000000230000
                                                ;   {poll_return}
  0x000000000287ff21: ret    

И, наконец, сборка с 30 корпусами (ниже) выглядит аналогично 18 корпусам, за исключением дополнительного movapd xmm0,xmm1 это появляется в середине кода, как заметил @cHao, однако наиболее вероятной причиной снижения производительности является то, что метод слишком длинный, чтобы его можно было встроить с настройками JVM по умолчанию:

[Verified Entry Point]
  # {method} 'multiplyByPowerOfTen' '(DI)D' in 'javaapplication4/Test1'
  # parm0:    xmm0:xmm0   = double
  # parm1:    rdx       = int
  #           [sp+0x20]  (sp of caller)
  0x0000000002524560: mov    DWORD PTR [rsp-0x6000],eax
                                                ;   {no_reloc}
  0x0000000002524567: push   rbp
  0x0000000002524568: sub    rsp,0x10           ;*synchronization entry
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@-1 (line 56)
  0x000000000252456c: movapd xmm1,xmm0
  0x0000000002524570: cmp    edx,0x1f
  0x0000000002524573: jae    0x0000000002524592  ;*tableswitch
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56)
  0x0000000002524575: movsxd r10,edx
  0x0000000002524578: shl    r10,0x3
  0x000000000252457c: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe3c]        # 0x00000000025243c0
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@364 (line 118)
                                                ;   {section_word}
  0x0000000002524584: movabs r8,0x2524450       ;   {section_word}
  0x000000000252458e: jmp    QWORD PTR [r8+r10*1]  ;*tableswitch
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56)
  0x0000000002524592: mov    ebp,edx
  0x0000000002524594: mov    edx,0x31
  0x0000000002524599: xchg   ax,ax
  0x000000000252459b: call   0x00000000024f90a0  ; OopMap{off=64}
                                                ;*new  ; - javaapplication4.Test1::multiplyByPowerOfTen@370 (line 120)
                                                ;   {runtime_call}
  0x00000000025245a0: int3                      ;*new  ; - javaapplication4.Test1::multiplyByPowerOfTen@370 (line 120)
  0x00000000025245a1: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe27]        # 0x00000000025243d0
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@358 (line 116)
                                                ;   {section_word}
  0x00000000025245a9: jmp    0x0000000002524744
  0x00000000025245ae: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe22]        # 0x00000000025243d8
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@348 (line 114)
                                                ;   {section_word}
  0x00000000025245b6: jmp    0x0000000002524744
  0x00000000025245bb: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe1d]        # 0x00000000025243e0
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@338 (line 112)
                                                ;   {section_word}
  0x00000000025245c3: jmp    0x0000000002524744
  0x00000000025245c8: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe18]        # 0x00000000025243e8
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@328 (line 110)
                                                ;   {section_word}
  0x00000000025245d0: jmp    0x0000000002524744
  0x00000000025245d5: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe13]        # 0x00000000025243f0
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@318 (line 108)
                                                ;   {section_word}
  0x00000000025245dd: jmp    0x0000000002524744
  0x00000000025245e2: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe0e]        # 0x00000000025243f8
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@308 (line 106)
                                                ;   {section_word}
  0x00000000025245ea: jmp    0x0000000002524744
  0x00000000025245ef: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe09]        # 0x0000000002524400
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@298 (line 104)
                                                ;   {section_word}
  0x00000000025245f7: jmp    0x0000000002524744
  0x00000000025245fc: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe04]        # 0x0000000002524408
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@288 (line 102)
                                                ;   {section_word}
  0x0000000002524604: jmp    0x0000000002524744
  0x0000000002524609: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffdff]        # 0x0000000002524410
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@278 (line 100)
                                                ;   {section_word}
  0x0000000002524611: jmp    0x0000000002524744
  0x0000000002524616: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffdfa]        # 0x0000000002524418
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@268 (line 98)
                                                ;   {section_word}
  0x000000000252461e: jmp    0x0000000002524744
  0x0000000002524623: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffd9d]        # 0x00000000025243c8
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@258 (line 96)
                                                ;   {section_word}
  0x000000000252462b: jmp    0x0000000002524744
  0x0000000002524630: movapd xmm0,xmm1
  0x0000000002524634: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe0c]        # 0x0000000002524448
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@242 (line 92)
                                                ;   {section_word}
  0x000000000252463c: jmp    0x0000000002524744
  0x0000000002524641: movapd xmm0,xmm1
  0x0000000002524645: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffddb]        # 0x0000000002524428
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@236 (line 90)
                                                ;   {section_word}
  0x000000000252464d: jmp    0x0000000002524744
  0x0000000002524652: movapd xmm0,xmm1
  0x0000000002524656: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffdd2]        # 0x0000000002524430
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@230 (line 88)
                                                ;   {section_word}
  0x000000000252465e: jmp    0x0000000002524744
  0x0000000002524663: movapd xmm0,xmm1
  0x0000000002524667: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffdc9]        # 0x0000000002524438
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@224 (line 86)
                                                ;   {section_word}

[etc.]

  0x0000000002524744: add    rsp,0x10
  0x0000000002524748: pop    rbp
  0x0000000002524749: test   DWORD PTR [rip+0xfffffffffde1b8b1],eax        # 0x0000000000340000
                                                ;   {poll_return}
  0x000000000252474f: ret    

Переключение регистра происходит быстрее, если значения регистра находятся в узком диапазоне, например,

case 1:
case 2:
case 3:
..
..
case n:

Потому что в этом случае компилятор может избежать выполнения сравнения для каждого сегмента case в операторе switch. Компилятор создает таблицу переходов, которая содержит адреса действий, которые должны быть выполнены на разных участках. Значением, на котором выполняется переключение, манипулируют, чтобы преобразовать его в индекс в jump table, В этой реализации время, затрачиваемое в операторе switch, намного меньше, чем время, затрачиваемое в эквивалентном каскаде оператора if-else-if. Кроме того, время, необходимое в операторе switch, не зависит от количества ветвей регистра в операторе switch.

Как указано в википедии об операторе switch в разделе Compilation.

Если диапазон входных значений определенно "мал" и имеет только несколько пробелов, некоторые компиляторы, которые включают оптимизатор, могут фактически реализовать оператор switch в виде таблицы ветвления или массива указателей индексированных функций вместо длинного ряда условных инструкций. Это позволяет оператору switch мгновенно определять, какую ветвь выполнять, не просматривая список сравнений.

Ответ лежит в байт-коде:

SwitchTest10.java

public class SwitchTest10 {

    public static void main(String[] args) {
        int n = 0;

        switcher(n);
    }

    public static void switcher(int n) {
        switch(n) {
            case 0: System.out.println(0);
                    break;

            case 1: System.out.println(1);
                    break;

            case 2: System.out.println(2);
                    break;

            case 3: System.out.println(3);
                    break;

            case 4: System.out.println(4);
                    break;

            case 5: System.out.println(5);
                    break;

            case 6: System.out.println(6);
                    break;

            case 7: System.out.println(7);
                    break;

            case 8: System.out.println(8);
                    break;

            case 9: System.out.println(9);
                    break;

            case 10: System.out.println(10);
                    break;

            default: System.out.println("test");
        }
    }       
}

Соответствующий байт-код; показаны только соответствующие части:

public static void switcher(int);
  Code:
   0:   iload_0
   1:   tableswitch{ //0 to 10
        0: 60;
        1: 70;
        2: 80;
        3: 90;
        4: 100;
        5: 110;
        6: 120;
        7: 131;
        8: 142;
        9: 153;
        10: 164;
        default: 175 }

SwitchTest22.java:

public class SwitchTest22 {

    public static void main(String[] args) {
        int n = 0;

        switcher(n);
    }

    public static void switcher(int n) {
        switch(n) {
            case 0: System.out.println(0);
                    break;

            case 1: System.out.println(1);
                    break;

            case 2: System.out.println(2);
                    break;

            case 3: System.out.println(3);
                    break;

            case 4: System.out.println(4);
                    break;

            case 5: System.out.println(5);
                    break;

            case 6: System.out.println(6);
                    break;

            case 7: System.out.println(7);
                    break;

            case 8: System.out.println(8);
                    break;

            case 9: System.out.println(9);
                    break;

            case 100: System.out.println(10);
                    break;

            case 110: System.out.println(10);
                    break;
            case 120: System.out.println(10);
                    break;
            case 130: System.out.println(10);
                    break;
            case 140: System.out.println(10);
                    break;
            case 150: System.out.println(10);
                    break;
            case 160: System.out.println(10);
                    break;
            case 170: System.out.println(10);
                    break;
            case 180: System.out.println(10);
                    break;
            case 190: System.out.println(10);
                    break;
            case 200: System.out.println(10);
                    break;
            case 210: System.out.println(10);
                    break;

            case 220: System.out.println(10);
                    break;

            default: System.out.println("test");
        }
    }       
}

Соответствующий байт-код; опять же, показаны только соответствующие части:

public static void switcher(int);
  Code:
   0:   iload_0
   1:   lookupswitch{ //23
        0: 196;
        1: 206;
        2: 216;
        3: 226;
        4: 236;
        5: 246;
        6: 256;
        7: 267;
        8: 278;
        9: 289;
        100: 300;
        110: 311;
        120: 322;
        130: 333;
        140: 344;
        150: 355;
        160: 366;
        170: 377;
        180: 388;
        190: 399;
        200: 410;
        210: 421;
        220: 432;
        default: 443 }

В первом случае с узкими диапазонами скомпилированный байт-код использует tableswitch, Во втором случае скомпилированный байт-код использует lookupswitch,

В tableswitch целочисленное значение в верхней части стека используется для индексации таблицы, чтобы найти цель перехода / перехода. Этот переход / ветвь затем выполняется немедленно. Следовательно, это O(1) операция.

lookupswitch сложнее. В этом случае целочисленное значение необходимо сравнивать со всеми ключами в таблице, пока не будет найден правильный ключ. После того, как ключ найден, цель перехода / прыжка (которой сопоставлен этот ключ) используется для прыжка. Таблица, которая используется в lookupswitch сортируется и алгоритм бинарного поиска может быть использован, чтобы найти правильный ключ. Производительность для бинарного поиска O(log n) и весь процесс также O(log n) потому что прыжок еще O(1), Таким образом, причина того, что производительность в случае разреженных диапазонов ниже, заключается в том, что сначала нужно найти правильный ключ, потому что вы не можете напрямую вносить в таблицу данные.

Если есть редкие значения, и у вас есть только tableswitch использовать, таблица будет по существу содержать фиктивные записи, которые указывают на default вариант. Например, предполагая, что последняя запись в SwitchTest10.java было 21 вместо 10, ты получаешь:

public static void switcher(int);
  Code:
   0:   iload_0
   1:   tableswitch{ //0 to 21
        0: 104;
        1: 114;
        2: 124;
        3: 134;
        4: 144;
        5: 154;
        6: 164;
        7: 175;
        8: 186;
        9: 197;
        10: 219;
        11: 219;
        12: 219;
        13: 219;
        14: 219;
        15: 219;
        16: 219;
        17: 219;
        18: 219;
        19: 219;
        20: 219;
        21: 208;
        default: 219 }

Таким образом, компилятор в основном создает эту огромную таблицу, содержащую фиктивные записи между пробелами, указывающие на цель ветвления default инструкция. Даже если нет default, он будет содержать записи, указывающие на инструкцию после блока переключателей. Я провел несколько базовых тестов и обнаружил, что если разрыв между последним индексом и предыдущим (9) больше, чем 35, он использует lookupswitch вместо tableswitch,

Поведение switch оператор определен в Спецификации виртуальной машины Java (§3.10):

Там, где случаи переключения редки, табличное представление инструкции tablewitch становится неэффективным с точки зрения пространства. Вместо этого может использоваться инструкция lookupswitch. Инструкция lookupswitch объединяет клавиши int (значения меток регистра) с целевыми смещениями в таблице. Когда выполняется команда lookupswitch, значение выражения switch сравнивается с ключами в таблице. Если один из ключей соответствует значению выражения, выполнение продолжается с соответствующим целевым смещением. Если ни один из ключей не соответствует, выполнение продолжается с целью по умолчанию. [...]

Поскольку на этот вопрос уже дан ответ (более или менее), вот несколько советов. использование

private static final double[] mul={1d, 10d...};
static double multiplyByPowerOfTen(final double d, final int exponent) {
      if (exponent<0 || exponent>=mul.length) throw new ParseException();//or just leave the IOOBE be
      return mul[exponent]*d;
}

Этот код использует значительно меньше IC (кэш инструкций) и всегда будет встроен. Массив будет в кеше данных L1, если код горячий. Таблица поиска - почти всегда выигрыш. (особенно на микробенчмарках:D)

Изменить: если вы хотите, чтобы метод был "горячим", рассмотрите не быстрые пути, как throw new ParseException() быть как можно короче минимума или переместить их в отдельный статический метод (следовательно, сделать их короткими как минимум). То есть throw new ParseException("Unhandled power of ten " + power, 0); это слабая идея, поскольку она потребляет много встроенного бюджета для кода, который может быть просто интерпретирован - конкатенация строк довольно многословна в байт-коде. Больше информации и реальный случай с ArrayList

На основе источника javac вы можете написать переключатель таким образом, чтобы он использовал tableswitch.

Мы можем использовать расчет из источника javac для расчета стоимости для вашего второго примера.

      lo = 0
hi = 220
nlabels = 24

table_space_cost = 4 + hi - lo + 1
table_time_cost = 3
lookup_space_cost = 3 + 2 * nlabels
lookup_time_cost = nlabels

table_cost = table_space_cost + 3 * table_time_cost // 234
lookup_cost = lookup_space_cost + 3 * lookup_time_cos // 123

Здесь стоимость tablewitch выше (234), чем lookupswitch (123), и поэтому lookupswitch будет выбран в качестве кода операции для этого оператора switch.

Другие вопросы по тегам