Comment optimiser la mémoire consommée

Pour laisser un commentaire

Je propose de parler d’optimisation de taille mémoire, de fragmentation, de mmap, de système, de C et de structures de données à travers l'exemple d'une bibliothèque qui implémente l'algorithme de recherche Aho-Corasick.

Pour un besoin en sécurité, je dois détecter des chaines de caractères dans du texte en un temps limité. Je vais par exemple essayer de trouver des patterns d’attaque connus. L’algorithme le plus basique est très simple, j’ai en entrée une liste de mots à rechercher dans du texte. Je prends le premier mot, je regarde pour chacun des caractères du texte si le mot est trouvé. Lorsque j’atteins la fin du texte je recommence avec le second mot. Rien de plus simple, mais les chercheurs en sécurité m’ont demandé de trouver environs 2400 mots dans mon texte. La complexité de recherche en prend un coup ! Si « n » est le nombre de mots, « m » la taille moyenne d’un mot et « t » la taille du texte, on obtient cette complexité :

Pour chaque caractère du texte, on doit tester chaque caractère de chaque mot. Cette manière de faire n'est pas compatible avec les contraintes de temps imposées pour faire une recherche. Par ailleurs, ce n’est pas satisfaisant d'un point de vue algorithmique.

La solution est bien connue, il faut utiliser l’algorithme Aho-Corasick qui permet d’avoir une complexité en O(t). Aho-Corasick permet de construire un graphe dans lequel on se déplace au fur et à mesure que l’on analyse les caractères du texte dans lequl on fait la recherche. Je ne souhaite pas entrer dans le détail de l’algorithme, voilà une bonne description :

https://fr.wikipedia.org/wiki/Algorithme_d%27Aho-Corasick

Je profite de l’occasion pour jouer avec ChatGPT :-) qui me fabrique approximativement le code C qui implémente l’algorithme de manière basique. Après la correction des bugs et l'adaptation de l’interface, j’obtient un comportement satisfaisant.

Le code source est versionné sur github: thierry-f-78/aho-corasick

Les tests

Je teste principalement sur mon mac « 2,3 GHz Quad-Core Intel Core i7 ». Il s'agit d'un processeur 64bit, aussi tous les pointeurs ont une taille de 8 octets. La procédure de tests est composée de ces étapes :

• Initialisation de l’arbre avec le chargement des mots et le calcul des liens d’échec.
• Calcul de la mémoire utile pour le stockage de l'arbre.
• Test de correspondance pour chaque mot chargé depuis la liste de référence (il peut y avoir plus d’une correspondance par mot). Ce test valide le bon fonctionnement de la fonction.
• Vérification du nombre de correspondances attendues par rapport a tous les test mots chargés depuis la liste de référence. Ce test valide le bon fonctionnement de la fonction.
• Test de vitesse en effectuant une boucle de 10 000 000 de recherches dans un texte de reference constant.

En parallèle, je mesure la mémoire RSS consommée qui est la mémoire réellement consommée par le processus.

Après le démarrage du programme et avant le chargement des données, la RSS vaut 522ko. Je n’essaye pas de réduire cette taille.

La liste de mots de référence contient 2358 mots d’une taille moyenne de 22 octets. Le texte de test fait 74 octets et deux mots correspondent. Une fois l’arbre généré, la liste de mots est représenté par un arbre de 23 701 nœuds.

La première mesure

L’algorithme de base de ne dispose d’aucune optimisation en terme de consommation mémoire et est raisonnablement rapide. Il consomme 60Mo de mémoire RSS et fait 4,2 millions de correspondances par seconde. La taille réelle des données utile qui composent l’arbre est de 46.6Mo.

A priori, l’utilisation de 60Mo de mémoire pour stocker un arbre de 2358 mots est excessif. Le dataset complet fait 23 701 nœuds, cela fait une surcharge approximative moyenne de 2650 octets par nœud. C’est une valeur élevée, mais c’est approximativement ce qui est attendu. Voila la déclaration d’une structure qui représente un nœud :

struct ac_node {
    struct ac_node *children[256];
    struct ac_node *fail;
    char *word;
};

