Как работает устройство Даффа? - PullRequest
131 голосов
/ 05 февраля 2009

Я прочитал статью в Википедии об устройстве Даффа , но не понял. Я действительно заинтересован, но я прочитал объяснение там пару раз, и я все еще не понимаю, как работает устройство Даффа.

Каким будет более подробное объяснение?

Ответы [ 9 ]

216 голосов
/ 05 февраля 2009

В другом месте есть несколько хороших объяснений, но позвольте мне попробовать. (Это намного проще на доске!) Вот пример из Википедии с некоторыми обозначениями.

Допустим, вы копируете 20 байтов. Управление потоком программы для первого прохода:

int count;                        // Set to 20
{
    int n = (count + 7) / 8;      // n is now 3.  (The "while" is going
                                  //              to be run three times.)

    switch (count % 8) {          // The remainder is 4 (20 modulo 8) so
                                  // jump to the case 4

    case 0:                       // [skipped]
             do {                 // [skipped]
                 *to = *from++;   // [skipped]
    case 7:      *to = *from++;   // [skipped]
    case 6:      *to = *from++;   // [skipped]
    case 5:      *to = *from++;   // [skipped]
    case 4:      *to = *from++;   // Start here.  Copy 1 byte  (total 1)
    case 3:      *to = *from++;   // Copy 1 byte (total 2)
    case 2:      *to = *from++;   // Copy 1 byte (total 3)
    case 1:      *to = *from++;   // Copy 1 byte (total 4)
           } while (--n > 0);     // N = 3 Reduce N by 1, then jump up
                                  //       to the "do" if it's still
    }                             //        greater than 0 (and it is)
}

Теперь, начните второй проход, мы запускаем только указанный код:

int count;                        //
{
    int n = (count + 7) / 8;      //
                                  //

    switch (count % 8) {          //
                                  //

    case 0:                       //
             do {                 // The while jumps to here.
                 *to = *from++;   // Copy 1 byte (total 5)
    case 7:      *to = *from++;   // Copy 1 byte (total 6)
    case 6:      *to = *from++;   // Copy 1 byte (total 7)
    case 5:      *to = *from++;   // Copy 1 byte (total 8)
    case 4:      *to = *from++;   // Copy 1 byte (total 9)
    case 3:      *to = *from++;   // Copy 1 byte (total 10)
    case 2:      *to = *from++;   // Copy 1 byte (total 11)
    case 1:      *to = *from++;   // Copy 1 byte (total 12)
           } while (--n > 0);     // N = 2 Reduce N by 1, then jump up
                                  //       to the "do" if it's still
    }                             //       greater than 0 (and it is)
}

Теперь начните третий проход:

int count;                        //
{
    int n = (count + 7) / 8;      //
                                  //

    switch (count % 8) {          //
                                  //

    case 0:                       //
             do {                 // The while jumps to here.
                 *to = *from++;   // Copy 1 byte (total 13)
    case 7:      *to = *from++;   // Copy 1 byte (total 14)
    case 6:      *to = *from++;   // Copy 1 byte (total 15)
    case 5:      *to = *from++;   // Copy 1 byte (total 16)
    case 4:      *to = *from++;   // Copy 1 byte (total 17)
    case 3:      *to = *from++;   // Copy 1 byte (total 18)
    case 2:      *to = *from++;   // Copy 1 byte (total 19)
    case 1:      *to = *from++;   // Copy 1 byte (total 20)
           } while (--n > 0);     // N = 1  Reduce N by 1, then jump up
                                  //       to the "do" if it's still
    }                             //       greater than 0 (and it's not, so bail)
}                                 // continue here...

20 байт теперь скопированы.

Примечание. Исходное устройство Duff (показано выше) скопировано на устройство ввода-вывода по адресу to. Таким образом, нет необходимости увеличивать указатель *to. При копировании между двумя буферами памяти вам нужно использовать *to++.

