Tag: open source

SubscribeStar Logo

jdupes 1.16.0: File Extension Filtering, And I Need Your Support

Please consider supporting me on SubscribeStar so I can continue to bring open source software and tutorial videos to you!

Over the past weekend, I implemented a feature in jdupes that was pretty strongly desired by the user community. Version 1.16.0 has the ability to filter by file extensions, either by excluding files with certain extensions or only scanning files with certain extensions. Now you can do things like scan only the JPEG files you dumped from your phone while ignoring all of the videos, scan a software project folder’s .c and .h files for duplicates while ignoring all of the others, or find all duplicates except for XML files.

In addition, I’ve cleaned up the extended filter (-X/–extfilter) framework and created an entirely separate help text section (jdupes -X help) that explains the extfilter options and behavior in great detail.

The extended filters are also cumulative, so specifying multiple filter options works as expected; for example, “jdupes -X noext=mp3 -X noext=aac -X size+=:1M” will exclude all files from consideration that end in .mp3/.aac as well as all files that are 1MiB or larger in size.

Unfortunately, there is not currently a way to combine filters, i.e. exclude all files with a particular extension over a particular size. That may be a feature in the future, but right now, I’m trying to add some basic filter functionality that satisfies as many basic filtering use cases as possible with as little work as possible. In the case of the extension filter, it took me about 3-4 hours to code, test, and fix issues with the feature, then issue a new release. It was relatively easy to implement, and even includes the ability to scan a comma-separated list of extensions rather than requiring a separate option for every single extension you want to filter.

Other features that filter on file paths will be more difficult to implement, but are highly desired by the community, so I have plans to implement those soon. The next fix, however, will be for the problematic BTRFS/XFS dedupe support that can’t dedupe (ioctl_fideduperange) large file sets properly.

Thanks as always for your continued support. More support means more time to work on my projects! I appreciate all of your help.

https://github.com/jbruchon/jdupes/releases/tag/v1.16.0

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?

Finding Duplicates Faster: The story of ‘jdupes’, or how I unexpectedly became a better programmer

The problem of finding and handling duplicate files has been with us for a long time. Since the end of the year 1999, the de facto answer to “how can I find and delete duplicate files?” for Linux and BSD users has been a program called ‘fdupes’ by Adrian Lopez. This venerable staple of system administrators is extremely handy when you’re trying to eliminate redundant data to reclaim some disk space, clean up a code base full of copy-pasted files, or delete photos you’ve accidentally copied from your digital camera to your computer more than once. I’ve been quite grateful to have it around–particularly when dealing with customer data recovery scenarios where every possible copy of a file is recovered and the final set ultimately contains thousands of unnecessary duplicates.

Unfortunately, development on Adrian’s fdupes had, for all practical purposes, ground to a halt. From June 2014 to July 2015, the only significant functional changes to the code have been modification to compile on Mac OS X. The code’s stagnant nature has definitely shown itself in real-world tests; in February 2015, Eliseo Papa published “What is the fastest way to find duplicate pictures?” which contains benchmarks of 15 duplicate file finders (including an early version of my fork which we’ll ignore for the moment) that places the original fdupes dead last in operational speed and shows it to be heavily CPU-bound rather than I/O-bound. In fact, Eliseo’s tests say that fdupes takes a minimum of 11 times longer to run than 13 of the other duplicate file finders in the benchmark!

As a heavy user of the program on fairly large data sets, I had noticed the poor performance of the software and became curious as to why it was so slow for a tool that should simply be comparing pairs of files. After inspecting the code base, I found a number of huge performance killers:

  1. Tons of time was wasted waiting on progress to print to the terminal
  2. Many performance-boosting C features weren’t used (static, inline, etc)
  3. A couple of one-line functions were very “hot,” adding heavy call overhead
  4. Using MD5 for file hashes was slower than other hash functions
  5. Storing MD5 hashes as strings instead of binary data was inefficient
  6. A “secure” hash like MD5 isn’t needed; matches get checked byte-for-byte

