Null-Allokations-IO für Go-Wettbewerbe

Zero-Allocation I/O für Go-Wettbewerbe: Sechs Ingenieurlösungen

Go-Entwickler im Wettbewerbsprogrammieren stoßen oft an Grenzen der Standard-I/O-Tools. fmt.Fscan allokiert bei jedem Aufruf Speicher, bufio.Scanner ist auf Scan-Modus festgelegt, und manuelles Parsen mit bufio.Reader erfordert massenhaft Boilerplate-Code. Die contestio-Bibliothek löst das, indem sie direkt mit dem internen Buffer von bufio.Reader arbeitet und für alle Operationen Zero-Allocation liefert.

Sechs zentrale Lösungen verbinden die Geschwindigkeit des manuellen Parsens, die Einfachheit von fmt und die Flexibilität von bufio. Sie verarbeitet gemischte Eingabetypen – Zahlen, Strings, sogar Zeichen-für-Zeichen-Parsing – ohne Moduswechsel.

Direkter Buffer-Zugriff: _nextToken ohne Kopieren

Der Kerntrick ist die _nextToken-Funktion, die einen Byte-Slice direkt aus dem internen Buffer von bufio.Reader zurückgibt. Keine Allokationen oder Kopien. Du kannst weiterhin bufio.Reader-Methoden wie ReadString, Peek und ReadByte nutzen.

var age int
var name string

ScanInt(br, &age)               // via contestio
name, _ = br.ReadString('\n')   // Standardmethode
name = strings.TrimSpace(name)

Hochwertige Funktionen wie ScanInt und ScanWord harmonieren mit Low-Level-Aufrufen. Kein starrer „Scanner-Modus“ – lies Daten in beliebiger Reihenfolge.

Universeller Integer-Parser mit Generics

Eine generische _parseInt[T Int]-Funktion behandelt int8, uint16, int64, uint64. Der Compiler erzeugt spezialisierte Maschinencode für jeden Typ:

• Überspringt Vorzeichenbehandlung bei unsigned Typen.
• Bettet Bereichskonstanten ein (absMin = 1<<7 für int8).
• Eigene Ziffern-Schleife bis 20 Stellen, mit Fallback auf ParseUint.

func _parseIntT Int (T, error) {
    unsigned := ^T(0) >= 0
    // Vorzeichenbehandlung, Ziffern-Schleife, Bereichsprüfungen
}

Der Assembler zeigt straffen, optimierten Code ohne unnötige Prüfungen. Vielseitigkeit ohne Leistungseinbußen.

Zero-Allocation-Ausgabe: Scratch-Buffer für dynamische Daten

Zum Schreiben nutzt sie bufio.Writer mit angehängtem scratch [32]byte-Array. Ist der Hauptbuffer zu voll, füllt sie den Scratch-Buffer und spült mit einem einzigen Write.

func _writeAppendFunc(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
}

Ergebnis: Zero-Allocation-Ausgabe für alle unterstützten Typen.

Leichtgewichtige Reflexion für beliebige Typen

Typisierte Funktionen wie ScanInt[T], ScanFloat[T], ScanWord[T] bilden die Haupt-API. Für Flexibilität verwendet ScanAny(br, &product, &price) eine Parser-Tabelle nach reflect.Kind:

var _parseAnyTab = []_parseAnyFunc{
    reflect.Int:     _parseIntToAny[int],
    reflect.Int8:    _parseIntToAny[int8],
    reflect.Float32: _parseFloatToAny[float32],
    reflect.String:  _parseWordToAny[string],
}

Reflexion dient nur dem Dispatch: Sie prüft den Argumenttyp und ruft den passenden Parser auf. Übergebe Pointer auf wiederverwendbare Variablen außerhalb von Schleifen – keine Allokationen.

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

Must-Tags: Panic oder Errors via Build-Tags

Wettbewerbseingaben sind meist sauber, aber Prüfungen sind essenziell. Spar dir if err != nil { panic(err) } nach jedem Aufruf – nutze private _must-Funktionen.

func _scanSliceT any (int, error) {
    return _must(_scanSliceCommon(br, parse, a))
}

In must.go (//go:build must) panict _must bei Fehlern außer io.EOF. In nomust.go gibt es error zurück. Der Compiler inlinet die richtige Version.

go run -tags=must main.go   # panict
go run main.go              # Errors

Inline-Utility für eigenständige Lösungen

Plattformen wie Codeforces verbieten externe Pakete. contestio-inline analysiert den AST und einbettet nur die genutzten contestio-Funktionen in main.go.

contestio-inline main.go          # einbetten
contestio-inline -clear main.go   # wiederherstellen

Erfordert einen präzisen Import import . "github.com/aaa2ppp/contestio". Das Tool prüft die Kompilierung, sichert Dateien und unterstützt -tags=must.

Vorteile von Inline:

• Keine Abhängigkeiten.
• Nur benötigter Code (Abhängigkeitsgraph).
• Dein Lösungscode bleibt unberührt.

Benchmarks: 1 Mio. Zahlen, 4-KB-Buffer

| Methode | Lesezeit, ms | Allokationen | Schreibzeit, ms | Allokationen |

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

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

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

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

| contestio | 62 | 0 | 39 | 0 |

Testumgebung: Intel Core i3-7100, Go 1.24.2, Windows.

Wichtige Erkenntnisse

• Zero-Allocation Lesen/Schreiben durch direkten Buffer-Zugriff.
• Generics erzeugen optimalen Code pro Integer-Typ.
• Scratch-Buffer ermöglicht allokationsfreie Ausgabe.
• Reflexion nur für Dispatch, nicht für Serialisierung.
• must-Build-Tags reduzieren Error-Checking-Boilerplate.

— Editorial Team