Entspricht der unten gezeigte Code der Leistung?

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

Die Antwort ist nein .

Für Details und Erklärungen frage ich unter Katze.

Guten Tag, bevor Sie das Thema eröffnen, möchte ich mich vorstellen.
Mein Name ist Iskander und von Zeit zu Zeit sende ich Commits an das Golang / Go- Repository.

Früher habe ich dies im Auftrag des Intel Go- Teams getan, aber unsere Wege gingen auseinander und jetzt bin ich ein unabhängiger Mitarbeiter. Vor kurzem habe ich in vk im Infrastruktur-Team gearbeitet.

In meiner Freizeit mache ich verschiedene Tools für Go, wie z. B. Go-Kritiker und Go-Consistent . Ich zeichne auch Gophers .

Messen Sie es!

Fahren Sie sofort mit dem Vergleich fort und skizzieren Sie den Benchmark:

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

Anstatt Ihnen Benchstat zu empfehlen, zeige ich Ihnen Benchrun .

Mit einem Befehl können wir beide Benchmarks ausführen und einen Vergleich erhalten:

 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) 

Die Option mit manueller Einbettung ist viel schneller als der Code, der durch Einbetten des Funktionskörpers in den Compiler erhalten wurde. Versuchen wir herauszufinden, warum dies geschieht.

string.HasPrefix

Erinnern Sie sich an die Implementierung von 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 } 

Die HasPrefix Funktion HasPrefix vom Compiler integriert.
Sie können dies wie folgt überprüfen:

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

Um strings.HasPrefix aus Option (A) aufzurufen, erhalten wir den folgenden Maschinencode:

  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 

Ignorieren Sie die Tatsache, dass der Code wie Nudeln aussieht.

Worauf Sie achten sollten:

• strings.HasPrefix wirklich eingefügt, kein Aufruf.
• Um Zeichenfolgen zu vergleichen, wird runtime.memequal .

