O código mostrado abaixo é equivalente em desempenho?

// (A).  HasPrefix  . return strings.HasPrefix(s, "#") // (B).    HasPrefix. return len(s) >= len("#") && s[:len("#")] == "#" 

A resposta é não .

Para detalhes e explicações, pergunto em cat.

Bom dia, antes de abrir o tópico, eu gostaria de me apresentar.
Meu nome é Iskander e, de tempos em tempos, eu envio confirmações para o repositório golang / go .

Eu costumava fazer isso em nome da equipe Intel Go , mas nossos caminhos divergiam e agora eu sou um colaborador independente. Recentemente, tenho trabalhado em vk na equipe de infraestrutura.

Nos meus tempos livres, faço ferramentas diferentes para o Go, como go-critical e go-consistente . Eu também desenho esquilos .

Meça!

Prossiga imediatamente para a comparação e defina a referência:

 package benchmark import ( "strings" "testing" ) var s = "#string" func BenchmarkHasPrefixCall(b *testing.B) { for i := 0; i < bN; i++ { _ = strings.HasPrefix(s, "#") _ = strings.HasPrefix(s, "x") } } func BenchmarkHasPrefixInlined(b *testing.B) { for i := 0; i < bN; i++ { _ = len(s) >= len("#") && s[:len("#")] == "#" _ = len(s) >= len("x") && s[:len("x")] == "x" } } 

Em vez de recomendar benchstat para você, mostrarei a você o benchrun .

Com um comando, podemos executar os dois benchmarks e obter uma comparação:

 go-benchrun HasPrefixCall HasPrefixInlined -v -count=10 . Benchstat results: name old time/op new time/op delta HasPrefixCall-8 9.15ns ± 1% 0.36ns ± 3% -96.09% (p=0.000 n=10+9) 

A opção com incorporação manual é muito mais rápida que o código que foi obtido incorporando o corpo da função ao compilador. Vamos tentar descobrir por que isso está acontecendo.

strings.HasPrefix

Lembre-se da implementação de strings.HasPrefix :

 // HasPrefix tests whether the string s begins with prefix. func HasPrefix(s, prefix string) bool { return len(s) >= len(prefix) && s[0:len(prefix)] == prefix } 

A função HasPrefix incorporada pelo compilador.
Você pode verificar isso da seguinte maneira:

 go build -gcflags='-m=2' strings 2>&1 | grep 'can inline HasPrefix' 

Para chamar strings.HasPrefix da opção (A) , obtemos o seguinte código de máquina:

  MOVQ (TLS), CX CMPQ SP, 16(CX) JLS more_stack fn_body: SUBQ $40, SP MOVQ BP, 32(SP) LEAQ 32(SP), BP XCHGL AX, AX MOVQ s+56(SP), AX CMPQ AX, $1 JGE compare_strings XORL AX, AX MOVB AL, ~ret1+64(SP) MOVQ 32(SP), BP ADDQ $40, SP return: RET compare_strings: MOVQ s+48(SP), AX MOVQ AX, (SP) LEAQ go.string."#"(SB), AX MOVQ AX, 8(SP) MOVQ $1, 16(SP) CALL runtime.memequal(SB) MOVBLZX 24(SP), AX JMP return more_stack: CALL runtime.morestack_noctxt(SB) JMP fn_body 

Ignore o fato de que o código se parece com macarrão.

O que você deve prestar atenção:

• strings.HasPrefix realmente foi inserido, nenhuma chamada.
• Para comparar seqüências de caracteres, runtime.memequal é runtime.memequal .

Mas o que então é gerado para a versão incorporada manualmente, o código do exemplo (B) ?

  MOVQ s+16(SP), AX CMPQ AX, $1 JLT different_length MOVQ s+8(SP), AX CMPB (AX), $35 // 35 -   "#" SETEQ AL return: MOVB AL, "".~ret1+24(SP) RET different_length: XORL AX, AX JMP 22 

