Рубрики

Как работает устройство Даффа?

Устройство Даффа — это уловка, позволяющая выразить развертывание цикла непосредственно в C или C ++ без дополнительного кода для обработки оставшегося частичного цикла. Уловка заключается в использовании оператора switch, где все метки case, кроме одного, находятся в середине цикла while. Кроме того, все случаи попадают в конец цикла while. Несмотря на такое впечатление, это делает устройство Даффа допустимым кодом C и C ++ (однако в Java это недопустимо).

Чем это полезно?

Есть две ключевые вещи для устройства Даффа.

  1. Во-первых, цикл развернут. Мы получаем большую скорость, избегая некоторых накладных расходов, связанных с проверкой завершения цикла и возвращаясь к вершине цикла. Процессор может работать быстрее, когда он выполняет прямой код вместо прыжков. Однако размер кода становится больше.
  2. Второй аспект — это оператор switch. Это позволяет коду переходить в середину цикла с первого раза. Для большинства людей удивительным является то, что такое разрешено. Ну, это разрешено.

пример

// C программа для иллюстрации работы
// Устройство Даффа. Даны копии программы
// количество элементов bool array src [] to
// dest []
#include<stdio.h>
#include<string.h>
#include <stdlib.h>

  
// Копирует биты размера из src [] в dest []

void copyBoolArray(bool src[], bool dest[],

                               int 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;

  

        // Важным моментом является переключатель

        // контроль может достигать ниже меток

        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;

        };

    }

}

  
// Код драйвера

int main()

{

    int size = 20;

    bool dest[size], src[size];

  

    // Назначаем несколько случайных значений для 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\t%d\n", 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 в массив назначения. Количество проходов, для которых он будет выполняться, также зависит от размера исходного массива.

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

Исходный цикл разматывается восемь раз, поэтому количество итераций делится на восемь. Если количество копируемых байтов не кратно восьми, то остаются некоторые байты. Большинство алгоритмов, которые копируют блоки байтов за раз, будут обрабатывать оставшиеся байты в конце, но устройство Даффа обрабатывает их в начале. Функция вычисляет число% 8 для оператора switch, чтобы выяснить, каким будет остаток, переходит на метку регистра для такого количества байтов и копирует их. Затем цикл продолжает копировать группы из восьми байтов в левые проходы.

Для первого прохода:

rounds = count / 8;

// rounds = 2 for count =20
i = 0;
switch(count % 8)
{

// The remainder is 4 (20 modulo 8)
// so jump to the case 4
case 0:
    while( !(rounds == 0) )
    {
        //[skipped]
        rounds = rounds - 1;
        dest[i] = src[i];
        i = i + 1;

    case 7:
        dest[i] = src[i];
        i = i + 1;     //[skipped]
    case 6:
        dest[i] = src[i];
        i = i + 1;     //[skipped]
    case 5:
        dest[i] = src[i];
        i = i + 1;     //[skipped]

    case 4:
        dest[i] = src[i];
        i = i + 1;     //Start here. Copy 1 byte (total 1)
    case 3:
        dest[i] = src[i];
        i = i + 1;     //Copy 1 byte (total 2)
    case 2:
        dest[i] = src[i];
        i = i + 1;     //Copy 1 byte (total 3)
    case 1:
        dest[i] = src[i];
        i = i + 1;     //Copy 1 byte (total 4)
    };
}

Для второго прохода:

rounds = count / 8;
i = 0;
switch(count % 8)
{
case 0:
    while( !(rounds == 0) )
    {
        // rounds is decremented by 1 as while
        // loop works, now rounds=1
        rounds = rounds - 1;
        dest[i] = src[i];
        i = i + 1;     // Copy 1 byte (total 5)
    case 7:
        dest[i] = src[i];
        i = i + 1; // Copy 1 byte (total 6)
    case 6:
        dest[i] = src[i];
        i = i + 1; // Copy 1 byte (total 7)
    case 5:
        dest[i] = src[i];
        i = i + 1; // Copy 1 byte (total 8)
    case 4:
        dest[i] = src[i];
        i = i + 1; // Copy 1 byte (total 9)
    case 3:
        dest[i] = src[i];
        i = i + 1; // Copy 1 byte (total 10)
    case 2:
        dest[i] = src[i];
        i = i + 1; // Copy 1 byte (total 11)
    case 1:
        dest[i] = src[i];
        i = i + 1; // Copy 1 byte (total 12)
    }
}

Для третьего прохода:

rounds = count / 8;
i = 0;
switch(count % 8)
{
case 0:
    while( !(rounds == 0) )
    {
        //now while loop works
        rounds = rounds - 1;    //rounds is decremented by 1, now rounds=0
        dest[i] = src[i];
        i = i + 1;         // Copy 1 byte (total 13)

    case 7:
        dest[i] = src[i];
        i = i + 1;    // Copy 1 byte (total 14)
    case 6:
        dest[i] = src[i];
        i = i + 1;    // Copy 1 byte (total 15)
    case 5:
        dest[i] = src[i];
        i = i + 1;    // Copy 1 byte (total 16)
    case 4:
        dest[i] = src[i];
        i = i + 1;    // Copy 1 byte (total 17)
    case 3:
        dest[i] = src[i];
        i = i + 1;     // Copy 1 byte (total 18)
    case 2:
        dest[i] = src[i];
        i = i + 1;     // Copy 1 byte (total 19)
    case 1:
        dest[i] = src[i];
        i = i + 1;     // Copy 1 byte (total 20)
    };
}

Ссылки:
Википедия
http://www.lysator.liu.se/c/duffs-device.html

Эта статья предоставлена Нихилом Кумаром Шармой . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Рекомендуемые посты:

Как работает устройство Даффа?

0.00 (0%) 0 votes