En mesurant la taille des données, on justifie facilement les 46,6Mo de mémoire. en revanche, on est loin des 60Mo de RSS mesurée, il manque 13,4Mo à justifier. Cela est probablement dû à la fragmentation de la mémoire, due à la taille des pages allouées par le kernel par rapport à la taille d'un nœud, ainsi qu'a la capacitée des pages à être contiguës.

Malloc et la fragmentation

Le système d’allocation mémoire en C est basé sur la distribution de petits blocs de mémoire pris dans un gros bloc délivré au programme par l’OS. Lorsque l’on veut stocker 5 octets le programme demande un peu de mémoire à l’allocateur, lui-même va en demander au système. Le système ne fournit que des pages mémoires complètes. Ces pages font généralement 4ko, elles peuvent être contiguës ou non.

L’allocateur mémoire va ensuite distribuer les pages de mémoire allouées par le kernel aux différentes fonctions qui en ont besoin. Afin que le système d’allocation (malloc/calloc/realloc/free) mémoire puisse gérer les sous-blocs alloués et les sous-blocs disponible, il utilise lui aussi une partie de cette mémoire allouée pour stocker des données. Ces données ne sont pas directement utiles pour le programme, mais sont indispensables pour l'allocateur.

Le kernel fournit donc des gros blocs mémoire contiguës ou non, et la bibliothèque d'allocation mémoire du logiciel (malloc/calloc/realloc/free) gère leur découpage granulaire pour l'usage final.

Supposons un bloc kernel de 10 octets et négligeons la mémoire utilisée par l'allocateur pour se structurer. Les schema ci dessous représentent les octets allouées en bleu, les octets libre en blanc. L'adresse de l'espace mémoire commencent à 0 pour plus de lisibilité.

• Le logiciel nécessite 4 octets, il prends les 4 premiers.
  
• Il nécessite ensuite 2 octets, il prends les seconds.
  
• Il n’a plus besoin des 4 premiers octets, il les rends. Il y a donc 8 octets disponible.
  
• Le logiciel à besoin de 5 octets, il y a bien 5 octets disponibles, mais pas contiguës, malloc doit donc demander un nouveau bloc au système. Dans le premier cas, l’espace mémoire du process permet l’ajout d’un bloc contigüe. Seuls les octets 0 à 3 ne peuvent pas être utilisés et forment un trou.
  
  dans le second cas, il ne le permet pas et le nouveau bloc n’est pas contigüe. Les octets 0 à 3 et 6 à 8 ne peuvent pas être utilisés et forment deux trous:
  

C’est ici qu’apparait la fragmentation, elle se manifeste via les trous de 4 octets. Deux dans le premier cas, et un seul dans le second cas. La défragmentation de la mémoire n’est pas un chose simple en C ni dans n'importe quel langage a base d'allocation mémoire. Aussi, bien que ce ne soit pas facile, il peut être intéressant de ne pas créer de trous, ou de limiter leur apparition.

Les trous créés seront tout de même utilisés lorsque le programme aura besoin d'un bloc de mémoire d'une taille correspondante a la taille contigüe disponible.

Dans la cas de la bibliothèque, la taille d'un nœud est de 2064 octets. La taille d'une page mémoire est de 4096 octets. On ne peut mettre qu'un seul nœud par page de 4ko. Chaque fois que le kernel ne peux pas fournir de pages contigües en mémoire, on crée un trou de 4096 - 2064 octets, soit 2032 octets. Si l'on regarde combien de trous de 2032 octets il faut pour gaspiller 13,4Mo de mémoire, on obtient 6914. Par rapport aux 23701 nœuds qui composent l'arbre, cela représente 29% des alloctions qui ne seraient pas contigües. C'est un ratio bien trop élevé. La véritable raison doit être une mélange entre la fragmentation et les structures de controles de l'allocateur.

Première optimisation de la mémoire

L’idée est de réduire la taille de la mémoire nécessaire. On peut noter un tableau de pointeurs 256 valeurs qui sert d'index pour indiquer rapidement vers quel nœud fils se diriger en fonction du caractère entré. chaque caractère est un octet, soit 256 possibilités d'aiguillage. On appellera ce tableau l’index des fils ou l'index. Il s'agit de voir si l'on peut réduire la taille de cet index.

