Is “dupd” really faster than my duplicate scanner “jdupes?”

UPDATE: I posted this and went to sleep. After I woke up, my inbox was full of issue report and pull request comments and closings. dupd now supports relative path arguments, has a larger I/O block size, and I patched a bug that caused total failure on XFS. That’s awesome!

Why am I picking on dupd?

I have written about my duplicate scanner “jdupes” in a previous post and have spent a lot of time enhancing it. I have run across two different blog posts online about duplicate file finders that compare jdupes with another scanner called “dupd” and proclaims dupd the clear speed winner for finding duplicate files. One post is by Eliseo Papa, comparing jdupes (when it was briefly called “fdupes-jody”) against dupd and showing that dupd was insanely faster, but used significantly more CPU and RAM. The other is by the dupd developer Jyri J. Virkki with a much newer version of jdupes than Eliseo used, finding that the scanned home directory with over 160,000 files was scanned by jdupes in approximately double the time as by dupd. Eliseo was using what today would be considered a very old and slow version of my program. Eliseo also tested a lot of scanners and didn’t provide any actual commands or methodology beyond a simple overview, though that’s completely understandable given how many programs were involved and that each one probably worked very differently. I’m more interested in Jyri’s results; Jyri provides actual command usage so I can attempt to replicate those results on my own systems. If dupd is double the speed of jdupes, I’d love to know how it’s being done, but first I must run some tests to verify that this is true.

Please note that I’m not really “picking on” dupd. It has been declared better than my own duplicate scanner by a third party and by the developer. There’s some pretty brilliant programming work in dupd and I have thoroughly enjoyed reading the code. This is intended to be a respectful rebuttal due to a combination of my own pride in my work and some obvious issues with Jyri’s testing. With that said, let’s discuss!

Methodology

Here’s a brief overview of the rest of this post.

1. Use dupd and understand how to use it
2. Explain the problem with Jyri’s tests
3. Compile the latest version of both programs (GitHub master source)
4. Detail of test system and test data
5. Attempt to replicate Jyri’s results with a large data set on one of my machines
6. Run my own benchmark tests to see which one is actually faster for me
7. Final thoughts

Use and understand dupd

I ran into some immediate problems and quirks with how dupd works. Within about 15 minutes, I realized that dupd is a very different beast from jdupes. Where jdupes operates on the specified directories and saves no state anywhere between program runs, dupd will maintain an SQLite database in your home directory (by default) with the information it finds during its file scans. I tested dupd somewhere that had a directory with a backtick in the name and dupd skipped it; this is due to the use of a backtick as the SQLite separator character; dupd auto-ignores anything with a backtick to avoid potential problems with SQLite queries (–pathsep provides a workaround but this is still not quite ideal). dupd also doesn’t provide a way to ignore hard linked file pairs, so it’s up to the user to check the inode/device number pairs of dupd’s reported duplicate files with a command like stat if this is an important thing.

The most painful flaw I’ve found in dupd (and the one that gave me the most difficulty in working with it) is the file path specification restrictions. They’re absolutely maddening for my purposes because specifying paths is difficult. With jdupes I can arbitrarily work with multiple directories and use shell wildcard expansion to pick them out, but dupd only takes its file paths two ways: the implicit default of the current directory or one or more absolute paths (starting from /) which must each be prefixed with the -p or –path option. I can type something like “cd /home/user/food; jdupes -nr A* B*” but dupd requires that I type out e.g. “dupd scan –path /home/user/food/Apple –path /home/user/food/Avocado –path /home/user/food/Bacon –path /home/user/food/Broccoli” to selectively scan the same data set. For this reason, I restricted my testing to a single directory, passing nothing to dupd and passing a single dot to jdupes.

Why Jyri’s tests are flawed

There are some flaws that make Jyri’s “dupd vs. jdupes” tests unfair, mostly due to mismatched overhead:

