Pourquoi chaque octet compte en performance

Le hardware parle plus fort que l'algorithme

Depuis des années, on te dit que O(N) c'est O(N) : si ta boucle est linéaire, c'est linéaire. Faux.

Deux boucles apparemment identiques peuvent avoir des latences complètement différentes selon comment les données sont arrangées en mémoire et comment le CPU les charge.

Comment ça marche : les lignes de cache

Quand tu lis un octet, le CPU ne charge pas juste cet octet — il attrape 64 octets (ta ligne de cache) et les cale en cache L1. C'est une optimisation : les données qu'on accède sont généralement proches les unes des autres en mémoire.

Voilà les hiérarchies réelles :

• ▸Cache L1d : ~35 Kio/cœur, ~4-5 cycles, ~1-2 ns (35 Kio ÷ 64 o = ~560 lignes de cache)
• ▸Cache L2 : ~2 Mio/paire, ~12-15 cycles, ~4-5 ns
• ▸Cache L3 : 12 Mio partagé, ~30-40 cycles, ~10-15 ns
• ▸DRAM : mémoire principale, ~100-200 cycles, ~60-100 ns

Quand ta structure ne rentre plus en L1, tu tombes 4 à 10 fois plus lent. C'est violent.

Le cas concret : Array of Structs vs Struct of Arrays

Imagine une liste de 4096 monstres de jeu, chacun avec des stats (id, position xyz, vitesse xyz, hp, attaque, défense, vivant, équipe, nom).

Disposition classique (AoS) :

struct Monster {
  uint32_t id;        // 4 octets
  float x, y, z;      // 12 octets
  // ... autres champs
  uint8_t is_alive;   // 1 octet ← c'est le seul qu'on veut
};
// Total : 64 octets

Quand tu itères pour filtrer les vivants, tu charges 64 octets entiers par monstre. La ligne de cache contient UNE SEULE structure.

Disposition optimisée (SoA) :

struct Monsters {
  uint32_t *ids;
  float *xs, *ys, *zs;
  uint8_t *is_alives;  // 4096 octets de suite
};

Là, une seule ligne de cache (64 octets) contient 64 statuts de monstres différents. Tu en charges 64 d'un coup.

Résultat ? Jusqu'à 30x plus rapide avec la bonne structure pour le bon schéma d'accès.

Accès aléatoire : quand la taille totale devient le goulot

C'est pire avec les graphes, tables de hachage, ou le pointer-chasing (vraiment aléatoire). Le CPU ne peut pas prédire où tu vas aller — il faut que tout soit en cache pour ne pas caler.

Regarde les latences réelles mesurées :

Doubler de 64 o à 128 o, c'est doubler ton empreinte mémoire. À 512 éléments, tu passes du L1 (3 ns) au L2 (11 ns). À 32k, c'est +50% de latence.

Donc ?

Aujourd'hui, beaucoup de devs ignorent où vivent leurs données. En Java tu ajoutes un champ, tu t'en fous. Mais sur du traitement en masse (ML, gaming, data processing), c'est ton deuxième goulot après l'algorithme.

Avant d'ajouter un truc à ta structure :

• ▸Demande-toi si c'est vraiment nécessaire
• ▸Mesure ton empreinte totale avec lscpu
• ▸Si tu fais de l'accès aléatoire, compte les mégaoctets
• ▸Envisage SoA pour le chemin critique

Chaque octet compte.