Zero-allocation IO pro Go soutěže

Zero-allokace I/O pro Go soutěže: šest inženýrských řešení

Vývojáři v Go na soutěžích často narážejí na omezení standardních nástrojů pro vstup-výstup. fmt.Fscan alokuje paměť při každém volání, bufio.Scanner je pevně svázán se skenovacím režimem a ruční parsování přes bufio.Reader vyžaduje kus kódu. Knihovna contestio tyto problémy řeší prací přímo s vnitřním bufferem bufio.Reader a zajišťuje zero-allokaci pro všechny operace.

Šest klíčových řešení umožňuje kombinovat rychlost ručního parsování, pohodlí fmt a flexibilitu bufio. Podporuje smíšené typy vstupu: čísla, řetězce, znak po znaku – bez přepínání režimů.

Práce přímo s buffrem: _nextToken bez kopírování

Základní přístup je funkce _nextToken, která vrací slice bajtů z vnitřního bufferu bufio.Reader. To vylučuje alokace i kopírování. Metody bufio.Reader zůstávají dostupné: ReadString, Peek, ReadByte.

var age int
var name string

ScanInt(br, &age)               // přes contestio
name, _ = br.ReadString('\n')   // standardní metoda
name = strings.TrimSpace(name)

Vysokoúrovňové ScanInt, ScanWord koexistují s nízkouúrovňovými voláními. Žádný fixní "režim skeneru" – čtěte data v libovolném pořadí.

Univerzální parser celých čísel přes generika

Pro int8, uint16, int64, uint64 slouží jediný generický _parseInt[T Int]. Kompilátor generuje specializovaný kód pro každý typ:

• Pro nepodepsané typy přeskakuje zpracování znaménka.
• Vkládá konstanty rozsahů (absMin = 1<<7 pro int8).
• Ruční smyčka parsování až 20 cifer s fallbackem na ParseUint.

func _parseInt[T Int](T, error) {
    unsigned := ^T(0) >= 0
    // zpracování znaménka, smyčka cifer, kontrola rozsahů
}

Assembler ukazuje optimalizovaný kód bez zbytečných kontrol. Univerzálnost bez ztráty výkonu.

Výstup bez alokací: scratch-buffer pro dynamická data

Pro zápis se používá bufio.Writer s připojeným polem scratch [32]byte. Pokud v hlavním bufferu není dost místa, dočasný buffer se naplní a pak se vyprázdní jedním voláním Write.

func _writeAppendFunc[T any](bw *Writer, appendVal func([]byte, T) []byte, v T) error {
    var buf []byte
    if bw.Available() < len(bw.scratch) {
        buf = bw.scratch[:0]
    } else {
        buf = bw.AvailableBuffer()
    }
    buf = appendVal(buf, v)
    _, err := bw.Write(buf)
    return err
}

Výsledek: zero-allokace při výstupu libovolných podporovaných typů.

Lehká reflexe pro any-typy

Typizované funkce ScanInt[T], ScanFloat[T], ScanWord[T] tvoří hlavní API. Pro univerzálnost slouží ScanAny(br, &product, &price) s tabulkou parserů podle reflect.Kind:

var _parseAnyTab = map[reflect.Kind]_parseAnyFunc{
    reflect.KindInt:    _parseIntToAny[int],
    reflect.KindInt8:   _parseIntToAny[int8],
    reflect.KindFloat32: _parseFloatToAny[float32],
    reflect.KindString: _parseWordToAny[string],
}

Reflexe slouží jako dispečer: určí typ argumentu a zavolá specializovaný parser. Předávejte ukazatele na opakovaně používané proměnné mimo smyčku – alokací nebude.

var x int
for i := 0; i < N; i++ {
    x = data[i]
    PrintAny(bw, op, &x)
}

Téma must: panika nebo chyby přes build tagy

Na soutěžích je vstup správný, ale kontroly jsou nutné. Místo if err != nil { panic(err) } po každém volání – privátní funkce _must.

func _scanSlice[T any](int, error) {
    return _must(_scanSliceCommon(br, parse, a))
}

V must.go (//go:build must) _must panikuje na chybách kromě io.EOF. V nomust.go vrací error. Kompilátor inlineuje potřebnou verzi.

go run -tags=must main.go   # panika
go run main.go              # chyby

Inline nástroj pro samostatná řešení

Platformy jako Codeforces zakazují externí balíčky. contestio-inline analyzuje AST, vloží pouze použité funkce z contestio do main.go.

contestio-inline main.go          # vloží
contestio-inline -clear main.go   # obnoví

Vyžaduje přesný import import . "github.com/aaa2ppp/contestio". Nástroj kontroluje kompilaci, dělá zálohu, podporuje -tags=must.

Výhody inline:

• Žádné závislosti.
• Pouze potřebný kód (graf závislostí).
• Originální kód řešení se nemění.

Benchmarky: 1M čísel, buffer 4 KB

| Metoda | Čas, ms (čtení) | Alokace | Čas, ms (výstup) | Alokace |

|--------|-----------------|---------|------------------|---------|

| fmt.Fscan/Fprint | 473 | 1 005 000 | 109 | 965 000 |

| Scanner+Atoi | 106 | 0 | - | - |

| strconv.AppendInt | - | - | 37 | 2 600 |

| contestio | 62 | 0 | 39 | 0 |

Testování: Intel Core i3-7100, Go 1.24.2, Windows.

Co je důležité

• Zero-allokace pro všechny operace čtení/zápisu přímým přístupem k bufferům.
• Generika generují optimální kód pro každý celočíselný typ.
• Scratch-buffer zajišťuje výstup bez dynamických alokací.
• Lehká reflexe jen pro dispečerizaci, ne pro serializaci.
• Build tagy must minimalizují kód pro kontroly chyb.

— Editorial Team