• dupd’s use of SQLite; to perform an apples-to-apples comparison, the –nodb switch is mandatory to disable this feature and dump the duplicate list to stdout just like jdupes.
• Jyri’s test performed a duplicate scan with dupd which produced no output (no –nodb option and no run of “dupd report”) whereas jdupes produced full output
• In addition to producing output, jdupes dumped that output to a file on disk
• The jdupes progress indicator wasn’t disabled; progress indication blocks while printing to the terminal, slowing execution significantly for the sake of user-friendliness
• Jyri’s tests were only run on cached data (high CPU, run times didn’t deviate) which tests algorithm speed but not performance when reading uncached data on a rotating disk

Compile the latest versions of each

For the record, I used dupd at commit 8f6ea02 and jdupes at commit 14d92bc in this test. If you want to attempt to replicate my results, you’ll need these exact revisions.

Test system and test data set

The system in use has an AMD A8-7600 quad-core CPU, 8GB of DDR3-1600 RAM, and 3x3TB 7200RPM SATA-6G hard drives. The drives are configured as a Linux md raid5 using the XFS filesystem (mounted with ‘noatime’). The deadline I/O scheduler is used for all physical devices. Maximum raw streaming read (measured with ‘pv’) on this array tops out at 374 MiB/sec near the beginning of the array and is about half as fast at the end. The array contains an “aged filesystem” which has some file fragmentation and probably has significantly less than ideal distribution of files relative to one another, making it an excellent choice for testing the program differences in a less artificial manner.

The test system is a dedicated, isolated system. It is not running anything other than the benchmarks. The CPU scaling governor is set to “performance” to lock the CPU at maximum speed and remove deviations caused by CPU frequency changes.

The first data set is a large collection of over 48,000 files that are stored in 135 subdirectories with no further subdirectories of their own. The average file size is 495 KB, while the smallest file is 925 bytes and the largest file is 3.3 MB. Total size is 23 GB. There are five hard-linked sets of files between them, but none are duplicates otherwise, so this is sort of a worst-case scenario because all actual duplicate scan comparison work is wasted effort.

The second data set is a smaller set of over 31,000 files in 12 subdirectories and 762 total directories (find -type d | wc -l). The average file size is 260 KB, the smallest file is 40 bytes while the largest file is 6.3 MB. Total size is 7.8 GB. There are no hard linked pairs and there are 208 duplicate files in 39 duplicate sets, occupying 23 MB.

Attempt to replicate Jyri’s tests

Jyri ran the following commands:

repeat 5 time ./jdupes -r $HOME -A  > out

repeat 5 time dupd scan -p $HOME -q

To normalize the results, I’ll read all the files so they’ll populate the disk cache as Jyri seems to have done. I will run the Bash equivalent of these commands on my data set as my first tests. I also ran

$ export TIMEFORMAT='%Us user %Ss system %P%% cpu %E total'

to get timing output similar to Jyri’s time measurement output. I have erased the jdupes progress output beyond the first run for aesthetic reasons.

Data set 1

$ X=0; while [ $X -lt 5 ]; do time jdupes -r . -A > out; X=$((X + 1)); done
Examining 48271 files, 135 dirs (in 1 specified)
0.043s user 0.060s system 96.47% cpu 0.107 total
0.027s user 0.080s system 97.53% cpu 0.109 total
0.043s user 0.060s system 95.55% cpu 0.108 total
0.040s user 0.067s system 97.02% cpu 0.110 total
0.037s user 0.067s system 95.76% cpu 0.108 total

$ X=0; while [ $X -lt 5 ]; do time dupd scan -q; X=$((X + 1)); done
0.110s user 0.087s system 36.43% cpu 0.540 total
0.120s user 0.077s system 67.83% cpu 0.290 total
0.117s user 0.077s system 67.13% cpu 0.288 total
0.110s user 0.083s system 67.80% cpu 0.285 total
0.120s user 0.077s system 53.00% cpu 0.371 total

