Как работает устройство Даффа?
Устройство Даффа - это уловка для выражения развертывания цикла непосредственно на C или C ++ без дополнительного кода для обработки оставшегося частичного цикла. Уловка заключается в использовании оператора switch, где все метки case, кроме одной, находятся в середине цикла while. Кроме того, все случаи выпадают до конца цикла while. Несмотря на это впечатление, это делает устройство Даффа законным кодом C и C ++ (однако он не действует в Java).
Чем это полезно?
В устройстве Даффа есть два ключевых момента.
- Сначала разворачивается петля. Мы получаем больше скорости, избегая некоторых накладных расходов, связанных с проверкой того, завершен ли цикл, и возвращением к началу цикла. ЦП может работать быстрее, если он выполняет прямой код вместо прыжков. Однако размер кода становится больше.
- Второй аспект - это оператор switch. Это позволяет коду перейти в середину цикла с первого раза. Удивительно для большинства людей то, что это разрешено. Что ж, это разрешено.
Пример
// C program to illustrate the working of// Duff's Device. The program copies given// number of elements bool array src[] to// dest[]#include<stdio.h>#include<string.h>#include <stdlib.h> // Copies size bits from src[] to dest[]void copyBoolArray( bool src[], bool dest[], size) int{ // Do copy in rounds of size 8. int rounds = size / 8; int i = 0; switch (size % 8) { case 0: while (!(rounds == 0)) { rounds = rounds - 1; dest[i] = src[i]; i = i + 1; // An important point is, the switch // control can directly reach below labels case 7: dest[i] = src[i]; i = i + 1; case 6: dest[i] = src[i]; i = i + 1; case 5: dest[i] = src[i]; i = i + 1; case 4: dest[i] = src[i]; i = i + 1; case 3: dest[i] = src[i]; i = i + 1; case 2: dest[i] = src[i]; i = i + 1; case 1: dest[i] = src[i]; i = i + 1; }; }} // Driver codeint main(){ int size = 20; bool dest[size], src[size]; // Assign some random values to src[] int i; for (i=0; i<size; i++) src[i] = rand ()%2; copyBoolArray(src, dest, size); for (i=0; i<size ; i++) printf ( "%d %d
" , src[i], dest[i]);} |
Выход:
1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1
Как работает вышеуказанная программа?
В приведенном выше примере мы имеем дело с 20 байтами и копируем эти 20 случайных битов из массива src в массив назначения. Количество проходов, для которых он будет выполняться, также зависит от размера исходного массива.
Для первого прохода выполнение начинается с вычисленной метки case, а затем переходит к каждому последующему оператору присваивания, как и любой другой оператор switch. После последней метки case выполнение достигает конца цикла, после чего возвращается к началу. Вершина цикла находится внутри оператора switch, поэтому переключатель больше не переоценивается.
Исходный цикл разматывается восемь раз, поэтому количество итераций делится на восемь. Если количество копируемых байтов не кратно восьми, значит, осталось несколько байтов. Большинство алгоритмов, которые копируют блоки байтов за раз, обрабатывают оставшиеся байты в конце, но устройство Даффа обрабатывает их в начале. Функция вычисляет счет% 8 для оператора switch, чтобы определить, каким будет остаток, переходит к метке case для этого количества байтов и копирует их. Затем цикл продолжает копировать группы из восьми байтов в левые проходы.
Для первого прохода:
раундов = количество / 8;
// раундов = 2 для count = 20
я = 0;
переключатель (количество% 8)
{
// Остаток 4 (20 по модулю 8)
// так что переходим к случаю 4
case 0:
в то время как (! (раунды == 0))
{
// [пропущено]
патронов = патронов - 1;
dest [i] = src [i];
я = я + 1;
case 7:
dest [i] = src [i];
я = я + 1; // [пропущено]
case 6:
dest [i] = src [i];
я = я + 1; // [пропущено]
случай 5:
dest [i] = src [i];
я = я + 1; // [пропущено]
случай 4:
dest [i] = src [i];
я = я + 1; //Начните здесь. Скопируйте 1 байт (всего 1)
случай 3:
dest [i] = src [i];
я = я + 1; // Копируем 1 байт (всего 2)
случай 2:
dest [i] = src [i];
я = я + 1; // Копируем 1 байт (всего 3)
Дело 1:
dest [i] = src [i];
я = я + 1; // Копируем 1 байт (всего 4)
};
}
Для второго прохода:
раундов = количество / 8;
я = 0;
переключатель (количество% 8)
{
case 0:
в то время как (! (раунды == 0))
{
// количество раундов уменьшается на 1 как в то время как
// цикл работает, теперь rounds = 1
патронов = патронов - 1;
dest [i] = src [i];
я = я + 1; // Копируем 1 байт (всего 5)
case 7:
dest [i] = src [i];
я = я + 1; // Копируем 1 байт (всего 6)
case 6:
dest [i] = src [i];
я = я + 1; // Копируем 1 байт (всего 7)
случай 5:
dest [i] = src [i];
я = я + 1; // Копируем 1 байт (всего 8)
случай 4:
dest [i] = src [i];
я = я + 1; // Копируем 1 байт (всего 9)
случай 3:
dest [i] = src [i];
я = я + 1; // Копируем 1 байт (всего 10)
случай 2:
dest [i] = src [i];
я = я + 1; // Копируем 1 байт (всего 11)
Дело 1:
dest [i] = src [i];
я = я + 1; // Копируем 1 байт (всего 12)
}
}
Для третьего прохода:
раундов = количество / 8;
я = 0;
переключатель (количество% 8)
{
case 0:
в то время как (! (раунды == 0))
{
// теперь цикл работает
патронов = патронов - 1; // количество раундов уменьшается на 1, теперь раунды = 0
dest [i] = src [i];
я = я + 1; // Копируем 1 байт (всего 13)
case 7:
dest [i] = src [i];
я = я + 1; // Копируем 1 байт (всего 14)
case 6:
dest [i] = src [i];
я = я + 1; // Копируем 1 байт (всего 15)
случай 5:
dest [i] = src [i];
я = я + 1; // Копируем 1 байт (всего 16)
случай 4:
dest [i] = src [i];
я = я + 1; // Копируем 1 байт (всего 17)
случай 3:
dest [i] = src [i];
я = я + 1; // Копируем 1 байт (всего 18)
случай 2:
dest [i] = src [i];
я = я + 1; // Копируем 1 байт (всего 19)
Дело 1:
dest [i] = src [i];
я = я + 1; // Копируем 1 байт (всего 20)
};
}
Использованная литература:
Википедия
http://www.lysator.liu.se/c/duffs-device.html
Эта статья предоставлена Нихилом Кумаром Шармой . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью с помощью provide.geeksforgeeks.org или отправить ее по электронной почте на deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.