Dlaczego „pozwól” szybciej dzięki zakresowi leksykalnemu?

31

Podczas czytania kodu źródłowego dolistmakra natrafiłem na następujący komentarz.

;; To nie jest wiarygodny test, ale nie ma to znaczenia, ponieważ obie semantyki są dopuszczalne, jedna jest nieco szybsza z dynamicznym określaniem zakresu, a druga jest nieco szybsza (i ma czystszą semantykę) z określaniem zakresu leksykalnego .

Które odnosiły się do tego fragmentu (który uprościłem dla jasności).

(if lexical-binding
    (let ((temp list))
      (while temp
        (let ((it (car temp)))
          ;; Body goes here
          (setq temp (cdr temp)))))
  (let ((temp list)
        it)
    (while temp
      (setq it (car temp))
      ;; Body goes here
      (setq temp (cdr temp)))))

Zaskoczyło mnie, gdy zobaczyłem letformę używaną w pętli. Kiedyś myślałem, że to jest powolne w porównaniu do wielokrotnego używania setqtej samej zmiennej zewnętrznej (jak to ma miejsce w drugim przypadku powyżej).

Odrzuciłbym to jako nic, gdyby nie komentarz znajdujący się bezpośrednio nad nim, wyraźnie mówiąc, że jest szybszy niż alternatywa (z powiązaniem leksykalnym). Więc ... Dlaczego to jest?

  1. Dlaczego powyższy kod różni się wydajnością wiązania leksykalnego od dynamicznego?
  2. Dlaczego letforma jest szybsza dzięki leksykalnemu?
Malabarba
źródło

Odpowiedzi:

38

Oprawa leksykalna a oprawa dynamiczna w ogóle

Rozważ następujący przykład:

(let ((lexical-binding nil))
  (disassemble
   (byte-compile (lambda ()
                   (let ((foo 10))
                     (message foo))))))

Kompiluje i natychmiast dezasembluje prosty lambdaze zmienną lokalną. Po lexical-bindingwyłączeniu, jak wyżej, kod bajtu wygląda następująco:

0       constant  10
1       varbind   foo
2       constant  message
3       varref    foo
4       call      1
5       unbind    1
6       return    

Zwróć uwagę na instrukcje varbindi varref. Instrukcje te wiążą i wyszukują odpowiednio zmienne według ich nazwy w globalnym środowisku powiązań w pamięci sterty . Wszystko to ma negatywny wpływ na wydajność: obejmuje haszowanie i porównywanie ciągów , synchronizację globalnego dostępu do danych oraz powtarzający się dostęp do pamięci sterty, który źle działa przy buforowaniu procesora. Ponadto powiązania zmiennych dynamicznych należy przywrócić do ich poprzedniej zmiennej na końcu let, co dodaje ndodatkowe wyszukiwania dla każdego letbloku z npowiązaniami.

Jeśli wiążą lexical-bindingsię tw powyższym przykładzie, kod bajtowy wygląda nieco inaczej:

0       constant  10
1       constant  message
2       stack-ref 1
3       call      1
4       return    

Zauważ, że varbindi varrefcałkowicie zniknęły. Zmienna lokalna jest po prostu wypychana na stos i określana przez stałe przesunięcie za pomocą stack-refinstrukcji. Zasadniczo zmienna jest związana i odczytywana ze stałym czasem , pamięć na stosie odczytuje i zapisuje, co jest całkowicie lokalne, a zatem dobrze gra z buforowaniem współbieżności i procesora , i nie wymaga żadnych łańcuchów.

Generalnie, z leksykalnych wiążących wyszukiwań zmiennych lokalnych (np let, setqetc.) mają znacznie mniejszą złożoność wykonania i pamięci .

Ten konkretny przykład

Z dynamicznym wiązaniem każdy z nich ponosi karę wydajnościową z powyższych powodów. Im więcej pozwala, tym bardziej dynamiczne wiązania zmiennych.

W szczególności, z dodatkową letczęścią loopciała, powiązana zmienna musiałaby być przywracana przy każdej iteracji pętli , dodając dodatkowe wyszukiwanie zmiennych do każdej iteracji . Dlatego szybsze jest utrzymanie wypuszczenia z ciała pętli, tak że zmienna iteracji jest resetowana tylko raz , po zakończeniu całej pętli. Nie jest to jednak szczególnie eleganckie, ponieważ zmienna iteracyjna jest związana, zanim faktycznie będzie wymagana.

