bytes.Buffer in Go: Optimierungen, die nicht funktionieren

Published on September 06, 2018

bytes.Buffer in Go: Optimierungen, die nicht funktionieren

    Viele Go- Programmierer kennen sich mit Bytes aus . Einer der Vorteile besteht darin, dass Sie Heap-Zuweisungen vermeiden können, wenn Sie dasselbe Muster wie bei der " Optimierung kleiner Puffer / Größen " verwenden:


    type Buffer struct {
        bootstrap [64]byte // для избежания аллокации малых слайсов в куче
        // ... другие поля
    }

    Es gibt nur ein Problem. Diese Optimierung funktioniert nicht .


    Am Ende dieses Artikels erfahren Sie, warum diese Optimierung nicht funktioniert und was wir dagegen tun können.


    Wie geplant, "Small Buffer Optimization"


    Wir führen eine leicht vereinfachte Definition ein bytes.Buffer:


    const smallBufSize int = 64
    type Buffer struct {
        bootstrap [smallBufSize]byte
        buf       []byte
    }

    Wenn Sie Bufferbeispielsweise Aktionen für eine Methode ausführen Buffer.Write, wird der Datensatz immer in erstellt buf, bevor er in einer ähnlichen Methode gestartet wird. Dadurch Buffer.grow(n)wird sichergestellt, dass in diesem Bereich genügend Speicherplatz für die nächsten nBytes vorhanden ist.


    Es growkönnte so aussehen:


    func (b *Buffer) grow(n int) {
        // Код сильно упрощён по сравнению с настоящей реализацией bytes.Buffer.
        l := len(b.buf) // Фактическая длина Buffer
        need := n + l
        have := cap(b.buf) - l
        if have >= need {
            b.buf = b.buf[:need]
            return
        }
        if need <= smallBufSize {
            // Может быть только первой аллокацией,
            // копирование не нужно.
            b.buf = b.bootstrap[:]
        } else {
            // growFactor - функция подбора следующего размера аллокации.
            // В простейшем случае это need или need*2.
            newBuf := make([]byte, need, growFactor(need))
            copy(newBuf, b.buf)
            b.buf = newBuf
        }
    }

    Annahmen, die in unserer Implementierung von Buffer.grow verwendet wurden


    Wir gehen davon aus, dass dies len(b.buf)die tatsächliche Länge der Daten im Puffer ist, für die WriteMethoden zum Hinzufügen neuer Bytes zum Slice erforderlich sind. Dies bytes.Bufferist in der Standardbibliothek nicht der Fall, aber zum Beispiel ist dies ein unwichtiges Implementierungsdetail.




    Wenn bauf dem Stapel zugewiesen, wird das bootstrapInnere des Stapels zugewiesen. Dies bedeutet, dass der Slice b.bufden internen Speicher wieder verwendet, bohne dass eine zusätzliche Zuordnung erforderlich ist.


    Wenn festgestellt wird, growdass das bootstrapArray nicht mehr ausreicht, wird ein neues "echtes" Segment erstellt, in das Elemente aus dem vorherigen Speicher kopiert werden (aus dem "kleinen Puffer"). Danach Buffer.bootstrapwird die Relevanz verlieren. Wenn genannt Buffer.Reset, cap(b.buf)wird das gleiche bleiben, und die Notwendigkeit , in bootstrapder Matrix wird nicht mehr sein.


    Gedächtnis, das im Haufen entgeht


    Ferner wird erwartet, dass der Leser zumindest oberflächlich mit der Tatsache vertraut ist, dass eine solche Fluchtanalyse in Go erfolgt.


    Betrachten Sie die folgende Situation:


    func f() *Buffer {     
        var b bytes.Buffer // leak.go:11:6: moved to heap: b
        return &b          // leak.go:12:9: &b escapes to heap
    }

    Hier bwird auf dem Haufen hervorgehoben. Der Grund dafür ist ein "durchgesickerter" Zeiger auf b:


    $ go tool compile -m leak.go
    leak.go:12:9: &b escapes to heap
    leak.go:11:6: moved to heap: b

    Terminologie


    In diesem Artikel werden Undichtigkeiten und Fluchtwege fast synonym verwendet.


    В самом компиляторе есть некоторое различие, например, значение "убегает в кучу" (x escapes to heap), но параметры функции "утекающие" (leaking param x).


    Утекающий параметр означает, что переданный аргумент под этот параметр будет выделения в куче. Другими словами, leaking параметр заставляет аргументы убегать в кучу.




    Oben war der offensichtliche Fall, aber wie wäre es damit:


    func length() int {
        var b bytes.Buffer
        b.WriteString("1")
        return b.Len()
    }

    Hier brauchen wir nur 1 Byte, alles passt rein bootstrap, der Puffer selbst ist lokal und "rennt" nicht von der Funktion weg. Sie werden vielleicht überrascht sein, aber das Ergebnis wird bauf dem Haufen dasselbe sein .



    Um sicherzugehen, können Sie dies mit einem Benchmark überprüfen:


    BenchmarkLength-8  20000000  90.1 ns/op  112 B/op  1 allocs/op

    Benchmarklisting


    package p
    import (
        "bytes"
        "testing"
    )
    func length() int {
        var b bytes.Buffer
        b.WriteString("1")
        return b.Len()
    }
    func BenchmarkLength(b *testing.B) {
        for i := 0; i < b.N; i++ {
            _ = length()
        }
    }



    Erläuterung 112 B / op


    Когда runtime просит у аллокатора N байт, не обязательно, что будет выделено ровно N байт.


    Все результаты ниже указаны для комбинации GOOS=linux и GOARCH=AMD64.

    package benchmark
    import "testing"
    //go:noinline
    func alloc9() []byte {
        return make([]byte, 9)
    }
    func BenchmarkAlloc9(b *testing.B) {
        for i := 0; i < b.N; i++ {
            _ = alloc9()
        }
    }

    Если запустить go test -bench=. -benchmem с этим тестом:


    BenchmarkAlloc9-8  50000000  33.5 ns/op  16 B/op  1 allocs/op

    Запрошено 9 байтов, выделено 16. Теперь вернёмся к bytes.Buffer:


    fmt.Println(unsafe.Sizeof(bytes.Buffer{})) => 104

    Посмотрим на $GOROOT/src/runtime/sizeclasses.go:


    // class  bytes/obj  bytes/span  objects  tail waste  max waste
    //     1          8        8192     1024           0     87.50%
    //     2         16        8192      512           0     43.75%
    //     3         32        8192      256           0     46.88%
    //     4         48        8192      170          32     31.52%
    //     5         64        8192      128           0     23.44%
    //     6         80        8192      102          32     19.07%
    //     7         96        8192       85          32     15.95%
    //     8        112        8192       73          16     13.56%
    // ... остальные

    В 96 байт не влезает, выбирается 112.




    Aber warum passiert das?


    Was passiert und warum


    Eine Analyse der Situation findet sich in der eingangs erwähnten Ausgabe .
    Es gibt auch einen einfachen Reproducer .


    Problem einfach in Auftrag geben b.buf = b.bootstrap[:]. Dieser Code bewirkt, dass die Escape-Analyse davon ausgeht, dass sie b.bootstrap"wegläuft", und da es sich um ein Array handelt, wird es im Objekt selbst gespeichert, was bedeutet, dass Sie alles auf dem Heap zuweisen müssen b.


    Wenn Bootstrap ein Slice wäre, kein Array, dann wäre dies nicht geschehen, da es eine Ad-hoc-Optimierung für die Zuweisung von Slices von einem Objekt zu dem Objekt selbst gibt:


    // Несмотря на то, что здесь практически идентичная ситуация,
    // object не обязателен к размещению на куче.
    object.buf1 = object.buf2[a:b]

    Die Antwort lautet, warum diese Optimierung für Arrays nicht funktioniert. Dies wurde bereits oben formuliert. Hier ein Auszug aus esc.go # L835-L866 (der gesamte Optimierungscode wird durch Verweis hervorgehoben):


    // Note, this optimization does not apply to OSLICEARR,
    // because it does introduce a new pointer into b that was not already there
    // (pointer to b itself). After such assignment, if b contents escape,
    // b escapes as well. If we ignore such OSLICEARR, we will conclude
    // that b does not escape when b contents do.

    Hier ist es wert, hinzugefügt zu werden, dass es für den Zeigeranalysator mehrere Ebenen von "Lecks" gibt, die wichtigsten sind:


    1. Das Objekt entkommt (b entkommt). In diesem Fall muss das Objekt selbst auf dem Heap zugeordnet werden.
    2. Objektelemente entkommen (b Inhalte entkommen). In diesem Fall werden die Zeiger im Objekt als ausweichend betrachtet.

    Der Fall eines Arrays ist insofern besonders, als wenn ein Array leckt, das Objekt, das es enthält, lecken sollte.


    Die Escape-Analyse bestimmt, ob das Objekt auf dem Stapel abgelegt werden kann oder nicht, und stützt sich nur auf die Informationen, die im Hauptteil der analysierten Funktion verfügbar sind. Die Methode Buffer.grownimmt beinen Zeiger an, daher ist es erforderlich, einen geeigneten Platz für die Platzierung zu berechnen. Wie im Fall eines Arrays, können wir nicht unterscheiden "b escape"von "b contents escape", wir pessimistischen und kommen zu dem Schluss sein , dass der bPlatz auf dem Stapel nicht sicher ist.


    Angenommen, das self-assignmentMuster erlaubt die gleichen Arrays wie für Slices:


    package example
    var sink interface{}
    type bad struct {
        array [10]byte
        slice []byte
    }
    func (b *bad) bug() {
        b.slice = b.array[:] // ignoring self-assignment to b.slice
        sink = b.array       // b.array escapes to heap
        // b does not escape
    }

    Die Entscheidung, bin dieser Situation auf den Stapel zu legen, führt zu einer Katastrophe: Nach dem Verlassen der Funktion, in der sie erstellt wurde b, ist der Speicher, auf den sie verweist sink, nichts als Müll.


    Zeiger auf Arrays


    Stellen Sie sich vor, unsere Bufferwurde etwas anders deklariert:


    const smallBufSize int = 64
    type Buffer struct {
    -   bootstrap [smallBufSize]byte
    +   bootstrap *[smallBufSize]byte
        buf       []byte
    }

    Im Gegensatz zu einem regulären Array speichert ein Zeiger auf ein Array nicht alle Elemente in sich Buffer. Dies bedeutet, dass wenn die Auswahl bootstrapauf dem Heap nicht die Auswahl auf dem Heap mit sich bringt Buffer. Da die Escape-Analyse Zeigerfelder auf einem Stapel zuordnen kann, können wir, wenn möglich, davon ausgehen, dass eine solche Definition Buffererfolgreicher ist.


    Aber es ist in der Theorie. In der Praxis hat ein Zeiger auf ein Array keine spezielle Verarbeitung und fällt in dieselbe Kategorie wie ein Slice aus einem regulären Array, was nicht ganz korrekt ist. Das selbstzuweisende Array-Slice CL133375: cmd / compile / internal / gc: handle in esc.go versucht , dieses Problem zu beheben.


    Angenommen, diese Änderung wurde am Go-Compiler vorgenommen.


    Null Wert, den wir verloren haben


    Leider hat der Übergang von [64]bytenach *[64]byteein Problem: Wir können es nicht mehr verwenden, bootstrapohne es explizit zu initialisieren, der Nullwert ist Buffernicht mehr nützlich, wir brauchen einen Konstruktor.


    func NewBuffer() Buffer {
        return Buffer{bootstrap: new(*[smallBufSize]byte)}
    }

    Wir kehren Buffereher zurück, als *Bufferum Probleme mit der Analyse von Zeigern zu vermeiden (dies ist in Go sehr konservativ), und unter Berücksichtigung der Tatsache, dass es NewBufferimmer an der Stelle des Aufrufs eingebettet ist, tritt kein unnötiges Kopieren auf.


    Nach dem Einbetten des Körpers NewBufferin den Aufruf kann die Escape-Analyse nachweisen, dass new(*[smallBufSize]byte)die Lebensdauer des Rahmens der Funktion, in der er aufgerufen wird, die Lebensdauer nicht überschreitet. In diesem Fall befindet sich die Zuordnung auf dem Stapel.


    Intel Bytebuf


    Die oben beschriebene Optimierung wurde im Paket intel-go / bytebuf angewendet .


    Diese Bibliothek exportiert einen Typ bytebuf.Buffer, der bytes.Buffer99,9% dupliziert . Alle Änderungen beschränken sich auf die Einführung des Konstruktors ( bytebuf.New) und eines Zeigers auf ein Array anstelle des üblichen Arrays:


    type Buffer struct {
        buf       []byte   // contents are the bytes buf[off : len(buf)]
        off       int      // read at &buf[off], write at &buf[len(buf)]
    -   bootstrap [64]byte // helps small buffers avoid allocation.
    +   bootstrap *[64]byte // helps small buffers avoid allocation.
        lastRead  readOp   // last read operation (for Unread*).
    }

    Hier ist ein Leistungsvergleich mit bytes.Buffer:


    name            old time/op    new time/op    delta
    String/empty-8     138ns ±13%      24ns ± 0%   -82.94%  (p=0.000 n=10+8)
    String/5-8         186ns ±11%      60ns ± 1%   -67.82%  (p=0.000 n=10+10)
    String/64-8        225ns ±10%     108ns ± 6%   -52.26%  (p=0.000 n=10+10)
    String/128-8       474ns ±17%     338ns ±13%   -28.57%  (p=0.000 n=10+10)
    String/1024-8      889ns ± 0%     740ns ± 1%   -16.78%  (p=0.000 n=9+10)
    name            old alloc/op   new alloc/op   delta
    String/empty-8      112B ± 0%        0B       -100.00%  (p=0.000 n=10+10)
    String/5-8          117B ± 0%        5B ± 0%   -95.73%  (p=0.000 n=10+10)
    String/64-8         176B ± 0%       64B ± 0%   -63.64%  (p=0.000 n=10+10)
    String/128-8        368B ± 0%      256B ± 0%   -30.43%  (p=0.000 n=10+10)
    String/1024-8     2.16kB ± 0%    2.05kB ± 0%    -5.19%  (p=0.000 n=10+10)
    name            old allocs/op  new allocs/op  delta
    String/empty-8      1.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)
    String/5-8          2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=10+10)
    String/64-8         2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=10+10)
    String/128-8        3.00 ± 0%      2.00 ± 0%   -33.33%  (p=0.000 n=10+10)
    String/1024-8       3.00 ± 0%      2.00 ± 0%   -33.33%  (p=0.000 n=10+10)

    Alle weiteren Informationen finden Sie in der README .


    Aufgrund der Unmöglichkeit der Verwendung des Nullwerts und der Bindung an die Konstruktionsfunktion kann Newdiese Optimierung bytes.Buffernicht angewendet werden .


    Ist dies der einzige Weg, um es schneller zu machen bytes.Buffer? Die Antwort lautet nein. Genau so müssen jedoch nur minimale Änderungen an der Implementierung vorgenommen werden.


    Pläne für die Fluchtanalyse


    In der jetzigen Form ist Go's Analyse ziemlich schwach. Fast alle Operationen mit Zeigerwerten führen zu Heap-Zuweisungen, auch wenn dies keine gültige Entscheidung ist.


    Die meiste Zeit, die ich dem Golang / Go- Projekt widme , werde ich versuchen, es darauf auszurichten, genau diese Probleme zu lösen, sodass in der nächsten Version (1.12) einige Verbesserungen möglich sind.


    Über die Ergebnisse und Details der internen Struktur dieses Teils des Compilers können Sie in einem meiner folgenden Artikel lesen. Ich werde auch versuchen, eine Reihe von Empfehlungen bereitzustellen, die in einigen Fällen helfen, den Code so zu strukturieren, dass er weniger unerwünschte Speicherzuordnungen aufweist.