Duff's device или loop unrolling в Си своими руками
Выглядит ли следующий код валидным С++ кодом? Если да, то какое значение будет выведено в результате его работы?
#include
int main() {
int number = 11;
int count = number / 4;
int i = 0;
switch (number % 4) {
case 0:
do {
++i;
case 3: ++i;
case 2: ++i;
case 1: ++i;
} while (count-- > 0);
}
std::cout << i;
} С первого взгляда этот код может показаться какой-то кашей, в которой конструкция switch и цикл do-while просто наложены друг на друга. Однако с точки зрения стандарта языка , здесь все совершенно законно.
На самом деле, здесь описан цикл, в котором переменная i увеличивается на единицу number раз, и, как не сложно теперь догадаться, в данном случае программа выведет число 11. То есть код выше будет справедливо «упростить» следующим образом:
#include
int main() {
int number = 11;
int i = 0;
while (number-- > 0) {
++i;
}
std::cout << i;
} Но для чего же тогда извращаться и скрещивать do-while и switch?
Duff’s device (устройство Даффа)
Этот прием был изобретен ещё в 1983 году программистом по имени Tom Duff, и его применение позволяет реализовать на Си вручную такую оптимизацию, как loop unrolling.
Заключается эта оптимизация в следующем. При выполнении циклов в конце каждой итерации совершается проверка, не закончился ли цикл и не пора ли из него выйти. В нашем случае, после каждой итерации цикла происходит проверка, что number еще не достиг нуля. Выполняя loop unroling (или развертывание цикла), мы уменьшаем количество таких проверок тем, что за одну итерацию выполняем не одно тело цикла, а сразу несколько. В примере выше телом цикла является инкремент переменной i. В дальнейшем цикл, в котором используется данная оптимизация, я буду называть — развернутый цикл.
Тогда возникает следующая проблема. Допустим мы применяем такую оптимизацию, выполняя одновременно не одно тело цикла, а четыре. Как нам быть в том случае, если общее число выполняемых итераций не кратно четырем? Очевидное решение — найти остаток от деления общего числа итераций на количество итераций в теле развернутого цикла, и выполнить такое количество итераций до начала развернутого цикла. Тогда наш изначальный код,
#include
int main() {
int number = 11;
int i = 0;
while (number-- > 0) {
++i;
}
std::cout << i;
} можно оптимизировать следующим образом, выполняя по четыре тела цикла за раз:
int main() {
int number = 11; // общее число итераций = 11.
// в развернутом цикле выполняем по 4 тела цикла за раз.
int count = number / 4; // количество итераций развернутого цикла.
int left = number % 4; // количество итераций, которые в него "не влезли".
int i = 0;
// выполняем "невлезшие" в развернутый цикл итерации
// перед выполнением развернуто цикла.
while (left-- > 0) {
i++;
}
// выполняем развернутый цикл по 4 итерации за раз.
while (count-- > 0) {
i++;
i++;
i++;
i++;
}
std::cout << i;
}В данном случае мы выполнили не 11 проверок условия выхода из цикла, как в первом примере, а number / 4 + number % 4 проверок, то есть всего 5, при number равном 11.
Но у программистов на Assembly есть более изящное решение этой проблемы: в начале выполнения развернутого цикла производиться jump на его середину, чтобы сначала выполнить остаток итераций. И устройство Даффа позволяет сделать точно так же в Си. Рассмотрим еще раз код, который я приводил в самом начале:
#include
int main() {
int number = 11; // общее число итераций все еще равно 11.
int count = number / 4; // число итераций развернутого цикла.
int i = 0;
// находим остаток от деления общего числа итераций на количество итераций
// в одной итерации развернутого цикла и совершаем переход к этой итерации
// внутрь тела развернутого цикла.
switch (number % 4) {
case 0:
do {
++i;
case 3: ++i; // <- наш случай. Выполнение цикла начнется отсюда и при первой
case 2: ++i; // итерации развернутого цикла будет совершено не четыре, а
case 1: ++i; // только три итерации исходного цикла (11 % 4 итераций).
} while (count-- > 0);
}
std::cout << i;
} В данном случае мы выполнили только number / 4 проверок условия выхода из цикла, то есть всего две проверки, вместо первоначальных одиннадцати. Данный прием возможен благодаря тому, что в конструкции switch в Си выполнение кода будет «проваливаться» из блока одной метки case в блок следующей при отсутствии между ними оператора break. Но, как правило, никто не ожидает увидеть метку case посередине какой-то другой конструкции, как цикл do-while в нашем случае. Но в действительности, метка case может находится в любом месте внутри switch, и управление будет просто передано на следующую за ней инструкцию, что бы там не находилось.
В оригинале устройство Даффа выглядело следующим образом:
send(to, from, count)
// to - регистр ввода/вывода, отображаемый в память. Он не увеличивается
// при каждой итерации цкла.
// from - массив в памяти, откуда происходит копирование в регистр 'to'
register short *to, *from;
register count;
{
// в данном случае цикл разворачивался по 8 итераций за раз
register n = (count + 7) / 8;
switch (count % 8) {
case 0: do { *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
} while (--n > 0);
}
}Положительные и побочные эффекты
У этого приема есть как плюсы, так и минусы. Очевидным плюсом является рост производительности за счет снижения количества выполняемых проверок, но, помимо ухудшения читаемости исходного кода, неочевидным минусом является увеличение размера исполняемого файла, ведь теперь в нем банально будет больше кода. Но так ли все хорошо на самом деле?
Предлагаю посмотреть, во что превращается код в обоих случаях после компиляции. Для этого воспользуемся Compiler Explorer’ом с компилятором gcc 11.1 для x86–64 без дополнительных опций. Рассмотрим сгенерированный код, не сильно вдаваясь в подробности.
В случае без оптимизации наш цикл скомпилируется в следующее:
...
; рассмотрим только код самого цикла while
; [rbp-4] - это переменная number = 11 на стеке
; [rbp-8] - это переменная i = 0 на стеке
jmp .L2
.L3:
add DWORD PTR [rbp-8], 1 ; увеличили i на единицу
.L2:
mov eax, DWORD PTR [rbp-4] ; кладем в регистр eax значение number
lea edx, [rax-1] ; отнимаем от number единицу
mov DWORD PTR [rbp-4], edx ; сохраняем значение number-1 на стек
test eax, eax ; проверяем, что number еще не стал 0
jg .L3 ; если не стал, повторяем цикл еще раз
...В данном случае проверка условия выхода из цикла находится после метки .L2, и, как мы уже разобрались ранее, она будет выполненна 11 раз. Теперь взгянем, что получается с использованием устройства Даффа.
...
; рассматриваем только внутренности switch
; в [rbp-4] и [rbp-8] все как и было
; [rbp-12] - переменная count
mov eax, DWORD PTR [rbp-4] ; весь этот код до метки .L8 нужен для
cdq ; вычисления остатка от деления общего
shr edx, 30 ; количества итераций на количество
add eax, edx ; итераций в одной итерации развернутого
and eax, 3 ; цикла и перехода к нужной итерации.
sub eax, edx
cmp eax, 3 ; в зависимости от остатка мы прыгаем на:
je .L2 ; вторую итерацию
cmp eax, 3
jg .L3
cmp eax, 2
je .L4 ; третью итерацию
cmp eax, 2
jg .L3
test eax, eax
je .L5 ; первую итерацию
cmp eax, 1
je .L6 ; четвертую итерацию
jmp .L3 ; да, в худшем случае мы дойдем аж до сюда
; проверив все предыдущее.
.L8:
nop
.L5: ; а вот наши "развернутые итерации":
add DWORD PTR [rbp-8], 1 ; перый i++
.L2:
add DWORD PTR [rbp-8], 1 ; второй i++
.L4:
add DWORD PTR [rbp-8], 1 ; третий i++
.L6:
add DWORD PTR [rbp-8], 1 ; четвертый i++
mov eax, DWORD PTR [rbp-4] ; дальше выполняется точно такая же, как
lea edx, [rax-1] ; и в первом случае, проверка условия
mov DWORD PTR [rbp-4], edx ; выхода из цикла
test eax, eax
jg .L8
.L3:
; тут идет завершение программы
...Во первых, сразу заметно, что кода стало значительно больше. Во вторых, хотя мы и уменьшили количество проверок условия выхода из цикла в конце с 11 до 2, у нас появилось несколько новых проверок при вычислении остатка от деления и переходе на нужную итерацию в начале.
Вопрос, как на самом деле поулучается быстрее и эффективнее, остаеться открытым. Во многом это зависит от конкретной платформы и от того, на сколько хорошо компилятор оптимизирует код под эту платформу. В каких то случаях быстрее окажется вариант с двумя циклами, где сперва идет цикл с «остатками», а потом развернутый цикл. Так что перед применением устройства Даффа на практике стоит проанализировать, действительно ли в вашем конкретном случае так получается более производительный код. Так же стоит понимать, что сейчас уже далеко не 1983 год, и в наше время многие компиляторы сами умеют делать оптимизации циклов, и правильнее будет доверить это дело им, потому что у них, как правило, получится сделать это лучше.
Мой блог в Телеграме
