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’œil pour les interfaces, et je savais qu’il serait minutieux et qu’il ne mâcherait pas ses mots. Son jugement sur la justesse d’un rendu et d’une expérience vaut plus que la plupart des retours que je peux recevoir. Il possède aussi un vieux Mac Intel avec 16 Go de RAM, et l’un de ses disques externes contenait quelque chose comme 13 millions de fichiers.

Il a lancé un scan complet. La première chose qu’il a signalée, ce n’était pas la mémoire. C’était : « Je ne comprends pas ce que sont les blocs noirs. » Des rectangles sombres éparpillés sur le treemap, sans texte visible. J’ai passé un temps gênant à traquer un bogue de rendu : problèmes de repli de police, écarts d’espace colorimétrique entre Intel et Apple Silicon, cas limites en mode sombre. Rien de tout ça n’était le problème. Le problème, c’est qu’il avait décoché l’option « En-têtes de répertoire », ce qui masquait le texte des étiquettes tout en laissant visible l’arrière-plan des en-têtes. Des blocs noirs sans texte. Je n’avais pas fait le lien parce que je n’avais moi-même jamais désactivé cette option.

Puis il a mentionné, poliment, que le Moniteur d’activité affichait 1,2 Go de RAM 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 données d’origine était simple. FileNode était une classe. Chaque instance portait un UUID, une chaîne de chemin stockée, un tableau d’enfants, la taille, la date de modification et quelques drapeaux. Pour 5,2 millions de fichiers, c’était un problème.

Cinq millions d’instances de classe, c’est cinq millions d’allocations distinctes sur le tas. Chacune transporte un compteur de références, des métadonnées de type et un bourrage d’alignement que personne n’a demandé. La fragmentation du tas fait que la mémoire réellement consommée dépasse la somme des tailles des objets. 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 ».

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)

Après (struct SlimNode dans ContiguousArray) :
  parentIndex :  4 octets (UInt32)
  nameIndex :    4 octets (UInt32)
  size :         8 octets (Int64)
  nodeType :     1 octet
  flags :        1 octet
  pad :          2 octets
  Total par nœud : 20 octets
  × 5,2M nœuds = ~104 Mo
  + pool de noms : ~156 Mo (UTF-8, ~30 octets de nom moyen)
  Total : ~260 Mo

Le UUID seul pesait 16 octets par nœud. Pour 5,2 millions de nœuds : 83 Mo rien que pour les identifiants. Le correctif pour cette partie relève de l’arithmétique pure : passer à un NodeID en UInt32, 4 octets pièce, total 21 Mo. Un UInt32 adresse 4,2 milliards de nœuds, bien au-delà de ce qu’un scan de disque produira jamais.

La chaîne de chemin stockée posait un problème plus lourd.

Chaque nœud conservait son chemin complet. /Users/dinh/Library/Application Support/SomeApp/SomeSubfolder/somefile.dat. Cette chaîne se reconstitue à tout moment à partir de deux informations déjà disponibles : le chemin du parent et le nom propre du nœud. Stocker le chemin complet est redondant. Mais la redondance à grande échelle cesse d’être un choix d’architecture pour devenir un gouffre de mémoire : un chemin moyen de 40 à 50 octets, multiplié par 5,2 millions de nœuds, ça fait 200 Mo de chaînes qui n’ont aucune raison d’exister.

Supprimer les chemins stockés. Reconstruire à la demande en remontant la chaîne des parents. Le nom reste, parce qu’on en a besoin pour l’affichage et la reconstruction. Le chemin, lui, disparaît.

