Como o dispositivo de Duff funciona?

Eu li o artigo na Wikipedia no dispositivo Duff e não entendi. Estou realmente interessado, mas li a explicação algumas vezes e ainda não entendi como o dispositivo da Duff funciona.

Qual seria uma explicação mais detalhada?

Existem algumas boas explicações em outros lugares, mas deixe-me tentar. (Isso é muito mais fácil em um quadro branco!) Aqui está o exemplo da Wikipedia com algumas anotações.

Digamos que você esteja copiando 20 bytes. O controle de fluxo do programa para a primeira passagem é:

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

Agora, inicie a segunda passagem, executamos apenas o código indicado:

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

Agora, inicie a terceira passagem:

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 bytes agora são copiados.

Nota: O dispositivo Duff original (mostrado acima) copiou para um dispositivo de E / S no toendereço. Portanto, não era necessário incrementar o ponteiro *to. Ao copiar entre dois buffers de memória, você precisará usar *to++.

A explicação no Diário do Dr. Dobb é a melhor que encontrei sobre o assunto.

Sendo este o meu momento da AHA:

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

torna-se:

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

torna-se:

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

Há duas coisas principais no dispositivo de Duff. Primeiro, que eu suspeito que seja a parte mais fácil de entender, o loop é desenrolado. Isso troca um tamanho de código maior para obter mais velocidade, evitando parte da sobrecarga envolvida na verificação se o loop está concluído e retornando ao topo do loop. A CPU pode funcionar mais rapidamente quando está executando código linear em vez de pular.

O segundo aspecto é a instrução switch. Ele permite que o código pule para o meio do loop pela primeira vez. A parte surpreendente para a maioria das pessoas é que isso é permitido. Bem, é permitido. A execução começa no rótulo do caso calculado e, em seguida, se aplica a cada instrução de atribuição sucessiva, como qualquer outra instrução de chave. Após o último rótulo do caso, a execução atinge a parte inferior do loop e, nesse ponto, ela volta ao topo. A parte superior do loop está dentro da instrução switch, portanto, o switch não é mais reavaliado.

O loop original é desenrolado oito vezes, portanto, o número de iterações é dividido por oito. Se o número de bytes a serem copiados não for um múltiplo de oito, haverá alguns bytes restantes. A maioria dos algoritmos que copiam blocos de bytes de cada vez manipula os bytes restantes no final, mas o dispositivo de Duff os manipula no início. A função calcula count % 8para a instrução switch para descobrir qual será o restante, pula para o rótulo do caso com muitos bytes e os copia. Em seguida, o loop continua a copiar grupos de oito bytes.

O objetivo do dispositivo duffs é reduzir o número de comparações feitas em uma implementação restrita de memcpy.

Suponha que você queira copiar 'contar' bytes de a para b, a abordagem direta é fazer o seguinte:

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

Quantas vezes você precisa comparar a contagem para ver se está acima de 0? 'contar' vezes.

Agora, o dispositivo duff usa um efeito colateral não intencional desagradável de uma caixa de comutação que permite reduzir o número de comparações necessárias para contar / 8.

Agora, suponha que você queira copiar 20 bytes usando o dispositivo duffs, quantas comparações você precisaria? Apenas 3, desde que você copie oito bytes por vez, exceto o último primeiro, onde você copia apenas 4.

ATUALIZADO: Você não precisa fazer 8 comparações / instruções caso a interruptor, mas é razoável uma troca entre tamanho e velocidade da função.

Quando o li pela primeira vez, adaptei-o automaticamente a este

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

e eu não tinha ideia do que estava acontecendo.

Talvez não quando essa pergunta foi feita, mas agora a Wikipedia tem uma explicação muito boa

O dispositivo é C válido e legal devido a dois atributos em C:

• Especificação relaxada da instrução switch na definição do idioma. No momento da invenção do dispositivo, essa era a primeira edição da The C Programming Language, que requer apenas que a declaração controlada do comutador seja uma declaração (composta) sintaticamente válida dentro da qual os rótulos de casos possam aparecer como prefixo de qualquer sub-declaração. Em conjunto com o fato de que, na ausência de uma declaração de interrupção, o fluxo de controle passa de uma declaração controlada por um rótulo de caso para aquela controlada pelo próximo, isso significa que o código especifica uma sucessão de cópias de contagem de endereços de origem seqüencial para a porta de saída mapeada na memória.
• A capacidade de pular legalmente no meio de um loop em C.