W przypadku leksykalnego wiązania lets są tanie. W szczególności, letciało wewnątrz pętli nie jest gorsze (pod względem wydajności) niż letciało zewnętrzne pętli. Dlatego idealnie można powiązać zmienne tak lokalnie, jak to możliwe, i zachować zmienną iteracyjną ograniczoną do ciała pętli.

Jest również nieco szybszy, ponieważ kompiluje się do znacznie mniej instrukcji. Rozważ następujący demontaż side-by-side (lokalny let po prawej stronie):

0       varref    list            0       varref    list         
1       constant  nil             1:1     dup                    
2       varbind   it              2       goto-if-nil-else-pop 2 
3       dup                       5       dup                    
4       varbind   temp            6       car                    
5       goto-if-nil-else-pop 2    7       stack-ref 1            
8:1     varref    temp            8       cdr                    
9       car                       9       discardN-preserve-tos 2
10      varset    it              11      goto      1            
11      varref    temp            14:2    return                 
12      cdr       
13      dup       
14      varset    temp
15      goto-if-not-nil 1
18      constant  nil
19:2    unbind    2
20      return    

Nie mam jednak pojęcia, co powoduje różnicę.

księżycowy
źródło
7

Krótko mówiąc - dynamiczne wiązanie jest bardzo wolne. Oprawa leksykalna jest niezwykle szybka w czasie wykonywania. Podstawowym powodem jest to, że powiązanie leksykalne można rozwiązać w czasie kompilacji, podczas gdy powiązanie dynamiczne nie.

Rozważ następujący kod:

(let ((x 42))
    (foo)
    (message "%d" x))

Podczas kompilacji letkompilator nie może wiedzieć, czy foouzyska dostęp do (dynamicznie powiązanej) zmiennej x, dlatego musi utworzyć powiązanie xi zachować nazwę zmiennej. Dzięki powiązaniu leksykalnemu kompilator po prostu zrzuca wartość ze xstosu powiązań bez jego nazwy i uzyskuje bezpośredni dostęp do właściwego wpisu.

Ale czekaj - jest więcej. Dzięki powiązaniu leksykalnemu kompilator jest w stanie zweryfikować, czy to szczególne powiązanie xjest używane tylko w kodzie do message; ponieważ xnigdy nie jest modyfikowany, można go bezpiecznie wstawiać xi uzyskiwać

(progn
  (foo)
  (message "%d" 42))

Nie sądzę, że obecny kompilator bajtów wykonuje tę optymalizację, ale jestem pewien, że zrobi to w przyszłości.

W skrócie:

  • dynamiczne wiązanie jest ciężką operacją, która pozwala na kilka możliwości optymalizacji;
  • Oprawa leksykalna jest lekką operacją;
  • Wiązanie leksykalne wartości tylko do odczytu można często zoptymalizować.
jch
źródło
3

Ten komentarz nie sugeruje, że wiązanie leksykalne jest szybsze lub wolniejsze niż wiązanie dynamiczne. Sugeruje raczej, że te różne formy mają różne cechy wydajnościowe w powiązaniu leksykalnym i dynamicznym, np. Jedna z nich jest preferowana w ramach jednej dyscypliny wiążącej, a druga preferowana w drugiej.

Czy zakres leksykalny jest szybszy niż zakres dynamiczny? Podejrzewam, że w tym przypadku nie ma dużej różnicy, ale nie wiem - naprawdę musiałbyś to zmierzyć.

gsg
źródło
1
W varbindkompilacji leksykalnej nie ma kodu skompilowanego. Taki jest cały cel i cel.
lunaryorn
Hmm Utworzyłem plik zawierający powyższe źródło, zaczynając od ;; -*- lexical-binding: t -*-, załadowałem go i wywołałem (byte-compile 'sum1), zakładając, że utworzyłem definicję skompilowaną w powiązaniu leksykalnym. Jednak wydaje się, że nie.
gsg
Usunięto komentarze kodu bajtowego, ponieważ były one oparte na tym błędnym założeniu.
gsg
odpowiedź lunaryona pokazuje, że kod ten jest wyraźnie szybszy w powiązaniu leksykalnym (choć oczywiście tylko na poziomie mikro).
shosti
@gsg Ta deklaracja jest tylko standardową zmienną pliku, która nie ma wpływu na funkcje wywoływane spoza odpowiedniego bufora plików. IOW, ma to wpływ tylko wtedy, gdy odwiedzasz plik źródłowy, a następnie wywołujesz byte-compilez odpowiednim bieżącym buforem, który - nawiasem mówiąc - jest dokładnie tym, co robi kompilator bajtów. Jeśli wywołujesz byte-compileosobno, musisz jawnie ustawić lexical-binding, tak jak ja w mojej odpowiedzi.
lunaryorn