Heute werden wir die Bindung von kurzen Leitungen in Go um 30% beschleunigen. Und dafür müssen wir Go selbst nicht ändern, all dies wird als Bibliothek eines Drittanbieters implementiert.

Unter dem Schnitt, auf den Sie warten:

• Vergleichen von + , strings.Builder und nativen Verkettungsfunktionen
• Gehen Sie zu internen Zeilendetails
• Ziemlich viel Assembler

Dieser Artikel kann auch als Ausrede für CL123256 angesehen werden: Laufzeit, cmd / compile: specialize concatstring2 . Ideen zur Verbesserung dieser Änderungsliste sind willkommen.

Sofort Ergebnisse

Der Vergleich wurde mit der go tip (Master) -Version des Compilers durchgeführt. Sie können ähnliche Ergebnisse für Versionen um Go 1.5 erhalten. Die letzte signifikante Änderung an der Funktion concatstrings war CL3120: cmd / gc: Zuweisen von Puffern für nicht maskierte Zeichenfolgen auf dem Stapel .

 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 verwendet + .
ConcatBuilder verwendet ConcatBuilder mit der richtigen ConcatBuilder .
Concat verwendet die Funktion, die wir als Teil dieser Geschichte implementieren.

Vergleich über 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) 

Die Assembler-Implementierung unter GOARCH=AMD64 etwas schneller und verfügt über eine zusätzliche Optimierung, die im integrierten Operator + vorhanden ist. Weitere GOARCH=AMD64 weiter unten:

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

Wir werden die Assembler-Funktion als 100% ige Leistung betrachten (im Vergleich zu den übrigen betrachteten Implementierungen).

Ergebnisse für längere Zeilen finden Sie in README.md . Je länger die Zeichenfolge ist, desto weniger ausgeprägt ist der Unterschied zwischen den Implementierungen.

Naive Verkettung

Die einfachste Lösung ist die Verwendung des Operators + .

Die Semantik dieser Anweisung lautet wie folgt: Nehmen Sie zwei Zeilen und geben Sie eine Ergebniszeichenfolge zurück, die die Verkettung beider Zeilen enthält. Es gibt keine Garantie dafür, dass eine neue Zeile zurückgegeben wird. Wenn beispielsweise eine leere Zeichenfolge und eine andere verknüpft sind, gibt die Laufzeit möglicherweise ein nicht leeres Argument zurück, sodass kein neuer Speicher zugewiesen und keine Daten kopiert werden müssen.

Wie aus den Ergebnissen am Anfang des Artikels hervorgeht, ist dies jedoch der langsamste Weg.

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

Leistungsbewertung: 67,8% .

Strings.Builder

Vor nicht allzu langer Zeit wurde Go - strings.Builder ein neuer Typ hinzugefügt. Dies ist ein Analogon zu bytes.Buffer , aber beim Aufrufen der String() -Methode wird der Speicher nicht neu zugewiesen und die Daten werden nicht kopiert.

Im Gegensatz zu bytes.Buffer verfügt der Builder nicht über die Optimierung eines kleinen Puffers und daher des zuvor zugewiesenen Speichers für eine Zeichenfolge. Wenn Sie die Grow Methode nicht verwenden, ist die Leistung schlechter als bei bytes.Buffer . Mehrere Regressionen in Go 1.11 werden durch diese spezielle Funktion verursacht (siehe CL113235 ).

In unserem Code werden wir diesen Fehler aus Gründen der Reinheit des Experiments vermeiden.

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

Leistungsbewertung: 80,5% (+12,7).

Codegenerierung zur Verkettung

Wenn wir uns ansehen, welchen Code der Compiler für den Operator + generiert, werden Aufrufe der Funktionen concatstring2 , concatstring3 concatstring2 concatstring3 (bis einschließlich concatstring5 ).

 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) 

Schauen Sie sich runtime / string.go selbst an :

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

Es bleibt also, die Funktion concatstrings zu lernen.
Eine vollständige Liste finden Sie unten unter dem Spoiler, aber hier ist eine allgemeine Beschreibung:

1. Der Parameter buf kann nil . Dieser Puffer wird vom Compiler zugewiesen, wenn die Zeile nicht aus ihrer Definition "entkommt". Wenn die Zeichenfolge länger als der Frame lebt, ist dieser Puffer immer nil (wie es am häufigsten vorkommt). Wenn dieser Puffer jedoch verfügbar ist, kann die Zuordnung vermieden werden, falls das Ergebnis in ihn eindringt (seine Größe beträgt 32 Byte).
2. Wenn alle Zeilen außer einer leer sind, gibt die Funktion diese Zeile zurück. Gleichzeitig umgehen die auf dem Stapel ausgewählten Zeilen, die ihren Frame verlassen, diese Optimierung, sodass der Aufrufer keinen bereits freigegebenen Speicher erhält.
3. Ferner werden alle Zeilen in den neuen Speicher kopiert.

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

