Почему этот код с несколькими операторами "или" немного быстрее, чем использование таблицы поиска в Java?
Глядя на вопрос о микрооптимизации, который я задал вчера ( здесь), я обнаружил нечто странное: or Оператор в Java выполняется немного быстрее, чем поиск логического значения в массиве логических значений.
В моих тестах выполняются следующие алгоритмы на long значения от 0 до 1 млрд, alg1 примерно на 2% быстрее. (Я изменил порядок, в котором тестируются алгоритмы, и получаю те же результаты). Мой вопрос: почему alg1 быстрее? Я ожидал бы, что alg2 будет немного быстрее, поскольку он использует таблицу поиска, тогда как alg1 должен выполнить 4 сравнения и 3 или операции для 75% входных данных.
private final static boolean alg1(long n)
{
int h = (int)(n & 0xF);
if(h == 0 || h == 1 || h == 4 || h == 9)
{
long tst = (long)Math.sqrt(n);
return tst*tst == n;
}
return false;
}
private final static boolean[] lookup = new boolean[16];
static
{
lookup[0] = lookup[1] = lookup[4] = lookup[9] = true;
}
private final static boolean alg2(long n)
{
if(lookup[(int)(n & 0xF)])
{
long tst = (long)Math.sqrt(n);
return tst*tst == n;
}
else
return false;
}
Если вам интересно, этот код проверяет, является ли число идеальным квадратом, и использует тот факт, что идеальные квадраты должны заканчиваться на 0, 1, 4 или 9 в гексе.
5 ответов
Загрузка некоторого случайного фрагмента данных, как правило, медленнее, чем небольшой не ветвящийся код.
Конечно, все зависит от архитектуры процессора. Ваш первый оператор if может быть реализован в виде четырех инструкций. Второму может потребоваться проверка нулевого указателя, проверка границ, а также загрузка и сравнение. Кроме того, больше кода означает больше времени компиляции и больше шансов для оптимизации каким-либо образом.
Я предполагаю, что проблема заключается в том, что проверка диапазона для массива и поиск массива реализован как вызов метода. Это, безусловно, затмевает 4 прямых сравнения. Вы смотрели на байт-код?
В текущем примере я согласен, что проверка границ - это, вероятно, то, что вас привлекает (почему JVM не оптимизирует это вне моего понимания - пример кода может быть детерминированно показан не переполненным...
Другая возможность (особенно для больших таблиц поиска) - это задержка кэша... Это зависит от размера регистров процессора и того, как JVM решит использовать их - но если байтовый массив не полностью хранится на процессоре, тогда вы ' Вы увидите снижение производительности по сравнению с простым ИЛИ, когда массив загружается в ЦП для каждой проверки.
Согласно этой статье, доступ к элементам массива "в 2 или 3 раза дороже, чем доступ к элементам, не относящимся к массиву". Ваш тест показывает, что разница может быть даже больше.
Это интересный кусок кода, но 2% - это действительно небольшая разница. Я не думаю, что вы можете сделать очень многое из этого.