Mechanizm Duffa

Mechanizm Duffa – w informatyce jest zoptymalizowaną wersją kopiowania jednej tablicy do drugiej. Używa do tego metody szeroko stosowanej w assemblerze polegającej na odwijaniu pętli. Wynalezienie tej metody dla języka C jest przypisywane Tomowi Duffowi (listopad 1983). W praktyce jednak stosowanie tej metody przy tworzeniu programów nie jest konieczne, ponieważ większość współczesnych kompilatorów sama optymalizuje kod w ten sposób.

Działanie

Przykład prostego kopiowania dwóch tablic znakowych wykonuje test zakończenia działania po przepisaniu każdego elementu:

void kopiuj(char *wej, char *wyj, int krotnosc) {
    while (krotnosc-- > 0)    {
        *wyj++ = *wej++;    
    }
}

Mechanizm Duffa pozwala wyeliminować dużą część niepotrzebnych sprawdzeń:

void kopiuj(char *wej, char *wyj, int krotnosc)
{
    int n = (krotnosc + 7) / 8;
    switch (krotnosc % 8) {
      case 0: do { *wyj++ = *wej++;
      case 7:      *wyj++ = *wej++;
      case 6:      *wyj++ = *wej++;
      case 5:      *wyj++ = *wej++;
      case 4:      *wyj++ = *wej++;
      case 3:      *wyj++ = *wej++;
      case 2:      *wyj++ = *wej++;
      case 1:      *wyj++ = *wej++;
                 } while (--n > 0);
    }
}

Opis

Zapis metody może być mylący, jednak program działa tak, jak gdyby pętla do…while była całkowicie pod całym switch, natomiast pod każdym case byłoby polecenie skoku do odpowiedniego miejsca pętli do…while. Inny rodzaj zapisu ułatwiający zrozumienie mógłby mieć postać:

void kopiuj(char *wej, char *wyj, int krotnosc) {
    int n = (krotnosc + 7) / 8;
    switch (krotnosc % 8) {
      case 0: goto miejsce0;
      case 7: goto miejsce7;
      case 6: goto miejsce6;
      case 5: goto miejsce5;
      case 4: goto miejsce4;
      case 3: goto miejsce3;
      case 2: goto miejsce2;
      case 1: goto miejsce1;
    }

miejsce0: do { *wyj++ = *wej++;
miejsce7: *wyj++ = *wej++;
miejsce6: *wyj++ = *wej++;
miejsce5: *wyj++ = *wej++;
miejsce4: *wyj++ = *wej++;
miejsce3: *wyj++ = *wej++;
miejsce2: *wyj++ = *wej++;
miejsce1: *wyj++ = *wej++;
              } while (--n > 0);
}

Instrukcja przypisania *wyj++ = *wej++ musi być wykonana krotnosc razy. Pętla do zawiera 8 kopiowań. Dlatego należy obliczyć ile razy krotnosc dzieli się przez 8 – właśnie tyle razy należy wykonać do. Natomiast reszta z dzielenia to liczba dodatkowych kopii, dlatego następuje skok pod odpowiednie miejsca, spod którego wykona się tyle kopiowań, ile wyniosła reszta z dzielenia. Po tym zostanie sprawdzony warunek while (--n > 0) i ewentualny skok do początku do i wykonanie pozostałych kopii. Dodanie do krotnosc siedmiu pochodzi z oryginalnego rozwiązania, możliwe jest wyeliminowanie tego dodania przy odpowiedniej modyfikacji etykiet skoków.