Even with Jyri’s switch choices which are biased towards dupd, dupd is still 2.5 times slower (or worse) than jdupes here. Surprisingly, the wild time deviation seen above happened in nearly every run. The closest run to any consistency circled around 0.300 total time. This test implies that if there are almost no duplicates, dupd wastes significantly more time than jdupes.

Data set 2

$ X=0; while [ $X -lt 5 ]; do time jdupes -r . -A > out; X=$((X + 1)); done
Examining 31663 files, 762 dirs (in 1 specified)
0.037s user 0.060s system 99.88% cpu 0.097 total
0.040s user 0.053s system 67.59% cpu 0.138 total
0.027s user 0.067s system 97.13% cpu 0.096 total
0.020s user 0.073s system 96.78% cpu 0.096 total
0.027s user 0.067s system 96.71% cpu 0.096 total

$ X=0; while [ $X -lt 5 ]; do time dupd scan -q; X=$((X + 1)); done
0.090s user 0.077s system 79.69% cpu 0.209 total
0.100s user 0.070s system 82.49% cpu 0.206 total
0.107s user 0.067s system 60.84% cpu 0.285 total
0.090s user 0.080s system 80.92% cpu 0.210 total
0.097s user 0.077s system 81.33% cpu 0.213 total

I chose the most favorable run for the dupd results; the highest total time reported was 0.561 but similar inconsistency to data set 1 was also present here. Regardless, dupd is still over two times slower than jdupes on this data set.

My benchmarks of jdupes vs. dupd

I wanted to run thorough tests on both programs to compare both algorithmic and real-world performance. I also wanted to see how the use of SQLite affects dupd’s performance since that is a major difference and could be adding some overhead. I ran one set of tests with all scanned file data already in the block cache to test the algorithm’s raw speed (no disk access other than possibly dupd’s SQLite accesses) and another with drives synced and disk caches dropped prior to each run using “sync; echo 3 > /proc/sys/vm/drop_caches”. I tested dupd with and without the –nodb option to see if it made any difference. I turned off all forms of jdupes output except printing the final duplicate list. All program output for both programs was redirected to /dev/null to eliminate any waiting resulting from I/O blocking on terminals or disks. The dupd SQLite database was purged during all runs.

Cached (algorithmic) performance: data set 1

$ X=0; while [ $X -lt 5 ]; do time jdupes -Arq . >/dev/null; X=$((X + 1)); done
0.047s user 0.053s system 98.33% cpu 0.102 total
0.053s user 0.047s system 99.30% cpu 0.101 total
0.033s user 0.067s system 98.95% cpu 0.101 total
0.043s user 0.053s system 96.32% cpu 0.100 total
0.027s user 0.073s system 99.09% cpu 0.101 total

$ X=0; while [ $X -lt 5 ]; do rm -f ~/.dupd_sqlite; sync; time dupd scan -q >/dev/null 2>/dev/null; X=$((X + 1)); done
0.087s user 0.110s system 91.32% cpu 0.215 total
0.110s user 0.087s system 91.61% cpu 0.215 total
0.107s user 0.090s system 90.56% cpu 0.217 total
0.120s user 0.077s system 68.85% cpu 0.286 total
0.117s user 0.077s system 92.83% cpu 0.208 total

$ X=0; while [ $X -lt 5 ]; do rm -f ~/.dupd_sqlite; sync; time dupd scan -q --nodb >/dev/null 2>/dev/null; X=$((X + 1)); done
0.100s user 0.093s system 140.85% cpu 0.137 total
0.117s user 0.073s system 140.16% cpu 0.136 total
0.110s user 0.080s system 140.22% cpu 0.136 total
0.100s user 0.090s system 139.95% cpu 0.136 total
0.113s user 0.077s system 140.69% cpu 0.135 total

Wow! dupd’s performance went up significantly with the –nodb option! This seems to prove that SQLite is slowing things down for these one-shot runs. Even with the 30+% performance boost, the dupd algorithm still seems to be 35% slower than jdupes despite dupd having the obvious advantage of multi-threaded execution.

