🔝 Retour au Sommaire
La section 12.9 a posé le principe : les flat containers stockent les données en mémoire contiguë, ce qui favorise l'utilisation du cache CPU. Mais de combien ? Dans quelles conditions ? Et y a-t-il des cas où std::map reste plus rapide ? Cette section quantifie les différences et fournit les clés pour comprendre quand le gain est réel.
📎 Pour les fondamentaux du cache CPU (niveaux L1/L2/L3, cache lines, false sharing), voir section 41.1. Cette section se concentre sur l'impact mesurable pour les flat containers.
Sur un processeur moderne typique (2026), les latences d'accès mémoire sont approximativement :
| Niveau | Latence | Rapport vs L1 |
|---|---|---|
| Registre | ~0.3 ns | — |
| Cache L1 | ~1 ns | 1× |
| Cache L2 | ~4 ns | 4× |
| Cache L3 | ~12 ns | 12× |
| RAM principale | ~60-100 ns | 60-100× |
Quand le processeur suit un pointeur vers un nœud d'arbre rouge-noir, il y a de fortes chances que ce nœud ne soit pas dans le cache L1 ni L2. Le processeur doit alors attendre 60 à 100 nanosecondes pour récupérer les données depuis la RAM — une éternité à l'échelle du CPU, qui pourrait exécuter des centaines d'instructions pendant ce temps.
Considérons une recherche dans un conteneur de 10 000 éléments. La recherche binaire nécessite environ ⌈log₂(10 000)⌉ = 14 comparaisons dans les deux cas. Mais le pattern d'accès mémoire est radicalement différent :
std::map — Traversée d'arbre :
Chaque comparaison suit un pointeur vers un nœud dispersé en mémoire.
14 comparaisons = potentiellement 14 cache misses = 14 × ~80 ns ≈ 1120 ns
std::flat_map — Recherche binaire sur vecteur :
Les premières comparaisons touchent des éléments distants (milieu, quarts),
mais les dernières sont sur des éléments voisins, déjà dans la même cache line.
14 comparaisons ≈ 4-6 cache misses + 8-10 hits L1 ≈ 330-500 ns
Cette estimation simplifiée illustre le mécanisme. En pratique, les résultats varient selon la taille des éléments, la taille du conteneur, et l'état du cache, mais l'ordre de grandeur du gain — un facteur 2× à 5× pour la recherche — est cohérent avec les benchmarks publiés.
Les processeurs modernes disposent de mécanismes de prefetching matériel : quand ils détectent un pattern d'accès séquentiel ou prédictible, ils anticipent les lectures suivantes et chargent les données dans le cache avant qu'elles ne soient demandées. La recherche binaire dans un vecteur trié bénéficie de ce prefetching, car les accès convergent vers des zones de mémoire de plus en plus proches. Les traversées d'arbre, avec leurs sauts imprévisibles d'un nœud à l'autre, ne déclenchent pas ce mécanisme.
Les flat containers ne sont pas uniformément plus rapides que std::map. Le profil de performance dépend fortement de l'opération considérée.
C'est l'opération où le gain est le plus marqué. La recherche binaire sur un vecteur trié exploite pleinement la localité mémoire :
Recherche — Temps relatif (std::map = 100%)
Taille std::map std::flat_map Gain
100 100% ~40-50% 2-2.5×
1 000 100% ~30-45% 2-3×
10 000 100% ~25-40% 2.5-4×
100 000 100% ~30-50% 2-3×
1 000 000 100% ~40-60% 1.5-2.5×
Le gain est maximal pour les tailles moyennes (quelques milliers à quelques dizaines de milliers d'éléments), où le vecteur tient entièrement dans le cache L2 ou L3. Pour les très grandes tailles, le vecteur ne tient plus dans le cache et le gain diminue, tout en restant significatif.
⚠️ Ces chiffres sont indicatifs et basés sur des benchmarks avec des clésintoustd::stringcourtes sur x86_64. Les résultats réels dépendent du hardware, du compilateur, de la taille des clés/valeurs et du contexte d'exécution. Toujours benchmarker son propre cas d'usage (section 35).
C'est le second avantage majeur. Itérer sur un std::flat_map revient à itérer sur un std::vector — un accès séquentiel optimal pour le cache et le prefetcher :
Itération complète — Temps relatif (std::map = 100%)
Taille std::map std::flat_map Gain
1 000 100% ~15-25% 4-7×
10 000 100% ~10-20% 5-10×
100 000 100% ~15-25% 4-7×
Le gain en itération est souvent le plus spectaculaire, avec des facteurs pouvant atteindre 10× pour les tailles moyennes. C'est parce que l'itération d'un arbre rouge-noir est un parcours in-order qui suit des pointeurs parent/enfant à chaque nœud, provoquant un cache miss quasi systématique, tandis que l'itération d'un vecteur est un simple parcours linéaire que le hardware optimise nativement.
C'est ici que std::flat_map paie le prix de la mémoire contiguë. Insérer un élément au milieu d'un vecteur trié nécessite de décaler tous les éléments suivants — une opération O(n) :
Insertion unitaire — Temps relatif (std::map = 100%)
Taille std::map std::flat_map Comparaison
100 100% ~80-120% ≈ comparable
1 000 100% ~150-300% 1.5-3× plus lent
10 000 100% ~500-1000% 5-10× plus lent
100 000 100% ~2000-5000% 20-50× plus lent
Pour les insertions unitaires dans un conteneur déjà peuplé, std::map est nettement plus rapide dès que la taille dépasse quelques centaines d'éléments. Le décalage mémoire (memmove) dans le vecteur domine largement le coût de l'allocation et du rééquilibrage d'un nœud d'arbre.
La suppression suit le même profil — O(n) pour les flat containers vs O(log n) pour std::map.
Le tableau s'inverse complètement quand on construit le conteneur en une seule fois à partir de données triées :
Construction depuis données triées — Temps relatif (std::map = 100%)
Taille std::map std::flat_map (sorted_unique) Gain
1 000 100% ~10-20% 5-10×
10 000 100% ~8-15% 7-12×
100 000 100% ~5-12% 8-20×
La construction sorted_unique d'un flat_map à partir de vecteurs pré-triés est une opération O(n) — un simple déplacement de mémoire. La construction d'un std::map nécessite n insertions dans l'arbre, chacune avec allocation et rééquilibrage. Le gain est massif et croît avec la taille.
Au-delà de la vitesse, les flat containers consomment significativement moins de mémoire par élément.
Chaque nœud d'un std::map contient, en plus de la paire clé-valeur, des pointeurs de maintenance (parent, enfant gauche, enfant droit) et un bit de couleur. Sur une architecture 64 bits, l'overhead typique est de 32 à 40 octets par nœud, plus le coût de l'allocation heap individuelle (header d'allocateur, alignement).
Un std::flat_map n'a aucun overhead par élément — les clés et valeurs sont stockées directement dans les vecteurs, dos à dos :
std::map<int, int> — 10 000 éléments :
Données utiles : 10 000 × 8 octets = 80 Ko
Overhead nœuds : 10 000 × ~40 octets = ~400 Ko
Overhead alloc : 10 000 × ~16 octets = ~160 Ko
Total estimé : ~640 Ko
std::flat_map<int, int> — 10 000 éléments :
vector<int> clés : 10 000 × 4 octets = 40 Ko
vector<int> valeurs : 10 000 × 4 octets = 40 Ko
Total estimé : ~80 Ko
Pour cet exemple avec des clés et valeurs int, le flat_map utilise environ 8× moins de mémoire. Le ratio varie selon la taille des types, mais le gain est toujours substantiel parce que l'overhead des nœuds d'arbre est fixe (~40 octets) quel que soit le type stocké.
La réduction de mémoire a un effet multiplicateur sur les performances : moins de mémoire utilisée signifie qu'une plus grande proportion du conteneur tient dans le cache. Un flat_map de 10 000 paires <int, int> (80 Ko) tient entièrement dans un cache L2 typique de 256 Ko, alors que le std::map équivalent (640 Ko) déborde sur le L3. Cette différence amplifie le gain en recherche et en itération.
C'est le cas d'usage idéal des flat containers. Le conteneur est construit au démarrage ou lors d'une phase d'initialisation, puis consulté intensivement sans modification :
// Phase de construction (une seule fois)
std::vector<std::pair<std::string, Config>> entries = load_from_database();
std::ranges::sort(entries, {}, &std::pair<std::string, Config>::first);
std::vector<std::string> keys;
std::vector<Config> values;
keys.reserve(entries.size());
values.reserve(entries.size());
for (auto& [k, v] : entries) {
keys.push_back(std::move(k));
values.push_back(std::move(v));
}
std::flat_map<std::string, Config> config(
std::sorted_unique, std::move(keys), std::move(values));
// Phase d'utilisation (millions de lookups)
// Chaque lookup bénéficie de la localité mémoire
auto it = config.find(key); // 2-4× plus rapide que std::mapGain attendu : 2-5× sur les recherches, 5-10× sur l'itération, 5-10× sur la construction initiale, 3-8× de réduction mémoire.
Quand les lectures et les écritures sont entremêlées, le choix dépend du ratio :
Ratio lecture/écriture Recommandation
> 90% lectures flat_map (le gain en lecture compense largement)
70-90% lectures flat_map probable, benchmarker
50-70% lectures Dépend de la taille — benchmarker
< 50% lectures std::map probablement meilleur
Si les insertions et suppressions sont fréquentes et le conteneur est grand, std::map est plus performant. Le coût O(n) des décalages dans le vecteur domine :
// Anti-pattern pour flat_map : insertions fréquentes dans un grand conteneur
std::flat_map<int, Data> fm;
for (int i = 0; i < 100'000; ++i) {
fm.insert({random_key(), data}); // Chaque insertion décale potentiellement
} // des dizaines de milliers d'élémentsDans ce cas, préférer std::map pour la phase de construction, puis éventuellement convertir en flat_map si la phase de lecture qui suit est critique :
// Stratégie hybride : construire avec map, convertir pour la lecture
std::map<int, Data> build_phase;
for (int i = 0; i < 100'000; ++i) {
build_phase.insert({random_key(), data});
}
// Conversion en flat_map pour la phase de lecture intensive
std::vector<int> keys;
std::vector<Data> values;
keys.reserve(build_phase.size());
values.reserve(build_phase.size());
for (auto& [k, v] : build_phase) {
keys.push_back(k);
values.push_back(std::move(v));
}
// Pas besoin de trier : std::map itère déjà en ordre
std::flat_map<int, Data> query_phase(
std::sorted_unique, std::move(keys), std::move(values));Pour les petits conteneurs, std::flat_map est presque toujours plus rapide que std::map, y compris pour les insertions. La raison : l'overhead d'allocation d'un nœud d'arbre (appel à operator new, gestion du heap) est plus coûteux que le décalage de quelques dizaines d'éléments dans un vecteur déjà en cache L1 :
// Pour les petits conteneurs, flat_map gagne sur toutes les opérations
std::flat_map<std::string, int> small_config; // < 50 éléments
// Insertion, recherche, itération : tout est plus rapide qu'avec std::mapCe cas couvre de nombreuses situations réelles : options de configuration, tables de correspondance, registres de handlers, petits dictionnaires.
Il est important de ne pas confondre std::flat_map avec std::unordered_map. Les deux sont plus rapides que std::map pour la recherche, mais pour des raisons différentes et avec des compromis différents :
| Critère | std::flat_map |
std::unordered_map |
|---|---|---|
| Recherche | O(log n) — binaire | O(1) amorti — hash |
| Ordre | Trié | Non ordonné |
| Itération ordonnée | Oui, native | Non |
| Mémoire | Compacte | Plus élevée (buckets) |
| Cache-friendliness | Excellente | Variable |
| Pire cas recherche | O(log n) | O(n) — collisions |
| Lookup sur petits N | Très rapide | Overhead du hash |
Pour de la pure recherche par clé sur de grands conteneurs sans besoin d'ordre, std::unordered_map avec un bon hash reste le plus rapide en moyenne. std::flat_map est le choix quand l'ordre est nécessaire, quand la mémoire est contrainte, ou quand l'itération séquentielle ordonnée est fréquente.
┌───────────────────────────────────────────────────────────────────┐
│ std::flat_map vs std::map — Synthèse │
├───────────────────────┬───────────────────────────────────────────┤
│ Recherche (find) │ 2-4× plus rapide (flat_map gagne) │
│ Itération complète │ 4-10× plus rapide (flat_map gagne) │
│ Construction batch │ 5-20× plus rapide (flat_map gagne) │
│ Insertion unitaire │ 2-50× plus lent selon N (map gagne) │
│ Suppression unitaire │ 2-50× plus lent selon N (map gagne) │
│ Consommation mémoire │ 3-8× moins (flat_map gagne) │
│ Petits conteneurs │ Plus rapide partout (flat_map gagne) │
└───────────────────────┴───────────────────────────────────────────┘
Le message clé : si le profil d'usage est « construire puis consulter » — ce qui est le cas de la majorité des conteneurs associatifs dans le code réel — std::flat_map est supérieur sur tous les axes qui comptent. Le seul domaine où std::map reste indispensable est la modification fréquente de grands conteneurs, et les cas où la stabilité des itérateurs est une exigence.