noalloc: Tooling en bibliotheken voor zero heap allocations in Golang

Het is één ding om code te schrijven die niet op de heap alloceert. Het is iets anders om te voorkomen dat code gaat alloceren naarmate de code verandert. Met noalloc kun je vaststellen dat Golang-functies niet mogen alloceren, waarna de noalloc CLI de volledige aanroepboom van die functie controleert op heap-allocaties.

noalloc geeft elke regel aan die alloceert, waardoor je deze kunt herstellen of vrijstellen. Daarnaast biedt noalloc data-structuren en algoritmen met een vaste grootte die nul allocaties veroorzaken (inclusief een JSON-encoder en -decoder), om het gemakkelijker en overzichtelijker te maken om code te schrijven die niet alloceert.

Installatie en basisgebruik

Installeer de tool met het volgende commando:

go install github.com/theconsensuslabs/noalloc/cmd/noalloc@latest

Vereiste: Go 1.27 of later.

Voorbeeld

Markeer een functie met //noalloc:root en voer noalloc uit in de betreffende module:

//noalloc:root
func (c *Counter) Add(name string, n int) string {
    c.counts[name] += n
    return name + "=" + strconv.Itoa(c.counts[name])
}

Uitvoer van de CLI:

$ noalloc
counter.go:11: (*example.com/counter.Counter).Add: map write
counter.go:12: (*example.com/counter.Counter).Add: calls strconv.Itoa; string concatenation; escapes: name + "=" + ~r0 escapes to heap

noalloc sluit af met exitcode 1 (er is een allocatie gevonden) of 2 (de tool kon niet worden uitgevoerd). Allocaties op een fout (error) of panic die de aanroep van de root beëindigt, en allocaties bij de eerste opstart (first-use setup), worden toegestaan (zie de kanttekeningen hieronder).

Directieven

• //noalloc:root: Controleert een functie en alles wat deze aanroept.
• //noalloc:exempt <reden>: Vrijstelt de regel waarop het staat en alles wat die regel aanroept. Wanneer het op een eigen regel staat, geldt het voor de volgende regel.
• //noalloc:fixed: Geeft bij een type aan dat de methoden de slices nooit laten groeien, waardoor noalloc deze behandelt als hergebruikt geheugen.
• //noalloc:append: Markeert een functie die werkt zoals append, zodat een aanroep naar deze functie wordt beoordeeld als een aanroep naar append.

Hergebruikt geheugen en externe bronnen

Hergebruikt geheugen is geheugen dat tussen verzoeken wordt bewaard, zoals een buffer in een langlevende struct. Een append hieraan is alleen toegestaan nadat een vergelijking bewijst dat er ruimte is. Je kunt velden van een type ook markeren als hergebruikt geheugen met -scratch pkg/path.Type.

Een aanroep naar een functie buiten je module is toegestaan wanneer de code van die functie zelf niets alloceert. noalloc stelt dit vast op basis van de broncode, of op basis van gecompileerde code als deze in assembly is geschreven of deel uitmaakt van de runtime.

Pakketten die je via -source (met een importpad-prefix) controleert, worden behandeld als onderdeel van je module. Zo kun je de bibliotheken van noalloc zelf controleren: -source github.com/theconsensuslabs/noalloc/bounded (en hetzelfde voor encoding/json), zodat hun //noalloc:fixed types en andere directieven worden meegeteld. Gebruik noalloc -h voor alle beschikbare vlaggen.

Ontwerpen met bounded

De bounded bibliotheek bevat vier containers met een vaste maximale capaciteit: Buf, Vec, Slice, en Map. Wanneer een schrijfactie de capaciteit overschrijdt, gebeurt er niets en wordt de container als "vol" gemarkeerd. Hierdoor kun je één keer aan het einde controleren in plaats van na elke schrijfactie. Het geheugen van een container kan eigen geheugen zijn, of geleend van een Pool via een Region.

Buf

Een Buf is een byte-buffer. Geef het geheugen via Reset. Zodra een schrijfactie niet past, blijft het vol:

var b bounded.Buf
b.Reset(make([]byte, 32), nil)
b.WriteString("id=")
b.WriteInt(42)
fmt.Println(string(b.Bytes()), b.Full()) // id=42 false

b.WriteString(strings.Repeat("x", 40))
fmt.Println(string(b.Bytes()), b.Full()) // id=42 true

