Hoje vamos acelerar a ligação de linhas curtas em Go em 30%. E, para isso, não precisaremos modificar o Go, tudo isso será implementado como uma biblioteca de terceiros .

Abaixo do corte que você está esperando:

• Comparando as funções + , strings.Builder e concatenação nativa
• Ir para detalhes da linha interna
• Bastante montador

Este artigo também pode ser considerado uma desculpa para discutir CL123256: tempo de execução, cmd / compile: specialize concatstring2 . Idéias para melhorar essa lista de alterações são bem-vindas.

Resultados Imediatamente

A comparação foi feita com a versão go tip (master) do compilador. Você pode obter resultados semelhantes nas versões do Go 1.5. A última alteração significativa na função concatstrings foi CL3120: cmd / gc: aloque buffers para seqüências de caracteres não escapadas na pilha .

 BenchmarkConcat2Operator-8 20000000 83.8 ns/op BenchmarkConcat2Builder-8 20000000 70.9 ns/op BenchmarkConcat2-8 20000000 62.1 ns/op BenchmarkConcat3Operator-8 20000000 104 ns/op BenchmarkConcat3Builder-8 20000000 89.9 ns/op BenchmarkConcat3-8 20000000 82.1 ns/op 

ConcatOperator usa + .
ConcatBuilder usa strings.Builder com a pré-alocação correta.
Concat usa a função que implementamos como parte desta história.

Comparação via benchstat :

 name old time/op new time/op delta Concat2-8 84.2ns ± 1% 62.7ns ± 2% -25.49% (p=0.000 n=9+10) Concat3-8 103ns ± 3% 83ns ± 4% -19.83% (p=0.000 n=10+9) 

A implementação do assembler em GOARCH=AMD64 um pouco mais rápida e possui otimização adicional, que está presente no operador + incorporado, mas mais sobre isso abaixo:

 name old time/op new time/op delta Concat2-8 84.2ns ± 1% 57.1ns ± 3% -32.20% (p=0.000 n=9+9) 

Assumiremos a função assembler como 100% de desempenho (em relação ao restante das implementações consideradas).

Os resultados para linhas mais longas podem ser vistos em README.md . Quanto maior a string, menos pronunciada é a diferença entre implementações.

Concatenação ingênua

A solução mais fácil é usar o operador + .

A semântica desta instrução é a seguinte: pegue duas linhas e retorne uma sequência de resultados que contenha a concatenação de ambas as linhas. Não há garantia de que uma nova linha será retornada. Por exemplo, se houver uma concatenação de uma cadeia vazia e de qualquer outra, o tempo de execução poderá retornar um argumento não vazio, evitando a necessidade de alocar nova memória e copiar dados nela.

Mas, como pode ser visto nos resultados no início do artigo, esse é o caminho mais lento.

 func concat2operator(x, y string) string { return x + y } 

Avaliação de desempenho: 67,8% .

strings.Builder

Não faz muito tempo, um novo tipo foi adicionado ao Go - strings.Builder . Este é um análogo de bytes.Buffer , mas ao chamar o método String() , a memória não é realocada e os dados não são copiados.

Diferentemente de bytes.Buffer , o construtor não possui otimização de um buffer pequeno e, portanto, alocou memória anteriormente para uma sequência. Se você não usar o método Grow , o desempenho será pior do que com bytes.Buffer . Várias regressões no Go 1.11 são causadas por esse recurso específico (consulte CL113235 ).

