Jak działa urządzenie Duffa?

Przeczytałem artykuł na Wikipedii na urządzeniu Duffa i nie rozumiem. Jestem bardzo zainteresowany, ale przeczytałem tam wyjaśnienie kilka razy i nadal nie rozumiem, jak działa urządzenie Duffa.

Jakie byłoby bardziej szczegółowe wyjaśnienie?

Gdzie indziej jest kilka dobrych wyjaśnień, ale spróbuję. (Na tablicy jest to o wiele łatwiejsze!) Oto przykład z Wikipedii z pewnymi zapisami.

Powiedzmy, że kopiujesz 20 bajtów. Sterowanie przepływem programu dla pierwszego przejścia to:

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

Teraz zacznij drugi przebieg, uruchamiamy tylko wskazany kod:

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

Teraz zacznij trzeci przebieg:

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

Kopiowanych jest teraz 20 bajtów.

Uwaga: Oryginalne urządzenie Duffa (pokazane powyżej) zostało skopiowane do urządzenia I / O pod toadresem. W związku z tym nie było potrzeby zwiększania wskaźnika *to. Podczas kopiowania między dwoma buforami pamięci trzeba by użyć *to++.

Wyjaśnienie Dr. Dobb za Urzędowym jest najlepszym, które znalazłem na ten temat.

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

Istnieją dwie kluczowe rzeczy dotyczące urządzenia Duffa. Po pierwsze, co, jak podejrzewam, jest łatwiejsze do zrozumienia, pętla jest rozwijana. W ten sposób można uzyskać większą szybkość kodu, unikając części narzutów związanych ze sprawdzaniem, czy pętla jest zakończona i przeskakując z powrotem na początek pętli. Procesor może działać szybciej, gdy wykonuje kod w linii prostej zamiast skakać.

Drugim aspektem jest instrukcja przełączania. Pozwala kodowi przeskoczyć do środka pętli za pierwszym razem. Zaskakujące dla większości ludzi jest to, że takie rzeczy są dozwolone. Cóż, jest to dozwolone. Wykonywanie rozpoczyna się od obliczonej etykiety przypadku, a następnie przechodzi do każdej kolejnej instrukcji przypisania, tak jak każda inna instrukcja switch. Po ostatniej etykiecie przypadku wykonanie dociera do końca pętli, po czym wraca na początek. Góra pętli znajduje się wewnątrz instrukcji switch, więc przełącznik nie jest już ponownie oceniany.

Oryginalna pętla jest rozwijana osiem razy, więc liczba iteracji jest dzielona przez osiem. Jeśli liczba bajtów do skopiowania nie jest wielokrotnością ośmiu, pozostało jeszcze kilka bajtów. Większość algorytmów, które kopiują 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 % 8dla instrukcji switch, jaka będzie reszta, przeskakuje do etykiety przypadku dla tej liczby 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ń wykonywanych w ścisłej implementacji memcpy.

Załóżmy, że chcesz skopiować `` licznik '' bajtów z a do b, prostym podejściem jest wykonanie następujących czynności:

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

Ile razy musisz porównać liczbę, aby sprawdzić, czy jest powyżej 0? „policz” razy.

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

Teraz przypuść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, w którym kopiujesz tylko 4.

AKTUALIZACJA: Nie musisz robić 8 porównań / instrukcji przełączania wielkości liter, ale rozsądny jest kompromis między rozmiarem funkcji a szybkością.

Kiedy przeczytałem go po raz pierwszy, automatycznie sformatowałem go w ten sposób

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

i nie miałem pojęcia, co się dzieje.

Może nie, kiedy zadano to pytanie, ale teraz Wikipedia ma bardzo dobre wyjaśnienie

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

• Rozluźniona specyfikacja instrukcji switch w definicji języka. W czasie wynalezienia urządzenia było to pierwsze wydanie Języka programowania C, które wymaga jedynie, aby kontrolowana instrukcja przełącznika była instrukcją poprawną składniowo (złożoną), w ramach której etykiety przypadków mogą pojawiać się przed każdą instrukcją podrzędną. W połączeniu z faktem, że w przypadku braku instrukcji break przepływ kontroli będzie przechodził z instrukcji kontrolowanej przez jedną etykietę przypadku do tej kontrolowanej przez następną, oznacza to, że kod określa następstwo liczby kopii z kolejne adresy źródłowe do portu wyjściowego mapowanego w pamięci.
• Możliwość legalnego wskoczenia w środek pętli w C.

1: Urządzenie Duffsa jest szczególną implementacją rozwijania pętli. Co to jest rozwijanie pętli?
Jeśli masz operację do wykonania N razy w pętli, możesz zamienić rozmiar programu na szybkość, wykonując pętlę N / n razy, a następnie w pętli wprowadzając (rozwijając) 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!
}

Co działa świetnie, jeśli N% n == 0 - nie ma potrzeby korzystania z Duff! Jeśli to nie jest prawda, musisz poradzić sobie z resztą - co jest bólem.

