Там три с половиной алгоритма. Третий оптимален по свопам для c == 0, для других c его кажется несложно допилить, но мне влом. Третий-с-половиной ещё и кэш не так убивает.

А, я не прав был. То есть он говорит, что в 60% случаев там вообще получится один цикл (прыгающий как безумный по всему массиву), и в остальных случаях локальность будет только на первой итерации обычно, но "It [loop fusion] is, nevertheless, an important technique that is worth demonstrating" =) Типа, его прёт, что её можно сделать достаточно генерик и без залезания в нутро компилятора, и она будет работать быстро!

Это потому что он считает в том числе и moves to/from the temporary variable.

Посмотри внимательно на первые шесть строк кода на 194 странице. Это весь алгортм, в оставшихся строках он вычисляет новое положение границы между a и b. Ну, плюс do_cycle имплементирован ранее - он тупо сдвигает циклически фигню используя особый итератор. Ну, берём первый элемент, он должен попасть куда-то там, но там уже есть элемент, он тоже в результате должен попасть куда-нибудь, и так далее, формулка и имплементация этого итератора -- на 163 странице. Ну и вот, вся магия (которую я не до конца понимаю) состоит в утверждении, что первые GCD(m - f, l - m) элементов обязательно принадлежат разным циклам и больше циклов у нас нет, то есть если мы вызовем do_cycle для них по очереди, то всё окажется на своих местах и каждый элемент будет считан/записан ровно один раз.

У него в оценке времени появляется GCD потому что do_cycle для цикла длины n производит дополнительно n-1 чтений-записей во временную переменную, ну и вот он утверждает, что если циклов -- GCD(a, b), то этих дополнительных moves будет как раз a + b - GCD(a, b) если я ничего не путаю, но вообще нам это совершенно неважно.