Hier sehen wir mehrere Stellen gleichzeitig, die für einen bestimmten Fall optimiert werden können:

• buf meistens leer. Wenn der Compiler nicht beweisen konnte, dass die Zeichenfolge sicher auf dem Stapel abgelegt werden kann, führt das Übergeben eines zusätzlichen Parameters und das Überprüfen auf nil innerhalb der Funktion nur zu Overhead.
• Für den Sonderfall mit len(a) == 2 benötigen wir keinen Zyklus und die Berechnungen können vereinfacht werden. Und dies ist die häufigste Form der Verkettung.

Version für alle Architekturen

Um die Spezialisierung zu implementieren, müssen wir wissen, wie die Linien in Go dargestellt werden. Die Binärkompatibilität ist uns wichtig, während sie unsafe.Pointer ist. Der unsafe.Pointer kann ohne Einbußen durch *byte werden.

 type stringStruct struct { str *byte len int } 

Die zweite wichtige Schlussfolgerung, die wir aus der Laufzeit ziehen können: Linien beginnen ihr Leben veränderlich. Es wird ein Speicher zugewiesen, auf den durch das []byte verwiesen wird, in das der Inhalt der neuen Zeile geschrieben wird, und erst danach wird das []byte verworfen, und der Speicher, auf den es verweist, wird in stringStruct gespeichert.

Für diejenigen, die mehr Details wünschen, wird empfohlen, die Funktionen von rawstringtmp und 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 } 

Mit der dunklen Seite des unsafe Pakets können wir ungefähr gleich hochdrehen:

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

Wir markieren []byte , mit dem wir den Inhalt einer neuen Zeile bilden. Dann können wir die Zeile nur finalisieren, indem wir sie auf die erwartete Laufzeitdarstellung bringen. Die goString Funktion ist dafür verantwortlich:

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

Leistungsbewertung: 91,9% (+10,9).

AMD64-Version

Leider hat die vorherige Version der Funktion keine Optimierung für die Verkettung mit einer leeren Zeichenfolge, und wir führen auch eine Reihe unnötiger Berechnungen durch, da der Speicher nicht direkt zugewiesen werden kann. Wir müssen mit dem Byte-Slice arbeiten.

Eine der interessanten Funktionen des Go-Assemblers besteht darin, dass Sie beispielsweise nicht exportierbare Laufzeitfunktionen aufrufen können. Wir können runtime·mallocgc aus dem Assemblycode runtime·mallocgc , auch wenn es nicht Teil des runtime . Wir werden diese Eigenschaft nutzen.

Wir können auch den Besitz der Stapelspeicherzeilen überprüfen, wodurch es sicher ist, die Rückgabe eines der Argumente als Ergebnis zu optimieren.

Angenommen, eine Funktion wird mit den Argumenten concat2("", "123") aufgerufen. x ist eine leere Zeichenfolge, und wenn y nicht auf dem Stapel zugeordnet ist, können wir sie als Ergebnis der Verkettung zurückgeben.

 //; ,  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 verschiebt * g in das AX Register. Das Lesen bei Nullpunktverschiebung ergibt das Feld g.stack.lo , und g.stack.hi beginnt mit dem 8. Byte (für eine 64-Bit-Plattform).

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

Der concatenate Körper weist Speicher zu, füllt ihn mit beiden Zeilen und gibt eine neue Zeile zurück.

 #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 

Leistungsbewertung: 100% (+8,6).

Abschließend

Der gesamte Code wird als Concat- Paket bereitgestellt.

Ist die Welt bereit für eine so schnelle Verkettung? Wer weiß.

Zu Beginn des Artikels wurde CL123256 erwähnt. Er hat mehrere Entwicklungspfade:

1. Variationsspezialisierung für den Fall, dass der Compiler keinen temporären Puffer zuweist. Es gibt weniger Wachstum für jeden Fall, aber es deckt mehr Arten der Verkettung ab und erhöht praktisch nicht die Größe des Codes (sowohl Maschinen- als auch Go-Code).
2. Weitere Spezialisierungen für Sonderfälle. Höhere Gewinne, aber mehr Maschinencode können den Anweisungscache beschädigen.
3. Tonnenweise Maschinencode für jeden Sonderfall und jedes spezielle Memmove in der Art und Weise, wie dies in glibc erfolgt. Hier stellen sich vor allem Fragen der Zweckmäßigkeit.

Die derzeit vorgeschlagene Option beschleunigt nur den häufigsten und einfachsten Fall der Verkettung eines Zeichenfolgenpaars (arity = 2).

Wenn Go diese Änderung nicht akzeptiert, kann eine vergleichbare Beschleunigung erreicht werden, indem Zeichenfolgenoperationen in Form einer Bibliothek eines Drittanbieters implementiert werden. Weniger bequem, schön und elegant, aber es funktioniert.