De 1,2 Go à 469 Mo

J’avais 5,2 millions d’objets FileNode. Je n’en avais pas besoin.

J’ai demandé à un ami de tester Renala. Il travaille dans le design graphique, il a l’oeil, et je savais qu’il serait minutieux sans me ménager. Son jugement sur ce qui tombe juste dans une interface vaut plus pour moi que la plupart des retours. Il a aussi un vieux Mac Intel avec 16 Go de RAM, et l’un de ses disques externes contenait environ 13 millions de fichiers.

Il a lancé un scan complet. Son premier retour ne portait pas sur la mémoire, mais sur ça : « Je ne comprends pas ces blocs noirs. » J’ai perdu un temps embarrassant à traquer un bug de rendu. Ce n’en était pas un. Il avait décoché l’option « En-têtes de répertoire », qui masquait le texte tout en laissant visible le fond des en-têtes. Je n’ai pas compris tout de suite, je n’avais jamais désactivé cette option moi-même.

Puis il a glissé, poliment, que le Moniteur d’activité affichait 1,2 Go de mémoire pour Renala pendant le scan et que sa machine s’était mise à swapper.

J’avais lancé le même scan des dizaines de fois sur un M3 Pro avec 18 Go. Pas une seule fois je n’avais ouvert le Moniteur d’activité. Tout développeur croit que sa machine est représentative.

Le modèle de départ était simple : une classe FileNode. Chaque instance embarquait un UUID, une chaîne de chemin, un tableau d’enfants, la taille, la date de modification et quelques drapeaux. À 5,2 millions de fichiers, ça ne tenait plus.

Cinq millions d’instances de classe, c’est cinq millions d’allocations distinctes sur le tas. Chacune embarque un surcoût dont personne n’a besoin, plus le prix d’exister comme objet séparé. La fragmentation du tas aggrave le tout : la mémoire réellement consommée dépasse la somme propre des champs. Sur une machine à 16 Go de RAM, cinq millions d’objets dispersés dans la mémoire virtuelle, c’est la différence entre « ça tourne » et « l’OS commence à swapper ».

Les chiffres ici viennent de la colonne Mémoire du Moniteur d’activité, parce que c’est celle que voit l’utilisateur quand l’app se met à swapper.¹

Le coût par FileNode se décomposait à peu près ainsi :

Avant (instance de classe FileNode) :
  UUID :              16 octets
  chaîne de chemin :  ~40 octets en moyenne (tas)
  enfants [] :        24 octets d'en-tête + 8 par enfant
  métadonnées :       ~24 octets
  surcoût objet Swift : ~16 octets
  Total par nœud :    ~120 octets
  × 5,2M nœuds = ~624 Mo (+ fragmentation du tas)

Le diagnostic était simple. Le plus dur, c’était de décider par quoi remplacer ça.

Étape 1, le modèle compact qui a validé la direction

La première passe n’était pas le design final. C’était le premier modèle compact qui rendait le problème assez petit pour qu’on puisse enfin le regarder en face.

Le seul UUID coûtait 16 octets par nœud. À 5,2 millions de nœuds, cela fait 83 Mo rien que pour les identifiants. Le premier correctif relevait de l’arithmétique : remplacer ça par un NodeID en UInt32, 4 octets pièce, 21 Mo au total. C’était suffisant.²

Le vrai poids mort, c’était la chaîne de chemin stockée.

Chaque nœud conservait son chemin complet. /Users/dinh/Library/Application Support/SomeApp/SomeSubfolder/somefile.dat. Cette chaîne est reconstructible à partir des données qu’on a déjà. Stocker le chemin complet est redondant. Mais à cette échelle, la redondance cesse d’être une commodité pour devenir une taxe : un chemin moyen de 40 à 50 octets, multiplié par 5,2 millions de nœuds, cela fait 200 Mo de chaînes qui n’ont aucune raison d’exister.

Le premier objectif compact ressemblait donc à ça :

Premier objectif compact :
  parentIndex :  4 octets (UInt32)
  nameIndex :    4 octets (UInt32)
  size :         8 octets (Int64)
  type + flags : 4 octets
  Total par nœud : 20 octets
  × 5,2M nœuds = ~104 Mo
  + plafond du pool de noms : ~156 Mo (UTF-8, ~30 octets de nom moyen)
  Total plafond : ~260 Mo

Les chemins stockés disparaissent : on les reconstruit à la demande en remontant la chaîne des parents. Le nom reste, parce qu’il faut bien afficher un nom et reconstituer le chemin. Le chemin, lui, disparaît.

