Urządzenie Duffa

W języku programowania C urządzenie Duffa jest sposobem ręcznego rozwijania pętli poprzez przeplatanie dwóch konstrukcji składniowych języka C: pętli do - while i instrukcji switch . Jego odkrycie przypisuje się Tomowi Duffowi w listopadzie 1983 r., Kiedy Duff pracował dla Lucasfilm i użył go do przyspieszenia programu animacji w czasie rzeczywistym.

Rozwijanie pętli ma na celu zmniejszenie narzutu rozgałęzień warunkowych potrzebnych do sprawdzenia, czy pętla została wykonana, poprzez wykonanie partii treści pętli na iterację. Aby obsłużyć przypadki, w których liczba iteracji nie jest podzielna przez przyrosty rozwiniętej pętli, powszechną techniką wśród języka asemblera jest przeskoczenie bezpośrednio do środka rozwiniętej treści pętli, aby obsłużyć resztę. Duff zaimplementował tę technikę w C, używając opadania etykiety opakowania C , aby wskoczyć do rozwiniętego ciała.

Orginalna wersja

Problem Duffa polegał na skopiowaniu 16-bitowych liczb całkowitych bez znaku („skróty” w większości implementacji C) z tablicy do rejestru wyjściowego odwzorowanego w pamięci , oznaczonego w C wskaźnikiem . Jego oryginalny kod w C wyglądał następująco: 

  
   
 

                               
          
        0
 wyślij  (  do  ,  z  ,  policz  )  zarejestruj się  krótko  *  do  ,  *  z  ;  liczba  rejestrów  ;  {  do  {  /* licz > założono 0 */  *  to  =  *  from  ++  ;  }  while  (  -liczba  >  )  ;  }

Ten kod zakłada, że ​​liczba początkowa > 0 . Ponieważ lokalizacja wyjściowa jest rejestrem odwzorowanym w pamięci, wskaźnik do nie jest zwiększany, jak byłoby to wymagane w przypadku kopiowania z pamięci do pamięci.

Gdyby liczba była zawsze podzielna przez osiem, ośmiokrotne rozwinięcie tej pętli dałoby: 

  
   
 

         
     
          
          
          
          
          
          
          
          
        0
 wyślij  (  do  ,  z  ,  policz  )  zarejestruj się  krótko  *  do  ,  *  z  ;  liczba  rejestrów  ;  {  rejestr  n  =  liczba  /  8  ;  wykonaj  {  *  do  =  *  z  ++  ;  *  do  =  *  z  ++  ;  *  do  =  *  z  ++  ;  *  do  =  *  z  ++  ;  *  do  =  *  z  ++  ;  *  do  =  *  z  ++  ;  *  do  =  *  z  ++  ;  *  do  =  *  z  ++  ;  }  podczas  (  -  n  >  );  }

Duff zdał sobie sprawę, że aby obsłużyć przypadki, w których liczba nie jest podzielna przez osiem, technikę programisty asemblera polegającą na przeskakiwaniu do treści pętli można zaimplementować, przeplatając struktury instrukcji switch i pętli, umieszczając etykiety przypadków przełącznika w punktach pętli ciało, które odpowiada pozostałej części count/8 : 

  
   
 

           
        
     0     
             
             
             
             
             
             
             
                0
    
 wyślij  (  do  ,  z  ,  policz  )  zarejestruj się  krótko  *  do  ,  *  z  ;  liczba  rejestrów  ;  {  rejestr  n  =  (  liczba  +  7  )  /  8  ;  przełącz  (  licz  %  8  )  {  case  :  do  {  *  to  =  *  from  ++  ;  przypadek  7  :  *  do  =  *  z  ++  ;  przypadek  6  :  *  do  =  *  z  ++  ;  przypadek  5  :  *  do  =  *  z  ++  ;  przypadek  4  :  *  do  =  *  z  ++  ;  przypadek  3  :  *  do  =  *  z  ++  ;  przypadek  2  :  *  do  =  *  z  ++  ;  przypadek  1  :  *  do  =  *  z  ++  ;  }  podczas  (  -  n  >  );  }  }