2: Czym różni się urządzenie Duffs od tego standardowego rozwijania pętli?
Urządzenie Duffsa jest po prostu sprytnym sposobem radzenia sobie z pozostałymi cyklami pętli, gdy N% n! = 0. Całe do / while wykonuje N / n tyle razy, jak w przypadku standardowego rozwijania pętli (ponieważ ma zastosowanie przypadek 0). Przy ostatnim przejściu przez pętlę („N / n + 1-ty raz”) przypadek zaczyna działać i przechodzimy do przypadku N% n i uruchamiamy kod pętli tyle razy, ile „reszta”.

Chociaż nie jestem w 100% pewien, o co prosisz, oto ...

Problem, który adresuje urządzenie Duff, polega na rozwijaniu pętli (jak bez wątpienia zauważyłeś w opublikowanym przez Ciebie łączu Wiki). To, co w zasadzie oznacza, to optymalizacja wydajności w czasie wykonywania w stosunku do zużycia pamięci. Urządzenie Duffa radzi sobie z kopiowaniem seryjnym, a nie tylko z jakimkolwiek starym problemem, ale jest klasycznym przykładem tego, jak można dokonać optymalizacji, zmniejszając liczbę razy, gdy porównanie musi być wykonywane 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 za każdym razem dodaj do nich 1 ... zwykle możesz użyć pętli for i wykonać pętlę około 100 razy . Wydaje się to dość logiczne i jest ... jednak optymalizacja może być dokonana poprzez rozwinięcie pętli (oczywiście niezbyt daleko ... lub równie dobrze możesz po prostu nie używać pętli).

A więc zwykła pętla for:

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

To, co robi urządzenie Duffa, to implementacja tego pomysłu w C, ale (jak widzieliście na Wiki) z kopiami seryjnymi. To, co widzisz powyżej, z odwiniętym przykładem, to 10 porównań w porównaniu do 100 w oryginale - to niewielka, ale prawdopodobnie znacząca optymalizacja.

Oto nie szczegółowe wyjaśnienie, które wydaje mi się być sednem urządzenia Duffa:

Rzecz w tym, że C jest w zasadzie ładną fasadą dla języka asemblera (konkretnie assembler PDP-7; gdybyś przestudiował, zobaczyłbyś, jak uderzające są podobieństwa). A w języku asemblera tak naprawdę nie masz pętli - masz etykiety i instrukcje rozgałęzień warunkowych. Więc pętla jest tylko częścią ogólnej sekwencji instrukcji z etykietą i gdzieś odgałęzieniem:

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

a instrukcja przełącznika nieco się rozgałęzia / przeskakuje:

        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 asemblerze łatwo sobie wyobrazić, jak połączyć te dwie struktury kontrolne, a kiedy pomyślisz o tym w ten sposób, ich połączenie w C nie wydaje się już takie dziwne.

To jest odpowiedź, którą opublikowałem na inne pytanie dotyczące urządzenia Duffa, które otrzymało kilka pozytywnych ocen, zanim pytanie zostało zamknięte jako duplikat. Myślę, że dostarcza tu trochę cennego kontekstu, dlaczego należy unikać tej konstrukcji.

„To jest urządzenie Duffa . Jest to metoda rozwijania pętli, która pozwala uniknąć konieczności dodawania dodatkowej pętli ustalającej, aby poradzić sobie z momentami, w których liczba iteracji pętli nie jest dokładną wielokrotnością współczynnika rozwijania.

Ponieważ większość odpowiedzi tutaj wydaje się być ogólnie pozytywna, zamierzam podkreślić wady.

Z tym kodem kompilator będzie miał trudności z zastosowaniem jakiejkolwiek optymalizacji w treści pętli. Jeśli właśnie napisałeś kod jako prostą pętlę, nowoczesny kompilator powinien być w stanie obsłużyć rozwijanie za Ciebie. W ten sposób zachowujesz czytelność i wydajność oraz masz nadzieję na zastosowanie innych optymalizacji do treści pętli.

Artykuł Wikipedii, do którego odwołują się inni, mówi nawet, że kiedy ten „wzorzec” został usunięty z kodu źródłowego Xfree86, wydajność faktycznie się poprawiła.

Ten wynik jest typowy dla ślepej ręcznej optymalizacji dowolnego kodu, o którym myślisz, że może go potrzebować. Uniemożliwia kompilatorowi prawidłowe wykonanie swojej pracy, sprawia, że ​​kod jest mniej czytelny i bardziej podatny na błędy, a także zazwyczaj go spowalnia. Gdybyś robił wszystko we właściwy sposób, tj. Pisał prosty kod, potem tworzył profilowanie pod kątem wąskich gardeł, a potem optymalizował, nawet nie pomyślałbyś o użyciu czegoś takiego. W każdym razie nie z nowoczesnym procesorem i kompilatorem.

Dobrze to zrozumieć, ale zdziwiłbym się, gdybyś kiedykolwiek go użył ”.

Po prostu eksperymentowałem, znalazłem inny wariant, który radził sobie bez przeplatania przełącznika i pętli:

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