Il peut être intéressant de voir combien de fils dispose chaque nœud et d’en faire une statistique. Cela donnera une ordre de grandeur sur l'utilisation de l'index. Pour cela, il faut créer l’arbre et coder un algorithme récursif qui parcours l’arbre et met à jour des compteurs. On ajoute le nombre de liens valides dont dispose chaque nœud a un compteur global que l’on divise à la fin par le nombre de nœuds total (bref, on calcule la moyenne du nombre de fils valide par nœud). Le résultat est :

• Nombre maximum de nœuds fils : 32
• Nombre moyen de nœuds fils : 1

On en conclut qu’il y a en moyenne 255 valeurs de trop (sur les 256 valeurs possibles et prévues) pour décrire l'index des fils de chaque nœud. Aussi théoriquement, la structure d'un nœud pourrait en moyenne être limitée à une taille de 3 pointeurs de 8 octets (un lien fils, un lien fail et le mot recherché), ce qui donne une taille mémoire utilisée théorique de :

Pour réduire la taille de l’index de fils, on peux utiliser un index borné. Dans l'exemple ci-dessous, les 4 premiers et les 4 derniers pointeurs sont NULL, ils ne sont donc pas utiles pour l'index des fils. Autrement dit, on peut compresser l'index en signalant le nombre d'élément NULL en début d'index et le nombre d'éléments NULL en fin d'index.

Il s'agit donc de modifer la structure d'un nœud afin de stocker le premier et le dernier pointeur significatif. L'index ne disposant que de 256 valeurs possible de 0 à 255, il suffit d'un octet par borne pour stocker l'information. Ces octets sont nommées « first » et « last » La structure de stockage d’un nœud devient :

struct ac_node {
    unsigned char first;
    unsigned char last;
    struct ac_node **children;
    struct ac_node *fail;
    char *word;
};

Le résultat est satisfaisant. La mémoire RSS est passée à 1,9Mo, en revanche la vitesse d’exécution est passée à 3,7 millions de correspondances par seconde.

La vitesse d’exécution a baissée car l’accès à l’index n’est plus immédiat. Dans la précédente version, on pouvait rechercher directement un octet dans l’index, dans cette nouvelle version, il faut d’abord vérifier que l’octet soit contenu dans l’index, puis appliquer un offset et choisir le bon index dans l’arbre. Ces 3 opérations (deux comparaisons et une soustraction) justifient la baisse de performances.

Le programme de test indique une consommation mémoire utile de 1.01Mo, or la RSS mesure 1.9Mo, soit quasiment le double. On ne peut plus négliger la mémoire nécessaire au processus pour fonctionner, à savoir les 522ko de RSS observés au démarrage du programme. On a donc 1.4Mo utilisés au lieu de 1Mo attendus. Il semble que la place excedante soit occupée par la fragmentation mémoire due à l'allocateur, ainsi que le modèle de nœud utilisé qui n’est pas aussi idéal que celui évoqué. En effet, l’index est maintenant désigné par un pointeur qui utilise 8 octets et les limites de l’index sont stockées avec deux entiers de 8 bits qui prennent donc 2 octets.

Voila le calcul de la taille d’un nœud,

On multiplie par le nombre de nœuds (23 701), et cela donne 1.26Mo, ce qui s’approche des 1.4Mo mesurés.

Peut-on encore faire baisser la quantité de mémoire utilisée ?

En regardant la structure qui porte chaque nœud, on peut se demander si le pointeur sur le mot sert à quelque chose. Dans la pratique il est utilisé pour savoir si on a trouvé un mot en vérifiant que ce pointeur n’est pas NULL. Un seul bit peut remplacer cette valeur. Son autre utilité est de retourner le mot qui correspond à l’appelant.

Étant donné que le mot correspond à une portion du texte dans lequel on fait la recherche, il n’est pas utile de stocker le mot trouvé, seule la position dans le texte ainsi que le nombre de caractères correspondants est suffisant à reconstruire l’information.

Essayons donc de supprimer le pointeur « char *word ». Il s’agira simplement de le remplacer par un entier qui contient le nombre de caractères correspondant ou 0 si le nœud n’est pas final. Un entier de 16bits sera suffisant. D’une part il suffit à mes besoins puisqu’il autorise des mots de 64ko de long, et d’autre part il ne prend que deux octets en mémoire. On économise donc 6 octets par nœud.

struct ac_node {
    unsigned char first;
    unsigned char last;
    struct ac_node **children;
    struct ac_node *fail;
    unsigned short match;
};

