Trouver les doublons à grande échelle

Calculer l’empreinte de 300 Go de fichiers, sur un portable, sans lui faire rendre l’âme.

Le besoin 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 : passer chaque fichier au moulin SHA-256, regrouper par empreinte, c’est réglé.¹ Correct, déterministe, et ça finira d’ici la semaine prochaine.

Sauf que « calculer l’empreinte de chaque fichier » sur 5,2 millions de nœuds, ce n’est pas anodin : 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. Avec 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, sans la moindre E/S. En pratique, ça écarte la grande majorité du lot : sur un disque classique, la plupart des fichiers ont une taille unique.

Phase 2 : filtre par nom. Au sein de chaque groupe de taille, on subdivise par nom de fichier (insensible à la casse). Un report.pdf et un backup.pdf qui font la même taille ne seront pas des doublons. C’est une heuristique, pas une garantie : elle peut rater des doublons quand une copie a été enregistrée sous un autre nom.² Mais elle réduit l’ensemble des candidats à peu de frais, et en pratique le compromis en vaut la peine.

Phase 3 : comparaison par lecture partielle. Pour les candidats qui partagent taille et nom, on lit les 8 premiers Ko de chaque fichier et on compare octet par octet avec memcmp.³ Si les préfixes correspondent, on lit aussi les 8 derniers Ko pour comparer les suffixes. Ce contrôle de suffixe détecte 1,9 % des candidats identiques au début mais divergents à la fin. 1,9 %, un chiffre négligeable en apparence, jusqu’à ce qu’on mesure le prix de chaque comparaison évitée : un passage SHA-256 complet sur un fichier potentiellement de plusieurs gigaoctets.

Phase 3.5 : hash unique pour les paires. Quand il ne reste que deux fichiers dans un groupe, il existe un raccourci qui évite de calculer l’empreinte des deux copies. On lit les deux en parallèle, en comparant chaque bloc avec memcmp tout en calculant l’empreinte du premier fichier seulement. Si tous les blocs correspondent, les deux fichiers sont identiques de façon certaine, et l’empreinte unique sert de signature partagée. Si un bloc diverge, on s’arrête sans finir la lecture de l’un ou l’autre.

59,2 % des groupes atteignant cette étape étaient des paires : dans le cas majoritaire, une seule passe de lecture et un seul hash suffisaient.

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

graph TD
    accTitle: Multi-phase duplicate detection pipeline
    accDescr: Files are grouped by size, then unique sizes eliminated. Remaining candidates pass through a name filter, an 8 KB prefix and suffix comparison, a hash-once step for pairs, and finally full SHA-256 hashing. Confirmed duplicate groups are batched to the UI every 250 ms.
    A[Tous les fichiers] -->|regrouper par taille| B[Candidats de même taille]
    B -->|éliminer les tailles uniques| C[Filtre par nom]
    C -->|regrouper par taille+nom| D[Lecture partielle<br/>8 Ko préfixe+suffixe]
    D -->|préfixe+suffixe ok| D2[Hash unique pour les paires]
    D2 -->|groupes restants| 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 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 goroutine Go, ou une Task Swift, par fichier et 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 saturent la file d’E/S et ajoutent de la contention dans la pile de drivers.⁴ Le bon réglage, mesuré sur un SSD NVMe avec de petites lectures aléatoires, était de 6 workers dans un TaskGroup avec un plafond de concurrence manuel.⁵ 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 : trouver un groupe de doublons, l’ajouter au tableau, déclencher une mise à jour de l’interface. Puis un autre groupe, un autre ajout, une autre mise à jour, deux mille fois en quelques secondes. Chaque ajout forçait SwiftUI à réconcilier toute la liste de résultats : diff des identités de vues, calcul du layout, puis transmission au moteur de rendu.⁶ Plus le tableau grossissait, plus chaque mise à jour 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.

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 toutes les 250 ms. L’interface se rafraîchit 4 fois par seconde, quel que soit le nombre de groupes découverts entre deux envois, et le coût de mise à jour par lot devient constant au lieu de croître avec le tableau.

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

Débit mesuré via PerfLogWriter sur M3 Pro, cache NVMe chaud.⁷ Référence : traitement séquentiel mono-thread. Optimisé : TaskGroup à 6 workers + vidage par lots de 250 ms.

Le gain est d’environ 300× de bout en bout, du traitement séquentiel mono-thread à une architecture en pipeline avec mises à jour groupées de l’interface. Le changement d’algorithme (l’élimination multi-phase) a réduit les E/S radicalement, et le traitement par lots a éliminé la tempête de diffs SwiftUI. Ni l’un ni l’autre n’aurait suffi seul ; ensemble, ils ont transformé une fonctionnalité qui semblait cassée en une qui se termine en quelques secondes.

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 pipeline d’affichage. Corriger l’algorithme d’abord, parce qu’aucun traitement par lots ne rattrape un mauvais algorithme ; mais ne 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é. Avec 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 avérée la plus petite partie. Le véritable goulot d’étranglement était le cycle de mise à jour de SwiftUI. Quand une longue liste se met à jour à haute fréquence, c’est généralement là que ça coince.

Références

• SHA-2 (Wikipedia) : Spécification et propriétés de l’algorithme SHA-256.
• Apple CryptoKit documentation : API Swift pour SHA-256 et autres opérations cryptographiques.
• Swift TaskGroup documentation : Concurrence structurée pour la gestion dynamique de tâches enfants.