bc-duplicate : trouver des doublons 28 fois plus vite que fdupes

387 000 fichiers. 6,6 Go. 85 700 groupes de doublons. fdupes met 2 minutes 53 secondes. jdupes, sa version améliorée, descend à 23,5 secondes. bc-duplicate termine en 6,1 secondes.

28,8 fois plus rapide que fdupes. 3,7 fois plus rapide que jdupes. Et les résultats sont identiques – vérifié groupe par groupe sur un jeu de 86 000 fichiers.

Le goulot d’étranglement : les entrées/sorties

Trouver des doublons, c’est essentiellement un problème d’entrées/sorties. Tu dois lire le contenu de chaque fichier candidat pour le comparer aux autres. Sur 6,6 Go de données, même avec un SSD NVMe, le temps de lecture domine tout.

Le profil d’appels système de bc-duplicate le confirme :

Appel système	% du temps	Appels	Rôle
futex	23,5 %	8 841	synchronisation des fils
munmap	21,9 %	12 082	nettoyage mmap
mmap	19,7 %	12 093	lecture zéro-copie
read	13,6 %	36 152	lecture fichiers
openat	6,2 %	24 109	ouverture fichiers

Le processeur passe plus de temps à attendre le noyau qu’à calculer. Le compteur IPC (instructions par cycle) est à 0,89 – en dessous de 1,0, ce qui confirme que le travail est dominé par les entrées/sorties, pas par le calcul.

La question n’est donc pas “comment calculer plus vite” mais “comment lire moins”.

Première passe : éliminer sans lire

La première optimisation est triviale mais dévastatrice : grouper les fichiers par taille. Deux fichiers de tailles différentes ne peuvent pas être identiques. Cette étape ne lit aucun contenu – juste les métadonnées renvoyées par fstat. Elle élimine d’un coup tous les fichiers de taille unique.

Pour le regroupement, bc-duplicate utilise un tri par base (radix sort LSD) en O(n) au lieu du tri par comparaison en O(n log n) de qsort. Sur 387 000 entrées, la différence est mesurable : le radix sort élimine les défauts de prédiction de branchement qui pénalisent les tris classiques.

Deuxième passe : hachage CRC32C sur 4 Ko

Parmi les fichiers de même taille, bc-duplicate ne hache que les 4 premiers kilo-octets avec CRC32C. Pourquoi CRC32C ? Parce que c’est une instruction matérielle sur x86-64 (SSE4.2). Le calcul est quasi gratuit – quelques cycles par octet.

Et pourquoi seulement 4 Ko ? Parce que la majorité des fichiers différents de même taille divergent dans leurs premiers octets. Les en-têtes de fichiers (métadonnées EXIF, signatures PDF, horodatages) suffisent généralement à les distinguer. Lire 4 Ko au lieu de 6,6 Go, ça change tout.

Troisième passe : SHA-256 sur le contenu complet

Les fichiers qui ont la même taille ET le même CRC32C sur 4 Ko sont probablement des vrais doublons. Mais “probablement” ne suffit pas. bc-duplicate calcule alors un SHA-256 complet sur ces fichiers.

SHA-256 est aussi accéléré matériellement via l’extension SHA-NI présente sur les processeurs AMD récents (Zen+). Pas de bibliothèque externe, pas d’OpenSSL – les instructions natives du processeur font le travail.

Cette approche en deux passes minimise les entrées/sorties totales. Sur le jeu de 387 000 fichiers, seuls 12 000 fichiers environ passent par mmap pour le hachage complet (visible dans le profil : 12 093 appels mmap). Les 375 000 autres sont éliminés avant d’avoir lu plus de 4 Ko chacun.

Parallélisme à chaque étape

Chaque phase est multi-cœur :

• Parcours : un BFS (parcours en largeur) parallèle explore les répertoires. Une file circulaire évite les memmove en O(n) que ferait une file naïve à chaque lot.
• Hachage CRC32C : distribué sur 8 cœurs via un pool de tâches.
• Hachage SHA-256 : même pool, mêmes 8 cœurs.

La synchronisation entre fils utilise des futex, le mécanisme le plus léger du noyau Linux. Le profil montre 8 841 appels futex pour 23,5 % du temps – c’est le coût incompressible de la coordination.

Gestion mémoire : zéro allocation dynamique

bc-duplicate n’appelle jamais malloc en boucle. Les chemins de fichiers vont dans un allocateur en arena (un gros bloc pré-alloué, les allocations avancent un pointeur). Les entrées de fichiers vont dans un allocateur par pool (blocs de taille fixe, pas de fragmentation).

La disposition mémoire est optimisée pour le cache : les champs fréquemment accédés (chemin, taille, empreintes, drapeaux) tiennent dans la première ligne de cache (64 octets). Sur 387 000 entrées, ça réduit les défauts de cache L1 à 4,31 %.

Pourquoi fdupes est si lent

fdupes 2.3 met 2 minutes 53 secondes sur le même jeu de données. L’écart s’explique par plusieurs facteurs cumulés :

• Mono-cœur : fdupes ne parallélise ni le parcours ni le hachage.
• Hachage partiel moins agressif : fdupes 2.x fait un hachage partiel (MD5 sur les premiers octets), mais sans le filtrage en deux passes de bc-duplicate (CRC32C matériel sur 4 Ko puis SHA-256 uniquement sur les survivants). jdupes ajoute une comparaison octet par octet avant le hachage, ce qui le rend plus rapide que fdupes mais toujours mono-cœur.
• Allocations dynamiques : chaque chemin, chaque entrée passe par malloc/free, avec la fragmentation et les appels système brk/mmap que ça implique.
• Tri par comparaison : O(n log n) avec des défauts de prédiction de branchement.

jdupes corrige certains de ces problèmes (hachage partiel, optimisations diverses) et descend à 23,5 secondes. Mais il reste mono-cœur.

Exactitude vérifiée

Les benchmarks ne valent rien si les résultats sont faux. bc-duplicate est vérifié contre jdupes 1.28 sur un jeu de 86 000 fichiers : 368 groupes identiques, 899 fichiers identifiés, zéro divergence.

L’outil est aussi passé au crible des analyseurs dynamiques : ASAN (accès mémoire), UBSAN (comportements indéfinis), TSAN (concurrence) et Valgrind memcheck. Zéro fuite, zéro erreur.

Les chiffres, résumé

Outil	Temps (387K fichiers)	Facteur
bc-duplicate	6,1 s	–
jdupes 1.28	23,5 s	3,7x
fdupes 2.3	2 min 53 s	28,8x

Sur un jeu plus petit (86 000 fichiers, 1,6 Go) :

Outil	Temps	Facteur
bc-duplicate	141 ms	–
jdupes 1.28	786 ms	5,6x
fdupes 2.3	1,03 s	7,2x

Le code source est disponible sur GitHub sous licence MIT.