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

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

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

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

Допустим, вы копируете 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's (показанное выше) скопировано на устройство ввода-вывода по toадресу. Таким образом, нет необходимости увеличивать указатель *to. При копировании между двумя буферами памяти вы должны будете использовать *to++.

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

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

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);
}

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

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

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

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

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

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

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

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

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

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

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

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.

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 и запускаем цикл с кодом «остаток» несколько раз.

Хотя я не на 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;
}

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

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

Дело в том, что 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...

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

Это ответ, который я отправил на другой вопрос об устройстве Даффа, которое получило некоторые отзывы до того, как вопрос был закрыт как дубликат. Я думаю, что здесь приводится немного ценного контекста о том, почему вы должны избегать этой конструкции.

«Это устройство Даффа . Это метод развертывания циклов, в котором не нужно добавлять дополнительный цикл исправления, чтобы справиться со временем, когда число итераций цикла точно не кратно коэффициенту развертывания.

Поскольку большинство ответов здесь, как правило, положительно, я собираюсь выделить недостатки.

С этим кодом компилятор будет пытаться применить любую оптимизацию к телу цикла. Если вы просто написали код в виде простого цикла, современный компилятор сможет справиться с развертыванием за вас. Таким образом, вы сохраняете удобочитаемость и производительность, и у вас есть надежда на другие оптимизации, применяемые к телу цикла.

В статье Википедии, на которую ссылаются другие, даже говорится, что когда этот «шаблон» был удален из исходного кода Xfree86, производительность фактически улучшилась.

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

Это прекрасно понимать, но я был бы удивлен, если бы вы когда-нибудь использовали это на самом деле.

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

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