¿Por qué es 'let' más rápido con alcance léxico?

31

Mientras leía el código fuente de la dolistmacro, me encontré con el siguiente comentario.

;; Esta no es una prueba confiable, pero no importa porque ambas semánticas son aceptables, una es ligeramente más rápida con alcance dinámico y la otra es ligeramente más rápida (y tiene una semántica más limpia) con alcance léxico .

Que se refería a este fragmento (que he simplificado para mayor claridad).

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

Me sorprendió ver que letse usaba un formulario dentro de un bucle. Solía ​​pensar que es lento en comparación con el uso repetido setqen la misma variable externa (como se hace en el segundo caso anterior).

Hubiera descartado eso como nada, si no fuera por el comentario inmediatamente anterior que dice explícitamente que es más rápido que la alternativa (con enlace léxico). Entonces ... ¿por qué es eso?

  1. ¿Por qué el código anterior difiere en rendimiento en el enlace léxico vs dinámico?
  2. ¿Por qué la letforma es más rápida con léxico?
Malabarba
fuente

Respuestas:

38

Enlace léxico versus enlace dinámico en general

Considere el siguiente ejemplo:

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

Compila e inmediatamente desmonta un simple lambdacon una variable local. Con lexical-bindingdeshabilitado, como arriba, el código de bytes se ve de la siguiente manera:

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

Tenga en cuenta las instrucciones varbindy varref. Estas instrucciones enlazan y buscan variables respectivamente por su nombre en un entorno de enlace global en la memoria de almacenamiento dinámico . Todo esto tiene un efecto adverso en el rendimiento: implica el hash y la comparación de cadenas , la sincronización para el acceso a datos globales y el acceso repetido a la memoria de almacenamiento dinámico que juega mal con el almacenamiento en caché de la CPU. Además, los enlaces de variables dinámicas deben restaurarse a su variable anterior al final de let, lo que agrega nbúsquedas adicionales para cada letbloque con nenlaces.

Si se une lexical-bindingal tejemplo anterior, el código de bytes se ve algo diferente:

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

Tenga en cuenta que varbindy varrefse han ido por completo. La variable local simplemente se inserta en la pila y se hace referencia a ella mediante un desplazamiento constante a través de la stack-refinstrucción. Esencialmente, la variable está vinculada y se lee con tiempo constante , lecturas y escrituras en la memoria en la pila , que es completamente local y, por lo tanto, juega bien con la concurrencia y el almacenamiento en caché de la CPU , y no involucra ninguna secuencia.

Generalmente, con las búsquedas de enlace léxico de variables locales (p let. Ej . setq, Etc.) tienen mucho menos tiempo de ejecución y complejidad de memoria .

Este ejemplo especifico

Con enlace dinámico, cada let incurre en una penalización de rendimiento, por las razones anteriores. Cuantos más let, más enlaces variables dinámicos.

Notablemente, con un adicional letdentro del loopcuerpo, la variable vinculada necesitaría ser restaurada en cada iteración del ciclo , agregando una búsqueda de variable adicional a cada iteración . Por lo tanto, es más rápido mantener la salida del cuerpo del bucle, de modo que la variable de iteración solo se restablezca una vez , después de que finalice todo el bucle. Sin embargo, esto no es particularmente elegante, ya que la variable de iteración está vinculada mucho antes de que sea realmente necesaria.

Con encuadernación léxica, los lets son baratos. En particular, un letcuerpo dentro de un bucle no es peor (en términos de rendimiento) que un letexterior de un cuerpo de bucle. Por lo tanto, está perfectamente bien vincular variables lo más localmente posible y mantener la variable de iteración confinada al cuerpo del bucle.

También es un poco más rápido, ya que compila muchas menos instrucciones. Considere el siguiente desmontaje lado a lado (alquiler local en el lado derecho):

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    

Sin embargo, no tengo idea de qué está causando la diferencia.

Lunaryorn
fuente
7

En resumen, el enlace dinámico es muy lento. La unión léxica es extremadamente rápida en tiempo de ejecución. La razón fundamental es que el enlace léxico se puede resolver en tiempo de compilación, mientras que el enlace dinámico no.

Considere el siguiente código:

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

Cuando compila el let, el compilador no puede saber si fooaccederá a la variable (enlazada dinámicamente) x, por lo que debe crear un enlace xy debe retener el nombre de la variable. Con el enlace léxico, el compilador simplemente descarga el valor de xen la pila de enlaces, sin su nombre, y accede directamente a la entrada correcta.

Pero espera hay mas. Con el enlace léxico, el compilador puede verificar que este enlace particular xsolo se use en el código para message; Como xnunca se modifica, es seguro alinear xy ceder

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

No creo que el compilador actual de bytecode realice esta optimización, pero estoy seguro de que lo hará en el futuro.

En resumen:

  • El enlace dinámico es una operación pesada que permite pocas oportunidades de optimización;
  • la unión léxica es una operación ligera;
  • El enlace léxico de un valor de solo lectura a menudo se puede optimizar.
jch
fuente
3

Este comentario no sugiere que el enlace léxico sea más rápido o más lento que el enlace dinámico. Más bien, sugiere que esas formas diferentes tienen características de rendimiento diferentes bajo la vinculación léxica y dinámica, por ejemplo, una de ellas es preferible bajo una disciplina vinculante y la otra preferible en la otra.

Entonces, ¿el alcance léxico es más rápido que el alcance dinámico? Sospecho que en este caso no hay mucha diferencia, pero no sé, realmente tendría que medirlo.

gsg
fuente
1
No hay varbindcódigo compilado bajo enlace léxico. Ese es todo el punto y el propósito.
lunaryorn
Hmm Creé un archivo que contenía la fuente anterior, comencé con ;; -*- lexical-binding: t -*-, lo cargué y llamé (byte-compile 'sum1), suponiendo que producía una definición compilada bajo enlace léxico. Sin embargo, no parece tener.
Gsg
Se eliminaron los comentarios del código de bytes, ya que se basaban en esa suposición incorrecta.
Gsg
La respuesta de lunaryon muestra que este código claramente es más rápido bajo el enlace léxico (aunque, por supuesto, solo a nivel micro).
shosti
@gsg Esta declaración es solo una variable de archivo estándar, que no tiene efecto en las funciones invocadas desde fuera del búfer de archivo correspondiente. IOW, solo tiene efecto si visita el archivo fuente y luego invoca byte-compilecon el búfer correspondiente como actual, que es, por cierto, exactamente lo que está haciendo el compilador de bytes. Si invoca por byte-compileseparado, debe configurarlo explícitamente lexical-binding, como hice en mi respuesta.
lunaryorn