4 ms·

See also fclones (focuses on performance, has benchmarks https://github.com/pkolaczk/fclones https://github.com/pkolaczk/fclones). I didn't know about rdfind bu

See also fclones (focuses on performance, has benchmarks https://github.com/pkolaczk/fclones https://github.com/pkolaczk/fclones). I didn't know about rdfind but thought the standard was fdupes https://github.com/adrianlopezroche/fdupes https://github.com/adrianlopezroche/fdupes, which is as fast (or slow) as rdfind according to fclones (and fclones is much faster).

justinsaccount 5y ago
afaik fdupes is super slow because it checksums entire files in order to find duplicates. This causes a ton of unnecessary IO if you have a lot of size collisions. The efficient way to do things is to just read files in parallel and break once they diverge. Basically how `cmp` works.
- pvaldes 5y ago
  Rdfind is the logical evolution of fdupes. Not only faster but also more clever. This does not mean that fdupes is a bad tool at all, but rdfind can do things that fdupes can't. 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
  - pkolaczk 5y ago
    Instead of trying to be clever, fclones gives the user a choice. It can select files to remove by their nesting level, creation/update/access time or glob expression (include/exclude). It also allows the user to modify the list of found files before deleting.
- pkolaczk 5y ago
  jdupes, rdfind, fclones and possibly many others compute checksums of prefixes (and sometimes suffixes) of the files. That reduces the number of files to be fully hashed. 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).
- jjav 5y ago
  > The efficient way to do things is to just read files in parallel and break once they diverge. That's going to be pretty slow on a hard disk because it scatters the reads causing a lot of head movement.
  - Someone 5y ago
    That depends on the distribution of offsets at which a difference is found (if any) 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?
    - jjav 5y ago
      Well yes, that's all true. The approach of alternating reads of blocks is slow only if you need to do it. If there's a diff in the first block (or so) then there's not much to read. 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).
    - pkolaczk 5y ago
      > However, if most of them aren’t, chances are you find a difference in the first block read, 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/ https://pkolaczk.github.io/disk-access-ordering/
- deleted 5y ago
  [deleted]
jjav 5y ago
I use and test assorted duplicate finders regularly. 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/jbruchon/jdupes https://github.com/pauldreik/rdfind https://github.com/pauldreik/rdfind https://github.com/jvirkki/dupd https://github.com/jvirkki/dupd https://github.com/sahib/rmlint https://github.com/sahib/rmlint Had not encountered fclones before, will give it a try.

justinsaccount 5y ago

afaik fdupes is super slow because it checksums entire files in order to find duplicates. This causes a ton of unnecessary IO if you have a lot of size collisions. The efficient way to do things is to just read files in parallel and break once they diverge. Basically how `cmp` works.

pvaldes 5y ago
Rdfind is the logical evolution of fdupes. Not only faster but also more clever. This does not mean that fdupes is a bad tool at all, but rdfind can do things that fdupes can't. 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
- pkolaczk 5y ago
  Instead of trying to be clever, fclones gives the user a choice. It can select files to remove by their nesting level, creation/update/access time or glob expression (include/exclude). It also allows the user to modify the list of found files before deleting.
pkolaczk 5y ago
jdupes, rdfind, fclones and possibly many others compute checksums of prefixes (and sometimes suffixes) of the files. That reduces the number of files to be fully hashed. 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).
jjav 5y ago
> The efficient way to do things is to just read files in parallel and break once they diverge. That's going to be pretty slow on a hard disk because it scatters the reads causing a lot of head movement.
- Someone 5y ago
  That depends on the distribution of offsets at which a difference is found (if any) 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?
  - jjav 5y ago
    Well yes, that's all true. The approach of alternating reads of blocks is slow only if you need to do it. If there's a diff in the first block (or so) then there's not much to read. 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).
  - pkolaczk 5y ago
    > However, if most of them aren’t, chances are you find a difference in the first block read, 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/ https://pkolaczk.github.io/disk-access-ordering/
deleted 5y ago
[deleted]

jjav 5y ago

I use and test assorted duplicate finders regularly. 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/jbruchon/jdupes https://github.com/pauldreik/rdfind https://github.com/pauldreik/rdfind https://github.com/jvirkki/dupd https://github.com/jvirkki/dupd https://github.com/sahib/rmlint https://github.com/sahib/rmlint Had not encountered fclones before, will give it a try.