Door ook een writer mee te geven, flusht de buffer naar de writer in plaats van vol te raken:

var b bounded.Buf
b.Reset(make([]byte, 8), os.Stdout)
b.WriteString("hello, ")
b.WriteString("world\n") // flusht eerst "hello, "
b.Flush()                // print: hello, world

Vec

Een Vec is een lijst van elk type. Met het opgegeven geheugen bevat het zoveel items als de capaciteit van dat geheugen toelaat:

var v bounded.Vec[int]
v.Reset(make([]int, 0, 3))
for i := range 5 {
    v.Push(i * i)
}
fmt.Println(v.Items(), v.Full()) // [0 1 4] true

Met ResetFrom kan het chunks lenen uit een pool naarmate het vol raakt, tot aan het budget van de regio. Omdat de items niet aaneengesloten zijn, lees je ze met At of per chunk met Chunks:

pool := bounded.NewPool[int](4, 8)
var r bounded.Region
r.Reset(2 * pool.ChunkBytes())
defer r.Release()

var v bounded.Vec[int]
v.ResetFrom(&r, pool)
for i := range 10 {
    v.Push(i)
}
fmt.Println(v.Len(), v.Full(), v.At(6)) // 8 true 6
for c := range v.Chunks() {
    fmt.Println(c) // [0 1 2 3], dan [4 5 6 7]
}

Slice

Een Slice is aaneengesloten. Wanneer een chunk vol is, kan deze overgaan naar een chunk uit de volgende, grotere pool (vergelijkbaar met hoe append een slice verplaatst naar een groter array):

classes := bounded.NewClasses(bounded.NewPool[int](4, 8), bounded.NewPool[int](16, 8))
var r bounded.Region
r.Reset(1 << 10)
defer r.Release()

var s bounded.Slice[int]
s.ResetFrom(&r, classes)
for i := range 10 {
    s.Push(i)
}
fmt.Println(s.Items(), s.Cap()) // [0 1 2 3 4 5 6 7 8 9] 16

Map

Een Map bevat maximaal het aantal entries waarvoor deze is gereset. Een nieuwe sleutel buiten dit aantal wordt niet toegevoegd, maar bestaande sleutels kunnen nog wel worden bijgewerkt:

var m bounded.Map[string, int]
m.Reset(2)
m.Set("a", 1)
m.Set("b", 2)
fmt.Println(m.Set("c", 3), m.Full()) // false true
v, ok := m.Get("a")
fmt.Println(v, ok, m.Len()) // 1 true 2

Met Grow begint de map klein en kan deze overgaan naar grotere pools van slots naarmate deze vult:

maps := bounded.NewMapClasses(bounded.NewMapPool[string, int](4, 8), bounded.NewMapPool[string, int](64, 8))
var r bounded.Region
r.Reset(1 << 20)
defer r.Release()

var m bounded.Map[string, int]
m.Grow(&r, maps)
for i := range 20 {
    m.Set(strconv.Itoa(i), i)
}
fmt.Println(m.Len(), m.Limit()) // 20 64

Pool en Region

Een Pool leent een vast aantal chunks. Wanneer deze op zijn, geeft Take nil terug totdat een region er een teruggeeft:

pool := bounded.NewPool[byte](1<<10, 2)
var a, b bounded.Region
a.Reset(4 << 10)
b.Reset(4 << 10)

bounded.Take(&a, pool) // a krijgt de eerste chunk
bounded.Take(&a, pool) // en de tweede
bounded.Take(&b, pool) // nil: de pool is leeg
a.Release()
bounded.Take(&b, pool) // b krijgt een van a's
b.Release()

st := pool.Stats()
fmt.Println(st.Lent, st.Empty) // 3 1

Gebruik Wait in plaats van Take om te wachten op een chunk tot een channel sluit, en Reserve om meerdere chunks tegelijk (of geen) te claimen.

Omgaan met dynamische input

Omdat de grootte van de input van een verzoek pas bekend is bij binnenkomst, krijgt elk verzoek bij aanvang een Region met een vast budget. Binnen dat budget leent het chunks uit een gedeelde Pool. Het vrijgeven van de regio aan het einde van het verzoek geeft alle chunks terug:

var rows = bounded.NewPool[byte](16<<10, 64)
var nowOnly = func() chan struct{} { c := make(chan struct{}); close(c); return c }()

