3 ms·

> 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 scatte

by 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/

by jjav 5y ago

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/