E aqui o compilador não gera uma chamada para runtime.memequal e um único caractere é comparado diretamente. Idealmente, ele deveria ter feito o mesmo para a primeira opção.

Observamos o lado fraco do otimizador Go e vamos analisá-lo.

Otimização de Expressão Constante

A razão pela qual chamar strings.HasPrefix(s, "#") pode ser otimizada é porque o argumento prefix é uma constante. Conhecemos seu comprimento e conteúdo. Não faz sentido chamar runtime.memequal para sequências curtas, é mais rápido fazer uma comparação de caracteres "no local", evitando uma chamada extra.

Como você sabe, os compiladores geralmente têm pelo menos duas partes: frontend e backend do compilador . O primeiro funciona com uma visualização de nível superior, o segundo está mais próximo da máquina e a visualização intermediária parecerá um fluxo de instruções. Várias versões do Go já usaram a representação SSA para otimizações na parte de back-end do compilador.

Dobra constante, como {10*2 => 20} , é implementada no back-end. Em geral, a maioria das operações associadas à redução do custo computacional das expressões estão localizadas nesta parte do compilador. Mas há exceções.

Uma exceção é a otimização de comparações constantes de strings. Quando o compilador vê uma comparação de cadeia (ou substring) na qual um ou ambos os operandos são constantes, um código mais eficiente é gerado do que uma chamada para runtime.memequal .

Você pode ver o código fonte responsável por isso no arquivo cmd / compile / internal / gc / walk.go: 3362 .

A incorporação de funções ocorre antes do lançamento dessas otimizações, mas também na parte frontal do compilador.

Parece que tudo a mesma coisa não permite que essa otimização funcione no nosso caso?

Como vai incorporar chamadas de função

Veja como a incorporação ocorrerá:

 //    : return strings.HasPrefix(s, "#") //  : func HasPrefix(s, prefix string) bool //    : _s, _prefix := s, "#" return len(s) >= len(prefix) && s[:len(prefix)] == prefix 

Ao incorporar funções, o compilador atribui argumentos a variáveis ​​temporárias, o que interrompe as otimizações, pois o algoritmo em walk.go não vê constantes, mas argumentos com variáveis. Esse é o problema.

A propósito, isso não interfere nas otimizações de back-end que o SSA tem à sua disposição. Mas existem outros problemas, por exemplo, a incapacidade de restaurar construções de linguagem de alto nível para sua comparação efetiva (o trabalho para eliminar essa desvantagem foi “planejado” por vários anos).

Outro exemplo: análise de escape

