5 Вопрос: Почему этот код с несколькими операторами «или» немного быстрее, чем использование таблицы поиска в Java?

вопрос создан в Tue, May 23, 2017 12:00 AM

Рассматривая вопрос о микрооптимизации, который я задал вчера ( здесь ), я нашел что-то странное: оператор 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 в шестнадцатеричном виде.     

9
5 ответов                              5                         

Загрузка некоторого случайного фрагмента данных, как правило, медленнее, чем небольшой не ветвящийся код.

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

    
8
2008-11-18 16: 02: 39Z
  1. Простой поиск на уровне процессора обычно немного быстрее, чем даже небольшая строка вычисления. Я думаю, что это проверка границ /другие накладные расходы, которые Java добавляет для управления процессом.
    2008-11-18 16: 10: 35Z
  2. проверка границ FTL!
    2008-11-18 20: 06: 56Z

Я бы предположил , что проблема заключается в том, что проверка диапазона для массива и поиск массива реализован как вызов метода. Это, конечно, затмило бы 4 прямые сравнения. Вы смотрели на байт-код?

    
3
2008-11-18 15: 41: 29Z

В текущем примере я согласен с тем, что проверка границ - это, вероятно, то, что вас привлекает (почему JVM не оптимизирует это, мне не подходит - пример кода может быть детерминированно показан не переполненным ...

Еще одна возможность (особенно для больших таблиц поиска) - задержка кэша ... Это зависит от размера регистров процессоров и того, как JVM решит их использовать, но если байтовый массив не полностью хранится на процессоре, тогда вы увидите снижение производительности по сравнению с простым ИЛИ, когда массив загружается в ЦП для каждой проверки.

    
1
2008-11-20 03: 52: 06Z

Это интересный фрагмент кода, но 2% - это действительно небольшая разница. Я не думаю, что вы можете сделать очень многое из этого.

    
0
2008-11-19 00: 11: 28Z
  1. да, это не настолько важно, что я собираюсь изменить способ, которым я пишу код или что-то еще ... мне было просто любопытно, на интеллектуальном уровне, почему это может быть так.
    2008-11-19 13: 34: 21Z
источник размещен Вот