Aujourd'hui, nous accélérerons de 30% la liaison des lignes courtes en Go. Et pour cela, nous n'aurons pas besoin de modifier Go lui-même, tout cela sera implémenté comme une bibliothèque tierce .

Sous la coupe que vous attendez:

• Comparaison de + , strings.Builder et fonctions de concaténation natives
• Accéder aux détails de la ligne interne
• Un peu d'assembleur

Cet article peut également être considéré comme une excuse pour discuter de CL123256: runtime, cmd / compile: specialize concatstring2 . Les idées pour améliorer cette liste de changements sont les bienvenues.

Résultats immédiats

La comparaison a été faite avec la version go tip (master) du compilateur. Vous pouvez obtenir des résultats similaires sur les versions autour de Go 1.5. La dernière modification importante apportée à la fonction de concatstrings été CL3120: cmd / gc: allouer des tampons pour les chaînes non échappées sur la pile .

 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 utilise + .
ConcatBuilder utilise strings.Builder avec la pré-allocation correcte.
Concat utilise la fonction que nous implémentons dans le cadre de cette histoire.

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

L'implémentation de l'assembleur sous GOARCH=AMD64 légèrement plus rapide et a une optimisation supplémentaire, qui est présente dans l'opérateur + intégré, mais plus sur celui ci-dessous:

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

Nous prendrons la fonction assembleur comme une performance à 100% (par rapport au reste des implémentations considérées).

Les résultats pour les lignes plus longues peuvent être vus dans README.md . Plus la chaîne est longue, moins la différence entre les implémentations est prononcée.

Concaténation naïve

La solution la plus simple consiste à utiliser l'opérateur + .

La sémantique de cette instruction est la suivante: prenez deux lignes et retournez une chaîne de résultat qui contient la concaténation des deux lignes. Il n'y a aucune garantie qu'une nouvelle ligne sera retournée. Par exemple, s'il y a concaténation d'une chaîne vide et de toute autre, le runtime peut renvoyer un argument non vide, évitant ainsi la nécessité d'allouer de la nouvelle mémoire et d'y copier des données.

Mais, comme le montrent les résultats du début de l'article, c'est la voie la plus lente.

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

Indice de performance: 67,8% .

strings.Builder

Il n'y a pas si longtemps, un nouveau type a été ajouté à Go - strings.Builder . Il s'agit d'un analogue d' bytes.Buffer , mais lors de l'appel de la méthode String() , la mémoire n'est pas bytes.Buffer et les données ne sont pas copiées.

Contrairement à bytes.Buffer , le générateur n'a pas d'optimisation d'un petit tampon et, par conséquent, la mémoire précédemment allouée pour une chaîne. Si vous n'utilisez pas la méthode Grow , les performances seront moins bonnes qu'avec bytes.Buffer . Plusieurs régressions dans Go 1.11 sont causées par cette fonctionnalité particulière (voir CL113235 ).

Dans notre code, pour la pureté de l'expérience, nous éviterons cette erreur.

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

Indice de performance: 80,5% (+12,7).

Génération de code pour la concaténation

Si vous regardez quel code le compilateur génère pour l'opérateur + , nous verrons des appels aux concatstring3 concatstring2 , concatstring3 et ainsi de suite (jusqu'à concatstring5 inclus).

 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) 

Jetez un œil à runtime / string.go lui - même :

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

Il reste donc à apprendre les concatstrings fonctions.
Une liste complète est disponible ci-dessous sous le spoiler, mais voici une description de haut niveau:

1. Le paramètre buf peut être nil . Ce tampon est alloué par le compilateur si la ligne ne "s'échappe" pas de sa définition. Si la chaîne vit plus longtemps que le cadre, ce tampon sera toujours nil (comme cela arrive le plus souvent). Cependant, si ce tampon est disponible, il sera possible d'éviter l'allocation au cas où le résultat s'y casserait (sa taille est de 32 octets).
2. Si toutes les lignes sauf une sont vides, la fonction renverra cette ligne. Mais en même temps, les lignes sélectionnées sur la pile et laissant leur trame contournent cette optimisation pour que l'appelant ne reçoive pas de mémoire déjà libérée.
3. De plus, toutes les lignes sont copiées dans la nouvelle mémoire.

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