Em nosso código, pela pureza do experimento, evitaremos esse erro.

 func concat2builder(x, y string) string { var builder strings.Builder builder.Grow(len(x) + len(y)) //      builder.WriteString(x) builder.WriteString(y) return builder.String() } 

Avaliação de desempenho: 80,5% (+12,7).

Geração de código para concatenação

Se você olhar para qual código o compilador gera para o operador + , veremos as chamadas para as concatstring3 , concatstring3 e assim por diante (até concatstring5 inclusive).

 func concat2codegen(x, y) string { return x + y } // => CALL runtime.concatstring2(SB) func concat3codegen(x, y, z) string { return x + y + z } // => CALL runtime.concatstring3(SB) 

Dê uma olhada no próprio runtime / string.go :

 func concatstring2(buf *tmpBuf, a [2]string) string { return concatstrings(buf, a[:]) } func concatstring3(buf *tmpBuf, a [3]string) string { return concatstrings(buf, a[:]) } 

Portanto, resta aprender as funções concatstrings .
Uma lista completa está disponível abaixo do spoiler, mas aqui está uma descrição de alto nível:

1. O parâmetro buf pode ser nil . Esse buffer é alocado pelo compilador se a linha não "escapar" de sua definição. Se a string viver mais do que o quadro, esse buffer será sempre nil (como acontece com mais freqüência). No entanto, se esse buffer estiver disponível, será possível evitar a alocação caso o resultado seja invadido (seu tamanho é 32 bytes).
2. Se todas as linhas, exceto uma, estiverem vazias, a função retornará essa linha. Mas, ao mesmo tempo, as linhas selecionadas na pilha e deixando seu quadro ignoram essa otimização para que o chamador não receba memória já liberada.
3. Além disso, todas as linhas são copiadas para a nova memória.

 // concatstrings implements a Go string concatenation x+y+z+... // The operands are passed in the slice a. // If buf != nil, the compiler has determined that the result does not // escape the calling function, so the string data can be stored in buf // if small enough. func concatstrings(buf *tmpBuf, a []string) string { idx := 0 l := 0 count := 0 for i, x := range a { n := len(x) if n == 0 { continue } if l+n < l { throw("string concatenation too long") } l += n count++ idx = i } if count == 0 { return "" } // If there is just one string and either it is not on the stack // or our result does not escape the calling frame (buf != nil), // then we can return that string directly. if count == 1 && (buf != nil || !stringDataOnStack(a[idx])) { return a[idx] } s, b := rawstringtmp(buf, l) for _, x := range a { copy(b, x) b = b[len(x):] } return s } 

Aqui vemos vários lugares ao mesmo tempo que podem ser otimizados para um caso específico:

• buf geralmente está vazio. Quando o compilador não pôde provar que a string é segura para colocar na pilha, passar um parâmetro extra e verificar se há nil dentro da função gera apenas sobrecarga.
• Para o caso especial com len(a) == 2 não precisamos de um ciclo e os cálculos podem ser simplificados. E esta é a forma mais comum de concatenação.

Versão para todas as arquiteturas

Para implementar a especialização, precisamos saber como as linhas são representadas no Go. A compatibilidade binária é importante para nós, enquanto unsafe.Pointer . O unsafe.Pointer pode ser substituído por *byte sem sacrifícios.

 type stringStruct struct { str *byte len int } 

A segunda conclusão importante que podemos tirar do tempo de execução: as linhas começam sua vida mutável. É alocada uma parte da memória que é referenciada por []byte , na qual o conteúdo da nova linha é gravada e somente depois que o []byte descartado, e a memória à qual ela se refere é armazenada em stringStruct .

Para quem deseja obter mais detalhes, sugere-se estudar as funções de rawstringtmp e rawstring .

 // rawstring allocates storage for a new string. The returned // string and byte slice both refer to the same storage. // The storage is not zeroed. Callers should use // b to set the string contents and then drop b. func rawstring(size int) (s string, b []byte) { p := mallocgc(uintptr(size), nil, false) stringStructOf(&s).str = p stringStructOf(&s).len = size *(*slice)(unsafe.Pointer(&b)) = slice{p, size, size} return } 

Podemos iniciar o mesmo, usando o lado escuro do pacote unsafe :

 func concat2(x, y string) string { length := len(x) + len(y) if length == 0 { return "" } b := make([]byte, length) copy(b, x) copy(b[len(x):], y) return goString(&b[0], length) } 

Destacamos []byte , que usamos para formar o conteúdo de uma nova linha. Só podemos finalizar a linha trazendo-a para a representação de tempo de execução esperada. A função goString é responsável por isso:

 func goString(ptr *byte, length int) string { s := stringStruct{str: ptr, len: length} return *(*string)(unsafe.Pointer(&s)) } 

Avaliação de desempenho: 91.9% (+10.9).

Versão AMD64

Infelizmente, a versão anterior da função não possui otimização para concatenação com uma string vazia, e também realizamos vários cálculos desnecessários devido à incapacidade de alocar memória diretamente, precisamos trabalhar com a fatia de bytes.

Um dos recursos interessantes do montador Go é que ele permite chamar, por exemplo, funções de tempo de execução não exportáveis. Podemos chamar o runtime·mallocgc partir do código do assembly, mesmo que não faça parte do pacote de runtime de runtime . Usaremos essa propriedade.

Também podemos verificar a propriedade das linhas de memória da pilha, o que torna seguro otimizar o retorno de um dos argumentos como resultado.

Suponha que uma função seja chamada com argumentos concat2("", "123") . x é uma string vazia e, se y não y alocado na pilha, podemos devolvê-la como resultado da concatenação.

 //; ,  x  y   stringStruct. //; CX - y.str. //; SI - y.len. maybe_return_y: //;      . MOVQ (TLS), AX //; *g CMPQ CX, (AX) JL return_y //;  y_str < g.stack.lo CMPQ CX, 8(AX) JGE return_y //;  y_str >= g.stack.hi JMP concatenate //; y  ,    return_y: MOVQ CX, ret+32(FP) //; stringStruct.len MOVQ SI, ret+40(FP) //; stringStruct.str RET 

MOVQ (TLS), AX moverá * g para o registro do AX . A leitura no deslocamento zero dará o campo g.stack.lo e g.stack.hi começa com o 8º byte (para uma plataforma de 64 bits).

 type g struct { stack struct { lo uintptr // 0(AX) hi uintptr // 8(AX) } stackguard0 uintptr // 16(AX) stackguard1 uintptr // 24(AX) // ...   } 

O corpo concatenate aloca memória, preenche-a com as duas linhas e retorna uma nova linha.

 #include "textflag.h" #include "funcdata.h" TEXT ·Strings(SB), 0, $48-48 NO_LOCAL_POINTERS //    . MOVQ x+0(FP), DX MOVQ x+8(FP), DI MOVQ y+16(FP), CX MOVQ y+24(FP), SI TESTQ DI, DI JZ maybe_return_y // x -  ,   y TESTQ SI, SI JZ maybe_return_x // y -  ,   x concatenate: LEAQ (DI)(SI*1), R8 // len(x) + len(y) //     . MOVQ R8, 0(SP) MOVQ $0, 8(SP) MOVB $0, 16(SP) CALL runtime·mallocgc(SB) MOVQ 24(SP), AX //     MOVQ AX, newstr-8(SP) //  x. MOVQ x+0(FP), DX MOVQ x+8(FP), DI MOVQ AX, 0(SP) MOVQ DX, 8(SP) MOVQ DI, 16(SP) CALL runtime·memmove(SB) //  y   len(x). MOVQ x+8(FP), DI MOVQ y+16(FP), CX MOVQ y+24(FP), SI MOVQ newstr-8(SP), AX LEAQ (AX)(DI*1), BX MOVQ BX, 0(SP) MOVQ CX, 8(SP) MOVQ SI, 16(SP) CALL runtime·memmove(SB) //   . MOVQ newstr-8(SP), AX MOVQ x+8(FP), R8 ADDQ y+24(FP), R8 MOVQ AX, ret+32(FP) MOVQ R8, ret+40(FP) RET maybe_return_y: //      . MOVQ (TLS), AX // *g CMPQ CX, (AX) JL return_y //  y_ptr < stk.lo CMPQ CX, 8(AX) JGE return_y //  y_ptr >= stk.hi JMP concatenate // y  ,    return_y: MOVQ CX, ret+32(FP) MOVQ SI, ret+40(FP) RET maybe_return_x: //      . MOVQ (TLS), AX // *g CMPQ DX, (AX) JL return_x //  x_ptr < stk.lo CMPQ DX, 8(AX) JGE return_x //  x_ptr >= stk.hi JMP concatenate // x  ,    return_x: MOVQ DX, ret+32(FP) MOVQ DI, ret+40(FP) RET 

Avaliação de desempenho: 100% (+8,6).

Em conclusão

Todo o código é fornecido como um pacote concat .

O mundo está pronto para uma concatenação tão rápida? Quem sabe

No início do artigo, CL123256 foi mencionado. Ele tem vários caminhos de desenvolvimento:

1. Especialização variacional para o caso em que o compilador não aloca um buffer temporário. Há menos crescimento para cada caso, mas abrange mais tipos de concatenação e praticamente não aumenta o tamanho do código (máquina e código Go).
2. Mais especializações para casos especiais. Ganhos mais altos, mas mais código de máquina, podem prejudicar o cache de instruções.
3. Toneladas de código de máquina, para cada caso especial e memorando especializado, da maneira como isso é feito na glibc. Aqui surgem principalmente questões de conveniência.

A atual opção proposta acelera apenas o caso mais comum e mais simples de concatenação de um par de strings (arity = 2).

Se o Go não aceitar essa alteração, poderá obter uma aceleração comparável implementando operações de cadeia de caracteres na forma de uma biblioteca de terceiros. Menos conveniente, bonito e elegante, mas funciona.