Я работаю над некоторым Java-кодом, который должен быть сильно оптимизирован, так как он будет работать в горячих функциях, которые вызываются во многих точках моей основной логики программы. Часть этого кода включает в себя умножение doubleпеременных 10на произвольные неотрицательные int exponents. Один быстрый способ (изменить: но не самый быстрый, см. Обновление 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, поэтому caseв приведенном фрагменте кода действительно 19 секунд. Так как я не был уверен , буду ли я на самом деле нужна все силы 10 в caseотчетности 10через 18, я провел несколько microbenchmarks сравнивающих время для завершения 10 миллионов операций с этим switchутверждением против switchтолько с caseS 0через 9(с exponentограниченным до 9 или меньше избегайте ломать урезанный switch). Я получил довольно неожиданный (по крайней мере, для меня) результат, который заключался в том, что чем switchбольше caseоператоров, тем быстрее они выполнялись.
В общем, я попытался добавить еще больше cases, которые только что вернули фиктивные значения, и обнаружил, что я могу заставить коммутатор работать еще быстрее с 22-27 объявленными cases (хотя эти фиктивные случаи никогда не выполняются, пока код выполняется ). (Опять же, cases были добавлены непрерывным способом путем увеличения предыдущей caseконстанты на 1.) Эти различия во времени выполнения не очень значительны: для случайного значения exponentмежду 0и 10фиктивный switchоператор завершает 10 миллионов выполнений за 1,49 с против 1,54 с для не дополненного версия, для общей экономии 5 нс за исполнение. Таким образом, не та вещь, которая делает одержимость из-заswitchЗаявление стоит усилий с точки зрения оптимизации. Но я все еще нахожу любопытным и нелогичным, что a 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 . Обсуждение использования OP Array.binarySearch()дало мне идею простой реализации на основе массива вышеописанного шаблона возведения в степень. Там нет необходимости для двоичного поиска, так как я знаю, что записи в этом array. Похоже, что он работает примерно в 3 раза быстрее, чем при использовании switch, очевидно, за счет некоторого потока управления, который switchпредоставляет. Этот код был добавлен в репозиторий github.
источник
switchутверждениях, поскольку это однозначно самое оптимальное решение. : D (Не показывай это моему примеру, пожалуйста.)lookupswitchк atableswitch. Разборка кода с помощьюjavapпокажет вам наверняка.Ответы:
Как указано в другом ответе , поскольку значения регистра являются смежными (в отличие от разреженных), сгенерированный байт-код для ваших различных тестов использует таблицу переключателей (инструкция байт-кода
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):
В 18 случаях сборка выглядит следующим образом (обратите внимание на массив указателей, который используется и устраняет необходимость во всех сравнениях:
jmp QWORD PTR [r8+r10*1]переход непосредственно к правильному умножению) - это вероятная причина повышения производительности:И, наконец, сборка с 30 случаями (ниже) выглядит аналогично 18 случаям, за исключением дополнительного,
movapd xmm0,xmm1который появляется в середине кода, как замечено @cHao - однако наиболее вероятной причиной снижения производительности является то, что метод слишком долго быть встроенным с настройками JVM по умолчанию:источник
Переключение регистра происходит быстрее, если значения регистра находятся в узком диапазоне, например,
Потому что в этом случае компилятор может избежать выполнения сравнения для каждого этапа в выражении switch. Компилятор создает таблицу переходов, которая содержит адреса действий, которые необходимо выполнить на разных участках. Значение, на котором выполняется переключение, управляется, чтобы преобразовать его в индекс в
jump table. В этой реализации время, затрачиваемое в операторе switch, намного меньше, чем время, затрачиваемое в эквивалентном каскаде оператора if-else-if. Кроме того, время, необходимое в операторе switch, не зависит от количества ветвей регистра в операторе switch.Как сказано в википедии об операторе switch в разделе Compilation.
источник
Ответ лежит в байт-коде:
SwitchTest10.java
Соответствующий байт-код; показаны только соответствующие части:
SwitchTest22.java:
Соответствующий байт-код; опять же, показаны только соответствующие части:
В первом случае с узкими диапазонами скомпилированный байт-код использует
tableswitch. Во втором случае скомпилированный байт-код используетlookupswitch.В
tableswitchэтом случае целое значение в верхней части стека используется для индексации таблицы, чтобы найти цель перехода / перехода. Этот переход / ветвь выполняется немедленно. Следовательно, этоO(1)операция.lookupswitchсложнее. В этом случае целочисленное значение необходимо сравнивать со всеми ключами в таблице, пока не будет найден правильный ключ. После того, как ключ найден, цель перехода / прыжка (которой сопоставлен этот ключ) используется для прыжка. Используемая таблицаlookupswitchотсортирована, и для поиска правильного ключа можно использовать алгоритм двоичного поиска. Производительность для бинарного поиска естьO(log n), да и весь процесс тожеO(log n), потому что скачок ещеO(1). Таким образом, причина того, что производительность в случае разреженных диапазонов ниже, заключается в том, что сначала нужно найти правильный ключ, потому что вы не можете напрямую вносить в таблицу данные.Если есть разреженные значения и вам нужно было
tableswitchиспользовать только таблицу, таблица будет содержать фиктивные записи, указывающие на этуdefaultопцию. Например, если предположить, что последняя записьSwitchTest10.javaбыла21вместо10, вы получите:Таким образом, компилятор в основном создает эту огромную таблицу, содержащую фиктивные записи между пробелами, указывающие на цель перехода
defaultинструкции. Даже если его нетdefault, он будет содержать записи, указывающие на инструкцию после блока переключателей. Я провел несколько базовых тестов и обнаружил, что если разрыв между последним индексом и предыдущим (9) больше, чем35, он используетlookupswitchвместо atableswitch.Поведение
switchоператора определено в Спецификации виртуальной машины Java (§3.10) :источник
lookupswitch?Поскольку на этот вопрос уже дан ответ (более или менее), вот несколько советов. использование
Этот код использует значительно меньше IC (кэш инструкций) и всегда будет встроен. Массив будет в кеше данных L1, если код горячий. Таблица поиска почти всегда является выигрышной. (особенно на микробенчмарках: D)
Изменить: если вы хотите, чтобы метод был «горячим», рассмотрите небыстрые пути, такие как
throw new ParseException()должны быть как можно короче, или переместите их в отдельный статический метод (следовательно, сделайте их короткими как минимум). Этоthrow new ParseException("Unhandled power of ten " + power, 0);слабая идея, так как она потребляет много встроенного бюджета для кода, который можно просто интерпретировать - конкатенация строк довольно многословна в байт-коде. Больше информации и реальный случай с ArrayListисточник