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

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

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

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

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

while (condition) { 
  ... 
}

Рабочий процесс:

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

if (condition) do {
  ...
} while (condition);

Рабочий процесс:

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

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

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

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

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

Пожалуйста, не воспринимайте это как пример оптимизации на уровне исходного кода. Это было бы совершенно ошибочным, поскольку, как уже ясно из вашего вопроса, преобразование из первой формы во вторую - это то, что 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 в цикл 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 (что требуется в первом случае). Это улучшает производительность.