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

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