Что такое метод инверсии цикла?

Я просматривал документ, в котором говорится о just-in-time compiler (JIT) методы оптимизации для Java. Одним из них была "петлевая инверсия". И в документе сказано:

вы заменяете обычный while петли с do-while петли. И do-while цикл устанавливается в пределах if предложения. Эта замена приводит к двум меньшим скачкам.

как работает инверсия цикла и как она оптимизирует наш код путь?

N. B.:было бы здорово, если бы кто-нибудь мог объяснить на примере кода Java и как JIT оптимизирует его для собственного кода и почему он оптимален в современных процессорах.

4 87
javascript jit jvm machine-instruction

4 ответа:

while (condition) { 
  ... 
}

документооборот:

  1. проверяем условие;
  2. если false, перейти к вне цикла;
  3. выполнить одну итерацию;
  4. перейти к верхней.
if (condition) do {
  ...
} while (condition);

документооборот:

  1. проверяем условие;
  2. если false, перейти за пределы цикла;
  3. выполнить одну итерацию;
  4. проверяем условие;
  5. если true, перейдите к шагу 3.

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

переходы на современные конвейерные архитектуры ЦП могут быть довольно дорогими: поскольку ЦП завершает выполнение проверок перед переходом, инструкции за этим прыжком уже в середине трубопровода. Вся эта обработка должна быть отброшена, если предсказание ветви не удается. Дальнейшее выполнение откладывается, пока конвейер проходит повторную загрузку.

объяснения указанных предсказания ветвлений: для каждого вида условного перехода ЦП два инструкции, каждая из которых включает ставки о результатах. Например, вы бы поставили инструкцию, говорящую"переход если не ноль, ставки на не ноль " в конце цикла, потому что прыжок должен быть сделан на всех итерациях, кроме последней. Таким образом, процессор начинает перекачивать свой конвейер с инструкциями, следующими за целью перехода, а не за самой инструкцией перехода.

важное замечание

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

106

это может оптимизировать цикл, который всегда выполняется по крайней мере один раз.

обычный while цикл будет всегда возвращаться к началу по крайней мере один раз и перейти к концу один раз в конце. Пример простого цикла, выполняемого один раз:

int i = 0;
while (i++ < 1) {
    //do something
}

A do-while петля с другой стороны пропустит первый и последний прыжок. Вот эквивалентный цикл выше, который будет работать без прыжков:

int i = 0;
if (i++ < 1) {
    do {
        //do something
    } while (i++ < 1); 
}
23

давайте пройдемся по ним:

The while версия:

void foo(int n) {
    while (n < 10) {
       use(n);
       ++n;
    }
    done();
}
  1. Сначала мы тестируем n и перейти к done();, если условие не верно.
  2. затем мы используем и прирастить n.
  3. теперь мы возвращаемся к условию.
  4. смыть, повторить.
  5. когда условие больше не истинно, мы переходим к done().

The do-while версия:

(помните, мы на самом деле не делайте этого в исходном коде [что бы ввести проблемы обслуживания], компилятор/JIT делает это за нас.)

void foo(int n) {
    if (n < 10) {
        do {
            use(n);
            ++n;
        }
        while (n < 10);
    }
    done();
}
  1. Сначала мы тестируем n и перейти к done();, если условие не верно.
  2. затем мы используем и прирастить n.
  3. теперь мы проверяем условие и прыгаем назад, если это правда.
  4. смыть, повторить.
  5. когда условие больше не истинно, мы текем (не прыгаем) к done().

так, например, если n начинает быть 9, мы никогда не прыгаем вообще в do-while версия, а в while версия мы должны вернуться к началу, сделать тест, а потом вернуться к концу, когда мы видим, что это неправда.

3

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

этой ссылке предоставляет другой пример для инверсии цикла. В нескольких архитектурах, где декремент и сравнение реализованы как один набор команд, имеет смысл преобразовать цикл for В while с декрементом и сравнить операция.

Википедия имеет очень хороший пример, и я объясняю это здесь снова.

 int i, a[100];
  i = 0;
  while (i < 100) {
    a[i] = 0;
    i++;
  }

будет преобразован компилятором в 

  int i, a[100];
  i = 0;
  if (i < 100) {
    do {
      a[i] = 0;
      i++;
    } while (i < 100);
  }

как это переводится на производительность? Когда значение i равно 99, процессору не нужно выполнять GOTO (что требуется в первом случае). Это повышает производительность.

3