graph TD
    accTitle: FileNode memory layout before and after compaction
    accDescr: The original FileNode class uses approximately 120 bytes per node (UUID, path string, children array, metadata, object overhead), totaling 624 MB for 5.2 million nodes. The compact struct target uses 20 bytes per node (parent index, name index, size, flags), totaling 104 MB.
  subgraph FN["FileNode (instance de classe, tas)"]
    FN1["UUID : 16 octets"]
    FN2["chaîne de chemin : ~40 octets (tas)"]
    FN3["enfants : [FileNode], en-tête 24 octets<br/>+ 8 octets par pointeur enfant"]
    FN4["métadonnées (taille, mtime, drapeaux) : ~24 octets"]
    FN5["surcoût objet Swift : ~16 octets"]
    FN6["Par nœud : ~120 octets<br/>5,2M nœuds : ~624 Mo + fragmentation du tas"]
  end
  subgraph SN["Premier objectif compact"]
    SN1["parentIndex : 4 octets"]
    SN2["nameIndex : 4 octets"]
    SN3["size : 8 octets"]
    SN4["type + flags : 4 octets"]
    SN5["Objectif : 20 octets<br/>5,2M nœuds : ~104 Mo + noms mutualisés"]
  end
  FN6 -.->|"remplacé par"| SN5

Ce sont des ordres de grandeur, pas des mesures au bit près, mais ils suffisaient à prouver l’idée.³ Le vrai responsable, ce n’était pas le scan. C’était la forme des objets, les chaînes redondantes et des millions de petites allocations.

Les identifiants en UInt32 et la suppression des chemins relevaient de la première passe. Cela m’a permis de récupérer des centaines de mégaoctets. La version finalement livrée est plus compliquée, plus grosse, et beaucoup plus utile.

Étape 2, le store réellement livré

La version livrée utilise toujours un ContiguousArray<SlimNode> à plat. SlimNode est une struct, pas une classe : dans un ContiguousArray, les structs sont stockées à la suite en mémoire, sans pointeur par élément sur le tas. Mais le vrai SlimNode est plus large que le premier croquis, parce qu’il doit porter autre chose qu’un beau principe.

SlimNode actuel dans le NodeStore livré :
  sizeOnDisk :       8 octets
  cloudSize :        8 octets
  id :               4 octets (UInt32)
  nameOffset :       4 octets (UInt32)
  totalFileCount :   4 octets (UInt32)
  firstChild :       4 octets (UInt32)
  childCount :       4 octets (UInt32)
  lastModifiedDays : 4 octets (UInt32)
  nameLength :       2 octets (UInt16)
  flags :            2 octets (UInt16)
  Taille de struct : 44 octets
  Pas mémoire du tableau (stride) : 48 octets
  × 5,2M nœuds = ~250 Mo

La taille de struct correspond aux champs eux-mêmes. Le pas mémoire du tableau, autrement dit le stride, est l’espacement réel en mémoire d’une entrée à la suivante, une fois ajoutés les octets de remplissage nécessaires à l’alignement, d’où 44 octets de données mais 48 octets par élément stocké.

Le FileNode d’origine contenait un tableau [FileNode] pour ses enfants. L’en-tête de ce tableau pèse 24 octets, et chaque élément est un pointeur de 8 octets vers un objet enfant alloué sur le tas. Pour un répertoire de 50 enfants : 24 + 400 octets, plus 50 allocations distinctes pour les enfants eux-mêmes.

Le NodeStore remplace tout ça par un ContiguousArray<SlimNode>. Tous les nœuds du scan vivent dans un seul bloc contigu, sans allocation séparée sur le tas pour chaque élément. Chaque SlimNode stocke l’indice de son premier enfant et le nombre d’enfants directs. Pour retrouver les enfants d’un nœud, on lit cette plage. Ni tableau d’enfants par répertoire, ni parcours complet : juste une plage du store à plat. Le prix : chaque opération sur l’arbre devient de l’arithmétique d’indices au lieu de suivre des pointeurs. Le code est moins lisible, mais la disposition mémoire est prévisible.

Le store est organisé globalement en parcours en largeur : le scan écrit les nœuds niveau par niveau, mais au sein de chaque niveau, les enfants d’un répertoire sont écrits ensemble dans un segment contigu. C’est ce qui compte pour le parcours : les frères restent groupés, la lecture suivante est prévisible, et le processeur passe moins de temps à courir après des pointeurs éparpillés.

ContiguousArray n’est pas un détail. Le type Array standard de Swift peut déjà être très efficace, mais ici ce qui compte, c’est la garantie plus stricte de contiguïté.⁴

Le pool de noms est un ContiguousArray<UInt8> unique contenant des octets UTF-8. Chaque SlimNode stocke nameOffset et nameLength, et les noms répétés sont internés (stockés une seule fois, référencés par offset) : node_modules ou index.js n’occupe qu’un seul emplacement dans le pool.

Un seul buffer d’octets, qui grossit d’un bloc, sans objet alloué séparément sur le tas pour chaque nom. Même quand tous les noms sont uniques, ces octets coûtent moins cher que des millions de String distinctes avec leurs en-têtes de stockage et leur comptage de références.

Le premier modèle compact partait du principe que la reconstruction du chemin viendrait presque toute seule avec le store à plat. Ce n’est pas ce qui s’est passé. Dans la version livrée, ce problème est traité à part. Après le scan, Renala construit parentIndex et nameIndex une bonne fois pour toutes en tâche de fond. Le code de l’interface remonte ensuite la chaîne des parents en $O(depth)$, récupère les noms et recompose le chemin. Le travail coûteux sort ainsi de la boucle de survol. C’était le vrai gain.