func (p *page) serve(w io.Writer) error {
    p.region.Reset(4 * rows.ChunkBytes())
    defer p.region.Release()
    if !bounded.Reserve(nowOnly, &p.region, rows, 1) {
        return errBusy
    }
    p.out.ResetFrom(&p.region, rows, w)
    for p.next() {
        p.writeRow(&p.out)
    }
    p.out.Flush()
    return p.out.Err()
}

Hier streamt de pagina via één chunk die flusht zodra deze vol is, waardoor een lange pagina niet meer geheugen nodig heeft dan een korte. Output die volledig bewaard moet blijven, kan Buf.Borrow gebruiken, wat de buffer telkens naar een grotere chunk verplaatst tot het budget van de regio op is.

Elke site die het geheugenbudget kan uitputten, heeft een plan nodig voor dat scenario. Voorbeelden:

• De pagina voortijdig beëindigen en de client laten hervatten vanaf een cursor.
• Een optimalisatie overslaan wanneer het tragere pad nog steeds het juiste antwoord geeft.
• Een entry in een memo vergeten.
• Input weigeren die te groot is om te parsen voordat het parsen begint.
• Output streamen via een Buf die flusht naar de response. Reserveer wat een verzoek nodig heeft om te starten en dimensioneer de pool om elk toegelaten verzoek tegelijkertijd te kunnen accommoderen.

JSON Encoderen en Decoderen

encoding/json codeert en decodeert JSON zonder allocaties (inclusief de eerste aanroep), via methoden die het jsongen commando schrijft voor jouw types:

//go:generate go run github.com/theconsensuslabs/noalloc/cmd/jsongen -write Reply -read Request

WriteJSON schrijft via een Writer naar geheugen dat je opgeeft en over aanroepen heen behoudt, en flusht naar een io.Writer zodra dit vol is:

var w json.Writer
w.Reset(mem, out)
reply.WriteJSON(&w)
if w.Flush() != nil {
    return errReply
}

ReadJSON leest via een Reader vanuit geheugen of een io.Reader via een door jou opgegeven buffer. Strings worden gedecodeerd in de Arena van de Reader over jouw geheugen; als dit vol raakt, wordt More aangeroepen voor een nieuwe chunk. Slices worden gedecodeerd in de beschikbare capaciteit en een pointer naar waar deze naar wijst; voorbij deze limiet faalt de decode met Full in plaats van te alloceren:

req := Request{Tags: make([]string, 0, 16)}
var r json.Reader
r.Arena.Reset(stringMemory)
r.ResetBytes(body)
req.ReadJSON(&r)
if r.Finish() != nil {
    return errRequest
}

Een Writer of Reader kan lokaal leven zonder allocaties, maar het geheugen dat je eraan geeft kan dat niet: Reset behoudt de slice, wat een array erachter naar de heap verplaatst. De fouten Err, Flush en Finish retourneren pointers naar de Writer of Reader; vergelijk deze daarom met nil (zoals hierboven), in plaats van ze te retourneren of te loggen, omdat dat de volledige waarde naar de heap verplaatst.

Wat WriteJSON schrijft, kan worden gedecodeerd met de standaardbibliotheek encoding/json (het resultaat is gelijk aan json.Marshal). ReadJSON decodeert wat json.Unmarshal doet, behalve dat een time zijn instant behoudt maar in UTC decodeert. jsongen weigert types die niet zonder allocaties gecodeerd of gedecodeerd kunnen worden, zoals maps en interfaces. Een type kan in dat geval eigen WriteJSON of ReadJSON methoden implementeren.

Performance JSON

Onderstaande tabel toont de CPU-seconden (user en system) voor 3.000 feed-operaties (ca. 130 KB) of 3.000.000 cookie-operaties op een Apple M4 (10 cores) met Go 1.27.0.

Library	Feed encode (s)	Feed decode (s)	Cookie encode (s)	Cookie decode (s)	Allocaties per feed decode
goccy/go-json v0.11.2	0.64	0.74	0.68	0.67	4
noalloc's jsongen	0.87	1.16	0.75	1.08	0
go-faster/jx v1.2.0	0.98	1.54	0.80	1.13	3,500
mailru/easyjson v0.9.0	0.97	1.77	0.87	1.88	4,001
bytedance/sonic v1.15.5	1.52	1.04	1.89	1.82	3
encoding/json/v2	1.58	2.63	1.82	2.11	3,196
encoding/json	1.52	2.94	1.77	2.65	1,696

