Data-Oriented Design : arrêter de penser en objets
Le DOP n'est pas un paradigme de plus — c'est un changement de perspective sur ce que le code manipule vraiment. On part d'une liste de participants pour finir dans les entrailles d'un KV store.
On organise un concert. Cinquante mille inscrits. Certains ont droit à une entrée gratuite — ils doivent fournir un justificatif, un document administratif un peu lourd. On doit savoir qui est une femme, qui est un homme, qui a fourni son justificatif.
On code ce qu’on voit.
struct Justificatif {
path: String, // chemin vers le scan
contenu: Vec<u8>, // données brutes
metadonnees: String,
depose_le: u64,
valide: bool,
}
// ~120 octets
struct Participant {
nom: String, // 24 octets
sexe: Sexe, // 1 octet + padding
justificatif: Option<Justificatif>, // ~128 octets
}
// ~160 octets par participant
let inscrits: Vec<Participant> = vec![...];Lisible. Naturel. Et ça marche très bien — jusqu’au moment où on veut faire quelque chose de simple : compter les femmes qui ont fourni un justificatif.
let count = inscrits.iter()
.filter(|p| p.sexe == Sexe::Femme && p.justificatif.is_some())
.count();Pour 50 000 inscrits, cette struct occupe ~8,0 Mo en RAM — et la totalité doit être parcourue pour lire deux champs. Le justificatif de ceux qui n’en ont pas — une Option::None de 128 octets — pèse autant que celui de ceux qui en ont un.
Déporter ce qu’on ne stocke pas toujours
La première observation : le justificatif est lourd, mais 70 % des inscrits n’en ont pas. On le charge pourtant à chaque itération.
La solution : le sortir du struct et le stocker séparément. Chaque participant porte à sa place un simple index — ou rien.
struct Participant {
nom: String,
sexe: Sexe,
idx_justif: Option<u32>, // 8 octets
}
struct Inscrits {
participants: Vec<Participant>,
justificatifs: Vec<Justificatif>, // seulement ceux qui existent
}Le même comptage :
let count = inscrits.participants.iter()
.filter(|p| p.sexe == Sexe::Femme && p.idx_justif.is_some())
.count();Pour accéder à un justificatif précis :
if let Some(i) = inscrits.participants[n].idx_justif {
let j = &inscrits.justificatifs[i as usize];
}Empreinte pour le scan sur 50 000 inscrits :
Struct naïve — layout de Participant :
| Champ | Taille |
|---|---|
nom: String | 24 o |
sexe: Sexe + padding | 8 o |
justificatif: Option<Justificatif> | ~128 o |
| Total par entrée | ~160 o |
| 50 000 inscrits | ~8,0 Mo — justificatifs absents inclus |
Après déportation — layout de Participant :
| Champ | Taille |
|---|---|
nom: String | 24 o |
sexe: Sexe + padding | 8 o |
idx_justif: Option<u32> | 8 o |
| Total par entrée | ~40 o |
| 50 000 inscrits | ~1,9 Mo — parcouru à chaque scan |
Vec<Justificatif> | variable — accédé sur demande uniquement |
| Structure | RAM totale | RAM scan seul | Économie |
|---|---|---|---|
| Struct naïve | — | — | — |
| Après déportation | — | — | — |
Option<u32> pèse 8 octets : u32 n’a pas de valeur invalide exploitable, Rust ne peut pas appliquer la niche optimization et ajoute un discriminant avec son padding.
Le vrai coût de la déportation
Cette technique n’est pas gratuite. Quand on accède au justificatif, on fait deux accès mémoire : d’abord l’index, puis le slab. C’est une indirection en plus par rapport au stockage inline.
Le gain se réalise quand une minorité possède l’objet lourd, mais qu’on scanne tout le monde. Si 20 % des inscrits ont un justificatif et qu’on fait des dizaines de scans par seconde, on évite de charger en cache 80 % × 120 octets à chaque fois. Si au contraire tout le monde a un justificatif et qu’on y accède systématiquement, le stockage inline est plus efficace.
La règle : plus le taux de possession est bas et les scans fréquents, plus la déportation est rentable.
Éliminer le padding
La déportation règle le problème du justificatif. Mais sexe pose un problème différent, sans rapport : c’est un champ d’un octet noyé dans un struct de 40.
Rust (avec son repr par défaut) réordonne les champs pour minimiser le padding interne — il place nom (align 8), puis idx_justif (align 4), puis sexe (align 1), avec 7 octets de padding en queue pour que la taille totale soit un multiple de l’alignement du struct. Le résultat est le même qu’avec un layout naïf : 40 octets, dont 7 inutiles. Avec repr(C) et les champs dans l’ordre de déclaration, ce padding se retrouverait entre sexe et idx_justif — même gaspillage, autre emplacement.
struct Participant (repr Rust, layout optimisé)
nom : 24 o (align 8)
idx_justif : 8 o (align 4)
sexe : 1 o (align 1)
padding : 7 o ← queue, pour aligner la taille sur 8
= 40 o par entréePour 50 000 inscrits, ces 7 octets représentent 350 Ko qui ne contiennent rien. Et quand on parcourt le Vec<Participant> pour lire uniquement sexe, on charge 40 octets par entrée pour en lire 1.
La solution : sortir sexe dans son propre tableau. Le padding disparaît avec lui — un Vec<Sexe> ne contient que des octets utiles.
C’est là qu’on introduit repr(u8) : sans lui, Rust choisit seul la représentation de l’enum. Avec, on contrôle — un octet, pas plus.
#[repr(u8)]
enum Sexe { Homme = 0, Femme = 1 }
struct Inscrits {
noms: Vec<Rc<str>>, // 16 octets par entrée
sexes: Vec<Sexe>, // 1 octet par entrée — dense
idx_justif: Vec<Option<u32>>, // 8 octets par entrée
justificatifs: Vec<Justificatif>,
}Rc<str> au lieu de String : 16 octets au lieu de 24, sans champ capacity, partageable sans copie. Mais ça, c’est une autre histoire.
Un tableau de Sexe, c’est 1 octet par personne. Une cache line de 64 octets couvre 64 participants. C’est l’aboutissement naturel du DOP sur ce problème : chaque champ vit dans sa propre densité, optimisé pour son propre pattern d’accès.
Ouverture : dépenser ce qu’on a économisé
La progression DOP se termine là. Mais elle ouvre une porte : on est passé de 8,0 Mo à ~3,5 Mo. Cette mémoire libérée, on peut choisir de la dépenser pour obtenir quelque chose de différent.
Si le pattern d’accès dominant bascule vers des lookups par nom plutôt que des scans, on peut construire une HashMap par-dessus la structure existante — et se permettre son overhead parce que le DOP l’a rendu abordable.
struct Inscrits {
hommes: HashMap<Rc<str>, Option<u32>>,
femmes: HashMap<Rc<str>, Option<u32>>,
justificatifs: Vec<Justificatif>,
}Ce n’est plus du DOP — une HashMap éparpille les données en mémoire via du hashing, à l’opposé de la localité spatiale recherchée jusqu’ici. C’est un changement d’algorithme : on échange la densité d’itération contre des lookups O(1) et un comptage O(1) par sexe (femmes.len()).
hashbrown (l’implémentation Rust) alloue ~57 000 slots pour 50 000 entrées (facteur de charge 87,5 %). Chaque slot pèse 25 o. Deux maps : ~2,9 Mo. On repasse à ~4,7 Mo — plus que la version DOP pure, mais toujours loin des 8,0 Mo du départ.
Le point : le DOP avait rendu cette HashMap finançable. Sans la déportation préalable, une HashMap<Rc<str>, Option<Justificatif>> aurait été beaucoup plus lourde. C’est souvent comme ça que ça se passe — on économise d’un côté pour pouvoir dépenser de l’autre.
Ce que ça révèle
| Version | RAM totale (30 % avec justif) | RAM parcourue pour compter les femmes |
|---|---|---|
| Struct naïve | ~8,0 Mo | ~8,0 Mo |
| Après déportation | ~3,8 Mo | ~2,0 Mo (Vec<Participant>) |
+ Vec<Sexe> séparé | ~3,5 Mo | ~50 Ko (Vec<Sexe> seul) |
HashMap par sexe* | ~4,7 Mo | O(1) lookup par nom |
*pas du DOP — changement d’algorithme financé par les économies précédentes
Chaque étape optimise quelque chose de différent. La déportation réduit la RAM totale. La séparation élimine le padding et réduit la RAM parcourue. La HashMap repart à la hausse en mémoire, mais achète des lookups O(1) — elle n’est abordable que parce que le DOP l’a précédée.
Ce que cette progression fait apparaître : représenter une donnée et la caractériser sont deux besoins distincts qu’on mélange naturellement dans un struct naïf. Le justificatif est une représentation — un document lourd, accédé rarement. Le sexe est une caractérisation — un discriminant d’un bit, consulté à chaque opération. Les séparer permet de les optimiser indépendamment, et d’adapter la structure de données au pattern d’accès dominant plutôt qu’à la modélisation du monde réel.
En production : radixox
Radixox est un KV store Redis-compatible que j’ai écrit en Rust, basé sur un Adaptive Radix Tree. Chaque lookup traverse plusieurs nœuds — la taille d’un Node a un impact direct sur le nombre de cache fetches par opération. L’objectif : un nœud = une cache line = 64 octets.
Le budget de départ et ses contraintes
La version initiale utilisait une Value enum dont tous les variants tenaient en 32 octets :
// Option<Value> est free : niche optimization sur le discriminant de l'enum.
// All variants ≤ 32 bytes → no Box, no indirection.
pub enum Value {
String(SharedByte),
Int(i64), // 8 o
Hash(InnerHCommand), // ≤ 32 o
List(VecDeque<SharedByte>), // 32 o
Set(BTreeSet<SharedByte>), // ≤ 32 o
ZSet(InnerZCommand), // Small=Vec 24 o | Large=Box 8 o
}InnerZCommand illustre l’astuce pour tenir dans 32 octets : un sorted set petit tient inline (représentation Vec, 24 o), un grand bascule sur un Box de 8 o. L’enum reste à 32 octets dans les deux cas.
Option<Value> est free grâce à la niche optimization : l’enum expose une valeur bit-invalide utilisée comme sentinelle None sans octet supplémentaire.
Mais cette contrainte tient mal à l’échelle. BTreeMap et BTreeSet font 48 octets — les garder inline force des représentations intermédiaires de plus en plus complexes. Et Option<Value> à 32 octets gonfle tous les nœuds, y compris les nœuds intermédiaires sans valeur qui sont la majorité dans un radix tree profond.
Déporter la valeur : Tag + ValUnion + slabs
#[repr(u8)]
pub(crate) enum Tag {
None = 0, Int = 1, Bytes = 2,
Hash = 3, Set = 4, ZSet = 5, List = 6,
}
pub(crate) union ValUnion {
pub(crate) integer: i64,
pub(crate) bytes: ManuallyDrop<SharedByte>,
pub(crate) idx: u32,
}
// Radixox est entièrement single-thread : seul le thread principal existe.
// Les static mut sont unsafe (aliasing potentiel), mais sans risque de data race ici.
static mut HASH_SLAB: MaybeUninit<HiSlab<InnerHCommand>> = MaybeUninit::uninit();
static mut SET_SLAB: MaybeUninit<HiSlab<BTreeSet<SharedByte>>> = MaybeUninit::uninit();
static mut ZSET_SLAB: MaybeUninit<HiSlab<InnerZCommand>> = MaybeUninit::uninit();
static mut LIST_SLAB: MaybeUninit<HiSlab<VecDeque<SharedByte>>> = MaybeUninit::uninit();Tag (1 o) + ValUnion (8 o) = 9 octets par nœud au lieu de 32. Sur un million de clés, c’est 23 Mo économisés rien qu’en réduisant ce champ. Pour les types lourds, ValUnion stocke un u32 vers le slab typé — lors d’un scan, BTreeSet et VecDeque ne sont jamais touchés.
Les slabs donnent aussi la localité par type : toutes les valeurs Hash sont contiguës en mémoire. Une opération sur les hashes traverse un slab dense, pas du heap éparpillé.
Comprimer ce qui reste : niches et bit-packing
La déportation de la valeur libère de la place dans le Node, mais d’autres champs peuvent encore être comprimés.
CompactStr stocke les préfixes de compression des nœuds. Via une niche d’alignement — les bits de poids faible d’un pointeur aligné sont toujours zéro, et peuvent encoder des métadonnées — la représentation passe de 16 octets à 8 octets, tout en gardant 7 octets de stockage inline.
ExpAndRadix compresse deux champs en un seul u64 via une niche de valeur :
#[repr(transparent)]
struct ExpAndRadix { inner: u64 }
// Layout du u64 :
// [ 8 bits : parent_radix ][ 56 bits : timestamp d'expiration ]
//
// Niche : 0x00FFFFFFFFFFFFFF = "pas d'expiration"
// (tous les 56 bits à 1 — valeur jamais atteinte par un timestamp réel)
const NO_EXPIRACY: u64 = 0x00FFFFFFFFFFFFFF;Sans ce packing, ces deux champs auraient coûté : Option<u64> (16 o) + u8 (1 o) + padding (7 o) = 24 octets. Comprimés en un u64, ils en coûtent 8. La niche du timestamp (0x00FFFFFFFFFFFFFF ne sera jamais un timestamp Unix valide) joue le même rôle que la niche d’alignement de CompactStr : une valeur bit-invalide dans le contexte métier, recyclée comme sentinelle.
Le résultat : 64 octets, une cache line
Au prix de 10 → 6 enfants inline (légère perte de localité sur les nœuds larges), le Node tient maintenant en 64 octets avec align(64). Chaque traversée de l’arbre coûte exactement un fetch de cache line par nœud — deux fois moins que la version initiale à 128 octets. Pour les nœuds intermédiaires sans valeur, qui sont la majorité dans un radix tree profond, c’est la différence entre un nœud qui tient dans un seul slot de cache L1 et un qui en occupe deux.
Tag caractérise. ValUnion représente. ExpAndRadix compresse. Chaque octet du Node a une raison d’être.
Quand l’appliquer — et quand s’en abstenir
Le DOP n’est pas une discipline universelle. C’est une réponse à un problème précis : un pattern d’accès dominant qui se heurte à la structure des données.
Il est pertinent quand on itère souvent, sur beaucoup d’entrées, en ne lisant qu’une fraction des champs. Un scan d’expiration sur un million de clés, un filtre par sexe sur cinquante mille participants, un DBSIZE sur un store qui contient toutes sortes de types — dans ces cas, payer le prix de l’objet complet à chaque itération est un gaspillage mesurable.
Il est pertinent quand une minorité possède quelque chose de lourd. Si 5 % des entrées ont un justificatif de 120 octets, les stocker inline fait payer les 95 % restants pour une absence. La déportation rend le coût proportionnel à la présence réelle, pas à la possibilité.
Il devient moins utile — voire contre-productif — quand les accès sont ponctuels et par identifiant. Si on ne fait jamais de scans, si chaque opération porte sur un seul enregistrement accédé par clé, la densité des tableaux ne rapporte rien. Le surcoût en complexité du code n’est plus justifié.
Et il a un coût réel sur la lisibilité. Des tableaux parallèles sont moins évidents à maintenir qu’un struct : les invariants ne sont plus garantis par le type, ils reposent sur la discipline du code. Le bit-packing de ExpAndRadix est une bombe à retardement si on ne comprend pas la contrainte qui l’a produit. Ce n’est pas du code qu’on écrit d’emblée — c’est du code qu’on arrive à après avoir mesuré, après avoir compris où se concentre la pression.
La question à se poser avant de restructurer : quelles données est-ce que j’accède ensemble, et à quelle fréquence ? Si la réponse est “tout, rarement”, un struct naïf est juste. Si la réponse est “une fraction, en permanence”, la séparation a du sens.
Le DOP ne modélise pas le monde — il modélise les accès. C’est une discipline différente, moins naturelle, mais qui fait la différence quand le volume et la fréquence ne laissent plus de marge.