Desempenho do lexer estilo córtex em Go

By | Junho 7, 2022

Em 2011, Rob Pike fez um discurso sobre o assunto
Escaneamento léxico em Go, onde apresentou uma interessante abordagem de análise lexical com korutins (implementado através de goroutins que se comunicam por meio de canais). Desde que eu pensei no passado sobre a conexão entre corutinas e máquinas de estado, o discurso de Rob me inspirou a tentar aproximar essa abordagem em Python usando subgeradores.

Desde 2011, já vi esse discurso e a técnica apresentados nele várias vezes, tanto em fóruns Go quanto em comunidades de programas em geral. Há algo nessa abordagem que parece elegante – é um problema muito adequado para groselhas. No entanto, sempre havia uma voz calma e irritante na minha nuca que duvidava da eficácia da abordagem.

Desde que recentemente me encontrei em um jogo de lexer novamente, esta parecia uma boa oportunidade para eu dar outra olhada no lexer de Rob Pike e comparar seu desempenho com outras abordagens, usando o mesmo problema e medida de justiça.

Lexer original Rob Pike

No discurso, Rob descreve um lexer que projetou o pacote de propostas da Go. Lexer apresentou na conversa e slides é relativamente simples; sua versão muito mais significativa ainda vive texto / modelo pacote – lex.go. Como tal, este lexer é usado intensivamente todos os dias na produção.

Copiei o lexer original da fala para o meu repositório GitHub; está disponível aqui, com testes.

O principal apelo estético desse lexicógrafo é evitar a máquina de estado explícita usando uma goroutina separada para realizar a lexicografia. Essa goroutina altera os estados restaurando uma nova “função de estado” e transmite tokens para um canal que pode ser lido por clientes lexer.

Essa abordagem é particularmente atraente ao analisar modelos porque oscila entre dois estados principais – lexing de texto livre e lexing em ações restritas {}. O uso de uma abordagem concorrente evita a necessidade de um sinalizador de status explícito “estou dentro da ação” que deve ser verificado sempre que um novo token é solicitado.

Lexing TableGen

Para que eu pudesse ter uma comparação significativa de desempenho, reescrevi meu lexer TableGen, desta vez usando uma abordagem corutina. Todo o código para este lexer com testes é disponivel aqui.

A API é muito semelhante aos meus lexers TableGen anteriores – todos os detalhes da implementação (como o canal de leitura do token) estão ocultos do usuário. O tipo de token é o mesmo:

type Token struct {
  Name TokenName
  Val  string
  Pos  int
}

o PróximoToken o método também tem a mesma assinatura, embora a implementação agora use um canal:

func (l *Lexer) NextToken() Token {
  return <-l.tokens
}

O construtor cria novos Lexercria um canal no qual os tokens emitidos entram e aciona um rugido que executa o lexing real:

// Lex creates a new Lexer
func Lex(input string) *Lexer {
  l := &Lexer{
    input:  input,
    tokens: make(chan Token),
  }
  go l.run()
  return l
}

o Cooper o método serve como um trampolim para avançar o lexer de estado para estado (enquanto as funções de estado emitem tokens no canal):

type stateFn func(*Lexer) stateFn

func (l *Lexer) run() {
  for state := lexText; state != nil; {
    state = state(l)
  }
  close(l.tokens) // no more tokens will be delivered
}

E assim por diante. A implementação é acompanhada de perto pelo leproso Rob Pike, com as mesmas primitivas. Para a linguagem TableGen, que não possui o recurso de “dois estados” dos modelos, achei essa abordagem menos lucrativa do ponto de vista do estilo, embora ainda facilite o gerenciamento de estados.

atuação

Em um post anterior, o lexer Go mais rápido alcançado com Go 1.18 executa um valor de referência de cerca de 6 ms (s
GOGC = 1600 contexto).

Para um campo de jogo nivelado, lancei um novo lexer estilo córtex no mesmo arquivo de entrada, com a mesma chamada de benchmarking e o mesmo GOGC contexto:

$ GOGC=1600 TDINPUT=<path to input file> go test -bench=Preall -benchtime=5s
goos: linux
goarch: amd64
pkg: example.com
cpu: Intel(R) Core(TM) i7-4771 CPU @ 3.50GHz
BenchmarkLexerPrealloc-8            80          70507009 ns/op
PASS
ok    example.com     5.885s

Demora … 70 ms, mais de 10x mais lento!

