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

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

Литература

• Альфред Ахо, Моника Лам, Рави Сети, Джеффри Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е издание. — М.: «Вильямс», 2008. — 1184 с. — 1500 экз. — ISBN 978-5-8459-1349-4.
• Steven S. Muchnick. Advanced Compiler Design and Implementation. — 5-е издание. — San Francisco: Morgan Kaufmann Publishers, 1997. — 856 с. — ISBN 1-55860-320-4.
• Kennedy, Ken; & Allen, Randy. Optimizing Compilers for Modern Architectures: A Dependence-based Approach (англ.). — Morgan Kaufmann, 2001. — ISBN 1-55860-286-0.