Après avoir compilé et testé le programme, on voit que la quantité de mémoire baisse considérablement, mais pas autant qu’espéré. Voila donc une occasion de parler d'alignement mémoire.

L’alignement des structures

Un processeur x86 ou x86_64 est bien plus efficace lorsqu'il accède à de la mémoire alignée. alignée signifie que la mémoire est alignée sur la taile de la donnée que le processeur va récupérer. Ainsi un pointeur 64 bits sera positionné à une adresse mémoire qui soit une multiple de 8 octets. Sans cela certaines instructions ne fonctionnent tout simplement pas et d'autre sont émulées par le code assembleur généré. Le compilateur va donc aligner les membres d'une structure sur des multiples de la valeur la plus grande contenue dans la structure. Ici, ce sera 8 octets. Cette manière d'aligner n'est pas optimale car les types plus courts peuvent être alignés différement.

Donc en appliquant le concept d'alignement, la structure ci-dessous qui semble contenir uniquement 20 octets va en réalité en contenir 32, dont 12 qui ne sont pas utilisés.

struct ac_node {
    unsigned char first;
    unsigned char last;
    unsigned short match;
    struct ac_node **children;
    struct ac_node *fail;
};

Pour minimiser ces trous, il convient d’ordonner les membres d’une structure de manière à ce que l'ordre des membres soit déterminé en fonction de l'alignement de leur type. Le but est qu'il n'y ait pas d'espaces entre deux membres successif. En déclarant la structure comme ci-dessous, un max de trous sont bouchés. Au lieu de faire 32 octets, elle en fait 24. Il reste 4 octets de libres entre « last » et « children ».

struct ac_node {
    unsigned char first;
    unsigned char last;
    unsigned short match;
    struct ac_node **children;
    struct ac_node *fail;
};

On note qu'il reste un trou de 4 octets du à l'alignent 64 bits du pointeur « children ». On peut forcer le compilateur à compacter la structure au strict nécessaire en utilisant la directive __attribute((packed))__ à la fin de la déclaration de la structure. Dans ce cas précis les pointeurs 64 bits ne seront plus alignés sur des multiples de leur taille mais collés les uns aux autres.

Lorsque une structure n'est pas alignée, le programme fonctionne quand même. lorsque le programme veut récupérer une donnée en mémoire, il sait par définition que les données ne sont pas alignées il va souvent devoir faire deux accès pour lire la données en deux foisn Aussi appliquer un __attribute((packed))__ sur ses structures peut créer de gros problèmes de performances.

struct ac_node {
    unsigned char first;
    unsigned char last;
    unsigned short match;
    struct ac_node **children;
    struct ac_node *fail;
} __attribute((packed))__;

Les mesures montrent que la quantité de mémoire utilisée ne baisse pas. En effet l'allocateur retourne des structures alignées sur des multiples de 64bits, aussi bien que les structures ne contiennent plus de trous, les trous sont créés entre elles.

Dans l'exemple ci-dessus, si la première structure est allouée à l'adresse mémoire 0 et se termien à 19, la seconde devrait être alloué à l'adresse 20, or 20 n'est pas un multiple de 8, aussi l'allocteur positionnera le bloc de mémoire demandé à l'adresse 24, ce qui laisse une trou entre 20 et 23. Gardons cette optimisation pour plus tard.

Cette modification (sans __attribute((packed))__) fait baisser la quantité de mémoire utilisée de 100ko, mais elle impacte également les performances. La mémoire occupée est maintenant de 1,8Mo et la vitesse d’exécution est de 3.6 millions de correspondances par seconde. Les performances sont en légère baisse car à chaque correspondance il faut calculer le pointeur retourné en faisant une soustraction, et il faut également pousser deux valeurs dans la stack au lieu d’une seule.

Économisons encore quelques octets

La structure de nœud actuelle pointe sur un index. Chaque nœud ayant un index, l'index est necessairement présent, ce pointeur en peut pas être NULL. Le pointeur sur l'index n'apporte rien d'un point de vue fonctionnel, il est juste pratique pour pouvoir faire grossir et relocaliser l'index au fur et a mesure que l'on crée l'arbre. Si l'on arrive à positionner l'index à un emplacement relativement fixe en mémoire par rapport à l’adresse de structure, le pointeur ne servirai plus à rien.

