Перестановка циклов

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

Например, следующий код:

for (int j=0; j<10; j++) { for (int i=0; i<20; i++) { y[i][j] = i + j; } }

в результате применения оптимизации может быть преобразован в:

for (int i=0; i<20; i++) { for (int j=0; j<10; j++) { y[i][j] = i + j; } }

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

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

for (int i=0; i<10; i++) { for (int j=0; j<20; j++) { a[i] = a[i] + b[j][i] * c[i] } }

Применение оптимизации в данном случае может улучшить производительность доступа к b[j][i], однако появятся повторные чтения a[i] и c[i] во внутреннем цикле в течение каждой итерации. В результате, эффективность работы может ухудшиться.