Код быстрее с ненужным условным?

У меня есть следующая функция java, чтобы подсчитать общие элементы в двух отсортированных массивах. Обратите внимание на строку с вопросительным знаком.Код быстрее с ненужным условным?

public static int overlap(int[] a, int[] b) 
{ 
    int i = 0, j = 0; 

    int res = 0; 

    while(i < a.length && j < b.length) 
    { 
     if(a[i] > b[j]) 
      j ++; 
     else if(a[i] < b[j]) 
      i ++; 
     else if(a[i] == b[j]) // ? 
     { 
      res ++; 
      i ++; 
      j ++; 
     } 
    } 

    return res; 
}

Очевидно, что этот последний оператор if не должен быть там: в этой точке мы знаем, что эти два значения равны. Однако, когда я проверяю скорость (я проверял, имеет ли порядок проверок какой-либо разницы), метод с избыточной проверкой неизменно быстрее, чем без (иногда в два раза).

Что здесь происходит? Какая-то таинственная оптимизация? Я не замечаю ничего очевидного? Я использую компилятор подставки, версия 1.8. Я не могу читать байт-код, поэтому я не знаю, что происходит под капотом.

Вот полный тестовый класс: https://gist.github.com/pbloem/1523283211454ec58ce9c5b45204eebd

Bytecode: https://gist.github.com/pbloem/ce4f6758f0bb1424c155c26e83ca88a1

источник

2016-09-23 Peter

Я думаю, было бы полезно, если бы вы отметили язык. Для меня это похоже на Java. –

@HorseFace Must've удалил тег случайно. Благодарю. – Peter

_Possibly_ related: [Branch Prediction] (http://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array) – noahnu

Возможно JIT порядок перекачка «если» s, чтобы получить лучшую производительность, но не может менять порядок просто «другое» (без " if ") с другим« if »в начале, поэтому, когда вы добавили« if »после« else », он попробовал это как первую проверку, и если перекрытие массива похоже на% 90, тогда оно может сохранить это последнее« если », в первую очередь.

if(a[i] == b[j]) // say %70 probability after N iterations 
    {     // or less randomized branching 
     res ++; 
     i ++; 
     j ++; 
    } 
    else if(a[i] > b[j]) // %20 probability, medium branching 
     j ++; 
    else if(a[i] < b[j]) // %10, totally random branching, not predictable 
     i ++;

возможно при заказе массивы

а> б или б <

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

Когда есть, если + if + else, JIT может не предсказать, что вы имеете в виду. Добавляя равноценность, вы эллимизируете много случаев, кроме уравнения.

Не могли бы вы попросить упорядоченный массив и полностью рандомизированный массив?

Или это просто помогает предсказателю ветки процессора, поскольку @noahnu говорит в комментариях.

источник

2016-09-23 15:45:37

Я не думаю, что JIT может переупорядочить это из-за того, что параметры функции доступны для других потоков. –

Но нет никакой явной синхронизации в любом случае. Два кода должны действовать одинаково для всех значений i и j. –

Hogwash !! Что, если вызывающий объект этой функции только что запустил поток, который изменил 'a' и' b'? –

-1

С помощью System.currentTimeMillis() вы не можете получить точное истекшее время программы, поскольку иногда это может быть неправильно из-за оптимизации JIT. Попробуйте использовать System.nanoTime().

Также сделайте переменные, используемые при расчете времени, как глобальную переменную для надлежащего микро-теста.

double sumWith = 0.0; double sumWithout = 0.0;

источник

2016-09-23 16:12:07

Код быстрее с ненужным условным?

ответ

Смежные вопросы