Почему Java переключается на смежные целые, кажется, работает быстрее с добавленными случаями?
Я работаю над некоторым Java-кодом, который должен быть сильно оптимизирован, так как он будет выполняться в горячих функциях, которые вызываются во многих точках моей основной логики программы. Часть этого кода включает в себя умножение double
переменные по 10
возводится в произвольный неотрицательный int
exponent
s. Один быстрый способ (изменить: но не самый быстрый из возможных, см. Обновление 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);
}
}
Прокомментированные эллипсы выше указывают на то, что case
int
константы продолжают увеличиваться на 1, так что на самом деле есть 19 case
s в приведенном фрагменте кода. Так как я не был уверен, понадобятся ли мне все силы 10 в case
заявления 10
через 18
Я запустил несколько микробенчмарков, сравнивая время для выполнения 10 миллионов операций с этим switch
заявление против switch
только с case
s 0
через 9
(с exponent
ограничено 9 или меньше, чтобы избежать поломки урезанного switch
). Я получил довольно неожиданный (для меня, по крайней мере!) Результат, чем дольше switch
с более case
заявления на самом деле бежали быстрее
На жаворонке я попытался добавить еще больше case
s, которые только что вернули фиктивные значения, и обнаружили, что я могу заставить переключатель работать еще быстрее с объявленным 22-27 case
s (даже если эти фиктивные случаи никогда не выполняются, пока выполняется код). (Снова, case
s были добавлены непрерывным способом, увеличивая предыдущий case
постоянный 1
.) Эти различия во времени выполнения не очень значительны: для случайного exponent
между 0
а также 10
манекен проложен switch
оператор завершает 10 миллионов выполнений за 1,49 с против 1,54 с для незакрепленной версии, что дает общую экономию в 5 нс на выполнение. Таким образом, не та вещь, которая делает одержимость из-за switch
Заявление стоит усилий с точки зрения оптимизации. Но я все еще нахожу любопытным и нелогичным, что switch
не становится медленнее (или, возможно, в лучшем случае поддерживает постоянное время O(1)) для выполнения как более case
s добавлены к этому.
Это результаты, которые я получил от работы с различными ограничениями на случайно сгенерированные exponent
ценности. Я не включил результаты вплоть до 1
для exponent
предел, но общая форма кривой остается той же, с гребнем вокруг отметки 12-17 и долиной между 18-28. Все тесты выполнялись в JUnitBenchmarks с использованием общих контейнеров для случайных значений, чтобы обеспечить идентичные входные данные тестирования. Я также выполнил тесты в порядке от самого длинного switch
заявление в кратчайшие сроки, и наоборот, чтобы попытаться исключить возможность проблем, связанных с заказом теста. Я поместил свой тестовый код в репозиторий github, если кто-то хочет попытаться воспроизвести эти результаты.
Итак, что здесь происходит? Некоторые капризы моей архитектуры или микростандартной конструкции? Или это Java switch
действительно немного быстрее, чтобы выполнить в 18
в 28
case
диапазон, чем это от 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.