8
\$\begingroup\$

I want to write a relatively simple program, that can backup files from my computer to a remote location and encrypt them in the process, while also computing a diff (well not really...I'm content with seeing if anything changed at all, not so much what has changed) between the local and the remote files to see which ones have changed and are necessary to update.

I am aware that there are perfectly good programs out there to do this (rsync, or others based on duplicity). I'm not trying to reinvent the wheel, it's just supposed to be a learning experience for myself

My question is regarding to the diff part of the project. I have made some assumptions and wrote some sample code to test them out, but I would like to know if you see anything I might have missed, if the assumptions are just plain wrong, or if there's something that could go wrong in a particular constelation.

Assumption 1: If files are not of equal length, they can not be the same (ie. some modification must have taken place)
Assumption 2: If two files are the same (ie. no modification has taken place) any byte sub-set of these two files will have the same hash
Assumption 3: If a byte sub-set of two files is found which does not result in the same hash, the two files are not the same (ie. have been modified)

The code is written in Java and the hashing algorithm used is BLAKE-512 using the java implementation from Marc Greim.
_File1 and _File2 are 2 files > 1.5GB of type java.io.File

public boolean compareStream() throws IOException {
    int i = 0;
    int step = 4096;
    boolean equal = false;

    FileInputStream fi1 = new FileInputStream(_File1);      
    FileInputStream fi2 = new FileInputStream(_File2);

    byte[] fi1Content = new byte[step];
    byte[] fi2Content = new byte[step];

    if(_File1.length() == _File2.length()) { //Assumption 1
        while(i*step < _File1.length()) {   

            fi1.read(fi1Content, 0, step); //Assumption 2
            fi2.read(fi2Content, 0, step); //Assumption 2

            equal = BLAKE512.isEqual(fi1Content, fi2Content); //Assumption 2

            if(!equal) { //Assumption 3
                break;
            }

            ++i;
        }
    }

    fi1.close();
    fi2.close();
    return equal;
}

The calculation for two equal 1.5 GB files takes around 4.2 seconds. Times are of course much shorter when the files differ, especially when they are of different length since it returns immediately.

Thank you for your suggestions :)

\$\endgroup\$
  • 2
    \$\begingroup\$ Why are you hashing the two byte-arrays? You can simply check if they are equal and save CPU cycles by not calculating any hash. Just do Arrays.equals(fi1Content, fi2Content). \$\endgroup\$ – GiantTree May 8 '15 at 13:26
  • \$\begingroup\$ I was about to comment that.... too... but I also have more to say, so perhaps an answer would be better. \$\endgroup\$ – rolfl May 8 '15 at 13:30
  • \$\begingroup\$ Well the final functionality should be to check whether there is a difference between a remote file and a local file to decide whether or not the local file needs to be re-uploaded in order to keep the remote repository up to date. So I would hash every file before uploading and keep and store the hashes in a list. So when I want to do a backup next time I calculate hashes from my local files and compare them to the remote hash list to know which files have changed. Maybe not the best example I chose to display this though \$\endgroup\$ – Daniel W. May 8 '15 at 13:41
13
\$\begingroup\$

There are some basic issues here, as well as some algorithmic complexities, and then some advanced suggestions.

Basic issues relate to Java code conventions, etc.

Basics

Use try-with-resources. You have code which may fail, and leave open files lying around to be garbage collected. Consider the following code:

try (FileInputStream fi1 = new FileInputStream(_File1);      
    FileInputStream fi2 = new FileInputStream(_File2);) {

    // do stuff with the files - they will be auto-closed.

}

The next thing, is why open the files if they are different lengths?

FileInputStream fi1 = new FileInputStream(_File1);      
FileInputStream fi2 = new FileInputStream(_File2);

byte[] fi1Content = new byte[step];
byte[] fi2Content = new byte[step];