103 голосов
/ 05 февраля 2009

Объяснение в журнале доктора Добба - лучшее, что я нашел по теме.

Это мой момент АГА:

for (i = 0; i < len; ++i) {
    HAL_IO_PORT = *pSource++;
}

становится:

int n = len / 8;
for (i = 0; i < n; ++i) {
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
    HAL_IO_PORT = *pSource++;
}

n = len % 8;
for (i = 0; i < n; ++i) {
    HAL_IO_PORT = *pSource++;
}

становится:

int n = (len + 8 - 1) / 8;
switch (len % 8) {
    case 0: do { HAL_IO_PORT = *pSource++;
    case 7: HAL_IO_PORT = *pSource++;
    case 6: HAL_IO_PORT = *pSource++;
    case 5: HAL_IO_PORT = *pSource++;
    case 4: HAL_IO_PORT = *pSource++;
    case 3: HAL_IO_PORT = *pSource++;
    case 2: HAL_IO_PORT = *pSource++;
    case 1: HAL_IO_PORT = *pSource++;
               } while (--n > 0);
}
70 голосов
/ 05 февраля 2009

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

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

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

11 голосов
/ 05 февраля 2009

Смысл устройства duffs в том, чтобы уменьшить количество сравнений, выполняемых в тесной реализации memcpy.

Предположим, что вы хотите скопировать байты 'count' из a в b, прямой подход заключается в следующем:

  do {                      
      *a = *b++;            
  } while (--count > 0);

Сколько раз вам нужно сравнить счетчик, чтобы увидеть, является ли он выше 0? 'считать' раз.

Теперь устройство duff использует неприятный непреднамеренный побочный эффект от случая переключателя, который позволяет уменьшить количество сравнений, необходимых для подсчета / 8.

Теперь предположим, что вы хотите скопировать 20 байтов, используя устройство duffs, сколько сравнений вам понадобится? Только 3, поскольку вы копируете восемь байтов за раз, за ​​исключением last первого, куда вы копируете только 4.

ОБНОВЛЕНО: вам не нужно делать 8 операторов сравнения / case-in-switch, но это разумный компромисс между размером функции и скоростью.

8 голосов
/ 28 августа 2010

Когда я прочитал это в первый раз, я автоматически отформатировал его в этом

void dsend(char* to, char* from, count) {
    int 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);
    }
}

и я понятия не имел, что происходит.

Возможно, нет, когда этот вопрос был задан, но сейчас В Википедии есть очень хорошее объяснение

Устройство является действительным, допустимым C в силу двух атрибутов в C:

  • Расслабленная спецификация оператора switch в определении языка. На момент изобретения устройства это было первое издание языка программирования C, в котором требуется только, чтобы управляемый оператор коммутатора был синтаксически допустимым (составным) оператором, в котором метки регистра могут появляться перед префиксом любого подоператора. В сочетании с тем фактом, что в отсутствие оператора перерыва поток управления будет переходить от оператора, контролируемого одной меткой к регистру, к которому управляет следующий, это означает, что в коде указывается последовательность подсчета копий из последовательные адреса источника к отображенному в памяти выходному порту.
  • Возможность легально прыгнуть в середину цикла в C.
6 голосов
/ 20 июня 2013

1: устройство Duffs - это особая реализация развертывания петли. Что такое развертывание цикла?
Если у вас есть операция для выполнения N раз в цикле, вы можете обменять размер программы на скорость, выполняя цикл N / N раз, а затем в цикле вставляя (разворачивая) код цикла n раз, например. замена:

for (int i=0; i<N; i++) {
    // [The loop code...] 
}

с

for (int i=0; i<N/n; i++) {
    // [The loop code...]
    // [The loop code...]
    // [The loop code...]
    ...
    // [The loop code...] // n times!
}

Что отлично работает, если N% n == 0 - Дафф не нужен! Если это не так, то вы должны обработать остаток - это боль.