Ici, nous voyons plusieurs endroits à la fois qui peuvent être optimisés pour un cas particulier:

• buf plus souvent vide. Lorsque le compilateur n'a pas pu prouver que la chaîne est sûre à placer sur la pile, passer un paramètre supplémentaire et le vérifier pour nil à l'intérieur de la fonction ne donne que la surcharge.
• Pour le cas particulier avec len(a) == 2 nous n'avons pas besoin de cycle et les calculs peuvent être simplifiés. Et c'est la forme de concaténation la plus courante.

Version pour toutes les architectures

Pour implémenter la spécialisation, nous devons savoir comment les lignes sont représentées dans Go. La compatibilité binaire est importante pour nous, même si unsafe.Pointer n'est pas unsafe.Pointer peut être remplacé par *byte sans aucun sacrifice.

 type stringStruct struct { str *byte len int } 

La deuxième conclusion importante que nous pouvons tirer de l'exécution: les lignes commencent leur vie mutable. Un morceau de mémoire est alloué qui est référencé par []byte , dans lequel le contenu de la nouvelle ligne est écrit, et seulement après que cet []byte rejeté, et la mémoire à laquelle il fait référence est stockée dans stringStruct .

Pour ceux qui veulent plus de détails, il est suggéré d'étudier les fonctions de rawstringtmp et 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 } 

Nous pouvons monter à peu près la même chose, en utilisant le côté sombre du paquet 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) } 

Nous mettons en évidence []byte , que nous utilisons pour former le contenu d'une nouvelle ligne. Ensuite, nous ne pouvons finaliser la ligne qu'en la portant à la représentation d'exécution attendue. La fonction goString est responsable:

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

Indice de performance: 91,9% (+10,9).

Version AMD64

Malheureusement, la version précédente de la fonction n'a pas d'optimisation pour la concaténation avec une chaîne vide, et nous effectuons également un certain nombre de calculs inutiles en raison de l'impossibilité d'allouer directement la mémoire, nous devons travailler avec la tranche d'octets.

L'une des caractéristiques intéressantes de l'assembleur Go est qu'il vous permet d'appeler, par exemple, des fonctions d'exécution non exportables. Nous pouvons appeler runtime·mallocgc partir du code assembleur même s'il ne fait pas partie du package d' runtime . Nous utiliserons cette propriété.

Nous pouvons également vérifier la propriété des lignes de mémoire de la pile, ce qui permet d'optimiser le retour de l'un des arguments en toute sécurité.

Supposons qu'une fonction soit appelée avec des arguments concat2("", "123") . x est une chaîne vide, et si y pas alloué sur la pile, nous pouvons le renvoyer comme résultat de la concaténation.

 //; ,  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 déplace * g vers le registre AX . La lecture avec un décalage nul donnera le champ g.stack.lo , et g.stack.hi commence par le 8ème octet (pour une plate-forme 64 bits).

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

Le corps concatenate alloue de la mémoire, la remplit avec les deux lignes et renvoie une nouvelle ligne.

 #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 

Indice de performance: 100% (+8,6).

En conclusion

Tout le code est fourni sous forme de package concat .

Le monde est-il prêt pour une concaténation aussi rapide? Qui sait.

Au début de l'article, CL123256 a été mentionné. Il a plusieurs voies de développement:

1. Spécialisation variationnelle pour le cas où le compilateur n'alloue pas de tampon temporaire. Il y a moins de croissance pour chaque cas, mais il couvre plus de types de concaténation et n'augmente pratiquement pas la taille du code (machine et code Go).
2. Plus de spécialisations pour des cas spéciaux. Des gains plus élevés, mais plus de code machine, peuvent endommager le cache d'instructions.
3. Des tonnes de code machine, pour chaque cas spécial et memmove spécialisé, de la manière dont cela se fait dans la glibc. Ici se posent principalement des questions d'opportunité.

L'option actuellement proposée accélère uniquement le cas le plus courant et le plus simple de concaténation d'une paire de chaînes (arity = 2).

Si Go n'accepte pas cette modification, une accélération comparable peut être obtenue en implémentant des opérations de chaîne sous la forme d'une bibliothèque tierce. Moins pratique, beau et élégant, mais ça marche.