L’endroit fixe par rapport à la structure le plus évident est la fin de la structure. De cette manière l'index sera toujours à l'adresse de la structure à laquelle on ajoute la taille de la structure. On économise 8 octets par structure de nœud. Voila le fonctionnement et le positionnement de l'index:

Et voila son fonctionnement et son positionnement après cette optimisation. On note la disparition des octets 4 à 11 qui ne sont plus utiles.

La nouvelle structure est déclarée comme ci-dessous. Le tableau d’une taille de [0] n’est pas compté dans la taille de la structure (sizeof), en revanche il pointe sur la fin de la structure et indique la nature de l’index. C’est le développeur qui va devoir forcer la taille de l’allocation mémoire de la structure en fonction de ce qu’il veut faire.

struct ac_node {
	short match;
	unsigned char first;
	unsigned char last;
	struct ac_node *fail;
	struct ac_node *children[0];
};

La difficulté de cette évolution est qu'a chaque fois que l'index change de taille, via un realloc() la structure peut changer d'adresse. Aussi, il faut parcourir tout l'arbre pour corriger les pointeurs sur cette structure. Cela implique:

• Un temps de chargement des données plus long
• Plus de fragmentation mémoire.

Cela dit, comme statistiquement le nombre de fils est de 1, il devrait y avoir peu de reallocation mémoire.

Après la mise en place de cette évolution, on gagne 120ko de RAM. La RSS vaut maintenant 1,68Mo et on observe de meilleures performances sur la recherche de correspondance avec 3.7 millions de correspondances par seconde. Cela s’explique car l’index est plus proche en mémoire de la structure et peut donc se trouver dans le cache mémoire du CPU.

Essayons encore de faire baisser la quantité de mémoire

Cette fois ci, on va supprimer partiellement la fragmentation mémoire en faisant en sorte que les structures nécessaires à la création de l’arbre soient contiguës. Le fonctionnement de l’algorithme consiste à créer un arbre au démarrage du processus, puis de l’utiliser. Aussi lorsque l’arbre est créé les structures mémoire ne seront plus modifiées. Aussi, l’usage d’un malloc() pour chaque nœud, qui apporte de la souplesse pour supprimer ou ajouter facilement un nœud n’est pas justifié au dela de la phase de construction.

L'exemple ci-dessous montre le focntionnement de realloc() pour illustrer la création d'un trou en mémoire du à la fragmentation. Il montre par la même occasion l'usage de mémoire pour l'allocateur lui-même (notée « metadata »). Ceci n'est qu'une illustration, l'usage des metadata est plus complexe que cela.

Pour supprimer une grande partie de ces éléments, on peut allouer un gros bloc mémoire dans lequel le programme de création de l'arbre Aho-corasick ferra lui-même ses subdivisions sans utiliser l'allocateur. Il est à noter que le free n'a plus lieux d'être utilisé. En revanche, chaque fois qu'un index grossit, toutes les données de l'arbre sont décalées. Cette évolution demande donc un travail de déplacement de mémoire et de calcul d’offsets.

Après cette modification, la mémoire consommée diminue de 180ko pour un total de 1,50Mo de RSS et la vitesse d’exécution est en légère baisse à 3,69 milions de correspondances par seconde. Je ne sais pas expliqué cette baisse de vitesse, comme elle est minime je n'approfondit pas la question. Avec ce mode de fonctionnement l'indexation des mots est bien moins rapide. Bien que je ne l'ai pas mesurée, elle semble être deux fois plus lente.

Encore moins de mémoire consommée

Il reste encore une allocation dynamique, il s’agit de celle du gros bloc mémoire qui est souvent grossi via l'usage de realloc(). Chaque fois qu’il grossi, il peut potentiellement créer de la fragmentation qui augmentera la consommation mémoire du process. L’idéal serait de faire un seul bloc de la taille finale, mais il n’est pas possible de calculer cette taille sans créer l’arbre et donc utiliser de la mémoire pour cela.

Lorsqu’un processus demande de la mémoire au kernel l’augmentation du tas est définitive. Aussi, même lorsque la mémoire est libérée avec free(), elle n’est pas réellement rendue au kernel afin qu’elle soit utilisée pour un autre processus.

