Jak działa urządzenie Duffa?

Wyjaśnienie w Dzienniku doktora Dobba jest najlepsze, jakie znalazłem w tym temacie.

To jest mój moment AHA:

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

Staje się:

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

Staje się:

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

Są dwie kluczowe rzeczy dla urządzenia Duffa. Po pierwsze, co, jak podejrzewam, jest łatwiejsze do zrozumienia, pętla jest rozwinięta. Ten handluje większy rozmiar kodu dla większej prędkości, unikając niektórych kosztów związanych z sprawdzaniem, czy pętla jest zakończona i skoki z powrotem do górnej części pętli. Procesor może działać szybciej, gdy wykonuje kod prosty, zamiast skakać.

Drugim aspektem jest instrukcja switch. Pozwala na przeskoczenie kodu do środka pętli za pierwszym razem. Zaskakujące dla większości ludzi jest to, że takie rzeczy są dozwolone. Cóż, to dozwolone. Wykonanie rozpoczyna się od obliczonej etykiety przypadku, a następnie przechodzi przez do każdej kolejnej instrukcji przypisania, tak jak każda inna Instrukcja switch. Po ostatniej etykiecie przypadku wykonanie dociera do dołu pętli, po czym skacze z powrotem na górę. Górna część pętli jest wewnątrz instrukcji switch, więc przełącznik nie jest ponownie oceniany już nie.

Oryginalna pętla jest rozwinięta osiem razy, więc liczba iteracji jest podzielona przez osiem. Jeśli liczba bajtów do skopiowania nie jest wielokrotnością ośmiu, to pozostało kilka bajtów. Większość algorytmów kopiujących bloki bajtów na raz obsłuży Pozostałe bajty na końcu, ale urządzenie Duffa obsługuje je na początku. Funkcja oblicza count % 8 dla instrukcji switch, aby dowiedzieć się, jaka będzie reszta, przeskakuje do etykiety case dla tylu bajtów i kopiuje je. Następnie pętla kontynuuje kopiowanie grup po osiem bajtów.

Celem urządzenia duffs jest zmniejszenie liczby porównań wykonanych w ciasnej implementacji memcpy.

Załóżmy, że chcesz skopiować' count ' bajtów z a do b, proste podejście polega na wykonaniu następujących czynności:

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

Ile razy trzeba porównać count, aby zobaczyć, czy jest powyżej 0? "licz" razy.

Teraz urządzenie duff wykorzystuje paskudny niezamierzony efekt uboczny obudowy przełącznika, który pozwala zmniejszyć liczbę porównań potrzebnych do liczenia / 8.

Teraz Załóżmy, że chcesz skopiować 20 bajtów za pomocą urządzenia duffs, ile porównań potrzebujesz? Tylko 3, ponieważ kopiujesz osiem bajtów na raz, z wyjątkiem ostatniego pierwszego, gdzie kopiujesz tylko 4.

Aktualizacja: nie musisz robić 8 porównań / instrukcji case-in-switch, ale rozsądny jest kompromis między rozmiarem funkcji a szybkością.

Kiedy przeczytałem go po raz pierwszy, autoformatowałem go do tego

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

Może nie wtedy, gdy to pytanie zostało zadane, ale teraz Wikipedia ma bardzo dobre wyjaśnienie

Urządzenie jest ważne, legalne C na mocy dwóch atrybutów W C:

• uproszczona specyfikacja instrukcji switch w definicji języka. W momencie wynalezienia urządzenia była to pierwsza edycja języka programowania C co wymaga tylko, aby kontrolowana Instrukcja przełącznika była poprawną składniowo (złożoną) Instrukcją, w której etykiety przypadków mogą pojawiać się przed dowolną podpunktą. W połączeniu z faktem, że w przypadku braku instrukcji break, przepływ sterowania spadnie z instrukcji kontrolowanej przez etykietę jednego przypadku do instrukcji kontrolowanej przez następną, oznacza to, że kod określa kolejne kopie count z sekwencyjnych adresów źródłowych na wyjście mapowane w pamięci port.
[[13]}możliwość legalnego Skoku w środek pętli w C.

1: urządzenie Duffs jest szczególną implementacją rozwijania pętli. Rozwijanie pętli jest techniką optymalizacji mającą zastosowanie, jeśli masz operację, aby wykonać N razy w pętli - możesz wymienić rozmiar programu na prędkość, wykonując pętlę N / N razy, a następnie w pętli inlining (rozwijanie) kod pętli n razy, np. zastępując:

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

