В информатике инверсия цикла — это оптимизация компилятора и преобразование цикла , в котором цикл while заменяется блоком if, содержащим цикл do..while . При правильном использовании может повысить производительность за счет конвейеризации инструкций .
int i , a [ 100 ]; i = 0 ; пока ( i < 100 ) { a [ i ] = 0 ; i ++ ; } эквивалентно:
int i , a [ 100 ]; i = 0 ; если ( i < 100 ) { do { a [ i ] = 0 ; i ++ ; } while ( i < 100 ); } Несмотря на кажущуюся большую сложность второго примера, на современных процессорах он может работать быстрее, поскольку они используют конвейер инструкций . По своей природе любой скачок в коде вызывает остановку конвейера , что наносит ущерб производительности.
Кроме того, инверсия цикла обеспечивает безопасное перемещение кода, инвариантное к циклу .
я := 0 L1: если i >= 100 перейти к L2 а[я] := 0 я := я + 1 перейти на L1 L2:
Если бы i был инициализирован со значением 100, инструкции, выполняемые во время выполнения, были бы следующими:
если я >= 100 перейти к L2Предположим, что i было инициализировано некоторым значением меньше 100. Теперь давайте посмотрим на инструкции, выполняемые в момент после того, как i было увеличено до 99 в цикле:
перейти на L1 если я < 100 а[я] := 0 я := я + 1 перейти на L1 если я >= 100 перейти к L2 <<в L2>>Теперь давайте посмотрим на оптимизированную версию:
я := 0 если i >= 100 перейти к L2 L1: а[i] := 0 я := я + 1 если i < 100 перейти к L1 L2:
Давайте снова посмотрим на инструкции, выполняемые, если i инициализировано значением 100:
если я >= 100 перейти к L2Мы не потратили ни одного цикла по сравнению с исходной версией. Теперь рассмотрим случай, когда i увеличилось до 99:
если я < 100 перейти на L1 а[я] := 0 я := я + 1 если я < 100 <<в L2>>Как вы можете видеть, при выполнении были устранены два goto (и, следовательно, два простоя конвейера).