Duff's Device

Estou postando este artigo a título de curiosidade. Embora você ainda possa encontrar uma situação prática hoje em dia em que o Duff's Device possa ser útil, em 99,9% das situações seu benefício é desprezível.

O Duff's Device é uma técnica criada por Tom Duff em 1983 para fazer uma cópia serial de dados (a mesma coisa que o memcpy faz) com um desempenho maior. Foi amplamente utilizada por progamadores de Assembly e programadores de C no começo dos tempos.

Basicamente, a maneira mais rápida de se copiar dados de uma região de memória para outra, em C, é:

void meu_memcpy( unsigned char* destino, unsigned char* origem, int quantidade )

{

     while( quantidade-- > 0 )

     {

         *destino++ = *origem++;

     }

}

O problema com esta solução é que temos que verificar se quantidade é maior que zero em cada iteração. Se estivermos copiando mil bytes, haverá mil comparações.

A solução encontrada por Duff foi diminuir este número de comparações, copiando os elementos de 8 em 8. Depois de copiar 8 elementos, ele fazia as devidas verificações e partia para o próximo bloco de cópia.

O algoritmo original do Duff era:

void meu_memcpy( unsigned char* destino, unsigned char* origem, int quantidade )

{

     register int n = (quantidade + 7) / 8;

     switch(quantidade % 8)

     {

         case 0: do { *destino++ = *origem++;

         case 7: *destino++ = *origem++;

         case 6: *destino++ = *origem++;

         case 5: *destino++ = *origem++;

         case 4: *destino++ = *origem++;

         case 3: *destino++ = *origem++;

         case 2: *destino++ = *origem++;

         case 1: *destino++ = *origem++;

             } while(--n > 0);

     }

}

Basicamente n é a quantidade de oitos que cabem em quantidade. Se der número quebrado, arredonda para cima. Ou seja, se quantidade vale 8, n vale 1. Se quantidade vale 10, n vale 2.

O switch pega o resto da divisão de quantidade por 8 para que esta quantidade seja copiada na primeira iteração. Nas demais, serão copiados 8 bytes.

Você deve ter estranhado o formato do do...while no meio dos cases, mas este código é perfeitamente válido em C.

Talvez você esteja se perguntando também porque foi usado o valor 8, e não outro qualquer.

A explicação disso é que os processadores calculam mais rapidamente qualquer divisão por valores 2^n.

Por exemplo, se quiser dividir um número por 2, basta rotacioná-lo para a direita 1 bit. Para dividir por 4, rotacione 2 bits. Para dividir por 8, 3 bits, e assim por diante.

O Duff ' Device teve sua vantagem no passado, mas hoje em dia são pouquíssimas as situações em que se vale a pena aplicá-lo. Primeiro que o código tem uma complexidade razoável perto do original. Um leigo com certeza terá dificuldades em entendê-lo.

Segundo que não necessariamente este código será mais rápido. Os compiladores atuais executam vários tipos de otimizações. Se o ganho de desempenho for justificável na sua aplicação para que você venha a adotar esta implementação, é interessante que você faça testes com o memcpy original e com a sua implementação do Duff's Device para ver se, na prática, ela realmente é mais rápida.