Z

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

Który działa świetnie jeśli N % n = = 0-nie ma potrzeby Duff! jeśli to nie jest prawda, to musisz zająć się resztą - czyli ból.

2: czym urządzenie Duffs różni się od tego standardowego rozwijania pętli?
Urządzenie Duffs jest po prostu sprytnym sposobem radzenia sobie z pozostałymi cyklami pętli, gdy N % n != 0. CaĹ 'e do / while wykonuje n / n iloĹ" Ä ‡ razy zgodnie ze standardowym rozwiniÄ ™ ciem pętli (poniewaĹź ma zastosowanie przypadek 0). Na last pierwszy bieg przez pętlę sprawa zaczyna się i uruchamiamy kod pętli 'Rest' ilość razy-pozostałe biegnie przez pętlę run 'normally'.

Chociaż nie jestem w 100% pewien, o co prosisz, zaczyna się...

Problem, który adresuje urządzenie Duffa, polega na rozwijaniu pętli (jak zapewne zauważyłeś na linku Wiki, który opublikowałeś). To, co w zasadzie oznacza, to optymalizacja wydajności czasu pracy, nad przestrzenią pamięci. Urządzenie Duffa zajmuje się kopiowaniem seryjnym, a nie jakimkolwiek starym problemem, ale jest klasycznym przykładem tego, jak można dokonać optymalizacji poprzez zmniejszenie liczby razy, które trzeba porównać zrobione w pętli.

Jako alternatywny przykład, który może ułatwić zrozumienie, wyobraź sobie, że masz tablicę elementów, które chcesz zapętlić, i dodaj do nich 1 za każdym razem... zwykle można użyć pętli for i pętli około 100 razy. Wydaje się to dość logiczne i, jest... optymalizację można jednak dokonać poprzez odwijanie pętli (oczywiście nie za daleko... albo równie dobrze możesz po prostu nie używać pętli).

Więc zwykły dla loop:

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

Staje się

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

Urządzenie Duffa implementuje ten pomysł w C, ale (jak widziałeś na Wiki) z seryjnymi kopiami. To, co widzisz powyżej, w przykładzie unwound, to 10 porównań w porównaniu do 100 w oryginale - to jest niewielka, ale prawdopodobnie znacząca, optymalizacja.

Oto Nie-szczegółowe wyjaśnienie, które jest tym, co czuję, że jest sednem urządzenia Duffa:

Rzecz w tym, że C jest w zasadzie ładną fasadą dla języka assembly (PDP - 7 assembly by być konkretnym; gdybyś się tego uczył, zobaczyłbyś, jak uderzające są podobieństwa). W języku asemblowania nie masz pętli - masz etykiety i instrukcje gałęzi warunkowej. Pętla jest więc tylko częścią ogólnej sekwencji instrukcji z etykietą i odgałęzieniem gdzieś:

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

I instrukcja switch rozgałęzia się / przeskakuje nieco do przodu:

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

W assembly łatwo jest wyobrazić sobie, jak połączyć te dwie struktury sterujące, a kiedy tak o tym myślisz, ich kombinacja W C nie wydaje się już taka dziwna.

To jest odpowiedź, którą zamieściłem na inne pytanie dotyczące urządzenia Duffa, które dostało kilka upvaotes, zanim pytanie zostało zamknięte jako DUPLIKAT. Myślę, że dostarcza tu trochę cennego kontekstu, dlaczego powinieneś unikać tego konstruktu.

"to jest Urządzenie Duffa . Jest to metoda rozwijania pętli, która pozwala uniknąć konieczności dodawania dodatkowej pętli naprawczej, aby poradzić sobie z czasami, gdy liczba iteracji pętli nie jest znana jako dokładna wielokrotność współczynnika rozwijania.

Ponieważ większość odpowiedzi tutaj wydają się być ogólnie pozytywne o tym zamierzam podkreślić wady.

Z tym kodem kompilator będzie miał problemy z zastosowaniem optymalizacji do ciała pętli. Jeśli po prostu napisałeś kod jako prostą pętlę, nowoczesny kompilator powinien być w stanie obsłużyć rozwijanie za Ciebie. W ten sposób zachowasz czytelność i wydajność oraz masz nadzieję, że inne optymalizacje zostaną zastosowane do korpusu pętli.