Cached (algorithmic) performance: data set 2

 $  X=0; while [ $X -lt 5 ]; do time jdupes -Arqm . >/dev/null; X=$((X + 1)); done
0.027s user 0.063s system 99.29% cpu 0.091 total
0.037s user 0.050s system 95.70% cpu 0.091 total
0.040s user 0.047s system 95.93% cpu 0.090 total
0.033s user 0.057s system 99.29% cpu 0.091 total
0.033s user 0.053s system 96.08% cpu 0.090 total

$ X=0; while [ $X -lt 5 ]; do rm ~/.dupd_sqlite; sync; time dupd scan -q >/dev/null 2>/dev/null; X=$((X + 1)); done
0.090s user 0.080s system 58.91% cpu 0.289 total
0.107s user 0.063s system 82.97% cpu 0.205 total
0.110s user 0.060s system 65.64% cpu 0.259 total
0.110s user 0.060s system 47.40% cpu 0.359 total
0.100s user 0.073s system 59.90% cpu 0.289 total

$ X=0; while [ $X -lt 5 ]; do rm -f ~/.dupd_sqlite; sync; time dupd scan -q --nodb >/dev/null 2>/dev/null; X=$((X + 1)); done
0.113s user 0.053s system 136.57% cpu 0.122 total
0.103s user 0.063s system 136.45% cpu 0.122 total
0.107s user 0.060s system 138.46% cpu 0.120 total
0.097s user 0.067s system 136.78% cpu 0.119 total
0.090s user 0.077s system 137.49% cpu 0.121 total

For some reason, this data set significantly slowed down the SQLite-enabled run of dupd. It’s now about three times slower than jdupes. A major speedup with –nodb appears again, keeping in line with the approximate 1/3 slower performance than jdupes seen in the previous test.

Real-world performance: data set 1

# X=0; while [ $X -lt 5 ]; do sync; echo 3 > /proc/sys/vm/drop_caches; time jdupes -Arq . >/dev/null; X=$((X + 1)); done
 0.210s user 0.790s system 1.52% cpu 65.432 total
 0.190s user 0.730s system 1.39% cpu 66.036 total
 0.137s user 0.780s system 1.39% cpu 65.574 total
 0.230s user 0.813s system 1.59% cpu 65.361 total
 0.167s user 0.800s system 1.47% cpu 65.444 total

 # X=0; while [ $X -lt 5 ]; do rm -f ~/.dupd_sqlite; sync; echo 3 > /proc/sys/vm/drop_caches; time dupd scan -q >/dev/null 2>/dev/null; X=$((X + 1)); done
0.293s user 0.890s system 1.74% cpu 67.809 total
0.273s user 0.960s system 1.81% cpu 67.766 total
0.243s user 0.873s system 1.64% cpu 68.069 total
0.247s user 0.910s system 1.70% cpu 67.965 total
0.267s user 0.827s system 1.61% cpu 67.830 total

# X=0; while [ $X -lt 5 ]; do rm -f ~/.dupd_sqlite; sync; echo 3 > /proc/sys/vm/drop_caches; time dupd scan -q --nodb >/dev/null 2>/dev/null; X=$((X + 1)); done
0.273s user 0.767s system 1.54% cpu 67.403 total
0.253s user 0.930s system 1.75% cpu 67.448 total
0.233s user 0.817s system 1.55% cpu 67.409 total
0.223s user 0.890s system 1.63% cpu 67.908 total
0.273s user 0.987s system 1.83% cpu 68.511 total

AHA! Now that we’re testing on real disks with a large uncached workload, the story is very different. Neither jdupes nor dupd will make your hard drives faster. While dupd is still slower, the extra two or three seconds pales in comparison to the disk I/O time, bringing the performance gap down to an insignificant ~3.7%. Note that –nodb didn’t make a significant difference this time either. No one will ever notice that 0.3-0.4 second speedup.

Real-world performance: data set 2