Urządzenie Duffa można podobnie zastosować z dowolnym innym rozmiarem rozwiniętej pętli, a nie tylko z ośmioma, jak w powyższym przykładzie.

Mechanizm

W oparciu o algorytm szeroko stosowany przez programistów kodujących w asemblerze w celu zminimalizowania liczby testów i rozgałęzień podczas kopiowania, urządzenie Duffa wydaje się nie na miejscu, gdy jest zaimplementowane w C. Urządzenie jest ważne w C dzięki dwóm atrybutom w C:

  1. Zrelaksowana specyfikacja instrukcji switch w definicji języka. W czasie wynalezienia urządzenia było to pierwsze wydanie języka programowania C , które wymagało jedynie, aby treść przełącznika była poprawną składniowo (złożoną) instrukcją, w której etykiety przypadków mogą pojawiać się przed dowolnymi instrukcjami podrzędnymi. W połączeniu z faktem, że w przypadku braku break przepływ sterowania będzie przechodził od instrukcji kontrolowanej przez jedną etykietę przypadku do instrukcji kontrolowanej przez następną, oznacza to, że kod określa ciąg zliczania kopii z kolejnych adresy źródłowe do portu wyjściowego mapowanego w pamięci.
  2. Możliwość wskoczenia w środek pętli w C.

Prowadzi to do tego, co Jargon File nazywa „najbardziej dramatycznym jak dotąd użyciem upadku w C”. Domyślne przełączanie instrukcji case w języku C od dawna jest jedną z jego najbardziej kontrowersyjnych funkcji; Sam Duff powiedział, że „Ten kod stanowi jakiś argument w tej debacie, ale nie jestem pewien, czy jest za, czy przeciw”.

Chociaż działa w C, urządzenie Duffa jest sprzeczne z powszechnymi wytycznymi C, takimi jak wytyczne MISRA . Niektóre kompilatory (np. CompCert ) ograniczają się do takich wytycznych i dlatego mogą odrzucić urządzenie Duffa.

Uproszczone wyjaśnienie

Funkcjonalnie równoważna
z przełącznikiem i rozplątanym * 
  
   wysyłaniem  (  do  ,  z  ,  licznikiem  )  rejestru  short  *  to  ,   wersja 
 

           
        
         0   
            
            
            
            
            
            
            
    
       0 
          
          
          
          
          
          
          
          
    
 from  ;  liczba  rejestrów  ;  {  rejestr  n  =  (  liczba  +  7  )  /  8  ;  przełącz  (  licz  %  8  )  {  case  :  *  to  =  *  from  ++  ;  przypadek  7  :  *  do  =  *  z  ++  ;  przypadek  6  :  *  do  =  *  z  ++  ;  przypadek  5  :  *  do  =  *  z  ++  ;  przypadek  4  :  *  do  =  *  z  ++  ;  przypadek  3  :  *  do  =  *  z  ++  ;  przypadek  2  :  *  do  =  *  z  ++  ;  przypadek  1  :  *  do  =  *  z  ++  ;  }  while  (  -  n  >  )  {  *  do  =  *  z  ++  ;  *  do  =  *  z  ++  ;  *  do  =  *  z  ++  ;  *  do  =  *  z  ++  ;  *  do  =  *  z  ++  ;  *  do  =  *  z  ++  ;  *  do  =  *  z  ++  ;  *  do  =  *  z  ++  ;  }  }

Podstawową ideą rozwijania pętli jest to, że liczbę instrukcji wykonywanych w pętli można zmniejszyć, zmniejszając liczbę testów pętli, czasami zmniejszając ilość czasu spędzonego w pętli. Na przykład, w przypadku pętli z tylko jedną instrukcją w kodzie bloku, test pętli będzie typowo wykonywany dla każdej iteracji pętli, czyli za każdym razem, gdy instrukcja jest wykonywana. Jeśli zamiast tego w pętli zostanie umieszczonych osiem kopii tej samej instrukcji, wówczas test będzie wykonywany tylko co osiem iteracji, co może zyskać na czasie, unikając siedmiu testów. Jednak obsługuje to tylko wielokrotność ośmiu iteracji, wymagając czegoś innego do obsługi pozostałych iteracji .