if(_File1.length() == _File2.length()) { //Assumption 1

The code above, should be:

if(_File1.length() == _File2.length()) { //Assumption 1
    FileInputStream fi1 = new FileInputStream(_File1);      
    FileInputStream fi2 = new FileInputStream(_File2);

    byte[] fi1Content = new byte[step];
    byte[] fi2Content = new byte[step];

Use the power of the force, ... I mean parameters, Luke... I mean Daniel.

Your method should take the two files as parameters, not as class-level fields. As it stands, your code is not "reentrant", and it should be. Your method is:

public boolean compareStream() ....

but it should be

public boolean compareStream(File filea, File fileb) ....

Algorithm

Since you are comparing two files byte-by-byte, the hashing will make no difference. If the two files were on different machines, and you have a slow network between them, and if you could run the hashing algorithm remotely, then it probably makes sense to hash the two files on each side, and then just compare the small, and easy to transfer, hash result. Something like SHA-256.

So, there's no need to hash, just do byte-by-byte comparisons.

For large files like yours, why have such a small step size? Use something much larger like 4MB, not 4KB. It will make it much faster.

Alternatives

File IO is always slower than you want. Java has the NIO framework for higher-performance IO using Channels and Buffers. This would be a great time to learn how to use them, because, a 4MB Memory-Mapped IO operation on the two files will likely give you the best performance.

See the MemoryMapped IO JavaDoc

I ran up a test using NIO, and produced the following code:

public static final boolean compareFiles(final Path filea, final Path fileb) throws IOException {
    if (Files.size(filea) != Files.size(fileb)) {
        return false;
    }

    final long size = Files.size(filea);
    final int mapspan = 4 * 1024 * 1024;

    try (FileChannel chana = (FileChannel)Files.newByteChannel(filea);
            FileChannel chanb = (FileChannel)Files.newByteChannel(fileb)) {

        for (long position = 0; position < size; position += mapspan) {
            MappedByteBuffer mba = mapChannel(chana, position, size, mapspan);
            MappedByteBuffer mbb = mapChannel(chanb, position, size, mapspan);

            if (mba.compareTo(mbb) != 0) {
                return false;
            }

        }

    }
    return true;
}

private static MappedByteBuffer mapChannel(FileChannel channel, long position, long size, int mapspan) throws IOException {
    final long end = Math.min(size, position + mapspan);
    final long maplen = (int)(end - position);
    return channel.map(MapMode.READ_ONLY, position, maplen);
}

Note, the guts could be rewritten more concisely too:

            if (!mapChannel(chana, position, size, mapspan)
                   .equals(mapChannel(chanb, position, size, mapspan))) {
                return false;
            }

On my laptop, this is comparing 1.5GB files in under 2 seconds. Obviously, your milage may vary, and my laptop is an unknown beast.... but things that may play in to the equation:

  • I have 16GB mem
  • it's a 4 year old laptop
  • it has an SSD
  • there is file-system encryption
  • it runs linux.
\$\endgroup\$
  • \$\begingroup\$ I just updated my answer to include an NIO example (and some Paths, etc.). \$\endgroup\$ – rolfl May 8 '15 at 14:57
  • \$\begingroup\$ Thank you for your suggestions! The brain fart with checking _File1.length() == _File2.length() after I had already opened the streams I caught shortly after posting this myself :D However I wasn't aware of the try-with-resources...had been wondering if there was something similar to pythons with open("...") as f:. Good to know there is! As for the parameters: yeah I know I just put this together as a quick static example with hard-coded file paths. The NIO framework is a really good idea! Thanks for that \$\endgroup\$ – Daniel W. May 8 '15 at 16:18
  • \$\begingroup\$ However I have one last thing...I still think that hashing the files would be better for the kind of thing I want to do with it in the end (at least for files above a certain size). I was thinking to store the computed hashes remotely so that when I want to do my next backup I can just download the hashes of each file, and compare them to the hash I compute locally. I would assume that the process of download remote hash -> compute hash for local file -> compare downladed and computed hash would be faster than download remote file -> compare downloaded file and local file byte-by-byte \$\endgroup\$ – Daniel W. May 8 '15 at 16:24
  • \$\begingroup\$ @Daniel - remote-caching the hashes would be fine, but is beyond the scope of your question/review. How about chatting in the 2nd monitor. \$\endgroup\$ – rolfl May 8 '15 at 16:26

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.