# X=0; while [ $X -lt 5 ]; do sync; echo 3 > /proc/sys/vm/drop_caches; time jdupes -Arq . >/dev/null; X=$((X + 1)); done
 0.140s user 0.610s system 1.40% cpu 53.333 total
 0.147s user 0.717s system 1.56% cpu 55.284 total
 0.160s user 0.683s system 1.52% cpu 55.268 total
 0.173s user 0.710s system 1.60% cpu 54.890 total
 0.157s user 0.697s system 1.55% cpu 54.968 total

X=0; while [ $X -lt 5 ]; do rm -f ~/.dupd_sqlite; sync; echo 3 > /proc/sys/vm/drop_caches; time dupd scan -q >/dev/null 2>/dev/null; X=$((X + 1)); done
0.227s user 0.730s system 1.69% cpu 56.389 total
0.220s user 0.817s system 1.82% cpu 56.755 total
0.250s user 0.760s system 1.77% cpu 56.785 total
0.230s user 0.773s system 1.79% cpu 56.044 total
0.223s user 0.750s system 1.73% cpu 56.241 total

# X=0; while [ $X -lt 5 ]; do rm -f ~/.dupd_sqlite; sync; echo 3 > /proc/sys/vm/drop_caches; time dupd scan -q --nodb >/dev/null 2>/dev/null; X=$((X + 1)); done
0.293s user 0.750s system 1.83% cpu 56.803 total
0.237s user 0.727s system 1.71% cpu 56.052 total
0.247s user 0.773s system 1.82% cpu 55.988 total
0.177s user 0.873s system 1.86% cpu 56.439 total
0.217s user 0.820s system 1.83% cpu 56.409 total

Data set 1 and data set 2 have the same results. When disk access overhead is included in testing, the algorithmic speed differences don’t seem to make a significant difference overall.

Real-world performance: data set 3 (bonus round)

Based on the tight match with lots of files generally around 0.5 MB in size, I decided to do some extra real-world tests. Data set 3 is all of my personal photography, scanned family photos, and video clips from a combination of my various Android phones and my Canon T1i DSLR. Statistics: over 18500 files in 395 directories, average size 2.6 MB, smallest 0, largest 552 MB, 47GB total, no duplicates or hard links at all.

# X=0; while [ $X -lt 5 ]; do sync; echo 3 > /proc/sys/vm/drop_caches; time jdupes -Arq . >/dev/null; X=$((X + 1)); done
0.030s user 0.243s system 2.02% cpu 13.483 total
0.043s user 0.247s system 2.14% cpu 13.542 total
0.040s user 0.230s system 2.03% cpu 13.245 total
0.030s user 0.230s system 1.95% cpu 13.265 total
0.040s user 0.223s system 1.97% cpu 13.308 total

# X=0; while [ $X -lt 5 ]; do rm -f ~/.dupd_sqlite; sync; echo 3 > /proc/sys/vm/drop_caches; time dupd scan -q >/dev/null 2>/dev/null; X=$((X + 1)); done
0.060s user 0.267s system 2.59% cpu 12.601 total
0.063s user 0.267s system 2.63% cpu 12.510 total
0.057s user 0.277s system 2.67% cpu 12.447 total
0.057s user 0.273s system 2.65% cpu 12.432 total
0.053s user 0.273s system 2.62% cpu 12.447 total

# X=0; while [ $X -lt 5 ]; do rm -f ~/.dupd_sqlite; sync; echo 3 > /proc/sys/vm/drop_caches; time dupd scan -q --nodb >/dev/null 2>/dev/null; X=$((X + 1)); done
0.080s user 0.257s system 2.67% cpu 12.566 total
0.080s user 0.253s system 2.68% cpu 12.428 total
0.053s user 0.253s system 2.47% cpu 12.371 total
0.053s user 0.250s system 2.43% cpu 12.445 total
0.093s user 0.240s system 2.68% cpu 12.432 total