Linux, propose un type de mémoire qui peut être réellement libérée. Il s’agit des zones allouées avec mmap(). Mmap est conçu pour manipuler le contenu d’un fichier comme un bloc mémoire. Il permet de manipuler un fichier inexistant, et s’apparente donc à l’allocation d’un bloc mémoire. Lorsque cette zone mémoire n’est plus utilisée, elle est réellement libérée. En revanche, cette zone mémoire ne permet pas de croitre facilement. Plus précisement, sous Linux, on peut la faire grossir avec un mremap(), mais a priori pas sous MacOS, or j’utilise MacOS pour mes tests.

Maintenant que l’on sait allouer un gros bloc mémoire et travailler à l’intérieur, il est aisé de modifier et faire fonctionner l'algorithme de creation d'arbre avec un fournisseur de mémoire mmap() plutot qu'un fournisseur malloc(). Pour éviter de réallouer trop souvent de la mémoire, on fait en sorte d’allouer des blocs de 512ko, chaque fois que la mémoire nécessaire pour l’arbre dépasse 512ko, un nouveau mmap() d'une taille multiple de 512ko est fait, les données sont déplacées et l'ancien bloc est rendu au kernel avec un munmap().

A la fin de la création de l’arbre, on dispose de la taille totale des structures, mais comme l’allocation mémoire via mmap() est faite par bloc et donc par exces. Il s’agira donc de se débarrasser de cette mémoire en excès en allouant un bloc de la totalité nécessaire avec malloc(), transférant les données et libérant le bloc d'origine avec munmap().

Cette optimisation fait encore descendre la consommation mémoire de 200ko pour atteindre 1,30Mo de RSS. La vitesse d’exécution est passée à 4 millions de correspondances par seconde.

Si on prend en compte les 552ko de RSS consommés à vide par le processus, on en déduit que l’arbre tient dans 744ko, une mesure dans le code donne 684 192 octets. On est donc proche de la mémoire minimum requise.

Appliquons le __attribute((packed))__

Maintenant que toute la mémoire est compacte, on peut tester la déclaration de la structure de nœud avec __attribute((packed))__. Cela doit enlever des trous et faire encore baisser la quantité de mémoire utilisée.

Cette optimisation fait passer la RSS à 1152ko, soit une économie de 144ko. Si on prend en compte les 552ko de RSS consommés à vide par le processus, on en déduit que l’arbre tient dans 600ko, une mesure dans le code donne une taille de donnée utile de 576ko. L'ecart est negligeable. Probablement du à la mémoire consommée pour la seconde phase de cacul des failure links. L'impact sur la vitesse de match est vraiment minime car on passe de 4.03 millions de correspondances par secondes à 4.

En revanche, exposer une API avec un __attribute((packed))__ contraint l'usage de bibliothèque au compilateur qui comprennent cette directive car ce n'est pas du C standard.

La conso mémoire, et la vitesse en fonction des évolutions

La mesure initiale relative a l'évolution « raw » n'apparait car elle est relativement trop élevé et empeche de voir l'évolution de la consomation mémoire des autres améliorations. Dans la pratique, c'est la seule amélioration importante.

On peut noter que les évolutions « nofrag ». et « mmap ». ne font pas baissé la mémoire utilisée par les données, mais uniquement la RSS. En effet ces évolution améliorent l'allocaiton mémoire en reduisant la fragmentation. La mesure de mémoire utilisée ne comprends pas la fragmentation, aussi elle ne change pas.

La vitesse d'execution est difficile à expliquer car elle dépends de facteurs difficiles à mesurer, notament le contenu du cache du CPU. On peut noter que la vitesse d'execution varie peu au fur et à mesure des améliorations du code. La pire variation atteint 15.8% de baisse de performances. Bien que ce soit significatif, la performance absolu reste acceptable.

Que faire de tout ceci ?

Optimiser la consommation mémoire est un travail laborieux, mais nécessaire dans beaucoup de cas. En fonction des contraintes, on ne peut pas se permettre de gaspiller de la RAM pour économiser le cerveau du développeur. Typiquement, le domaine de l’embarqué impose souvent des quantités de mémoire très limités. Par ailleurs, à l’heure ou l’écologie est un sujet de société majeur, peut-on encore accepter de gaspiller des ressources ?