graph TD
    subgraph FN["FileNode (instance de classe, tas)"]
        FN1["UUID — 16 octets"]
        FN2["chaîne de chemin — ~40 octets (tas)"]
        FN3["enfants : [FileNode] — 24 octets d'en-tête<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["SlimNode (struct, ContiguousArray)"]
        SN1["parentIndex : UInt32 — 4 octets"]
        SN2["nameIndex : UInt32 — 4 octets"]
        SN3["size : Int64 — 8 octets"]
        SN4["nodeType + flags + pad — 4 octets"]
        SN5["Par nœud : 20 octets<br/>5,2M nœuds : ~104 Mo + ~156 Mo pool de noms"]
    end
    FN6 -.->|"remplacé par"| SN5

Chiffres approximatifs. Le coût de SlimNode inclut la part proportionnelle du pool de noms (~30 octets par nœud en moyenne). La mémoire de travail effective ajoute les métadonnées de scan et le cache de rectangles du treemap par-dessus.

Supprimer les chemins obligeait aussi à repenser les enfants.

Le FileNode original contenait un tableau [FileNode] pour ses enfants. L’en-tête de ce tableau pèse 24 octets (pointeur, longueur, capacité). 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 sur le tas pour les enfants eux-mêmes.

Le NodeStore remplace tout ça par un ContiguousArray<SlimNode>. Chaque nœud du scan entier vit dans un seul bloc de mémoire contiguë. Les relations parent-enfant s’expriment par des paires d’indices : chaque SlimNode stocke un parentIndex (la position du parent dans le tableau) et un nameIndex (le décalage de son nom dans un pool de noms UTF-8 séparé). Pour retrouver les enfants d’un nœud, on parcourt le tableau à la recherche des entrées dont le parentIndex correspond.

Le tableau est rempli en ordre de parcours en profondeur pendant le scan : les enfants se retrouvent adjacents à leur parent en mémoire. Trouver tous les enfants du nœud N revient à balayer un segment contigu du tableau. Pas de déréférencement de pointeurs, pas d’accès mémoire aléatoire.

ContiguousArray a son importance ici. Le Array standard de Swift ne garantit pas un stockage contigu. ContiguousArray le garantit : les éléments sont empaquetés en mémoire, le prefetcher du processeur peut anticiper les accès séquentiels, et les lignes de cache se chargent en avance. Pour 5,2 millions de nœuds, c’est la différence entre des succès de cache et des défauts de cache à chaque parcours.

Le pool de noms est un unique blob Data contenant tous les noms concaténés en UTF-8 brut. Le nameIndex dans SlimNode est un décalage en octets dans ce pool. La fin de chaque nom est repérée par un tableau parallèle de décalages.

Un seul blob, une seule allocation, zéro surcoût par nom sur le tas. Le nom de fichier moyen fait environ 30 octets. 5,2 millions de noms : environ 156 Mo dans le pool, dans une seule allocation contiguë. Comparez ça à 5,2 millions d’allocations String séparées sur le tas, chacune avec son propre comptage de références et ses métadonnées.

La reconstruction du chemin quand on en a besoin : lire le nameIndex du nœud, lire celui du parent, remonter la chaîne des parentIndex jusqu’à la racine, concaténer avec des barres obliques. On ne fait ça que quand l’interface a besoin d’afficher un chemin ou d’ouvrir un fichier. Ce n’est jamais sur un chemin d’exécution à chaud.

Le résultat : de 1,2 Go à 469 Mo au repos pour un scan de 5,2 M nœuds sur M3 Pro. Sur le Mac Intel, plus de swap. Le scan se termine, la mémoire se stabilise, et le reste du système d’exploitation peut respirer.

Les 469 Mo dépassent le minimum théorique calculé plus haut, parce que l’arbre FileNode reste en vie pendant la transition, les métadonnées de scan ajoutent du surcoût, et le cache de rectangles du treemap consomme de la mémoire supplémentaire pendant le rendu. L’estimation de 260 Mo concernait le store seul. En pratique, l’ensemble de travail est plus gros. Mais il pèse 60 % de moins que la version initiale, et la différence se ressent immédiatement sur du matériel contraint.

Les relations parent-enfant n’ont pas changé. Les noms, les tailles, les types sont les mêmes. Ce qui a changé, c’est la disposition en mémoire : une seule allocation qui contient tout, avec des indices entiers là où il y avait des pointeurs.

Les développeurs de jeux et les programmeurs système appellent ça le motif « struct of arrays ». On le voit rarement dans le code applicatif, parce que l’échelle le justifie rarement. À cinq millions de nœuds, l’échelle ne demande pas la permission.

L’ami au Mac Intel m’a envoyé un message 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 avait jamais eu de fuites mémoire. Il y avait juste trop de mémoire utilisée à dessein. En un sens, c’était pire.

References

• Identify trends with the Power and Performance API: WWDC 2020
• Detect and diagnose memory issues: WWDC 2021
• Memory Usage Performance Guidelines: Apple Developer Library
• Locality of reference: Wikipedia
• ContiguousArray: Swift Documentation