The plot thickens. On this data set with no duplicates, no hard links, and a wide variety of file sizes, jdupes is slower than dupd by ~6.4%, a very different result than with the huge sets of smaller files. It’s still not a large real-world variance; no one will miss the 0.8 second delay, but it is a very interesting result because it contradicts every previous test that says dupd is the slower choice. I also find it interesting that the gap between dupd with and without –nodb closes up on this data set.

Real-world performance: data set 4 (bonus round)

This is a superset of data set 1. It’s the same kind of data but it’s an absolutely massive set with much more variance and no shortage of duplicates, both hard linked and still duplicated. Stats: over 900,000 files in 12599 directories, average size 527 KB, smallest file 37 bytes, largest file 55 MB, lots of hard links and duplicates. After an entire day at work and only finishing three runs of jdupes (not unusual for this data set) I decided that two days worth of not accessing the machine to accommodate testing was too inconvenient, so I ultimately only finished one dupd test.

# X=0; while [ $X -lt 5 ]; do sync; echo 3 > /proc/sys/vm/drop_caches; time jdupes -Arq . >/dev/null; X=$((X + 1)); done
18.750s user 87.107s system 1.35% cpu 7818.862 total
18.047s user 86.247s system 1.32% cpu 7894.973 total
18.400s user 87.173s system 1.33% cpu 7890.817 total

# X=0; while [ $X -lt 5 ]; do rm -f ~/.dupd_sqlite; sync; echo 3 > /proc/sys/vm/drop_caches; time dupd scan -q >/dev/null 2>/dev/null; X=$((X + 1)); done
25.380s user 104.373s system 1.32% cpu 9804.224 total
^C

Why was dupd 2000 seconds slower than jdupes? I can only speculate. One possibility is that the multi-thread behavior of the program results in extra disk thrashing. My understanding is that dupd uses one thread to read metadata and another thread to perform hash and compare work; if directory reads and file reads happen at the same time (they reach the I/O queue in succession) the disk will have to thrash between those two locations to fulfill the I/O requests. Perhaps the deadline I/O scheduler and dupd don’t work well together. Perhaps SQLite overhead plays a big role. I know that 900,000 files are probably scattered across the disk from one another, so it could be that the always-sequential jdupes file access characteristics plus the large I/O block size (jdupes processes files in 1 MiB chunks at a time) reduce disk thrashing for this data; indeed, with an average file size of well under 1 MiB, an entire file is almost always read in one sequential shot.

Thoughts and conclusions

As far as bragging rights go, jdupes has a superior raw algorithm but dupd can still beat it marginally in real-world tests. Duplicate scanning is rarely performed on files that are 100% cached in RAM, so a program’s disk access characteristics relative to the data set being scanned can be more important than being double the speed in unrealistic algorithm benchmarks. In real-world testing with no pre-cached disk blocks available to artificially soften the huge performance hit of disk thrashing, jdupes and dupd are close enough in performance that neither is a “winner.” They generally seem to do their jobs at about the same speed on most of the data I’ve tested against…so which one should you use? The answer is very simple: use whichever tool you’re comfortable with that does what you want to do. I am partial to jdupes for obvious reasons and I have explained what I don’t like about dupd usage and behavior, but I’m also aware of some glaring flaws in how jdupes works as well. It’s a lot like deciding between two different claw hammers to bang on a nail: you can argue about the minor differences in appearance, dimensions, and weight all day long, but most users just have the need to hit nails and don’t have any reason to care which hammer they use to get the job done.

I’ve traced the terrible dupd performance on my huge data set down to dupd reading 8 KiB of each file at a time versus jdupes reading 1024 KiB (1 MiB) at a time, a difference that almost certainly reduces I/O slowdowns from disk thrashing. I’ve submitted a few bug fixes and pull requests for dupd to help Jyri keep track of the issues I’ve experienced and to improve dupd, including a mention of the bad performance due to the read block size. I also learned some tricks from the dupd source code that I hadn’t thought of before; they may not be useful in jdupes development, but I feel enriched as a programmer from my experience with the program and its code and I’ve tried to contribute back in exchange. Everyone wins!

Isn’t that what open source software is all about?

Advertisements