L’ancienne version montait à 1,2 Go pendant le scan qui a déclenché ce travail. La nouvelle se stabilise autour de 469 Mo au repos après un grand scan du même ordre. Sur le Mac Intel, plus de swap. Le scan se termine, la mémoire se calme, et le reste du système peut respirer.

Les 469 Mo ont été relevés au repos, une fois le scan terminé, pas pendant le scan ni pendant le rendu. Le pic de mémoire monte plus haut, parce que l’ancien arbre FileNode et le nouveau NodeStore se chevauchent brièvement, et parce que l’empreinte mémoire réelle inclut aussi les métadonnées de scan et le cache de rectangles du treemap.¹

Ce parcours en deux étapes explique aussi pourquoi 469 Mo n’est pas un nombre tombé du ciel. Le premier modèle compact m’a montré que le problème était soluble. La version livrée m’a montré ce que la solution coûtait réellement. Le store à plat seul représente environ 250 Mo à 5,2M nœuds. Le reste, c’est le prix à payer pour rendre ce store exploitable dans l’application réelle.⁵ Et malgré ça, on reste très loin de la version initiale, avec un gain qui se ressent immédiatement sur une machine contrainte.

La disposition à plat a apporté un bonus secondaire : la sérialisation. Des buffers contigus sont plus simples à écrire et à relire qu’un graphe d’objets récursif. Dans mes mesures, le temps d’encodage du cache a été divisé par environ 15, celui du décodage par 7,2. Le détail compte, parce que le temps de chargement du cache, c’est le temps de lancement quand on rouvre un scan sauvegardé. Un utilisateur qui a scanné la veille et relance Renala retrouve ses résultats en moins d’une seconde, sans attendre qu’un arbre soit reconstruit nœud par nœud.

Chemins non empruntés

Trois approches ont été envisagées puis abandonnées entre le premier modèle compact et la version finalement livrée.

Chargement paresseux par sous-arbre. L’idée consistait à ne matérialiser que les nœuds visibles dans la vue courante du treemap, au lieu de charger tout le scan en mémoire. Le gain de RAM aurait été réel. Mais un analyseur de disque a besoin d’un instantané complet : la recherche dans la barre latérale, la navigation par zoom et le treemap lui-même partent tous du principe que l’arbre entier est là.

Parcours DFS en direct pour reconstruire les chemins. Après la suppression des chaînes de chemin, la première version repartait dans un parcours en profondeur à chaque survol. À 5,2 millions de nœuds, chaque recherche coûtait $O(N)$. Comme le survol du treemap se déclenche en continu avec le mouvement du curseur, l’interface figeait pendant des centaines de millisecondes par chemin. Construire parentIndex et nameIndex une fois après le scan a transformé ça en remontées de chaîne en $O(depth)$.

Nom et parent dans la même entrée. Une première variante stockait (parentID: NodeID, name: String) dans le même dictionnaire, au lieu de séparer parentIndex et nameIndex. Cela fonctionnait, mais mélangeait deux tâches différentes. Les remontées de parents sont chaudes. La recherche de nom l’est beaucoup moins. Garder parentIndex comme une map légère [NodeID: NodeID] conservait un chemin chaud propre, et laisser les chaînes dans nameIndex évitait de faire remonter des données de nom dans la même API à chaque consultation.

Les relations parent-enfant, les noms, les tailles, les types : rien n’a changé. Ce qui a changé, c’est la manière de ranger la mémoire.

La première passe a supprimé le gaspillage le plus évident. La deuxième a rendu le store à plat réel. Découverte tardive : la propriété calculée .children allouait encore un Array neuf à chaque appel, copiant les références enfant dans un nouvel objet sur le tas à chaque fois. Le chemin chaud (mise en page du treemap, filtrage de la barre latérale) y passait sans arrêt. En la remplaçant par un parcours par indices à plat, le self-time de ce point d’appel est tombé de 5 432 ms à 8 ms (le logger de battement de cœur l’avait aussi signalé). Le goulot s’est déplacé. Il n’y avait plus qu’à le suivre.

Les développeurs de jeux et les programmeurs système connaissent ce réflexe : aplatir la structure, ranger les données de façon contiguë, remplacer les pointeurs par des indices. On le voit moins dans le code applicatif, parce que l’échelle l’exige rarement. À cinq millions de nœuds, elle ne demande plus la permission.

L’ami au Mac Intel m’a écrit après le correctif : « Ça a l’air bien plus rapide qu’hier, même avec le throttling thermique. Bien. » Puis : « J’ai l’impression qu’il n’y a plus de fuites mémoire. » Il n’y en avait jamais eu. Il y avait juste trop de mémoire utilisée délibérément. D’une certaine façon, c’était pire.

Références

• Detect and diagnose memory issues: WWDC 2021
• Memory Usage Performance Guidelines: Apple Developer Library
• Locality of reference: Wikipedia
• ContiguousArray: Swift Documentation