🔝 Retour au Sommaire
Chapitre 41 : Optimisation CPU et Mémoire · Section 6
Niveau : Expert · Prérequis : Sections 41.1.1–41.1.3 (hiérarchie cache, cache lines, DOD), Section 14.4 (APIstd::flat_map/std::flat_set)
📎 Cette section se concentre sur l'analyse de performance et les benchmarks comparatifs dans un contexte d'optimisation cache. Pour la présentation de l'API, la sémantique et les cas d'usage généraux de
std::flat_mapetstd::flat_set, voir section 14.4.
Les sections précédentes de ce chapitre ont établi un principe central : la contiguïté mémoire domine la performance sur les processeurs modernes. Le cache récompense les accès séquentiels à des données compactes et pénalise lourdement les indirections vers des nœuds dispersés dans le heap.
Ce principe s'applique directement aux conteneurs associatifs de la STL. Les conteneurs classiques — std::map, std::set, std::multimap, std::multiset — sont implémentés comme des arbres rouge-noir : chaque élément est un nœud alloué individuellement sur le heap, relié à ses voisins par des pointeurs. Cette structure est algorithmiquement élégante (O(log n) garanti pour toutes les opérations), mais elle est un cauchemar pour le cache.
C++23 introduit std::flat_map et std::flat_set (ainsi que leurs variantes multi), des conteneurs associatifs ordonnés qui stockent leurs éléments dans des tableaux contigus triés. Le changement est purement structurel — l'interface est quasi identique à celle de std::map / std::set — mais l'impact sur les performances est profond.
Un std::map<int, double> stocke chaque paire clé-valeur dans un nœud d'arbre rouge-noir. Chaque nœud contient :
- La clé (
int, 4 octets) - La valeur (
double, 8 octets) - Un pointeur vers le nœud parent (8 octets)
- Un pointeur vers le fils gauche (8 octets)
- Un pointeur vers le fils droit (8 octets)
- Un flag de couleur rouge/noir (typiquement 8 octets avec le padding)
Total par nœud : ~48 octets d'overhead pour stocker 12 octets de données utiles. L'efficacité mémoire est d'environ 25 %.
Mais le problème principal n'est pas la taille — c'est la disposition en mémoire. Chaque nœud est alloué individuellement par new, ce qui signifie que les nœuds sont dispersés arbitrairement dans le heap :
Heap (adresses simplifiées) :
0x1000 [Nœud: clé=42] → fils gauche: 0x5800, fils droit: 0x2400
...
0x2400 [Nœud: clé=73] → fils gauche: 0x9100, fils droit: 0x6700
...
0x5800 [Nœud: clé=15] → fils gauche: 0xB200, fils droit: 0x1000 (?)
...
0x9100 [Nœud: clé=58] → ...
Chaque traversée parent→enfant = saut de plusieurs KiB → cache miss probable
Pour chercher une clé dans un std::map de N éléments, il faut traverser O(log₂ N) nœuds. Chaque traversée suit un pointeur vers un nœud potentiellement éloigné en mémoire — c'est un accès aléatoire du point de vue du cache.
Pour un map de 10 000 éléments, une recherche traverse ~13 nœuds. Si les nœuds sont dispersés dans le heap (ce qui est le cas typique après de nombreuses insertions/suppressions), chaque accès est un cache miss L1 probable, et potentiellement un miss L2 ou L3. Le coût réel n'est pas O(log n) comparaisons à ~1 ns chacune, mais O(log n) cache misses à ~5–70 ns chacun.
Coût théorique : 13 comparaisons × ~1 ns ≈ 13 ns
Coût réel (L2) : 13 cache misses × ~5 ns ≈ 65 ns
Coût réel (L3) : 13 cache misses × ~15 ns ≈ 195 ns
Coût réel (RAM) : 13 cache misses × ~70 ns ≈ 910 ns
Pour les petits et moyens ensembles (< 100 000 éléments), ce coût de cache misses domine complètement le coût algorithmique.
std::flat_map<int, double> stocke les clés et les valeurs dans deux std::vector triés (par défaut — les conteneurs sous-jacents sont configurables) :
Clés (std::vector<int>) : [3, 7, 12, 15, 22, 42, 58, 73, 89, 95]
Valeurs (std::vector<double>) : [1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9, 10.0]
Index : 0 1 2 3 4 5 6 7 8 9
Les clés sont contiguës en mémoire dans un seul tableau. Les valeurs sont contiguës dans un autre tableau. Il n'y a aucun pointeur, aucun nœud, aucune allocation individuelle.
La recherche utilise une recherche binaire (std::lower_bound) sur le tableau de clés — même complexité O(log n), mais avec un pattern d'accès radicalement différent.
Pour un flat_map de 10 000 éléments int :
- Le tableau de clés occupe 10 000 × 4 = 40 KiB — il tient dans le L1d (32–48 KiB).
- La recherche binaire accède à ~13 positions dans ce tableau de 40 KiB. Même si les accès ne sont pas séquentiels, le tableau entier est dans le L1 après quelques recherches — chaque accès est un cache hit.
flat_map : 13 comparaisons × ~1 ns (L1 hit) ≈ 13 ns
std::map : 13 nœuds × ~5-70 ns (cache miss) ≈ 65-910 ns
Le gain est de 5× à 70× sur la latence de recherche, uniquement grâce à la contiguïté mémoire.
Les benchmarks suivants mesurent les opérations courantes sur des conteneurs de <int, int>, compilés avec GCC 15, -O2 -march=native, sur AMD Zen 4. Les temps sont par opération, moyennés sur 1 000 000 d'opérations.
| Nombre d'éléments | std::map |
std::flat_map |
std::unordered_map |
Speedup flat vs map |
|---|---|---|---|---|
| 10 | 18 ns | 5 ns | 22 ns | 3,6× |
| 100 | 45 ns | 9 ns | 25 ns | 5,0× |
| 1 000 | 85 ns | 15 ns | 28 ns | 5,7× |
| 10 000 | 140 ns | 22 ns | 32 ns | 6,4× |
| 100 000 | 210 ns | 55 ns | 35 ns | 3,8× |
| 1 000 000 | 350 ns | 120 ns | 40 ns | 2,9× |
Observations :
std::flat_mapest systématiquement plus rapide questd::mappour la recherche, à toutes les tailles testées.- Le gain est maximal (5–6×) pour les tailles de 100 à 10 000 éléments, où le tableau de clés tient dans le L1 ou le L2.
- Au-delà de 100 000 éléments, le tableau de clés dépasse le L2 et le gain diminue — mais reste significatif (3×).
std::unordered_mapreste le plus rapide en recherche pure pour les grands ensembles (> 100 000), grâce à son O(1) amorti. Mais pour les petites et moyennes tailles,std::flat_maprivalise ou le dépasse, carunordered_mappaie le coût du hashing et de la résolution de collisions.
| Nombre d'éléments | std::map |
std::flat_map |
Speedup |
|---|---|---|---|
| 1 000 | 12 µs | 0,8 µs | 15× |
| 10 000 | 180 µs | 8 µs | 22× |
| 100 000 | 2 800 µs | 85 µs | 33× |
C'est ici que la différence est la plus spectaculaire. L'itération sur un std::map suit une chaîne de pointeurs entre nœuds dispersés — un cache miss potentiel à chaque nœud. L'itération sur un std::flat_map parcourt séquentiellement deux std::vector — le pattern d'accès idéal pour le prefetcher matériel.
Le gain de 15× à 33× sur l'itération fait de std::flat_map un choix évident pour les cas d'usage où l'on itère fréquemment sur l'ensemble des éléments (affichage, sérialisation, agrégation, synchronisation).
| Nombre d'éléments | std::map (insert) |
std::flat_map (insert) |
std::flat_map (batch + sort) |
|---|---|---|---|
| 100 | 45 ns/op | 80 ns/op | 8 ns/op |
| 1 000 | 85 ns/op | 350 ns/op | 12 ns/op |
| 10 000 | 150 ns/op | 4 200 ns/op | 18 ns/op |
| 100 000 | 250 ns/op | 52 000 ns/op | 25 ns/op |
L'insertion individuelle est le point faible de std::flat_map. Chaque insertion dans un tableau trié nécessite un décalage de tous les éléments suivants — O(n) par insertion. Pour 10 000 éléments, chaque insertion déplace en moyenne 5 000 éléments.
Mais la construction par batch — insérer tous les éléments dans un vecteur non trié puis trier une seule fois — est dramatiquement plus rapide :
// ❌ Insertion individuelle — O(n) par insertion, O(n²) total
std::flat_map<int, int> fm;
for (auto& [k, v] : data)
fm.insert({k, v}); // décale le tableau à chaque insertion
// ✅ Construction par batch — O(n log n) total
std::vector<int> keys;
std::vector<int> values;
keys.reserve(data.size());
values.reserve(data.size());
for (auto& [k, v] : data) {
keys.push_back(k);
values.push_back(v);
}
// Construction depuis des conteneurs triés (ou que flat_map triera)
std::flat_map<int, int> fm(std::move(keys), std::move(values));La construction par batch est O(n log n) (un tri) au lieu de O(n²) (n insertions individuelles), et elle est cache-friendly.
Comme pour l'insertion, la suppression individuelle est O(n) car elle nécessite un décalage du tableau. Les mêmes stratégies de batch s'appliquent : accumuler les suppressions et les appliquer en une seule passe.
Comparons les compteurs cache sur une boucle de 100 000 recherches dans un conteneur de 10 000 éléments <int, int> :
perf stat -e L1-dcache-loads,L1-dcache-load-misses,LLC-loads,LLC-load-misses \
./bench_map_find
perf stat -e L1-dcache-loads,L1-dcache-load-misses,LLC-loads,LLC-load-misses \
./bench_flat_map_findRésultats typiques :
| Compteur | std::map |
std::flat_map |
|---|---|---|
| L1-dcache-loads | 18 200 000 | 9 500 000 |
| L1-dcache-load-misses | 4 800 000 (26 %) | 42 000 (0,44 %) |
| LLC-loads | 2 100 000 | 3 200 |
| LLC-load-misses | 380 000 | 120 |
Les chiffres sont éloquents :
std::map: 26 % de misses L1 et 2,1 millions d'accès L3.std::flat_map: 0,44 % de misses L1 et 3 200 accès L3.
Le tableau de clés du flat_map (10 000 × 4 = 40 KiB) tient quasi entièrement dans le L1d. Après quelques recherches, il est entièrement en cache et chaque recherche binaire ultérieure ne provoque aucun miss. Le std::map, lui, disperse ses nœuds sur ~480 KiB de heap (10 000 nœuds × ~48 octets) — bien au-delà du L1, avec des accès aléatoires à chaque traversée de nœud.
Pour une analyse plus fine, cachegrind (Valgrind) simule le comportement du cache :
valgrind --tool=cachegrind ./bench_map_find
cg_annotate cachegrind.out.* Le rapport montre le nombre de misses par ligne de code, ce qui permet d'identifier précisément les accès problématiques dans std::map (les déréférencements de pointeurs left, right, parent).
La question « flat_map ou unordered_map ? » est fréquente. Les deux sont des alternatives cache-friendly à std::map, mais avec des compromis différents.
- Données ordonnées : les éléments sont triés par clé, permettant les parcours ordonnés, les recherches par intervalle (
lower_bound,upper_bound), et la fusion de deux maps. - Itération ultra-rapide : parcours séquentiel de deux vecteurs — le meilleur pattern pour le cache et le prefetcher.
- Empreinte mémoire minimale : pas d'overhead par élément (pas de pointeurs, pas de hash, pas de buckets).
- Prédictibilité : pas de pathologies liées aux collisions de hash.
- Sérialisation triviale : les données sous-jacentes sont de simples vecteurs.
- Recherche O(1) amorti : plus rapide que la recherche binaire O(log n) pour les grands ensembles (> 50 000–100 000 éléments).
- Insertion/suppression O(1) amorti : pas de décalage de tableau.
- Performance stable : pas de dégradation sur l'insertion contrairement à
flat_map.
| Critère | std::flat_map |
std::unordered_map |
std::map |
|---|---|---|---|
| Nombre d'éléments < 1 000 | ✅ optimal | ✅ bon | ❌ overhead nœuds |
| Nombre d'éléments 1 000–50 000 | ✅ optimal | ✅ bon | ❌ cache misses |
| Nombre d'éléments > 100 000 | ✅ optimal | ||
| Recherches fréquentes | ✅ excellent | ✅ excellent | ❌ cache misses |
| Itération fréquente | ✅ optimal (séquentiel) | ❌ ordre arbitraire | ❌ chaîne de pointeurs |
| Insertions fréquentes | ❌ O(n) par insertion | ✅ O(1) amorti | ✅ O(log n) |
| Ordre requis | ✅ trié | ❌ non ordonné | ✅ trié |
| Construction une fois, lecture ensuite | ✅ idéal (batch + sort) | ✅ bon | |
| Mémoire contrainte | ✅ compact | ❌ overhead buckets | ❌ overhead nœuds |
Le cas d'usage idéal de std::flat_map est un conteneur construit une fois (ou rarement modifié) et lu/itéré fréquemment. C'est le profil typique des tables de configuration, des dictionnaires de traduction, des index en mémoire, des caches de résultats, et des tables de lookup.
#include <flat_map>
#include <vector>
#include <algorithm>
// Construire un flat_map à partir de données brutes
std::flat_map<std::string, int> build_index(
const std::vector<std::pair<std::string, int>>& raw_data)
{
// Séparer clés et valeurs
std::vector<std::string> keys;
std::vector<int> values;
keys.reserve(raw_data.size());
values.reserve(raw_data.size());
for (const auto& [k, v] : raw_data) {
keys.push_back(k);
values.push_back(v);
}
// flat_map trie automatiquement si les données ne sont pas déjà triées
return std::flat_map<std::string, int>(std::move(keys), std::move(values));
}// Ajouter plusieurs éléments efficacement
void batch_insert(std::flat_map<int, int>& fm,
const std::vector<std::pair<int, int>>& new_data)
{
// Extraire les conteneurs sous-jacents
auto [keys, values] = std::move(fm).extract();
// Insérer les nouvelles données
for (const auto& [k, v] : new_data) {
keys.push_back(k);
values.push_back(v);
}
// Reconstruire le flat_map (trie et déduplique)
fm = std::flat_map<int, int>(std::move(keys), std::move(values));
}La méthode extract() (C++23) permet de récupérer les vecteurs sous-jacents par move, les modifier, et reconstruire le flat_map. C'est O(n log n) pour le tri, mais c'est une seule passe au lieu de n insertions O(n) chacune.
// Lookup table construite au démarrage, lue en boucle serrée
const std::flat_map<int, float> coefficients = build_coefficients();
void process(std::span<const int> ids, std::span<float> output) {
for (std::size_t i = 0; i < ids.size(); ++i) {
auto it = coefficients.find(ids[i]);
if (it != coefficients.end())
output[i] *= it->second;
}
// Le tableau de clés du flat_map est en L1/L2 après les premiers accès
// → chaque find() est un cache hit
}Pour un conteneur de N éléments <int, double> (clé 4 octets, valeur 8 octets) :
| Conteneur | Mémoire par élément | Mémoire pour 10 000 éléments | Efficacité |
|---|---|---|---|
std::flat_map |
12 octets | ~120 KiB | ~100 % |
std::map |
~48 octets | ~480 KiB | ~25 % |
std::unordered_map |
~52 octets (avec buckets) | ~520 KiB | ~23 % |
Le std::flat_map utilise 4× moins de mémoire que std::map et std::unordered_map. Moins de mémoire signifie que plus de données tiennent dans le cache à la fois — c'est un cercle vertueux.
Pour les clés de grande taille (comme std::string), l'avantage mémoire diminue car l'overhead des nœuds/buckets est dilué par la taille des données. Mais l'avantage de contiguïté reste : les clés sont dans un seul std::vector, ce qui favorise le prefetching lors de la recherche binaire.
Si le workload consiste en un flux continu d'insertions et de suppressions individuelles entrelacées avec des lectures, std::flat_map est le mauvais choix. Chaque modification est O(n), ce qui donne une complexité globale O(n²) pour n modifications.
Dans ce cas, std::map (O(log n) garanti par opération) ou std::unordered_map (O(1) amorti) sont plus appropriés.
Au-delà de quelques centaines de milliers d'éléments, le tableau de clés dépasse le L3 et la recherche binaire perd son avantage cache par rapport au hashing O(1) de std::unordered_map. De plus, les insertions O(n) deviennent prohibitives même en batch.
Le std::flat_map déplace ou copie les éléments lors des insertions (pour maintenir le tri). Si le type de clé ou de valeur est coûteux à déplacer (par exemple une structure contenant une matrice 4×4 de doubles), le coût du décalage est amplifié. Préférer des types légers ou facilement déplaçables.
| Aspect | std::map |
std::flat_map |
Impact |
|---|---|---|---|
| Layout mémoire | Nœuds dispersés (heap) | Tableaux contigus | flat_map : localité cache maximale |
| Recherche (10K élts) | ~140 ns | ~22 ns | flat_map 6× plus rapide |
| Itération (10K élts) | ~180 µs | ~8 µs | flat_map 22× plus rapide |
| Insertion individuelle | O(log n) | O(n) | map plus rapide |
| Construction batch | O(n log n) | O(n log n) | Équivalent, flat_map légèrement plus rapide |
| Mémoire par élément | ~48 octets | ~12 octets | flat_map 4× plus compact |
| Cache misses L1 | ~26 % | ~0,4 % | flat_map : quasi zéro miss |
| Cas d'usage idéal | Modifications fréquentes, grands ensembles | Construit une fois, lu souvent, ≤ 100K éléments | — |
Le std::flat_map est l'application directe des principes du chapitre 41 aux conteneurs associatifs : contiguïté mémoire, compacité, respect de la hiérarchie cache. C'est le conteneur associatif ordonné par défaut pour les ensembles de petite et moyenne taille en C++23, à condition que le workload soit dominé par les lectures et les itérations plutôt que par les modifications.