2: Чем устройство Duffs отличается от этого стандартного развертывания петли?
Устройство Duffs - это просто умный способ справиться с циклами оставшихся циклов, когда N% n! = 0. Весь процесс do / while выполняется N / n количество раз, как при развертывании стандартного цикла (поскольку применяется случай 0). При последнем прогоне цикла («N / n + 1-й раз») случай запускается, и мы переходим к случаю N% n и запускаем цикл с кодом «остаток» несколько раз.

3 голосов
/ 05 февраля 2009

Хотя я не на 100% уверен, что вы просите, вот так ...

Проблема, с которой сталкиваются устройства Даффа, связана с разматыванием петли (как вы, без сомнения, видели в опубликованной вами вики-ссылке). То, к чему это в основном приравнивается, - это оптимизация эффективности во время выполнения по сравнению с объемом памяти. Устройство Даффа имеет дело с последовательным копированием, а не просто со старой проблемой, но является классическим примером того, как можно сделать оптимизацию, уменьшив количество раз, когда сравнение должно выполняться в цикле.

В качестве альтернативного примера, который может облегчить понимание, представьте, что у вас есть массив элементов, которые вы хотите зациклить, и каждый раз добавляйте 1 к ним ... обычно вы можете использовать цикл for и цикл около 100 раз. Это кажется довольно логичным, и, однако ... однако, оптимизация может быть выполнена путем разматывания цикла (очевидно, не слишком далеко ... или вы можете просто не использовать цикл).

Итак, обычный цикл:

for(int i = 0; i < 100; i++)
{
    myArray[i] += 1;
}

становится

for(int i = 0; i < 100; i+10)
{
    myArray[i] += 1;
    myArray[i+1] += 1;
    myArray[i+2] += 1;
    myArray[i+3] += 1;
    myArray[i+4] += 1;
    myArray[i+5] += 1;
    myArray[i+6] += 1;
    myArray[i+7] += 1;
    myArray[i+8] += 1;
    myArray[i+9] += 1;
}

Устройство Даффа реализует эту идею на C, но (как вы видели в Wiki) с серийными копиями. То, что вы видите выше, с приведенным примером, - это 10 сравнений по сравнению с 100 в оригинале - это незначительная, но, возможно, существенная оптимизация.

0 голосов
/ 20 июля 2016

Просто экспериментируя, нашел другой вариант, обходящийся без чередования переключателя и цикла:

int n = (count + 1) / 8;
switch (count % 8)
{
    LOOP:
case 0:
    if(n-- == 0)
        break;
    putchar('.');
case 7:
    putchar('.');
case 6:
    putchar('.');
case 5:
    putchar('.');
case 4:
    putchar('.');
case 3:
    putchar('.');
case 2:
    putchar('.');
case 1:
    putchar('.');
default:
    goto LOOP;
}
0 голосов
/ 12 марта 2016

Вот не подробное объяснение, которое, как мне кажется, суть устройства Даффа:

Дело в том, что C - это по сути хороший фасад для языка ассемблера (сборка PDP-7, если быть точным; если вы изучите это, вы увидите, насколько поразительно сходство). И на языке ассемблера у вас действительно нет циклов - у вас есть метки и инструкции условного перехода. Таким образом, цикл - это только часть общей последовательности инструкций с меткой и веткой где-то:

        instruction
label1: instruction
        instruction
        instruction
        instruction
        jump to label1  some condition

и команда switch несколько разветвляется / прыгает вперед:

        evaluate expression into register r
        compare r with first case value
        branch to first case label if equal
        compare r with second case value
        branch to second case label if equal
        etc....
first_case_label: 
        instruction
        instruction
second_case_label: 
        instruction
        instruction
        etc...

При сборке легко представить, как объединить эти две управляющие структуры, и, если подумать об этом, их сочетание в Си уже не кажется таким странным.

...