Trouver les doublons à grande échelle

Calculer l’empreinte de 300 Go de fichiers. Sur un portable. Sans le faire rendre l’âme.

La demande de fonctionnalité tenait en une phrase : trouver les fichiers en double. Les regrouper, montrer l’espace gaspillé, laisser l’utilisateur choisir quoi supprimer.

L’implémentation naïve s’écrit toute seule. On passe chaque fichier au moulin SHA-256. On regroupe par empreinte. C’est plié. Correct, déterministe, et ça devrait finir d’ici la semaine prochaine.

Sauf qu’il faut se représenter ce que « calculer l’empreinte de chaque fichier » implique sur une analyse de 5,2 millions de nœuds. On lit plus de 300 Go depuis le disque, on calcule SHA-256 sur chaque octet, sans aucun moyen de dire à l’utilisateur quand ça va finir. Sur un SSD NVMe, quelques minutes. Sur un disque dur ou un volume réseau, nettement plus. Et l’essentiel de ces E/S est du gaspillage pur : l’écrasante majorité des fichiers d’un disque ne sont le doublon de rien.

Le pipeline

L’intuition de départ : la plupart des fichiers ne peuvent tout simplement pas être des doublons, et on peut s’en assurer sans les lire. Un fichier de 4 Ko et un fichier de 400 Mo ne sont pas des doublons. Cette seule observation élimine la quasi-totalité des candidats avant la moindre E/S.

À partir de là, le pipeline empile les phases. Chacune coûte moins cher que SHA-256 et écarte des candidats supplémentaires avant que le gros du travail ne commence.

Phase 1 : regroupement par taille. On regroupe tous les fichiers par taille en octets. Ceux dont la taille est unique sont éliminés sur-le-champ. Zéro E/S. En pratique, ça dégage la grande majorité du lot. Sur un disque classique, la plupart des fichiers ont une taille qui ne se retrouve nulle part ailleurs.

Phase 2 : filtre par extension. Au sein de chaque groupe de taille, on subdivise par extension. Un .jpg et un .mp3 qui font la même taille ne seront jamais des doublons. C’est une heuristique, pas une garantie, mais elle réduit les faux positifs à bon compte et maintient l’ensemble de candidats à un niveau raisonnable.

Phase 3 : comparaison par lecture partielle. Pour les candidats qui partagent taille et extension, on lit les 4 premiers Ko de chaque fichier et on compare octet par octet avec memcmp. Beaucoup de fichiers de même taille divergent dès les premiers kilo-octets. Quelques lectures peu coûteuses et une comparaison rapide suffisent à écarter la plupart des faux positifs restants, sans toucher au reste du fichier.

Phase 4 : SHA-256. Seuls les survivants des trois phases précédentes arrivent jusqu’ici. On calcule l’empreinte d’un ensemble restreint de fichiers réellement susceptibles d’être des doublons. Le coût en E/S est bien réel, mais proportionnel aux vrais candidats, pas au disque entier.

graph TD
    A[Tous les fichiers] -->|regrouper par taille| B[Candidats de même taille]
    B -->|éliminer les tailles uniques| C[Filtre par extension]
    C -->|regrouper par taille+ext| D[Lecture partielle<br/>memcmp sur 4 Ko]
    D -->|survivants| E[Empreinte SHA-256]
    E -->|regrouper par empreinte| F[Groupes de doublons]
    F -->|lot toutes les 250ms| G[Mise à jour de l'interface]

Chaque phase élimine un ensemble de candidats progressivement plus petit, mais de plus en plus coûteux à écarter :

Les chiffres sont approximatifs et varient fortement selon le contenu du disque. Une machine de développeur remplie d’artefacts de compilation donnera des ratios très différents d’une photothèque. Le principe reste le même : la phase coûteuse ne porte que sur une fraction infime de l’ensemble initial.

Concurrence bornée

Les phases 3 et 4 impliquent des E/S. La tentation est de paralléliser à fond. Lancer une Task Swift par fichier. Laisser l’ordonnanceur se débrouiller.

Mauvaise idée pour les SSD, catastrophique pour les disques durs. Soixante requêtes d’E/S en parallèle ne font pas lire un disque soixante fois plus vite. Elles lui font passer plus de temps à décider quoi lire qu’à réellement lire. Le réglage optimal s’est révélé être 6 workers dans un TaskGroup borné, déterminé par mesure sur un SSD NVMe. Un disque dur en voudrait moins. Un RAID rapide pourrait en supporter davantage. Le nombre n’est pas le sujet. Ce qui compte, c’est que la concurrence bornée, où l’on fixe une limite et on s’y tient, bat presque toujours la concurrence débridée pour les E/S.

Le problème côté interface

L’algorithme était rapide. L’application, non.

Le mécanisme : on trouve un groupe de doublons, on l’ajoute à un tableau, on déclenche une mise à jour de l’interface. On en trouve un autre, on ajoute, on met à jour. Deux mille fois en quelques secondes. Chaque ajout forçait SwiftUI à recalculer le diff du tableau entier. Plus le tableau grossissait, plus chaque diff prenait de temps. Le thread principal accumulait du retard à chaque résultat. L’algorithme produisait des réponses plus vite que l’écran ne pouvait les afficher. Un problème de performances causé par un excès de vitesse. Je ne l’avais pas vu venir, celui-là.

La solution : le traitement par lots. Au lieu de publier chaque résultat immédiatement, le worker accumule les résultats et les transmet au @MainActor sur un minuteur de 250 ms. L’interface se rafraîchit 4 fois par seconde, quel que soit le nombre de groupes découverts entre deux envois. Le coût du diff devient constant au lieu de quadratique.

Ce motif n’est pas propre à la détection de doublons. Dès qu’un producteur à haute fréquence alimente un consommateur SwiftUI, le traitement par lots s’impose.

Les chiffres

Le gain de 3,5x, de 113 à 397 groupes par seconde, provient entièrement du traitement par lots. L’algorithme n’a pas changé. Le schéma d’E/S n’a pas changé. Seule la fréquence de transmission des résultats à la couche d’affichage a fait la différence.

C’est un schéma récurrent : la plupart des problèmes de performances dans ce type de fonctionnalités ont deux volets. L’algorithme, et le mécanisme de livraison. Il faut d’abord corriger l’algorithme, parce qu’un mauvais algorithme ne se sauve pas à coups de lots. Mais il ne faut pas s’arrêter là. Le chemin qui va du résultat calculé au pixel affiché a ses propres coûts, et ils se cumulent.

Le détecteur de doublons a été livré. Sur un cache de système de fichiers chaud, il traite une machine de développeur classique en moins d’une minute. La phase SHA-256, qui semblait constituer le problème tout entier au départ, s’est révélée être la plus petite partie. Le véritable goulot d’étranglement était un diff de tableau SwiftUI. C’est toujours ça, le goulot d’étranglement.

Références

• SHA-2 (Wikipedia): SHA-256 algorithm specification and properties.
• Apple CryptoKit documentation: Swift APIs for SHA-256 and other cryptographic operations.
• WWDC 2019: Advances in App Background Execution: Background task scheduling and concurrency constraints on Apple platforms.
• Swift TaskGroup documentation: Structured concurrency with bounded worker pools.