Opmerking: Sonic is gebouwd voor amd64, dus op de M4 (arm64) zijn deze cijfers waarschijnlijk lager dan in werkelijkheid.

HTML en URL Escaping

html/template heeft append-versies van zes van de zestien escapers: de twee voor HTML-tekst en attribuutwaarden, de URL-filter, normalizer, escaper, en de stap die een waarde in een script afrondt (gegeven dat deze al als JSON is gecodeerd). Het parseert of executeert geen templates en escaped geen CSS, JavaScript-strings, comments of srcset. net/url heeft een append-versie van url.QueryEscape.

Elk van deze schrijft de bytes die de standaardbibliotheek-tegenhanger zou retourneren, en alloceert alleen wanneer de doorgegeven slice moet groeien.

Veelvoorkomende fouten

Geheugen gebruiken na Region.Release

Een Vec of Slice veroorzaakt een panic als deze wordt gebruikt nadat de regio is vrijgegeven. Een Buf of Map kan dit niet detecteren en leest wat de volgende gebruiker heeft geschreven. Geef een regio pas vrij als het verzoek klaar is met alles wat het heeft geleend (gebruik defer direct na Reset).

Items of Bytes behouden over een schrijfactie heen

Wanneer een Slice of een Buf die kan lenen zijn capaciteit bereikt, kan deze verhuizen naar een grotere chunk en de oude teruggeven aan de pool. Een slice die je via Items of Bytes hebt verkregen vóór de verhuizing, wijst nog steeds naar de oude chunk. Roep Items of Bytes opnieuw aan na elke schrijfactie.

Reserveren buiten admission control

Een regio houdt chunks vast terwijl deze wacht op de rest. Twee regio's die elk beide chunks van een pool met twee chunks nodig hebben, kunnen elk één claimen en een deadlock veroorzaken. Reserveer pas zodra een verzoek is toegelaten (admitted) en dimensioneer de pool om elke reservering van toegelaten verzoeken tegelijkertijd te kunnen faciliteren.

Lenen per item

Lenen en teruggeven vereisen een lock. Leen daarom één keer per verzoek in plaats van één keer per item.

Een Region delen tussen goroutines

Een Pool is veilig om te delen tussen goroutines, maar een Region is dat niet. Gebruik -race om dit te detecteren.

ctx.Done() doorgeven aan Wait of Reserve

De eerste aanroep naar Done op een annuleerbare context alloceert zijn channel. noalloc telt dit als "first-use setup" en rapporteert het niet, maar elke nieuwe context alloceert zijn eigen channel. Geef in plaats daarvan een channel door dat je één keer maakt, zoals een channel dat je server sluit bij shutdown.

Verwachten van geneulde (zeroed) chunks

Een pool nulst een chunk alleen bij terugkomst als het type van de chunk pointers bevat. Anders krijg je wat de vorige gebruiker heeft achtergelaten. Maak de chunk zelf leeg als je nullen nodig hebt.

Een regel vrijstellen om de check stil te krijgen

Een vrijstelling (exempt) dekt alles wat de regel aanroept. Als noalloc bijvoorbeeld niet in format kijkt, worden allocaties daarin niet gerapporteerd. Om alleen de regel zelf vrij te stellen, geef je het type van de reden door aan -line-only.

Kanttekeningen (Caveats)

Functies geschreven in assembly

noalloc beoordeelt functies zonder Go-body op basis van de gecompileerde code. Aanroepen via een register kunnen niet worden gevolgd, waardoor een functie die dit doet als allocerend wordt geteld. Als noalloc een functie niet kan volgen waarvan je weet dat deze niets alloceert, lijst deze dan als measured en test deze met alloctest.Zero.

Aanroepen buiten je module

noalloc stelt vast wat elke functie buiten je module alloceert op basis van de code die je build compileert en cached dit in een noalloc directory in je user cache. De eerste run op een nieuwe toolchain of platform duurt langer. Functies die niet gevolgd kunnen worden (bijv. aanroepen via een functiewaarde) worden als allocerend geteld.

De output van de compiler

noalloc parseert de output van go build -gcflags=-m, en die output kan veranderen tussen Go-releases. Fix je toolchain in go.mod en voer noalloc opnieuw uit bij een upgrade.

