Tag: code

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.

Windows Registry FUSE Filesystem

Here’s some code which will allow you to mount Windows registry hive files as filesystems: https://github.com/jbruchon/winregfs

The README file says:

                       THE WINDOWS REGISTRY FUSE FILESYSTEM
                       ====================================

     If you have any questions, comments, or patches, send me an email:
                               jody@jodybruchon.com

One of the most difficult things to deal with in years of writing Linux
utilities to work with and repair Windows PCs is the Windows registry.
While many excellent tools exist to work with NTFS filesystems and to change
and remove passwords from user accounts, the ability to work with the
registry has always been severely lacking. Included in the excellent chntpw
package is a primitive registry editor "reged" which has largely been quite
helpful and I have been grateful for its existence, but it suffers from a
very limited interface and a complete lack of scriptability that presents a
major hurdle for anyone wanting to do more with the registry than wipe out a
password or change the "Start" flag of a system service.

Because of the serious limitations of "reged," the only practical way to do
anything registry-oriented with a shell script was to export an ENTIRE HIVE
to a .reg file, crudely parse the file for what you want, create a .reg file
from the script to import the changes, and import them. Needless to say, the
process is slow, complicated, and frustrating. I even wrote a tool called
"read_inf_section" to help my scripts parse INF/INI/REG files faster because
of this need (but also for an unrelated need to read .inf files from driver
packages.) This complexity became too excessive, so I came up with a much
better way to tweak the registry from shell scripts and programs.

Thus, the Windows Registry FUSE Filesystem "winregfs" was born. chntpw
( http://pogostick.net/~pnh/ntpasswd/ ) has an excellent library for
working with Windows NT registry hive files, distributed under the LGPL.
winregfs is essentially a glue layer between ntreg.c and FUSE, translating
Windows registry keys and values into ordinary directories and files.

winregfs features case-insensitivity and forward-slash escaping. A few keys
and value names in the Windows registry such as MIME types contain forward
slash characters; winregfs substitutes "_SLASH_" where a forward slash appears
in names.

To use winregfs, make a directory to mount on and point it to the registry
hive of interest:

---
$ mkdir reg
$ mount.winregfs /mnt/sdc2/Windows/System32/config/software reg
---

Now, you can see everything in that hive under "reg":

---
$ ls reg
7-Zip/                  Google/              Policies/
AVAST Software/         InstalledOptions/    Program Groups/
Adobe/                  Intel/               RegisteredApplications/
Analog Devices/         LibreOffice/         S3/
C07ft5Y/                Macromedia/          Schlumberger/
Classes/                Microsoft/           Secure/
Clients/                Mozilla/             Sigmatel/
Diskeeper Corporation/  MozillaPlugins/      The Document Foundation/
GNU/                    NVIDIA Corporation/  Windows 3.1 Migration Status/
Gabest/                 ODBC/                mozilla.org/
Gemplus/                Piriform/
---

Let's say you want to see some things that automatically run during startup.

---
$ ls -l reg/Microsoft/Windows/CurrentVersion/Run
total 0
-r--r--r-- 1 root root 118 Dec 31  1969 Adobe ARM.sz
-r--r--r-- 1 root root 124 Dec 31  1969 DiskeeperSystray.sz
-r--r--r-- 1 root root  60 Dec 31  1969 HotKeysCmds.sz
-r--r--r-- 1 root root  66 Dec 31  1969 IgfxTray.sz
-r--r--r-- 1 root root  70 Dec 31  1969 KernelFaultCheck.esz
-r--r--r-- 1 root root  66 Dec 31  1969 Persistence.sz
-r--r--r-- 1 root root 100 Dec 31  1969 SoundMAXPnP.sz
-r--r--r-- 1 root root 118 Dec 31  1969 avast.sz
---

You want to see what these values contain.

---
$ for X in reg/Microsoft/Windows/CurrentVersion/Run/*
> do echo -en "$X\n   "; cat "$X"; echo; done
reg/Microsoft/Windows/CurrentVersion/Run/Adobe ARM.sz
   "C:\Program Files\Common Files\Adobe\ARM\1.0\AdobeARM.exe"

reg/Microsoft/Windows/CurrentVersion/Run/DiskeeperSystray.sz
   "C:\Program Files\Diskeeper Corporation\Diskeeper\DkIcon.exe"

reg/Microsoft/Windows/CurrentVersion/Run/HotKeysCmds.sz
   C:\WINDOWS\system32\hkcmd.exe

reg/Microsoft/Windows/CurrentVersion/Run/IgfxTray.sz
   C:\WINDOWS\system32\igfxtray.exe

reg/Microsoft/Windows/CurrentVersion/Run/KernelFaultCheck.esz
   %systemroot%\system32\dumprep 0 -k

reg/Microsoft/Windows/CurrentVersion/Run/Persistence.sz
   C:\WINDOWS\system32\igfxpers.exe

reg/Microsoft/Windows/CurrentVersion/Run/SoundMAXPnP.sz
   C:\Program Files\Analog Devices\Core\smax4pnp.exe

reg/Microsoft/Windows/CurrentVersion/Run/avast.sz
   "C:\Program Files\AVAST Software\Avast\avastUI.exe" /nogui
---

Has anything hijacked the Windows "shell" value that runs explorer.exe?

---
$ cat reg/Microsoft/Windows\ NT/CurrentVersion/Winlogon/Shell.sz
Explorer.exe
---

How about the userinit.exe value?

---
$ cat reg/Microsoft/Windows\ NT/CurrentVersion/Winlogon/Userinit.sz
C:\WINDOWS\system32\userinit.exe,
---

Perhaps check if some system policies are set (note that REG_DWORD will
probably change in a future release to text files instead of raw data):

---
$ hexdump -C \
> reg/Policies/Microsoft/Windows/System/Allow-LogonScript-NetbiosDisabled.dw
00000000  01 00 00 00                                       |....|
00000004
---

You can probably figure out what to do with it from here. ;-)

I hate Java. I hate Java. I hate Java.

I’ll readily admit, my programming experience is mostly limited to 6502/65816 assembler, some C, and a lot of PHP/MySQL, but I already know that I hate Java.  Why?  It’s simple, really: it doesn’t make any sense at all, and it’s extremely unhelpful when something goes wrong.

This rant stems from working on a Java IRC bot that was torn up and rebuilt by someone for a custom purpose.  I was hosting the bot until it simply stopped working.  It choked up and wouldn’t start after a certain revision, despite working on the guy’s Windows box.  I snagged a newer JRE, and instead of the horrid 12-line error when trying to start it, I get nothing but “IO exception occured.”  Thanks for the informative message, really.  I’m so glad to know that an “IO” (don’t you mean I/O?) exception occurred.  Previously, when I tried to manipulate the code myself, I couldn’t even change it to do the most basic things.  Why not?  Because Java doesn’t make sense at all, especially to someone used to working with C and PHP (you know, real programming languages).  A lot of Java-heads will moan about my opinion or offer up lame excuses for Java, but the truth is that it’s a garbage language that doesn’t make any sense, and from what I’ve read its “standards” change as the Sun JRE releases incrementally move up.  I won’t touch it with a ten-foot pole.