5
\$\begingroup\$

I have a bunch of exact-duplicate pictures that I've acquired over the years. I'd like to create a list of all them so I can eventually delete some. My idea was simple: dump the hash and location of every image file under a path in MongoDB for later analysis. This is what I came up with:

import com.david.mongodocs.ImageEntry;
import com.mongodb.MongoClient;
import org.apache.commons.codec.digest.DigestUtils;
import org.mongodb.morphia.Datastore;
import org.mongodb.morphia.Morphia;

import java.io.FileInputStream;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;

public class MD5Deduplicator {
    private static Datastore datastore;

    public static void main(String[] args) throws Exception {
        long startTime = System.nanoTime();
        Morphia morphia = new Morphia();
        morphia.mapPackage("com.david.mongodocs");
        datastore = morphia.createDatastore(new MongoClient(), "md5Deduplicator");
        datastore.ensureIndexes();
        logDuplicates(Paths.get(args[0]));
        System.out.println("Completed scan in " + (System.nanoTime() - startTime )+ " nanosecs");
    }

    private static void logDuplicates(Path path) throws IOException {
        Files.walk(path).parallel()
                .filter(Files::isReadable)
                .filter(Files::isRegularFile)
                .forEach(filePath -> {
                    try {
                        String contentType = Files.probeContentType(filePath);
                        if (contentType != null && contentType.startsWith("image")) {
                            FileInputStream fis = new FileInputStream(filePath.toFile());
                            String md5 = DigestUtils.md5Hex(fis);
                            fis.close();
                            ImageEntry imageEntry = new ImageEntry(filePath.toAbsolutePath().toString(), md5);
                            datastore.save(imageEntry);

                        }
                    } catch (Exception e) {
                        e.printStackTrace();
                    }

                });
    }
}

ImageEntry class:

package com.david.mongodocs;

import org.mongodb.morphia.annotations.Entity;
import org.mongodb.morphia.annotations.Id;
import org.mongodb.morphia.annotations.Indexed;

@Entity
public class ImageEntry {
    @Id
    public final String filePath;
    @Indexed
    public final String md5;

    public ImageEntry(String filePath, String md5) {
        this.filePath = filePath;
        this.md5 = md5;
    }
}

From the visualVM profiler it looks like the slowest part of this is the md5hex function (I was a little surprised, I was expecting the slowest part to be related to the FileInputStream or save function). Is there perhaps an alternative hashing function or md5 implementation I should use?

I'm also a little worried that Files.walk().parallel() might be putting a little bit too much faith in Java defaults and may not be the most optimized way to parallelise this.

\$\endgroup\$
2
\$\begingroup\$

The question and the subject is interesting. Recently I needed to make some similar processing; this question pushed me to proceed.

Review

First of all, some remarks about the original implementation.

The method logDuplicates(Path), according to what I see, does not log duplicates, but saves into mongodb all ImageEntry objects corresponding to all image files found in the path. So, to trace duplicates, it is still necessary to execute a couple of requests in mongodb.

There is some room for improvements in this method. Calling datastore.save(imageEntry) for each item separately looked rather suspicious. Doing it in batch mode for all available items should make the thing quicker. Indeed, Datastore.save is overloaded with save(Iterable<T>) and save(T... entities). A slightly improved version of the method would look like this:

private void digestImages(Path path) throws IOException {
  List<ImageEntry> images = new ArrayList<>(APPROX_IMAGES_COUNT);
  Files.walk(path)
       .parallel()
       .filter(Files::isReadable)
       .filter(Files::isRegularFile)
       .forEach(filePath -> {
         if (isImage(filePath)) {
             ImageEntry img = digestAndBuildImageEntry(filePath);
             if (img != null) {
               images.add(img);
             } else {
               System.out.println(String.format("Failed to digest image: %1$s", filePath));
             }
         }});
  datastore.save(images);
}

private boolean isImage(Path path) {
  try {
    String contentType = Files.probeContentType(path);
    return contentType != null && contentType.startsWith("image");
  } catch (IOException ex) {
    ex.printStackTrace();
    return false;
  }
}

private ImageEntry digestAndBuildImageEntry(Path filePath) {
  try (InputStream is = Files.newInputStream(filePath);
       BufferedInputStream buffered = new BufferedInputStream(is)) {
    String hash = DigestUtils.md5Hex(buffered);
    return new ImageEntry(filePath.toAbsolutePath().toString(), hash);
  } catch (IOException ex) {
    ex.printStackTrace();
    return null;
  }
}

Tests

I've got a folder with about 900 JPG image files in numerous sub-folders that I used for tests. Introducing a try-with-resources + batch saving seemed to improve the overall performance for about 10% (see results below).

Based on this SO post that helped me recall different ways and APIs to produce checksums and hashes, I executed a few tests to compare the perfs with the reviewed implementation, as well as when using Guava. The averages of 5 runs on my old i7 gave the following results:

impl               avg time,ms    %
-------------------------------------
original              6583      100.0 
reviewed              5873       89.2 
guava/sha1            8267      125.6
guava/md5             5865       89.1 
guava/murmur3-128     3819       58.0
guava/murmur3-32      2689       40.9 
guava/adler32         2432       36.9
-------------------------------------

For the tests with Guava, I used the following overloading of digestAndBuildImageEntry:

private ImageEntry digestAndBuildImageEntry(Path filePath, HashFunction hashFunc) {
  try {
    String hash = com.google.common.io.Files.hash(filePath.toFile(), hashFunc).toString();
    return new ImageEntry(filePath.toAbsolutePath().toString(), hash);
  } catch (IOException ex) {
    ex.printStackTrace();
    return null;
  }
}

So, we can see that, at least for my test case and without entering into theoretical discussions, Guava's adler32 hash performs almost three times faster than the original implementation.

\$\endgroup\$
  • \$\begingroup\$ I considered doing it in batch mode, but I was concerned that putting it into a list would put me at risk of race conditions since I'm parallelising the stream. I would have to use a synchronized list instead and I worried that it would do more damage than individual saves. Also visuamVM seemed to imply that wasnt a pain point really, so I let it be. Your adler32 comment is definitely interesting though, so I'll give that a shot. \$\endgroup\$ – David says Reinstate Monica Nov 11 '15 at 22:05
  • \$\begingroup\$ Oups, of course, you are right about the race conditions!.. I've completely skipped this. There shouldn't be this ArrayList, but a concurrent Queue should do the job. \$\endgroup\$ – Antot Nov 11 '15 at 22:14
  • \$\begingroup\$ But would it be faster? (I'd check myself, but I wont be at my home computer for a while). \$\endgroup\$ – David says Reinstate Monica Nov 11 '15 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.