Por que `let 'é mais rápido com escopo lexical?

31

Ao ler o código fonte da dolistmacro, deparei-me com o seguinte comentário.

;; Este não é um teste confiável, mas não importa, porque ambas as semânticas são aceitáveis, uma é um pouco mais rápida com escopo dinâmico e a outra é um pouco mais rápida (e tem semântica mais limpa) com escopo lexical .

Que se refere a este trecho (que simplifiquei para maior clareza).

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

Surpreendeu-me ver um letformulário sendo usado dentro de um loop. Eu costumava pensar que isso é lento em comparação com o uso repetido setqna mesma variável externa (como é feito no segundo caso acima).

Eu teria descartado isso como nada, se não fosse o comentário imediatamente acima dizendo explicitamente que é mais rápido que a alternativa (com ligação lexical). Então ... por que isso?

  1. Por que o código acima difere no desempenho na ligação lexical x dinâmica?
  2. Por que o letformulário é mais rápido com o léxico?
Malabarba
fonte

Respostas:

38

Ligação lexical versus ligação dinâmica em geral

Considere o seguinte exemplo:

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

Compila e desmonta imediatamente um simples lambdacom uma variável local. Com lexical-bindingdesativado, como acima, o código de bytes é o seguinte:

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

Observe as instruções varbinde varref. Essas instruções ligam e pesquisam as variáveis, respectivamente, pelo nome em um ambiente de ligação global na memória heap . Tudo isso tem um efeito adverso no desempenho: envolve hash e comparação de strings , sincronização para acesso global a dados e acesso repetido à memória heap, que é prejudicial ao cache da CPU. Além disso, as ligações de variáveis ​​dinâmicas precisam ser restauradas para sua variável anterior no final de let, o que adiciona npesquisas adicionais para cada letbloco com nligações.

Se você vincular lexical-bindinga tno exemplo acima, o código byte parece um pouco diferente:

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

Note que varbinde se varrefforam completamente. A variável local é simplesmente empurrada para a pilha e referida por um deslocamento constante através da stack-refinstrução. Essencialmente, a variável é vinculada e lida com tempo constante , as leituras e gravações de memória na pilha , que são inteiramente locais e, portanto, funcionam bem com simultaneidade e cache de CPU , e não envolvem nenhuma string.

Geralmente, com pesquisas de ligação lexicais de variáveis locais (por exemplo let, setq, etc.) têm muito menos tempo de execução e memória complexidade .

Este exemplo específico

Com ligação dinâmica, cada uma delas incorre em uma penalidade de desempenho, pelas razões acima. Quanto mais vamos permitir, mais vinculações de variáveis ​​dinâmicas.

Notavelmente, com um adicional letdentro do loopcorpo, a variável vinculada precisaria ser restaurada a cada iteração do loop , adicionando uma pesquisa de variável adicional a cada iteração . Portanto, é mais rápido manter a liberação do corpo do loop, para que a variável de iteração seja redefinida apenas uma vez , após o término de todo o loop. No entanto, isso não é particularmente elegante, pois a variável de iteração é vinculada muito antes de ser realmente necessária.

Com encadernação lexical, lets são baratos. Notavelmente, um letcorpo dentro de um loop não é pior (em termos de desempenho) do que o letexterior de um corpo de loop. Portanto, é perfeitamente bom vincular variáveis ​​o mais local possível e manter a variável de iteração confinada ao corpo do loop.

Também é um pouco mais rápido, porque compila com muito menos instruções. Considere a desmontagem seguida a lado (local deixe no lado direito):

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    

Não tenho idéia, no entanto, o que está causando a diferença.

lunaryorn
fonte
7

Em resumo - a ligação dinâmica é muito lenta. A ligação lexical é extremamente rápida no tempo de execução. A razão fundamental é que a ligação lexical pode ser resolvida em tempo de compilação, enquanto a ligação dinâmica não pode.

Considere o seguinte código:

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

Ao compilar o let, o compilador não pode saber se fooacessará a variável (vinculada dinamicamente) x, portanto, deve criar uma ligação para xe deve manter o nome da variável. Com a ligação lexical, o compilador apenas despeja o valor de xna pilha de ligações, sem seu nome, e acessa a entrada correta diretamente.

Mas espere - há mais. Com ligação lexical, o compilador é capaz de verificar se essa ligação específica xé usada apenas no código para message; Como xnunca é modificado, é seguro incorporar xe produzir

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

Não acho que o compilador de bytecode atual execute essa otimização, mas estou confiante de que o fará no futuro.

Então, resumindo:

  • a ligação dinâmica é uma operação pesada que permite poucas oportunidades de otimização;
  • encadernação lexical é uma operação leve;
  • A ligação lexical de um valor somente leitura pode ser otimizada com frequência.
jch
fonte
3

Este comentário não sugere que a ligação lexical seja mais rápida ou mais lenta que a ligação dinâmica. Em vez disso, sugere que essas formas diferentes têm características de desempenho diferentes sob ligação lexical e dinâmica, por exemplo, uma delas é preferível sob uma disciplina de ligação e a outra preferível na outra.

Então, o escopo lexical é mais rápido que o escopo dinâmico? Suspeito que, neste caso, não haja muita diferença, mas não sei - você realmente teria que medir.

gsg
fonte
1
Não há varbindcódigo compilado sob ligação lexical. Esse é o objetivo e o objetivo.
Lunardorn 14/10
Hmm. Eu criei um arquivo contendo a fonte acima, começando com ;; -*- lexical-binding: t -*-, carregado e chamado (byte-compile 'sum1), assumindo que produzisse uma definição compilada sob ligação lexical. No entanto, parece não ter.
GSG
Foram removidos os comentários do código de bytes, pois eram baseados nessa suposição incorreta.
GSG
A resposta do lunaryon mostra que esse código é claramente mais rápido sob ligação lexical (embora, é claro, apenas no nível micro).
Shosti
@gsg Esta declaração é apenas uma variável de arquivo padrão, que não afeta as funções chamadas de fora do buffer de arquivo correspondente. IOW, isso só terá efeito se você visitar o arquivo de origem e depois chamar byte-compilecom o buffer correspondente atual, que é - a propósito - exatamente o que o compilador de bytes está fazendo. Se você chamar byte-compileseparadamente, precisará definir explicitamente lexical-binding, como eu fiz na minha resposta.
Lunaryorn 15/10