Contexte

Dans une application de calculs de risque chez un client, de nombreux crashs aléatoires survenaient. Le symptôme visible était la mémoire d’un processus qui augmentait de manière régulière jusqu’à 3Go, et là, le processus crashait. Cette application était multiprocessus répartis sur un cluster de 2 à 7 machines : chaque machine exécutant 1.5 fois plus de processus que de nombre de cœurs (une machine de 16 cœurs logiques exécutait donc 24 processus) et chaque processus travaillant avec de 4 à 30 threads. Du fait de l’architecture, plusieurs traders accédaient simultanément aux machines pour exécuter des simulations ce qui faisait que nous n’arrivions pas à reproduire le problème sur les environnements de développement ; d’autant plus que les traders, jaloux de leurs idées, ne nous disait pas vraiment quelles données ils avaient fourni au cluster : on avait au mieux un à peu près. Nous n’avions alors que les fichiers de logs et notre expérience pour comprendre les causes du problèmes…

L’application était écrite en C++ avec un framework (ICE) simplifiant la programmation distribuée et la communication entre les processus. Pour des raisons de « performances », les premiers développeurs avaient intégré boost et tbb (Thread Building Block d’Intel) pour, notamment, avoir accès à des conteneurs efficaces. Il y avait des changements de structures de données importants entre les conteneurs STL/boost et ceux du framework.

Nous allons nous préoccuper de l’usage des conteneurs et des points importants à savoir sur la mémoire consommée.

Le cas bizarre

Après rajout de logs dans l’application nous avons pu identifier une zone critique (on est un environnement très multi-threadé) qui allouait et libérait beaucoup de mémoire au moment du crash : la zone où était effectué le « marshalling » des données de la simulation en vue de communiquer avec un autre processus. Dans cette zone il y avait une conversion d’un dictionnaire ICE, qui permettait le transfert de données inter-processus, vers une « std::map< int, int > » (choix architecturel discutable au demeurant : convertir c’est perdre du temps et provoquer des pics de mémoire). Mais le point qui nous intéresse directement est le pic de mémoire atteint : nous avions 1 millions de paires d’entier ( 2 x sizeof(int) x 1000000= 8Mo environ), or le pic mémoire était beaucoup plus important que cela.

Après avoir étudié toutes les branches de code qui s’exécutaient à travers tous les threads actifs, nous n’avions pas trouvé d’explication à cette consommation anormale de mémoire… Vaillamment nous avons travaillé avec le débogueur en pas à pas pour comprendre ce qui se passait : en entrant dans le code de la STL dans l’ajout de couple (clé, valeur) nous avons eu un choc : la STL avait un fonctionnement dont nous ignorions les tenants et les aboutissants mais qui sont documentés (sic !!! qui lit la documentation de nos jours ? ☹).

Comment mesurer la mémoire consommée sous Windows

Microsoft fournit dans les API Windows de nombreuses fonctions pour contrôler la taille de l’espace de travail d’un processus. Nous allons nous concentrer sur une fonction relativement simple d’usage et utilisable sur la majorité des systèmes Windows existants.

En appelant cette fonction, vous obtiendrez la taille mémoire de l’espace adressable du processus… Par contre, le nombre obtenu sera pas très lisible, je vous conseille la fonction suivante pour avoir un affichage compréhensible par un humain :

