Jak działa urządzenie Duffa?


Odpowiedzi:


240

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


1
Jak można pominąć klauzulę case 0: i kontynuować sprawdzanie innych klauzul, które znajdują się w pętli do while, która jest argumentem pominiętej klauzuli? Jeśli jedyna klauzula znajdująca się poza pętlą do while jest pomijana, dlaczego przełącznik nie kończy się na tym?
Aurelius,

14
Nie patrz tak mocno na aparat. Nie patrz na dotak dużo. Zamiast tego spójrz na switchi whilejako staromodne GOTOinstrukcje obliczone lub jmpinstrukcje asemblera z przesunięciem. switchRobi trochę matematyki, a następnie jmps we właściwym miejscu. whileRobi logiczną kontrolę i następnie ślepo jmpS, aby prawo o tym, gdzie dobył.
Clinton Pierce

Jeśli to jest tak dobre, dlaczego nie wszyscy tego używają? Czy są jakieś wady?
AlphaGoku,

Czytelność @AlphaGoku.
LF

108

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

dobry post (plus muszę znaleźć jedną dobrą odpowiedź od Ciebie na głosowanie za;) 2 w dół, 13 do przejścia: stackoverflow.com/questions/359727#486543 ). Ciesz się odznaką miłej odpowiedzi.
VonC

13
Kluczowym faktem, który sprawił, że urządzenie Duffa było dla mnie najdłużej niezrozumiałe, jest to, że dziwactwem C, po raz pierwszy dociera do chwili, odskakuje i wykonuje wszystkie instrukcje. Zatem nawet jeśli len%8było 4, wykona przypadek 4, przypadek 2, przypadek 2 i przypadek 1, a następnie przeskoczy wstecz i wykona wszystkie obserwacje od następnej pętli. Jest to część, która wymaga wyjaśnienia, sposób, w jaki pętla i instrukcja przełącznika „współdziałają”.
ShreevatsaR

2
Artykuł dr. Dobbsa jest dobry, jednak poza linkiem odpowiedź nic nie dodaje. Zobacz odpowiedź Roba Kennedy'ego poniżej, która faktycznie dostarcza ważnego punktu na temat pozostałej części rozmiaru transferu, która jest obsługiwana jako pierwsza, po której następuje zero lub więcej bloków transferowych po 8 bajtów. Moim zdaniem to klucz do zrozumienia tego kodu.
Richard Chambers

3
Czy czegoś mi brakuje, czy w drugim fragmencie kodu len % 8bajty nie zostaną skopiowane?
nowicjusz

Utknąłem, zapominając, że jeśli nie napiszesz instrukcji break na końcu listy instrukcji sprawy, C (lub jakikolwiek inny język) będzie wykonywał instrukcje. Więc jeśli zastanawiasz się, dlaczego urządzenie
Duffa

75

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.


5
To wyjaśnienie ma więcej sensu. klucz do zrozumienia, że ​​reszta jest kopiowana najpierw w blokach po 8 bajtów, co jest niezwykłe, ponieważ, jak wspomniano, w większości przypadków kopiowano w blokach po 8 bajtów, a następnie kopiowano resztę. wykonanie pozostałej części w pierwszej kolejności jest kluczem do zrozumienia tego algorytmu.
Richard Chambers

+1 za wspomnienie o szalonym rozmieszczeniu / zagnieżdżaniu przełącznika / pętli podczas.
Trudno

13

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


3
Zauważ, że urządzenie duffa nie jest ograniczone do 8 powtórzeń w instrukcji switch.
strager

dlaczego nie możesz po prostu użyć zamiast --count, count = count-8? i użyć drugiej pętli, aby zająć się resztą?
hhafez

1
Hhafez, możesz użyć drugiej pętli, aby zająć się resztą. Ale teraz masz dwa razy więcej kodu, aby osiągnąć to samo bez zwiększania szybkości.
Rob Kennedy

Johan, masz to do tyłu. Pozostałe 4 bajty są kopiowane w pierwszej iteracji pętli, a nie w ostatniej.
Rob Kennedy,

8

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.

6

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


Zainteresowałem się urządzeniem Duffs po tym pytaniu: stackoverflow.com/questions/17192246/switch-case-weird-scoping, więc pomyślałem, że spróbuję wyjaśnić Duff - nie jestem pewien, czy to jakieś ulepszenie istniejących odpowiedzi ...
Ricibob

3

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.


8
Brakuje Ci kluczowej części. Nie chodzi tylko o rozwijanie pętli. Instrukcja switch przeskakuje do środka pętli. To właśnie sprawia, że ​​urządzenie wygląda tak zagmatwane. Twoja pętla powyżej zawsze wykonuje wielokrotność 10 kopii, ale Duff wykonuje dowolną liczbę.
Rob Kennedy,

2
To prawda - ale próbowałem uprościć opis PO. Być może nie wyjaśniłem tego wystarczająco! :)
James B

2

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.


1

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


0

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

Gdzie jest twój warunek zakończenia?
user2338150
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.