fdupes is the classic (going way way back) but it's really very slow, not worth using anymore.
The four I know are worth trying these days (depending on data set, hardware, file arrangement and other factors, any one of these might be fastest for a specific use case) are:
https://github.com/jbruchon/jdupes
https://github.com/pauldreik/rdfind
https://github.com/jvirkki/dupd
https://github.com/sahib/rmlint
Had not encountered fclones before, will give it a try.
The efficient way to do things is to just read files in parallel and break once they diverge. Basically how `cmp` works.
Example. For fileX.txt being X=1 to 10000 you have three copies of each archive in:
mydir/file-X.txt
mydir/subdir/file-X.txt and
mydir/subdir/copy/file-X.txt.
Fdupes would delete random files in mydir/, mydir/subdir/ and mydir/subdir/copy/. You would end with the remaining files scattered by all the directory tree. A mess with three incomplete copies.
Rdfind correctly guess that what most people would want is to remove entirely all files in two of the directories and keep one copy (files and tree-dir) intact. So it wipes the inner subdirs in a predictable way and keeps the outer dir intact. This is a terrific feature able to disentangle one tree directory cloned and nested into the original copy without distroying it, like in this case:
a/b/c/d/files00X.txt
a/b/a/b/c/d/files00X.txt
Computing incremental checksums in parallel and breaking up once checksums diverge does not work very well on HDDs because the files can be in distant physical locations, and that would cause lot of seeks (seeks are terribly slow on rotational drives).
That's going to be pretty slow on a hard disk because it scatters the reads causing a lot of head movement.
If all equally-sized files on your disk are duplicates, it makes you read both files in their entirety in a scatter version. That’s (expected to be) slow, indeed.
However, if most of them aren’t, chances are you find a difference in the first block read, which means you have to read only two blocks to decide they’re different.
So, what’s that distribution? Also, where is one most likely to find differences in equally-sized files? First block? Last?
But just to read the first block, you need to open both files and move the heads from one to another at least once. If the files are placed in distant cylinders, this will be a significant amount of time (a few ms).
At the beginning, fclones also processed files in each group matching by size together. But files matching by size do not necessarily live physically close to each other. Later fclones got a great speedup on HDD when I switched to processing the files in their physical order, regardless of their logical grouping. It is a bit more complex to do in terms of programming because in each grouping pass you have to "ungroup" the files to a flat list, sort the list by locations and group again, but it is really worth it (on rotational drives). You can read about this here: https://pkolaczk.github.io/disk-access-ordering/
But it's a good example why there can't be one optimal strategy for finding duplicates. Depending on the data set composition, various implementations turn out the fastest. It depends heavily on where most the files differ (or not).