Aber was wird dann für die manuell eingebaute Version generiert, den Code aus Beispiel (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 

Und hier generiert der Compiler keinen Aufruf von runtime.memequal und ein einzelnes Zeichen wird direkt verglichen. Idealerweise hätte er dasselbe für die erste Option tun sollen.

Wir beobachten die schwache Seite des Go-Optimierers und werden sie analysieren.

Optimierung des konstanten Ausdrucks

Der Grund, warum der Aufruf von strings.HasPrefix(s, "#") optimiert werden kann, liegt darin, dass das Präfixargument eine Konstante ist. Wir kennen seine Länge und seinen Inhalt. Es macht keinen Sinn, runtime.memequal für kurze Zeichenfolgen runtime.memequal . Es ist schneller, Zeichen "an Ort und Stelle" zu vergleichen, um einen zusätzlichen Aufruf zu vermeiden.

Wie Sie wissen, bestehen Compiler normalerweise aus mindestens zwei Teilen: dem Compiler-Frontend und dem Compiler-Backend . Die erste arbeitet mit einer übergeordneten Ansicht, die zweite befindet sich näher an der Maschine und die Zwischenansicht sieht aus wie ein Anweisungsstrom. Mehrere Versionen von Go haben die SSA- Darstellung bereits für Optimierungen im Backend-Teil des Compilers verwendet.

Eine konstante Faltung wie {10*2 => 20} ist im Backend implementiert. Im Allgemeinen befinden sich die meisten Operationen, die mit dem Verringern der Berechnungskosten von Ausdrücken verbunden sind, in diesem Teil des Compilers. Es gibt jedoch Ausnahmen.

Eine Ausnahme bildet die Optimierung konstanter String-Vergleiche. Wenn der Compiler einen String- (oder Teilstring-) Vergleich sieht, bei dem einer oder beide Operanden Konstanten sind, wird effizienterer Code generiert als ein Aufruf von runtime.memequal .

Den dafür verantwortlichen Quellcode sehen Sie in der Datei cmd / compile / internal / gc / walk.go: 3362 .

Das Einbetten von Funktionen erfolgt vor dem Start dieser Optimierungen, aber auch im Frontend-Teil des Compilers.

Es scheint, dass diese Optimierung in unserem Fall trotzdem nicht funktioniert.

Funktionsweise Einbetten von Funktionsaufrufen

So wird die Einbettung erfolgen:

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

Beim Einbetten von Funktionen weist der Compiler temporären Variablen Argumente zu, wodurch Optimierungen unterbrochen werden , da der Algorithmus in walk.go keine Konstanten, sondern Argumente mit Variablen sieht. Das ist das Problem.

Dies beeinträchtigt übrigens nicht die Backend-Optimierungen, über die die SSA verfügt. Dort gibt es jedoch noch andere Probleme, beispielsweise die Unfähigkeit, Sprachkonstrukte auf hoher Ebene für einen effektiven Vergleich wiederherzustellen (die Arbeiten zur Beseitigung dieses Nachteils sind seit mehreren Jahren „geplant“).

Ein weiteres Beispiel: Fluchtanalyse

Stellen Sie sich eine Funktion vor, die wichtig ist, um einen temporären Puffer auf dem Stapel zuzuweisen:

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

Da buf nicht "wegläuft", kann der Compiler diese 16 Bytes auf dem Stapel ohne Zuordnung auf dem Heap zuweisen. Nochmals alles dank des konstanten Wertes beim Aufruf von make . Um Speicher auf dem Stapel zuzuweisen, ist es wichtig, die erforderliche Größe zu kennen, die Teil des dem Funktionsaufruf zugewiesenen Rahmens ist.

Angenommen, wir wollten in Zukunft temporäre Puffer unterschiedlicher Größe zuweisen und einige Logik in Methoden einkapseln. Wir haben eine neue Abstraktion eingeführt und beschlossen, den neuen Typ tmpBuf . Die Designfunktion ist sehr einfach:

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

Anpassung des Originalbeispiels:

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

Der Konstruktor wird eingebettet, aber die Zuordnung befindet sich jetzt immer auf dem Heap, aus demselben Grund, aus dem Argumente über temporäre Variablen übergeben werden. Bei der Escape-Analyse wird make([]byte, 0, _sizeHint) , das für optimierte Anrufe nicht unter die Erkennungsmuster fällt.

Wenn wir "alles wie Menschen" hätten, würde das Problem nicht bestehen. Nach dem Einbetten des newTmpBuf Konstruktors wäre klar, dass die Größe in der Kompilierungsphase noch bekannt ist.

Dies stört fast mehr als die Situation beim Vergleichen von Zeichenfolgen.

Horizonte gehen 1.13

Die Situation kann leicht korrigiert werden und ich habe bereits den ersten Teil der Entscheidung gesendet.

Wenn Sie der Meinung sind, dass das im Artikel beschriebene Problem wirklich eine Lösung benötigt, setzen Sie bitte einen Daumen hoch in das entsprechende Problem .

Mein Standpunkt ist, dass das Einbetten von Code mit Ihren Händen, nur weil er in der aktuellen Version von Go schneller funktioniert, falsch ist. Es ist notwendig, diesen Fehler im Optimierer zu beheben, zumindest bis zu dem Punkt, an dem die oben beschriebenen Beispiele ohne unerwartete Leistungsrückgänge funktionieren.

Wenn alles nach Plan verläuft, wird diese Optimierung in der Version Go 1.13 enthalten sein.

Vielen Dank für Ihre Aufmerksamkeit.

Ergänzung: Lösungsvorschlag

Dieser Abschnitt ist für die Mutigsten, die nicht müde sind zu lesen.

Wir haben also mehrere Stellen, die schlechter funktionieren, wenn Variablen anstelle ihrer Werte direkt verwendet werden. Die vorgeschlagene Lösung besteht darin, eine neue Funktion im Frontend des Compilerteils einzuführen, mit der Sie den letzten gebundenen Wert nach Namen abrufen können. Geben Sie danach bei jeder Optimierung, die einen konstanten Wert erwartet, nicht auf, wenn eine Variable erkannt wird, sondern erhalten Sie diesen zuvor gespeicherten Status.

Die Signatur unserer neuen Funktion könnte folgendermaßen aussehen:

 func getConstValue(n *Node) *Node 

Die Definition des Node finden Sie in der Datei syntax.go .

Jede Variablendefinition verfügt über ein Node Tag mit einem ONAME Tag. In Node.Name.Defn meisten dieser Variablen einen Initialisierungswert.

Wenn Node bereits ein Literal ist, müssen Sie nichts tun und wir geben nur n . Wenn dies ONAME (Variable) ist, können Sie versuchen, denselben Initialisierungswert aus n.Name.Defn zu extrahieren.

Aber was ist mit den Änderungen zwischen dem Deklarieren und Lesen einer Variablen, für die wir getConstValue ? Wenn wir uns auf schreibgeschützte Variablen beschränken, gibt es kein Problem. Das Frontend von Go verfügt bereits über spezielle Knotenflags, die ähnliche Namen kennzeichnen. Wenn die Variable geändert wurde, gibt getConstValue keinen Initialisierungswert zurück.

Programmierer ändern in der Regel nicht die Eingabeargumente von numerischen Typen und Zeichenfolgentypen, und dies ermöglicht es, mit diesem primitiven Algorithmus eine relativ große Anzahl von Fällen abzudecken.

Jetzt sind wir bereit, die Implementierung zu prüfen:

 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 } 

So ändert sich der Code, was von den Konstanten abhängt:

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

Großartig und es funktioniert sogar:

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

Vor dieser Änderung konnte die Escape-Analyse den Wert 10 bis n nicht erhalten, weshalb ich davon ausgegangen bin, dass xs auf dem Heap platziert werden muss.

Der obige Code ähnelt syntaktisch der beim Einbetten beobachteten Situation. n kann eine temporäre Variable sein, die hinzugefügt wird, wenn das Argument übergeben wird.

Leider gibt es Nuancen.

Wir haben das Problem für lokale Variablen gelöst, die über OAS eingeführt wurden , aber Go initialisiert die Variablen für integrierte Funktionen über OAS2 . Aus diesem Grund benötigen wir eine zweite Änderung, die die Funktion getConstValue und den Code des Inliners selbst geringfügig ändert, da OAS2 unter anderem kein geeignetes Defn Feld hat.

Das waren schlechte Nachrichten. Gute Nachrichten: #gocontributing channel erschien in der russischsprachigen Lücke , wo Sie Ihre Ideen und Pläne teilen, Fragen stellen und alles diskutieren können, was mit der Teilnahme an der Go-Entwicklung zu tun hat .