1: O dispositivo Duffs é uma implementação específica do desenrolamento de loop. O que é desenrolamento de loop?
Se você possui uma operação para executar N vezes em um loop, você pode trocar o tamanho do programa por velocidade executando o loop N / n vezes e, em seguida, no loop inlining (desenrolando) o código do loop n vezes, por exemplo, substituindo:

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

com

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

O que funciona muito bem se N% n == 0 - não é necessário Duff! Se isso não for verdade, você terá que lidar com o restante - o que é uma dor.

2: Como o dispositivo Duffs difere desse desenrolamento de loop padrão?
O dispositivo Duffs é apenas uma maneira inteligente de lidar com os ciclos restantes do loop quando N% n! = 0. O conjunto do / while executa N / n número de vezes conforme o desenrolamento padrão do loop (porque o caso 0 se aplica). Na última execução do loop (a 'N / n + 1ª vez), o caso entra em ação e pulamos para o caso N% n e executamos o código do loop o número' restante 'de vezes.

Embora eu não esteja 100% certo do que você está pedindo, aqui vai ...

O problema abordado pelo dispositivo de Duff é o de desenrolar o loop (como você certamente já viu no link do Wiki que postou). Basicamente, isso é uma otimização da eficiência do tempo de execução, além da pegada de memória. O dispositivo de Duff lida com a cópia em série, e não com qualquer problema antigo, mas é um exemplo clássico de como as otimizações podem ser feitas, reduzindo o número de vezes que uma comparação precisa ser feita em um loop.

Como um exemplo alternativo, que pode facilitar a compreensão, imagine que você tenha uma série de itens que deseja repetir e adicione 1 a cada vez ... normalmente, você pode usar um loop for e repetir cerca de 100 vezes . Isso parece bastante lógico e, é ... no entanto, uma otimização pode ser feita desenrolando o loop (obviamente não muito longe ... ou você pode simplesmente não usar o loop).

Portanto, um loop for regular:

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

torna-se

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

O que o dispositivo de Duff faz é implementar essa ideia, em C, mas (como você viu no Wiki) com cópias seriais. O que você está vendo acima, com o exemplo não revelado, são 10 comparações em comparação com 100 no original - isso equivale a uma otimização menor, mas possivelmente significativa.

Aqui está uma explicação não detalhada, que é o que considero o cerne do dispositivo de Duff:

O fato é que C é basicamente uma fachada agradável para a linguagem assembly (a montagem do PDP-7 é específica; se você estudasse, veria como as semelhanças são impressionantes). E, na linguagem assembly, você realmente não possui loops - possui rótulos e instruções de ramificação condicional. Portanto, o loop é apenas uma parte da sequência geral de instruções com um rótulo e uma ramificação em algum lugar:

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

e uma instrução switch está ramificando / pulando um pouco à frente:

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

Na montagem, é facilmente concebível como combinar essas duas estruturas de controle e, quando você pensa dessa maneira, a combinação delas em C não parece mais tão estranha.

Esta é uma resposta que eu postei em outra pergunta sobre o dispositivo de Duff que recebeu algumas atualizações antes que a pergunta fosse fechada como duplicada. Eu acho que fornece um pouco de contexto valioso aqui sobre por que você deve evitar essa construção.

"Este é o dispositivo de Duff . É um método de desenrolar loops que evita ter que adicionar um loop de correção secundário para lidar com momentos em que o número de iterações de loop não é um múltiplo exato do fator de desenrolamento.

Como a maioria das respostas aqui parece ser geralmente positiva sobre isso, vou destacar as desvantagens.

Com esse código, um compilador terá dificuldades para aplicar qualquer otimização ao corpo do loop. Se você acabou de escrever o código como um loop simples, um compilador moderno deve ser capaz de lidar com o desenrolar para você. Dessa forma, você mantém a legibilidade e o desempenho e tem alguma esperança de que outras otimizações sejam aplicadas ao corpo do loop.

O artigo da Wikipedia referenciado por outros até diz quando esse 'padrão' foi removido do desempenho do código fonte do Xfree86 realmente melhorado.

Esse resultado é típico da otimização cega das mãos de qualquer código que você ache que possa precisar. Impede que o compilador faça seu trabalho corretamente, torna seu código menos legível e mais propenso a erros e, normalmente, diminui sua velocidade. Se você estivesse fazendo as coisas da maneira certa em primeiro lugar, ou seja, escrevendo código simples, criando perfis de gargalos e otimizando, você nunca pensaria em usar algo assim. Não com uma CPU e compilador modernos de qualquer maneira.

É bom entender isso, mas ficaria surpreso se você realmente o usar. "

Apenas experimentando, encontrei outra variante se dando bem sem intercalar o interruptor e o loop:

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