Pourquoi «laisser» plus vite avec une portée lexicale?

31

En lisant le code source de la dolistmacro, je suis tombé sur le commentaire suivant.

;; Ce n'est pas un test fiable, mais cela n'a pas d'importance car les deux sémantiques sont acceptables, l'une est légèrement plus rapide avec une portée dynamique et l'autre est légèrement plus rapide (et a une sémantique plus propre) avec une portée lexicale .

Qui faisait référence à cet extrait (que j'ai simplifié pour plus de clarté).

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

Cela m'a surpris de voir un letformulaire utilisé dans une boucle. Je pensais que c'était lent par rapport à l'utilisation répétée setqde la même variable externe (comme cela se fait dans le deuxième cas ci-dessus).

J'aurais rejeté cela comme rien, sinon pour le commentaire immédiatement au-dessus, disant explicitement que c'est plus rapide que l'alternative (avec liaison lexicale). Alors ... Pourquoi ça?

  1. Pourquoi le code ci-dessus diffère-t-il en termes de performances sur la liaison lexicale et dynamique?
  2. Pourquoi le letformulaire est-il plus rapide avec lexical?
Malabarba
la source

Réponses:

38

Reliure lexicale contre reliure dynamique en général

Prenons l'exemple suivant:

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

Il compile et démonte immédiatement un simple lambdaavec une variable locale. Avec lexical-bindingdésactivé, comme ci-dessus, le code d'octet se présente comme suit:

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

Notez les instructions varbindet varref. Ces instructions lient et recherchent respectivement des variables par leur nom dans un environnement de liaison global sur la mémoire de tas . Tout cela a un effet négatif sur les performances: cela implique le hachage et la comparaison des chaînes , la synchronisation pour l'accès aux données globales et l'accès répété à la mémoire de tas qui joue mal avec la mise en cache du processeur. De plus, les liaisons de variables dynamiques doivent être restaurées à leur variable précédente à la fin de let, ce qui ajoute ndes recherches supplémentaires pour chaque letbloc avec des nliaisons.

Si vous vous liez lexical-bindingà tdans l'exemple ci-dessus, le code d'octet est quelque peu différent:

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

Notez que varbindet varrefsont complètement partis. La variable locale est simplement poussée sur la pile et désignée par un décalage constant via l' stack-refinstruction. Essentiellement, la variable est liée et lue avec un temps constant , la lecture et l'écriture dans la mémoire de la pile , qui est entièrement locale et joue donc bien avec la concurrence et la mise en cache du processeur , et n'implique aucune chaîne .

En général, avec liaison lexicales de lookups variables locales (par exemple let, setq, etc.) ont beaucoup moins de complexité d'exécution et de la mémoire .

Cet exemple spécifique

Avec la liaison dynamique, chaque let entraîne une pénalité de performance, pour les raisons ci-dessus. Le plus permet, les liaisons de variables plus dynamiques.

En particulier, avec un élément supplémentaire letdans le loopcorps, la variable liée devrait être restaurée à chaque itération de la boucle , en ajoutant une recherche de variable supplémentaire à chaque itération . Par conséquent, il est plus rapide de conserver la sortie du corps de la boucle, de sorte que la variable d'itération n'est réinitialisée qu'une seule fois , une fois la boucle terminée. Cependant, ce n'est pas particulièrement élégant, car la variable d'itération est liée bien avant qu'elle ne soit réellement requise.

Avec la reliure lexicale, les lets sont bon marché. Notamment, un letcorps de boucle n'est pas pire (en termes de performances) qu'un letextérieur de corps de boucle. Par conséquent, il est parfaitement possible de lier des variables aussi localement que possible et de conserver la variable d'itération confinée au corps de la boucle.

Il est également légèrement plus rapide, car il compile beaucoup moins d'instructions. Considérez le démontage côte à côte suivi (let local sur le côté droit):

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    

Je n'ai cependant aucune idée de ce qui cause la différence.

lunaryorn
la source
7

En bref - la liaison dynamique est très lente. La reliure lexicale est extrêmement rapide à l'exécution. La raison fondamentale est que la liaison lexicale peut être résolue au moment de la compilation, contrairement à la liaison dynamique.

Considérez le code suivant:

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

Lors de sa compilation de let, le compilateur ne peut pas savoir s'il fooaccède à la variable (liée dynamiquement) x, il doit donc créer une liaison pour xet doit conserver le nom de la variable. Avec la liaison lexicale, le compilateur vide simplement la valeur de xsur la pile de liaisons, sans son nom, et accède directement à la bonne entrée.

Mais attendez - il y a plus. Avec la liaison lexicale, le compilateur est en mesure de vérifier que cette liaison particulière de xest uniquement utilisée dans le code pour message; comme il xn'est jamais modifié, il est sûr de s'aligner xet de céder

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

Je ne pense pas que le compilateur de bytecode actuel effectue cette optimisation, mais je suis convaincu qu'il le fera à l'avenir.

Bref:

  • la liaison dynamique est une opération lourde qui permet peu d'opportunités d'optimisation;
  • la reliure lexicale est une opération légère;
  • la liaison lexicale d'une valeur en lecture seule peut souvent être optimisée.
jch
la source
3

Ce commentaire ne suggère pas que la liaison lexicale soit plus rapide ou plus lente que la liaison dynamique. Au contraire, cela suggère que ces différentes formes ont des caractéristiques de performance différentes sous la liaison lexicale et dynamique, par exemple, l'une d'entre elles est préférable dans une discipline contraignante, et l'autre préférable dans l'autre.

La portée lexicale est-elle donc plus rapide que la portée dynamique? Je soupçonne que dans ce cas, il n'y a pas beaucoup de différence, mais je ne sais pas - il faudrait vraiment le mesurer.

gsg
la source
1
Il n'y a pas varbindde code compilé sous liaison lexicale. C'est tout le but et le but.
lunaryorn
Hmm. J'ai créé un fichier contenant la source ci-dessus, en commençant par ;; -*- lexical-binding: t -*-, chargé et appelé (byte-compile 'sum1), en supposant que produit une définition compilée sous liaison lexicale. Cependant, cela ne semble pas l'avoir fait.
gsg
Suppression des commentaires de code d'octet car ils étaient basés sur cette hypothèse erronée.
gsg
la réponse de lunaryon montre que ce code est clairement plus rapide sous reliure lexicale (bien sûr seulement au niveau micro).
shosti
@gsg Cette déclaration n'est qu'une variable de fichier standard, qui n'a aucun effet sur les fonctions appelées de l'extérieur du tampon de fichier correspondant. IOW, cela n'a d'effet que si vous visitez le fichier source, puis l'invoquez byte-compileavec le tampon correspondant en cours, ce qui est - soit dit en passant - exactement ce que fait le compilateur d'octets. Si vous invoquez byte-compileséparément, vous devez définir explicitement lexical-binding, comme je l'ai fait dans ma réponse.
lunaryorn