W artykule Wikipedii, do którego odwołują się inni, jest nawet napisane, że kiedy ten 'wzorzec' został usunięty z kodu źródłowego XFree86.

Ten wynik jest typowy dla ślepej ręki optymalizacji dowolnego kodu, który może być potrzebny. Uniemożliwia to kompilatorowi prawidłowe wykonywanie swojej pracy, sprawia, że kod jest mniej czytelny i bardziej podatny na błędy i zazwyczaj spowalnia go. Jeśli w pierwszej kolejności robisz rzeczy we właściwy sposób, tj. pisząc prosty kod, profilując wąskie gardła, a następnie optymalizując, nigdy nie pomyślałbyś, aby użyć coś w tym stylu. Nie z nowoczesnym procesorem i kompilatorem.

Dobrze jest to zrozumieć, ale zdziwiłbym się, gdybyś kiedykolwiek z tego skorzystał."

Oto działający przykład 64-bitowej memcpy z urządzeniem Duffa:

#include <iostream>
#include <memory>

inline void __memcpy(void* to, const void* from, size_t count)
{
    size_t numIter = (count  + 56) / 64;  // gives the number of iterations;  bit shift actually, not division
    size_t rest = count & 63; // % 64
    size_t rest7 = rest&7;
    rest -= rest7;

    // Duff's device with zero case handled:
    switch (rest) 
    {
        case 0:  if (count < 8)
                     break;
                 do { *(((unsigned long long*&)to)++) = *(((unsigned long long*&)from)++);
        case 56:      *(((unsigned long long*&)to)++) = *(((unsigned long long*&)from)++);
        case 48:      *(((unsigned long long*&)to)++) = *(((unsigned long long*&)from)++);
        case 40:      *(((unsigned long long*&)to)++) = *(((unsigned long long*&)from)++);
        case 32:      *(((unsigned long long*&)to)++) = *(((unsigned long long*&)from)++);
        case 24:      *(((unsigned long long*&)to)++) = *(((unsigned long long*&)from)++);
        case 16:      *(((unsigned long long*&)to)++) = *(((unsigned long long*&)from)++);
        case 8:      *(((unsigned long long*&)to)++) = *(((unsigned long long*&)from)++);
                } while (--numIter > 0);
    }

    switch (rest7)
    {
        case 7: *(((unsigned char*)to)+6) = *(((unsigned char*)from)+6);
        case 6: *(((unsigned short*)to)+2) = *(((unsigned short*)from)+2); goto case4;
        case 5: *(((unsigned char*)to)+4) = *(((unsigned char*)from)+4);
        case 4: case4: *((unsigned long*)to) = *((unsigned long*)from); break; 
        case 3: *(((unsigned char*)to)+2) = *(((unsigned char*)from)+2);
        case 2: *((unsigned short*)to) = *((unsigned short*)from); break;
        case 1: *((unsigned char*)to) = *((unsigned char*)from);
    }
}

void main()
{
    static const size_t NUM = 1024;

    std::unique_ptr<char[]> str1(new char[NUM+1]);  
    std::unique_ptr<char[]> str2(new char[NUM+1]);

    for (size_t i = 0 ; i < NUM ; ++ i)
    {
        size_t idx = (i % 62);
        if (idx < 26)
            str1[i] = 'a' + idx;
        else
            if (idx < 52)
                str1[i] = 'A' + idx - 26;
            else
                str1[i] = '0' + idx - 52;
    }

    for (size_t i = 0 ; i < NUM ; ++ i)
    {
        memset(str2.get(), ' ', NUM); 
        __memcpy(str2.get(), str1.get(), i);
        if (memcmp(str1.get(), str2.get(), i) || str2[i] != ' ')
        {
            std::cout << "Test failed for i=" << i;
        }

    }

    return;
}

Obsługuje zero-length case (w oryginalnym urządzeniu Duffa jest założenie num>0). Funkcja main () zawiera proste przypadki testowe dla _ _ memcpy.

Po prostu eksperymentowałem, znalazłem inny wariant dogadujący się bez przeplatania switch wypowiedzi i do-while-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;
}

Technicznie, goto nadal implementuje pętlę, ale ten wariant może być nieco bardziej czytelny.