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

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

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

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

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

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

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

Источник: Википедия