Urządzenie Duffa zapewnia rozwiązanie, wykonując najpierw pozostałe iteracje, a następnie powtarzając tyle razy, ile to konieczne, wielokrotność ośmiu podobnych instrukcji. Aby określić liczbę pozostałych iteracji, kod najpierw oblicza całkowitą liczbę iteracji modulo osiem. Zgodnie z tą resztą wykonanie programu przeskoczy do instrukcji case , po której nastąpi dokładnie taka liczba iteracji, jaka jest potrzebna . Po wykonaniu tej czynności wszystko jest proste – kod kontynuuje wykonywanie iteracji grup ośmiu instrukcji, co stało się możliwe, ponieważ pozostała liczba iteracji jest wielokrotnością ośmiu.

Urządzenie Duffa umożliwia rozwijanie zwartej pętli za pomocą słowa kluczowego case zarówno wewnątrz, jak i na zewnątrz pętli . Jest to niezwykłe, ponieważ treść instrukcji case jest tradycyjnie traktowana jako blok kodu zagnieżdżony w instrukcji case, a czytelnik zazwyczaj oczekuje, że zakończy się ona przed następną instrukcją case. Zgodnie ze specyfikacjami języka C nie jest to konieczne; w rzeczywistości instrukcje case mogą pojawić się w dowolnym miejscu wewnątrz przełącznika i na dowolnej głębokości; wykonanie programu po prostu przeskoczy do następnej instrukcji, gdziekolwiek się ona znajduje.

Wydajność

Wiele kompilatorów zoptymalizuje przełączanie do tablicy rozgałęzień, tak jak byłoby to zrobione w implementacji asemblera.

Podstawowy wzrost prędkości w porównaniu z prostą, prostą pętlą wynika z rozwijania pętli , które zmniejsza liczbę wykonywanych rozgałęzień, które są kosztowne obliczeniowo ze względu na konieczność przepłukania ‍ — „a tym samym zatrzymania” — ‌potoku instrukcji . Instrukcja switch służy do obsługi pozostałych danych, które nie są równo podzielne przez liczbę rozwiniętych operacji (w tym przykładzie rozwijanych jest osiem krótkich ruchów, więc przełącznik automatycznie obsługuje dodatkowe 1–7 krótkich ruchów).

Ta automatyczna obsługa reszty może nie być najlepszym rozwiązaniem we wszystkich systemach i kompilatorach — w niektórych przypadkach dwie pętle mogą być w rzeczywistości szybsze (jedna pętla, rozwinięta, do wykonania głównej kopii i druga pętla do obsługi pozostałej części). Wydaje się, że problem sprowadza się do zdolności kompilatora do prawidłowej optymalizacji urządzenia; może również zakłócać potokowanie i przewidywanie rozgałęzień w niektórych architekturach. Kiedy liczne instancje urządzenia Duffa zostały usunięte z XFree86 w wersji 4.0, nastąpiła poprawa wydajności i zauważalne zmniejszenie rozmiaru pliku wykonywalnego. Dlatego rozważając ten kod jako optymalizację programu , warto przeprowadzić kilka testów porównawczych , aby sprawdzić, czy faktycznie jest to najszybszy kod w docelowej architekturze, na docelowym poziomie optymalizacji, z docelowym kompilatorem, a także rozważyć ryzyko że zoptymalizowany kod będzie później używany na różnych platformach, gdzie nie jest to najszybszy kod.

Do celów kopiowania z pamięci do pamięci (co, jak wspomniano powyżej, nie było pierwotnym zastosowaniem urządzenia Duffa), standardowa biblioteka C udostępnia funkcję memcpy ; nie będzie działać gorzej niż wersja tego kodu kopiowana z pamięci do pamięci i może zawierać optymalizacje specyficzne dla architektury, które czynią go znacznie szybszym.

Zobacz też

Dalsza lektura

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Duff%27s_device&oldid=1133171666 ”