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

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

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

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

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

Источник

4 ответа

Решение
while (condition) { 
  ... 
}

Процедура:

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

Процедура:

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

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

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

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

Важная заметка

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

Источник

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

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

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

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

int i = 0;
if (i++ < 1) {
    do {
        //do something
    } while (i++ < 1); 
}
Источник

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

while версия:

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

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 В версии мы должны вернуться к началу, выполнить тест, а затем вернуться к концу, когда увидим, что это не так.

Источник

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

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

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

 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 (что требуется в первом случае). Это улучшает производительность.

Источник
Другие вопросы по тегам