Embora não me surpreenda que essa abordagem seja mais lenta, de manhã um pouco surpreso com o tamanho. Vamos pensar sobre isso. O que cada lexer faz em seu loop interno quente?

No meu lexer original, cada chamada para PróximoLexer função:

  1. Salta espaço: itera sobre a string de entrada runa por runa até que uma runa seja encontrada sem espaço.
  2. Ele examina a runa atual e decide a que tipo de token ela pertence.
  3. Finaliza o token token e o retorna como um snippet de string.

Enquanto no léxico no estilo da cortina toda chamada PróximoLexer:

  1. Invoca a recepção do canal no canal de token.

Enquanto isso, lexing goroutine:

  1. Ele pula o espaço e examina a runa atual, assim como em um lexer comum.
  2. Chamadas para enviar canal para canal de token.

O canal de envio/recepção é o principal culpado pela grande diferença de desempenho. Os canais em Go são totalmente sincronizados, o que significa travar dentro do loop interno. Além disso, uma vez que dois goroutins executando operações de canal estão envolvidos, o Go runtime tem muito mais trabalho a fazer para lidar com a suspensão do goroutin quando o canal é bloqueado e a ativação quando é desbloqueado. Todas essas operações são altamente otimizadas em Go, mas quando aparecem no loop interno de um processo de digitalização rápido, o custo relativo é alto.

Se criarmos o perfil de um novo scanner com pprof, esse custo é fácil de detectar:

Diagrama Pprof mostrando para onde vai o tempo para o léxico do canal

No léxico anterior, o método “recuperar a próxima runa” é muito dominante. Aqui representa apenas 5,8% do tempo de execução! Muito tempo passa
chansend1 e chanrecv1 que são funções de tempo de execução com nomes que devem ser autodescritivos. Há também um código de controle de tempo de execução que compõe uma grande porcentagem.

Usando o canal de buffer

Go’s fazer cria primitivamente um sem buffer o canal por padrão, o que significa que qualquer envio para ele é bloqueado até que o receptor remova o item. O que aconteceria se criássemos um canal da área de transferência? Teoricamente, isso deve melhorar o tempo de execução do léxico, pois haverá menos suspensão e despertar do goroutin.

Vejamos o que os diferentes valores de buffer nos dão; Reiniciei os tamanhos de buffer começando de 1 a 16384 em saltos de 4x:

Resultados de comparação para diferentes tamanhos de buffer de canal

Como esperado, o uso de um canal de buffer torna o lexing muito mais rápido, equivalendo a 1024, onde leva cerca de 24 ms para nosso valor de referência. Esta é uma grande melhoria, embora ainda muito mais lenta do que os 6 ms que tivemos com nosso lexer não competitivo.

Os canais têm muitos usos em Go; eles às vezes são usados ​​como mecanismos de sincronização, portanto, possuir um buffer grande nem sempre é viável. Em casos como o nosso lexer, a área de transferência realmente faz sentido porque não deve ser um problema para a lexicografia progredir um pouco. Observe, no entanto, que isso não funciona para nenhum tipo de entrada; se, por exemplo, usarmos o léxico C, podemos querer ter um mecanismo de feedback de volta ao lexer (para lidar com a sensibilidade contextual gramatical).

FWIW, template template lexist Rob Pike adicionado à biblioteca padrão usa um canal sem buffer. Talvez fizesse sentido adicionar um tampão modesto
acelerar um pouco 🙂

O desempenho importa aqui?

Para esta tarefa, o lexer estilo cortiça ainda é bastante rápido. Tenha em mente que é muitos mais rápido do que alguns lexers baseados em Python e JS que escrevi para a mesma tarefa há algum tempo.

Este lexer usa uma biblioteca padrão para analisar templates, mas eles são (1) raramente muito grandes e (2) quase sempre bons para analisar apenas uma vez durante a vida do programa, então o tempo necessário para analisá-los não é muito importante; em outras palavras, é muito improvável que domine os benchmarks de seu aplicativo.

Dito isto, posso imaginar cenários em que isso seja poderia matéria. Suponha que você esteja escrevendo um frontend para uma linguagem de programação não trivial (ou linguagem de configuração, etc.) e um intérprete rápido para essa linguagem. Isso pode fazer com que o desempenho do frontend seja um gargalo. Nesses cenários, apenas
Poderia é importante ter o lexer mais rápido que você possa implementar razoavelmente.


Deixe uma resposta

O seu endereço de email não será publicado.