I submitted a pull request to the fdupes repository which solved these problems in December 2014. Nothing from the pull request was discussed on Github and none of the fixes were incorporated into fdupes. I emailed Adrian to discuss my changes with him directly and there was some interest in certain changes, but in the end nothing was changed and my emails became one-way.

It seemed that fdupes development was doomed to stagnation.

In the venerable traditions of open source software. I forked it and gave my new development tree a new name to differentiate it from Adrian’s code: jdupes. I solved the six big problems outlined above with these changes:

  1. Rather than printing progress indication for every file examined, I added a delay counter to drastically reduce terminal printing. This was a much bigger deal when using SSH.
  2. I switched the code and compilation process to use C99 and added relevant keywords to improve overall performance.
  3. The “hot” one-line functions were changed to #define functions to chop function call overhead for them in half.
  4. (Also covers 5 and 6) I wrote my own hash function  and replaced all of the MD5 code with it, resulting in a benchmarked speed boost of approximately 17%. The resulting hashes are passed around as a 64-bit unsigned integer, not an ASCII string, which (on 64-bit machines) reduces hash comparisons to a single compare instruction.

 

After forking all of these changes and enjoying the massive performance boost they brought about, I felt motivated to continue looking for potential improvements. I didn’t realize at the time that a simple need to eliminate duplicate files more quickly would morph into spending the next half-year ruthlessly digging through the code for ways to make things better. Between the initial pull request that led to the fork and Eliseo Papa’s article, I managed to get a lot done:

 

At this point, Eliseo published his February 19 article on the fastest way to find duplicates. I did not discover the article until July 8 of the same year (at which time jdupes was at least three versions higher than the one being tested), so I was initially disappointed with where jdupes stood in the benchmarks relative to some of the other tested programs, but even the early jdupes (version 1.51-jody2) code was much faster than the original fdupes code for the same job.

1.5 months into development, jdupes was 19 times faster in a third-party test than the code it was forked from.

Nothing will make your programming efforts feel more validated than seeing something like that from a total stranger.

Between the publishing of the article and finding the article, I had continued to make heavy improvements:

 

When I found Eliseo’s article from February, I sent him an email inviting him to try out jdupes again:

I have benchmarked jdupes 1.51-jody4 from March 27 against jdupes 1.51-jody6, the current code in the Git repo. The target is a post-compilation directory for linux-3.19.5 with 63,490 files and 664 duplicates in 152 sets. A “dry run” was performed first to ensure all files were cached in memory first and remove variances due to disk I/O. The benchmarking was as follows:

$ ./compare_fdupes.sh -nrq /usr/src/linux-3.19.5/
Installed fdupes:
real 0m1.532s
user 0m0.257s
sys 0m1.273s

Built fdupes:
real 0m0.581s
user 0m0.247s
sys 0m0.327s

Five sequential runs were consistently close (about ± 0.020s) to these times.

In half a year of casual spare-time coding, I had made fdupes 32 times faster.

There’s probably not a lot more performance to be squeezed out of jdupes today. Most of my work on the code has settled down into working on new features and improving Windows support. In particular, Windows has supported hard linked files for a long time, and I’ve taken full advantage of Windows hard link support. I’ve also made the progress indicator much more informative to the user. At this point in time, I consider the majority of my efforts complete. jdupes has even gained inclusion as an available program in Arch Linux.

Out of the efforts undertaken in jdupes, I have gained benefits for other projects as well. For example, I can see the potential for using the string_table allocator in other projects that don’t need to free() string memory until the program exits. Most importantly, my overall experience with working on jdupes has improved my overall programming skills tremendously and I have learned a lot more than I could have imagined would come from improving such a seemingly simple file management tool.

If you’d like to use jdupes, feel free to download one of my binary releases for Linux, Windows, and Mac OS X. You can find them here.