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

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

Это мой ага момент:

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. Это позволяет коду, чтобы перейти в средний петли в первый раз до конца. Удивительно для большинства людей заключается в том, что такие вещи допускаются. Ну, это разрешено. Выполнение начинается с расчетной метки case, а затем она падает через для каждого последующего оператора присваивания, как и любой другой оператор switch. После последней метки case выполнение достигает нижней части цикла, после чего оно возвращается к началу. Верхняя часть цикла -внутри оператор switch, так коммутатор больше не переоценивается.

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

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

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

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

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

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

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

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

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

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, который требует только, чтобы управляемый оператор коммутатора был синтаксически допустимым (составным) оператором, в котором метки case могут появляться с префиксом любого под-оператора. В сочетании с тем фактом, что при отсутствии оператора break поток управления будет падать от оператора, управляемого одной меткой case, к тому, что управляется следующей, это означает, что код определяет последовательность копий подсчета из последовательного адреса источника к порту вывода, сопоставленному с памятью.
• возможность легально прыгать в середину петли в C.

1: обманный удар устройства является конкретное внедрение развертывание циклов. Что такое разворачивание цикла?
Если у вас есть операция для выполнения N раз в цикле, вы можете обменять размер программы на скорость, выполнив цикл N / n раз, а затем в цикле inlining (unrolling) код цикла 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 - нет необходимости в Duff! если это не так, то вы должны обрабатывать остальные - что является болью.

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

хотя я не 100% уверен, что вы просите, здесь идет...

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

таким образом, обычная для петля:

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 в оригинале-это незначительная, но, возможно, значительная оптимизация.

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

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

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

и команда переключателя ветвится / прыгает немного вперед:

        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 больше не кажется такой странной.

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

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