Une optimisation qui ne tient pas ses promesses

Dans un article technique publié le 23 mai 2026, Arthur O'Dwyer, un spécialiste reconnu du langage C++, a comparé deux implémentations de l'algorithme standard std::remove_if. La version traditionnelle, dite « lisse », déplace les éléments un par un via l'opérateur d'affectation. La version « chunkée », proposée par l'auteur, regroupe les éléments survivants en blocs et les déplace en une seule opération memmove via l'algorithme std::move, ce qui devrait théoriquement être plus efficace pour les types trivialement copiables.

Méthodologie du test

O'Dwyer a conçu un banc d'essai sur un tableau d'un million d'entiers (int). Un prédicat masque une fraction déterminée des éléments : un sur deux, un sur huit, un sur cent vingt-huit ou un sur mille vingt-quatre. Le chercheur a mesuré le temps d'exécution de std::remove_if ainsi que de ses deux versions personnelles (« smooth » et « chunky »). Le tableau de résultats montre que la version chunkée est systématiquement plus lente que la version lisse, et même que l'implémentation standard de la bibliothèque libc++.

Résultats chiffrés

  • Lorsque la moitié des éléments sont supprimés (1 sur 2) : la version standard exécute l'opération en 3122 microsecondes, la version « smooth » en 3157 µs, et la version « chunky » en 3797 µs, soit une pénalité de +20 %.
  • Pour une suppression d'un élément sur huit : chunky affiche 1471 µs contre 1105 µs pour smooth (+33 %).
  • Pour une suppression d'un élément sur 128 : chunky monte à 468 µs contre 420 µs (−11 %).
  • Pour une suppression d'un élément sur 1024 : chunky atteint 396 µs contre 326 µs (−21 %).

Même dans les cas où les blocs d'éléments conservés sont les plus longs (suppression la plus rare), la version chunkée n'offre aucun gain. Le nombre d'affectations individuelles chute de 998 482 (smooth) à seulement 958 déplacements groupés (chunky), mais le temps d'exécution reste supérieur.

Analyse des causes

O'Dwyer attribue cette contre-performance au prédicteur de branche du processeur. La version classique exécute une boucle serrée avec un seul branchement conditionnel (pred(*first)). Lorsque la proportion d'éléments supprimés est élevée (un sur deux), ce branchement est imprévisible, ce qui pénalise la version lisse. Cependant, la version chunkée introduit une couche supplémentaire de logique (recherche du prochain élément survivant, appel à std::move, gestion des limites) qui alourdit le code machine et sollicite davantage le prédicteur. Même avec une prédiction de branche favorable, le surcoût de la logique de contrôle et l'appel à memmove lui-même (qui doit vérifier l'absence de chevauchement) l'emportent sur toute économie potentielle.

« Ceci suggère que lorsqu'il s'agit d'évaluer les algorithmes liés à remove, il ne faut pas se focaliser uniquement sur la minimisation du nombre d'affectations ; ce genre de considération peut être éclipsé par les effets de cache et de prédiction de branche », conclut l'auteur.

Implications pour la conception d'algorithmes

L'étude ne concerne pas directement unstable_remove, une proposition qui remplacerait les éléments à supprimer par les derniers éléments du conteneur via swap et pop. Cependant, O'Dwyer note que ce type d'algorithme tend à inverser l'ordre des éléments conservés, ce qui pourrait nuire à la localité des données en mémoire cache. La leçon à retenir est que les optimisations de déplacement par blocs ne sont pas une panacée et que les caractéristiques matérielles modernes (prédiction de branche, hiérarchie de cache) doivent être prises en compte dans l'évaluation des performances.

Conclusion

Le fractionnement en blocs (chunking) des déplacements d'éléments dans std::remove_if, bien qu'intuitif, n'accélère pas l'exécution. Au contraire, il introduit une pénalité comprise entre 11 % et 33 % selon le scénario. L'implémentation classique, qui repose sur une boucle d'affectations individuelles, demeure la plus performante pour les types trivialement copiables.