void write_memory( SIZE_T mem, const char *title = "consumed" )
{
  // local variables
  const char* cst_units[] = { "b", "Kb", "Mb", "Gb", "Tb" };
  SIZE_T      values[ 5 ];
  int         i = 0;
  // split
  while( 0 != mem )
  {
    values[ i++ ]   = mem % 1024;
    mem           >>= 10;
  }
  --i;
  // write
  std::cout << title << " = ";
  while( i >= 0 )
  {
    if( 0 != values[ i ] )
    {
      std::cout << values[ i ] << cst_units[ i ]

Comment mesurer la mémoire consommée sous Windows

La STL est une formidable bibliothèque inventée initialement dans les laboratoires de HP. Les conteneurs sont un formidable outil pour faciliter le travail du développeur mais de par leur architecture, ils ont des contraintes qu’un bon développeur se doit de connaître pour comprendre le comportement du logiciel qu’ils écrivent… Nous ne parlerons pas du cas de std ::vector qui est conforme à nos attentes.

std::map

Tentons l'expérience

Nous allons partir sur une fonction de tests qui construit une map avec un nombre important d’entrées.

void test_std_map()
{
  std::map< int, int > m;
  SIZE_T before = getWorkingSize();
    for( int i = 0; i < 10000000; ++i )
    {
      m[ i ]

10 millions de couples d’entiers, une compilation en Release x64, on obtient :

Déjà, alors que nous avions 76Mb et 301Kb de données utiles, on se rend compte que le coût de ‘std::map’ est très supérieure en Release mais encore plus en Debug… Pourquoi autant de méga-octet ? Qu’est ce qui justifie autant de consommation de mémoire ?

Comment est implémentée la map ?

La map est en fait un arbre binaire implémentée selon la technique du Red-Black Tree inventé en 1972 par Rudolf Bayer.

Un arbre bicolore est un arbre binaire de recherche dans lequel chaque nœud a un attribut supplémentaire : sa couleur, qui est soit rouge soit noire. En plus des restrictions imposées aux arbres binaires de recherche, les règles suivantes sont utilisées :

• Un nœud est soit rouge soit noir

• La racine est noire

• Le parent d'un nœud rouge est noir

• Le chemin de chaque feuille à la racine contient le même nombre de nœuds noirs.

Ces contraintes impliquent une propriété importante des arbres bicolores : le chemin le plus long possible d'une racine à une feuille (sa hauteur) ne peut être que deux fois plus long que le plus petit possible. Un arbre est ainsi presque équilibré. Comme les opérations d'insertion, de recherche et de suppression requièrent dans le pire des cas un temps proportionnel à la hauteur de l'arbre, les arbres bicolores restent efficaces, contrairement aux arbres binaires de recherche ordinaires.

Chaque nœud possède deux pointeurs sur les nœuds enfants. Et, pour des raisons d’efficacité, un pointeur sur le nœud parent qui permettra d’implémenter plus facilement les itérateurs. De plus, dans la STL de Microsoft, il faudra ajouter 2 caractères _Color et _Isnil que voici dans le débogueur de VS2017 :

Si on se souvient du sujet de mon précédent article (mais si… cherchez bien…) sur le padding des structures, on arrive à la conclusion qu’un nœud nous coûte 40 octets… 40 octets multiplié par 10 millions de champs, ça nous fait 381Mb 481Kb. Il nous manque toujours environ 80Mb… La raison nous vient de la stratégie de l’allocateur : afin d’optimiser les insertions il alloue des paquets de nœuds au lieu des allouer un à un. On y gagne en performance mais on a alloué plus de nœuds que nécessaire dans notre exemple et malheureusement il n’y a pas de solutions simples pour contourner ce problème excepté remplacer l’allocateur par défaut par un autre que l’on pourra paramétrer.

Maintenant, la différence entre le mode Release et Debug nous vient des « Guard Bytes » : le compilateur ajoute de la mémoire avant et après les blocs afin de protéger le programme contre les dépassements d’index… Pour en savoir plus, je vous propose de vous référer à l’article suivant : https://en.wikipedia.org/wiki/Guard_byte.

std:list

Tentons l'expérience

Nous allons partir sur une fonction de tests qui construit une liste avec un nombre important d’entrées.

void test_std_list()
{
  std::list< double >

10 millions de flottant en double précision (8 octets), une compilation en Release x64, on obtient :

Et avec une compilation en Debug x64 :

Comme dans le cas de la std::map, on consomme plus de mémoire que la quantité nécessaire pour les données utiles ; et en Debug la mémoire consommée est vraiment très importante.

Comment est implémentée la liste ?

Les std::list sont des listes doublement chaînées :

Chaque nœud contient donc 2 pointeurs en plus de la donnée. Ce que l’on peut vérifier avec le débogueur :

Dans l’exemple, _NewNode contient bien 2 pointeurs ainsi que la valeur… La taille allouée est donc dans notre cas de 24 octets par nœud. De même que dans le cas de la map, l’allocateur alloue les données par blocs afin de gagner en performance et dans notre cas : il a alloué plus que nécessaire…

std::unordered_map

Tentons l'expérience

Nous allons partir sur une fonction de tests qui construit une map non-ordonnée avec un nombre important d’entrées : des couples d’entiers comme pour la std::map.

void test_std_unordered_map()
{
  std::unordered_map< int, int > m;
  SIZE_T before = getWorkingSize();
  for (int i = 0; i < 10000000; ++i)
  {
    m[i]

10 millions de couples (int, int) (chaque couple occupant 8 octets), avec une compilation en Release x64, on obtient :

Et avec une compilation en Debug x64 :

Comme dans le cas de la std::map, on consomme plus de mémoire que la quantité nécessaire pour les données utiles ; et en Debug la mémoire consommée est vraiment très importante.

Comment est implémentée la unordered_map ?

L’implémentation n’est pas la même selon le compilateur, par exemple Microsoft a utilisé la solution Dirkumwave :

En fait on a un vecteur qui pointe sur les éléments d’une liste doublement chaînée quand boost utilise une version plus optimisée (pour la consommation mémoire) :

En effet la liste est simplement chaînée et économise un pointeur par nœud…

En utilisant un débogueur avec Visual Studio, on peut regarder le détail de l’implémentation de notre unordered_map après l’insertion des 10 millions de couples :

On y voit bien le vecteur ainsi que la liste doublement chaînée. On constate que la liste contient bien 10 millions de nœuds (avec les couples de valeurs) ainsi que le vecteur de références sur les nœuds. On observe aussi que le redimensionnement par défaut des vecteurs entraine un espace non-utilisé. On peut ainsi se référer à nos tests précédents pour estimer la consommation mémoire :

void test_std_unordered_map()
{
  std::unordered_map< int, int > m;
  SIZE_T before = getWorkingSize();
  for (int i = 0; i < 10000000; ++i)
  {
    m[i] = 2 * i;
  }
  SIZE_T consumed = getWorkingSize() - before;
  write_memory(consumed);
  write_memory(8 * 10000000, "instead of");
  write_memory(33554432*8+10000000*

Ce qui nous fournit comme résultat :

Ce qui nous fournit une estimation cohérente en Release x64… 😊

Par contre unordered_map fournit une fonction nous permettant d’améliorer sensiblement la quantité de mémoire allouée ainsi que les performances à la création : reserve.

void test_std_unordered_map()
{
  std::unordered_map< int, int > m;
  m.reserve(10000000); // alloue immédiatement le bon nombre de nœuds…
  SIZE_T before = getWorkingSize();
  for (int i = 0; i < 10000000; ++i)
  {
    m[i] = 2 * i;
  }
  SIZE_T consumed = getWorkingSize() - before;
  write_memory(consumed);
  write_memory(8 * 10000000, "instead of");
  write_memory(33554432*8+10000000*

Ce qui nous donne :

Soit une économie de 253Mb… 😊

Conclusion

Si l’usage de la STL est fortement conseillé pour simplifier le développement il faut bien être conscient que les conteneurs de la STL consomment de la mémoire et que le coût dépend de la structure de données choisie ainsi que du nombre d’informations stockées : on peut facilement avoir de mauvaises surprises si on n’y prend garde… Et on peut transposer cette règle à tous les conteneurs de toutes les bibliothèques (boost, U++, etc…) : ils sont implémentés de manière assez similaires d’une bibliothèque à une autre.