Как работает Дафф?

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

Что было бы более подробным объяснением?

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

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

    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++ .

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

    Это мой момент AHA:

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

    🙂 становится:

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

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

     for (int i=0; i 

    с

     for (int i=0; i 

    Что отлично работает, если N% n == 0 - нет необходимости в Duff! Если это не так, тогда вам нужно обработать остаток - что является болью.

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

    Хотя я не на 100% уверен, что вы просите, здесь идет …

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

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

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

    Дело в том, что C – это в основном приятный фасад для языка ассемблера (конкретная assembly 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; } 
    Давайте будем гением компьютера.