Waar noalloc op vertrouwt

noalloc vertrouwt op de allowlist, //noalloc:fixed en elke vrijstelling zonder deze te verifiëren. De allowlist bevat functies die als niet-alloceerbaar worden beschouwd om de volgende redenen:

• amortized: alloceert alleen om geheugen te laten groeien dat de runtime bewaart en hergebruikt.
• measured: code kan niet gevolgd worden, maar een test toont aan dat er geen allocaties zijn.
• debug of profiling: alloceert alleen op een pad dat wordt gebruikt voor debugging of profiling.

Aanroepen die niet opgelost kunnen worden

Wanneer noalloc niet kan bepalen naar welke functie een functiewaarde verwijst, wordt de aanroep gerapporteerd. Dit kan worden opgelost door een concrete functie of type aan te roepen, of de aanroep vrij te stellen.

Interface aanroepen

noalloc controleert elke methode die een interface-aanroep kan bereiken. Als de concrete type van de waarde bekend is in de module, wordt alleen die methode gecontroleerd via VTA (variable type analysis). Anders worden alle implementaties die noalloc kan vinden gecontroleerd.

noalloc staat het volgende toe:

• Type assertions en type switches.
• Conversie van een waarde naar een interface, mits de waarde op de stack blijft of nul-grootte, één byte of een bool is.
• Het doorgeven van een eigen type als interface aan code buiten de module.

Beperkingen:

• Alleen pakketten die je module importeert worden doorzocht naar implementaties.
• Elk type in je module dat de interface implementeert wordt gecontroleerd, ook als geen enkele aanroeper dit type doorgeeft.
• Anonieme interfaces (bijv. interface{ Do() int }) en error hebben geen implementaties die noalloc buiten je module kan opzoeken.

Code die geen root bereikt

noalloc controleert alleen code die bereikbaar is vanuit een root. Markeer daarom elk toegangspunt met //noalloc:root.

Error en panic paden

noalloc staat allocaties toe op een fout die de aanroep van de root beëindigt (bijv. een pad dat paniekt of een non-nil error retourneert die de root bereikt). Een fout die de aanroep niet beëindigt, wordt wel gecontroleerd, omdat deze opnieuw kan voorkomen bij het volgende item in een loop.

First-use setup

noalloc staat een branch toe die controleert of een veld of package-variabele nil is en deze vervolgens instelt.

Controle tegen gecompileerde code

noalloc vergelijkt bevindingen met de allokerende runtime-aanroepen in de gecompileerde code. Er zijn enkele hiaten:

• Een baseline kan geen fouten opsommen; een run blijft falen tot de code is aangepast.
• Het is afhankelijk van assembly en symboolnamen van de compiler.
• Het telt maar vergelijkt geen inlined calls uit andere pakketten of calls naar runtime-functies die het niet kan classificeren.

Code die al alloceert

Als je noalloc toevoegt aan bestaande code, start dan met een baseline:

noalloc -baseline noalloc.txt -start
noalloc -baseline noalloc.txt

Het tweede commando faalt bij elke nieuwe allocatie.

Performance van bounded

De Pool en Map van bounded zijn trager dan sync.Pool en de standaard Go map, in ruil voor een begrensd geheugenverbruik.

Operatie	Go	bounded
Borrow and return a 16 KB buffer	8.0 ns (sync.Pool)	15.0 ns
Hetzelfde op 10 cores tegelijk, per borrow	1.5 ns (sync.Pool)	3.1 ns
1,024 sets and gets	12.0 µs (map)	17.3 µs (Map)
Read 4,096 ints	4.8 µs (slice)	4.0 µs (Vec.At), 4.8 µs (Vec.Chunks)

Prior Art

• OxCaml's zero_alloc checker: Laat de compiler bewijzen dat een functie en alles wat deze aanroept nooit op de heap alloceert.
• gcassert: Controleert specifieke geannoteerde regels.
• testing.AllocsPerRun: Telt allocaties voor specifieke test-inputs.
• TigerBeetle: Alloceert al het geheugen bij opstarten.
• PostgreSQL's memory contexts: Geeft al het geheugen van een query in één keer vrij.
• Zig: Geeft een allocator mee aan elke functie die alloceert.

Licentie

MIT. Zie LICENSE. Code die is aangepast van Go's source behoudt de BSD-licentie van Go. De JSONTestSuite is onder de MIT-licentie.