Zero-allocation IO dla konkursów Go

Zero-allokacyjny I/O dla konkursów Go: sześć inżynieryjnych rozwiązań

Programiści Go na konkursach często napotykają ograniczenia standardowych narzędzi do wejścia-wyjścia. fmt.Fscan alokuje pamięć przy każdym wywołaniu, bufio.Scanner jest sztywno powiązany z trybem skanowania, a ręczne parsowanie przez bufio.Reader wymaga boilerplate'u. Biblioteka contestio rozwiązuje te problemy, pracując bezpośrednio z wewnętrznym buforem bufio.Reader i zapewniając zero-allokacji dla wszystkich operacji.

Sześć kluczowych rozwiązań pozwala łączyć szybkość ręcznego parsowania, wygodę fmt i elastyczność bufio. Obsługiwane są mieszane typy wejścia: liczby, ciągi, parsowanie znak po znaku — bez przełączania trybów.

Praca bezpośrednio z buforem: _nextToken bez kopiowania

Główne podejście to funkcja _nextToken, zwracająca wycinek bajtów z wewnętrznego bufora bufio.Reader. To eliminuje alokacje i kopiowanie. Metody bufio.Reader pozostają dostępne: ReadString, Peek, ReadByte.

var age int
var name string

ScanInt(br, &age)               // przez contestio
name, _ = br.ReadString('\n')   // standardowa metoda
name = strings.TrimSpace(name)

Wysokopoziomowe ScanInt, ScanWord współistnieją z niskopoziomowymi wywołaniami. Nie ma sztywnego „trybu skanera” — czytaj dane w dowolnej kolejności.

Uniwersalny parser liczb całkowitych przez generyki

Dla int8, uint16, int64, uint64 używana jest jedna generyczna funkcja _parseInt[T Int]. Kompilator generuje wyspecjalizowany kod dla każdego typu:

• Dla typów bez znaku pomija obsługę znaku.
• Wbudowuje stałe zakresów (absMin = 1<<7 dla int8).
• Ręczna pętla parsowania do 20 cyfr z fallbackiem na ParseUint.

func _parseIntT Int (T, error) {
    unsigned := ^T(0) >= 0
    // obsługa znaku, pętla cyfr, sprawdzenie zakresów
}

Asembler pokazuje zoptymalizowany kod bez zbędnych sprawdzeń. Uniwersalność bez utraty wydajności.

Wyjście bez alokacji: bufor scratch dla danych dynamicznych

Do zapisu używany jest bufio.Writer z dołączonym tablicowym buforem scratch [32]byte. Jeśli w głównym buforze brakuje miejsca, tymczasowy bufor jest wypełniany, a następnie opróżniany jednym wywołaniem 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
}

Rezultat: zero-allokacja przy wyjściu dowolnych obsługiwanych typów.

Lekka refleksja dla typów any

Typizowane funkcje ScanInt[T], ScanFloat[T], ScanWord[T] to główny API. Dla uniwersalności istnieje ScanAny(br, &product, &price) z tablicą parserów według reflect.Kind:

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

Refleksja działa jako dyspozytor: określa typ argumentu i wywołuje wyspecjalizowany parser. Przekazuj wskaźniki na wielokrotnego użytku zmienne poza pętlą — alokacji nie będzie.

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

Tag must: panika lub błędy przez build tags

Na konkursach wejście jest poprawne, ale sprawdzenia są potrzebne. Zamiast if err != nil { panic(err) } po każdym wywołaniu — prywatne funkcje _must.

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

W must.go (//go:build must) _must panikuje na błędach poza io.EOF. W nomust.go zwraca error. Kompilator inlinuje odpowiednią wersję.

go run -tags=must main.go   # panika
go run main.go              # błędy

Inline-utilita dla samodzielnych rozwiązań

Platformy jak Codeforces zabraniają zewnętrznych pakietów. contestio-inline analizuje AST, wbudowując tylko używane funkcje z contestio do main.go.

contestio-inline main.go          # wbudowuje
contestio-inline -clear main.go   # przywraca

Wymaga punktowego importu import . "github.com/aaa2ppp/contestio". Narzędzie sprawdza kompilację, robi backup, obsługuje -tags=must.

Zalety inline:

• Brak zależności.
• Tylko potrzebny kod (graf zależności).
• Oryginalny kod rozwiązania nie ulega zmianie.

Benchmarki: 1M liczb, bufor 4 KB

| Metoda | Czas, ms (czytanie) | Alokacje | Czas, ms (wyjście) | Alokacje |

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

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

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

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

| contestio | 62 | 0 | 39 | 0 |

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

Co ważne

• Zero-allokacja dla wszystkich operacji czytania/zapisu przez bezpośredni dostęp do buforów.
• Generyki generują optymalny kod dla każdego typu liczb całkowitych.
• Bufor scratch zapewnia wyjście bez dynamicznych alokacji.
• Lekka refleksja tylko do dyspozytoryzacji, nie do serializacji.
• Build tags must minimalizują boilerplate dla sprawdzeń błędów.

— Editorial Team