Hoy aceleraremos la unión de líneas cortas en Go en un 30%. Y para esto no necesitaremos modificar el propio Go, todo esto se implementará como una biblioteca de terceros .

Debajo del corte que estás esperando:

• Comparando + , strings.Builder . strings.Builder y funciones de concatenación nativas
• Ir a detalles de la fila interna
• Bastante un poco de ensamblador

Este artículo también puede considerarse una excusa para discutir CL123256: runtime, cmd / compile: specialize concatstring2 . Las ideas para mejorar esta lista de cambios son bienvenidas.

Resultados inmediatos

La comparación se realizó con la versión go tip (master) del compilador. Puede obtener resultados similares en versiones alrededor de Go 1.5. El último cambio significativo en la función concatstrings fue CL3120: cmd / gc: asignar buffers para cadenas no escapadas en la pila .

 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 utiliza + .
ConcatBuilder utiliza strings.Builder con la preasignación correcta.
Concat usa la función que implementamos como parte de esta historia.

Comparación a través de 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) 

La implementación del ensamblador en GOARCH=AMD64 poco más rápida y tiene una optimización adicional, que está presente en el operador incorporado + , pero más sobre eso a continuación:

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

Tomaremos la función de ensamblador como 100% de rendimiento (en relación con el resto de las implementaciones consideradas).

Los resultados para líneas más largas se pueden ver en README.md . Cuanto más larga es la cadena, menos pronunciada es la diferencia entre implementaciones.

Concatenación ingenua

La solución más fácil es usar el operador + .

La semántica de esta declaración es la siguiente: tome dos líneas y devuelva una cadena de resultado que contenga la concatenación de ambas líneas. No hay garantía de que se devuelva una nueva línea. Por ejemplo, si hay una concatenación de una cadena vacía y cualquier otra, el tiempo de ejecución puede devolver un argumento no vacío, evitando la necesidad de asignar nueva memoria y copiar datos allí.

Pero, como se puede ver en los resultados al comienzo del artículo, esta es la forma más lenta.

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

Calificación de desempeño: 67.8% .

Strings.Builder

No hace mucho tiempo, se agregó un nuevo tipo a Go - strings.Builder . Este es un análogo de bytes.Buffer . bytes.Buffer , pero cuando se llama al método String() , la memoria no se reasigna y los datos no se copian.

A diferencia de bytes.Buffer , el generador no tiene optimización de un búfer pequeño y, por lo tanto, memoria previamente asignada para una cadena. Si no utiliza el método Grow , el rendimiento será peor que con bytes.Buffer . Varias regresiones en Go 1.11 son causadas por esta característica particular (ver CL113235 ).

En nuestro código, por la pureza del experimento, evitaremos este error.

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

Calificación de rendimiento: 80.5% (+12.7).

Generación de código para concatenación

Si observamos qué código genera el compilador para el operador + , veremos llamadas a las funciones concatstring2 , concatstring3 , etc. (hasta 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) 

Echa un vistazo a 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[:]) } 

Por lo tanto, queda por aprender la función concatstrings .
Una lista completa está disponible debajo del spoiler, pero aquí hay una descripción de alto nivel:

1. El parámetro buf puede ser nil . El compilador asigna este búfer si la línea no "escapa" de su definición. Si la cadena dura más que el marco, entonces este búfer siempre será nil (como suele suceder). Sin embargo, si este búfer está disponible, será posible evitar la asignación en caso de que el resultado se rompa en él (su tamaño es de 32 bytes).
2. Si todas las líneas, excepto una, están vacías, la función devolverá esta línea. Pero al mismo tiempo, las líneas seleccionadas en la pila y dejando su marco omiten esta optimización para que la persona que llama no reciba memoria ya liberada.
3. Además, todas las líneas se copian en la nueva memoria.

 // 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 } 

Aquí vemos varios lugares a la vez que se pueden optimizar para un caso particular:

• buf estar vacío. Cuando el compilador no pudo probar que la cadena es segura para colocar en la pila, pasar un parámetro adicional y verificar que sea nil dentro de la función solo genera una sobrecarga.
• Para el caso especial con len(a) == 2 no necesitamos un ciclo y los cálculos pueden simplificarse. Y esta es la forma más común de concatenación.

Versión para todas las arquitecturas.

Para implementar la especialización, necesitamos saber cómo se representan las líneas en Go. La compatibilidad binaria es importante para nosotros, aunque no es unsafe.Pointer se puede reemplazar con *byte sin ningún sacrificio.

 type stringStruct struct { str *byte len int } 

La segunda conclusión importante que podemos extraer del tiempo de ejecución: las líneas comienzan su vida mutable. Se asigna un trozo de memoria al que hace referencia el []byte , en el que se escribe el contenido de la nueva línea, y solo después de que []byte descarta ese []byte , y la memoria a la que hace referencia se almacena en stringStruct .

Para aquellos que desean más detalles, se sugiere estudiar las funciones de rawstringtmp y 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 subir más o menos lo mismo, usando el lado oscuro del paquete 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 el contenido de una nueva línea. Entonces solo podemos finalizar la línea llevándola a la representación de tiempo de ejecución esperada. La función goString es responsable de esto:

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

Calificación de desempeño: 91.9% (+10.9).

Versión AMD64

Desafortunadamente, la versión anterior de la función no tiene optimización para la concatenación con una cadena vacía, y también realizamos una serie de cálculos innecesarios debido a la incapacidad de asignar memoria directamente, tenemos que trabajar con el segmento de bytes.

Una de las características interesantes del ensamblador Go es que le permite llamar, por ejemplo, funciones de tiempo de ejecución no exportables. Podemos llamar a runtime·mallocgc desde el código de ensamblaje incluso si no es parte del paquete de runtime de runtime . Utilizaremos esta propiedad.

También podemos verificar la propiedad de las líneas de memoria de la pila, lo que hace que sea seguro optimizar el retorno de uno de los argumentos como resultado.

Supongamos que se llama a una función con argumentos concat2("", "123") . x es una cadena vacía, y si y no y asignado en la pila, podemos devolverlo como resultado de la concatenación.

 //; ,  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 al registro AX . La lectura en el desplazamiento cero dará el campo g.stack.lo , y g.stack.hi comienza con el octavo byte (para una 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) // ...   } 

El cuerpo concatenate asigna memoria, la llena con ambas líneas y devuelve una nueva línea.

 #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 

Calificación de rendimiento: 100% (+8.6).

En conclusión

Todo el código se proporciona como un paquete concat .

¿Está el mundo listo para una concatenación tan rápida? Quien sabe

Al comienzo del artículo, se mencionó CL123256 . Tiene varias vías de desarrollo:

1. Especialización variacional para el caso cuando el compilador no asigna un búfer temporal. Hay menos crecimiento para cada caso, pero cubre más tipos de concatenación y prácticamente no aumenta el tamaño del código (tanto la máquina como el código Go).
2. Más especializaciones para casos especiales. Mayores ganancias, pero más código de máquina, pueden dañar el caché de instrucciones.
3. Toneladas de código de máquina, para cada caso especial y memoria especializada, en la forma en que esto se hace en glibc. Aquí surgen principalmente cuestiones de conveniencia.

La opción propuesta actual acelera solo el caso más común y más simple de concatenación de un par de cadenas (arity = 2).

Si Go no acepta este cambio, se puede lograr una aceleración comparable mediante la implementación de operaciones de cadena en forma de una biblioteca de terceros. Menos conveniente, hermoso y elegante, pero funciona.