IO sans allocation pour les concours Go

I/O sans allocation pour les concours Go : six solutions ingénieuses

Les développeurs Go en programmation compétitive butent souvent sur les limites des outils I/O standards. fmt.Fscan alloue de la mémoire à chaque appel, bufio.Scanner est figé en mode scan, et le parsing manuel avec bufio.Reader impose d’écrire des tonnes de code répétitif. La bibliothèque contestio résout cela en travaillant directement avec le buffer interne de bufio.Reader, offrant un zéro allocation pour toutes les opérations.

Six solutions clés allient la vitesse du parsing manuel, la simplicité de fmt et la flexibilité de bufio. Elle gère les entrées mixtes — nombres, chaînes, même parsing caractère par caractère — sans basculer de mode.

Accès direct au buffer : _nextToken sans copie

L’astuce principale est la fonction _nextToken, qui renvoie une tranche d’octets du buffer interne de bufio.Reader. Pas d’allocation ni de copie. Vous pouvez toujours utiliser les méthodes de bufio.Reader comme ReadString, Peek et ReadByte.

var age int
var name string

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

Les fonctions de haut niveau ScanInt et ScanWord s’accordent parfaitement avec les appels de bas niveau. Pas de mode « scanner » rigide — lisez les données dans l’ordre qui vous convient.

Parseur universel d’entiers avec generics

Une seule fonction générique _parseInt[T Int] gère int8, uint16, int64, uint64. Le compilateur génère du code spécialisé pour chaque type :

• Ignore la gestion du signe pour les types non signés.
• Intègre les constantes de plage (absMin = 1<<7 pour int8).
• Boucle sur les chiffres personnalisée jusqu’à 20 chiffres, avec repli sur ParseUint.

func _parseIntT Int (T, error) {
    unsigned := ^T(0) >= 0
    // gestion du signe, boucle sur chiffres, vérifs de plage
}

L’assembleur montre un code compact et optimisé, sans vérifications superflues. Polyvalence sans perte de performance.

Sortie sans allocation : buffer temporaire pour données dynamiques

Pour l’écriture, elle utilise bufio.Writer avec un tableau scratch [32]byte attaché. Si le buffer principal est trop plein, elle remplit le buffer temporaire et flush avec un seul 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
}

Résultat : sortie sans allocation pour n’importe quel type supporté.

Réflexion légère pour tous les types

Les fonctions typées comme ScanInt[T], ScanFloat[T], ScanWord[T] forment l’API principale. Pour la flexibilité, ScanAny(br, &product, &price) utilise un tableau de parseurs par reflect.Kind :

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

La réflexion ne fait que dispatcher : elle vérifie le type de l’argument et appelle le bon parseur. Passez des pointeurs sur des variables réutilisables hors boucle — pas d’allocation.

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

Tags « must » : panic ou erreurs via tags de build

Les entrées de concours sont généralement propres, mais les vérifications sont indispensables. Oubliez if err != nil { panic(err) } après chaque appel — utilisez des fonctions privées _must.

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

Dans must.go (//go:build must), _must provoque un panic sur les erreurs sauf io.EOF. Dans nomust.go, elle renvoie error. Le compilateur intègre la bonne version.

go run -tags=must main.go   # panique
go run main.go              # erreurs

Utilitaire inline pour solutions autonomes

Les plateformes comme Codeforces interdisent les paquets externes. contestio-inline analyse l’AST et intègre uniquement les fonctions contestio utilisées dans main.go.

contestio-inline main.go          # intègre
contestio-inline -clear main.go   # restaure

Nécessite un import précis import . "github.com/aaa2ppp/contestio". L’outil vérifie la compilation, sauvegarde les fichiers et supporte -tags=must.

Avantages de l’inline :

• Aucune dépendance.
• Seul le code nécessaire (graphe de dépendances).
• Votre code de solution reste intact.

Benchmarks : 1M nombres, buffer 4KB

| Méthode | Temps lecture, ms | Allocations | Temps écriture, ms | Allocations |

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

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

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

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

| contestio | 62 | 0 | 39 | 0 |

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

Points clés

• Lecture/écriture sans allocation via accès direct au buffer.
• Les generics génèrent un code optimal par type d’entier.
• Buffer temporaire pour une sortie sans allocation.
• Réflexion uniquement pour le dispatch, pas la sérialisation.
• Tags must réduisent le code de vérification d’erreurs.

— Editorial Team