Imagine uma função importante para alocar um buffer temporário na pilha:

 func businessLogic() error { buf := make([]byte, 0, 16) // buf    //    . return nil } 

Como o buf não "foge", o compilador poderá alocar esses 16 bytes na pilha, sem alocação no heap. Novamente, tudo graças ao valor constante ao chamar make . Para alocar memória na pilha, é importante sabermos o tamanho necessário, que fará parte do quadro alocado para a chamada de função.

Suponha que no futuro desejássemos alocar buffers temporários de tamanhos diferentes e encapsular alguma lógica nos métodos. Introduzimos uma nova abstração e decidimos usar o novo tipo tmpBuf . A função de design é extremamente simples:

 func newTmpBuf(sizeHint int) tmpBuf { return tmpBuf{buf: make([]byte, 0, sizeHint)} } 

Adaptando o exemplo original:

 func businessLogic() error { - buf := make([]byte, 0, 16) + buf := newTmpBuf(16) // buf    //    . return nil } 

O construtor será incorporado, mas a alocação agora estará sempre no heap, pelo mesmo motivo que os argumentos são passados ​​por variáveis ​​temporárias. A análise de escape verá make([]byte, 0, _sizeHint) que não se enquadra em seus padrões de reconhecimento para make chamadas otimizadas.

Se tivéssemos “tudo é como seres humanos”, o problema não existiria, após a incorporação do newTmpBuf construtor newTmpBuf seria claro que o tamanho ainda é conhecido no estágio de compilação.

Isso incomoda quase mais do que a situação com a comparação de strings.

Horizons Go 1.13

A situação pode ser facilmente corrigida e eu já enviei a primeira parte da decisão .

Se você acha que o problema descrito no artigo realmente precisa de uma solução, dê um joinha na edição correspondente .

Minha posição é que incorporar o código com as mãos apenas porque ele funciona mais rápido na versão atual do Go está errado. É necessário corrigir esse defeito no otimizador, pelo menos até o ponto em que os exemplos descritos acima funcionam sem regressões inesperadas de desempenho.

Se tudo correr conforme o planejado, essa otimização será incluída na versão Go 1.13.

Obrigado pela atenção.

Adição: solução proposta

Esta seção é para os mais corajosos, aqueles que não estão cansados ​​de ler.

Portanto, temos vários locais que funcionam pior ao usar variáveis ​​em vez de seus valores diretamente. A solução proposta é introduzir uma nova função no frontend da parte do compilador, que permite obter o último valor vinculado pelo nome. Depois disso, em cada otimização que espera um valor constante, não desista quando uma variável for detectada, mas receba esse estado salvo anteriormente.

A assinatura do nosso novo recurso pode ser assim:

 func getConstValue(n *Node) *Node 

A definição de Node pode ser encontrada no arquivo syntax.go .

Cada definição de variável possui uma tag Node com uma tag ONAME . Dentro do Node.Name.Defn maioria dessas variáveis ​​possui um valor de inicialização.

Se o Node já Node um literal, você não precisa fazer nada e apenas retornamos n . Se for ONAME (variável), você pode tentar extrair o mesmo valor de inicialização de n.Name.Defn .

Mas e as modificações entre declarar e ler uma variável para a qual chamamos getConstValue ? Se nos restringirmos a variáveis ​​somente leitura, não haverá problema. O front-end do Go já possui sinalizadores de nó especiais que marcam nomes semelhantes. Se a variável foi modificada, getConstValue não retornará um valor de inicialização.

Os programadores, como regra, não modificam os argumentos de entrada dos tipos numéricos e de seqüência de caracteres, e isso permite cobrir um número bastante grande de casos com esse algoritmo primitivo.

Agora estamos prontos para considerar a implementação:

 func getConstValue(n *Node) *Node { //    ONAME    definition. if n.Op != ONAME || n.Name.Defn == nil { return n } //   ,     . // ,    ,     //      escape analysis' . maybeModified := n.Assigned() || n.Name.Defn.Assigned() || n.Addrtaken() if maybeModified { return n } // OAS - Node  . // n.Name.Defn.Left -  LHS. // n.Name.Defn.Right -  RHS. // consttype(v)     . //   CTxxx,      . if n.Name.Defn.Op == OAS { v := n.Name.Defn.Right if v != nil && consttype(v) != CTxxx { return v } } return n } 

Veja como o código é alterado, dependendo das constantes:

 - i := indexconst(r) + i := indexconst(getConstValue(r)) 

Ótimo, e até funciona:

 n := 10 xs := make([]int, n) //     ! 

Antes dessa alteração, a análise de escape não conseguia obter o valor de 10 a n , e foi por isso que assumi a necessidade de colocar xs no heap.

O código acima é sintaticamente semelhante à situação observada durante a incorporação. n pode ser uma variável temporária que é adicionada quando o argumento é passado.

Infelizmente, existem nuances.

Resolvemos o problema para variáveis ​​locais introduzidas através da OEA , mas o Go inicializa as variáveis ​​para funções internas através da OEA2 . Por isso, precisamos de uma segunda alteração que estenda a função getConstValue e modifique levemente o código do próprio inliner, porque, entre outras coisas, o OAS2 não possui um campo Defn adequado.

Foram más notícias. Boas notícias: o canal #gocontributing apareceu na folga no idioma russo , onde você pode compartilhar suas idéias e planos, fazer perguntas e discutir tudo relacionado à participação no desenvolvimento do Go.