Suggestions for duplicate file finder algorithm (using C)

Question

Hello, I wanted to write a program that test if two files are duplicates (have exactly the same content). First I test if the files have the same sizes, and if they have i start to compare their contents.

My first idea, was to "split" the files into fixed size blocks, then start a thread for every block, fseek to startup character of every block and continue the comparisons in parallel. When a comparison from a thread fails, the other working threads are canceled, and the program exits out of the thread spawning loop.

The code looks like this: dupf.h

#ifndef __NM__DUPF__H__
#define __NM__DUPF__H__
#define NUM_THREADS 15
#define BLOCK_SIZE 8192

/* Thread argument structure */
struct thread_arg_s {
    const char *name_f1;        /* First file name */
    const char *name_f2;        /* Second file name */
    int cursor;                 /* Where to seek in the file */
};
typedef struct thread_arg_s thread_arg;

/**
 * 'arg' is of type thread_arg.
 * Checks if the specified file blocks are 
 * duplicates.
 */
void *check_block_dup(void *arg);

/**
 * Checks if two files are duplicates
 */
int check_dup(const char *name_f1, const char *name_f2);

/**
* Returns a valid pointer to a file.
* If the file (given by the path/name 'fname') cannot be opened
* in 'mode', the program is interrupted an error message is shown.
**/
FILE *safe_fopen(const char *name, const char *mode);

#endif

dupf.c

#include <errno.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include "dupf.h"

FILE *safe_fopen(const char *fname, const char *mode)
{
    FILE *f = NULL;
    f = fopen(fname, mode);
    if (f == NULL) {
        char emsg[255];
        sprintf(emsg, "FOPEN() %s\t", fname);
        perror(emsg);
        exit(-1);
    }
    return (f);
}

void *check_block_dup(void *arg)
{
    const char *name_f1 = NULL, *name_f2 = NULL;    /* File names */
    FILE *f1 = NULL, *f2 = NULL;                    /* Streams */
    int cursor = 0;                                 /* Reading cursor */
    char buff_f1[BLOCK_SIZE], buff_f2[BLOCK_SIZE];  /* Character buffers */
    int rchars_1, rchars_2;                         /* Readed characters */
    /* Initializing variables from 'arg' */
    name_f1 = ((thread_arg*)arg)->name_f1;
    name_f2 = ((thread_arg*)arg)->name_f2;
    cursor = ((thread_arg*)arg)->cursor;
    /* Opening files */
    f1 = safe_fopen(name_f1, "r");
    f2 = safe_fopen(name_f2, "r");
    /* Setup cursor in files */
    fseek(f1, cursor, SEEK_SET);
    fseek(f2, cursor, SEEK_SET);
    /* Initialize buffers */
    rchars_1 = fread(buff_f1, 1, BLOCK_SIZE, f1);
    rchars_2 = fread(buff_f2, 1, BLOCK_SIZE, f2);
    if (rchars_1 != rchars_2) {
        /* fread failed to read the same portion.
         * program cannot continue */
        perror("ERROR WHEN READING BLOCK");
        exit(-1);
    }
    while (rchars_1-->0) {
        if (buff_f1[rchars_1] != buff_f2[rchars_1]) {
            /* Different characters */
            fclose(f1);
            fclose(f2);
            pthread_exit("notdup");
        }
    }
    /* Close streams */
    fclose(f1);
    fclose(f2);
    pthread_exit("dup");
}

int check_dup(const char *name_f1, const char *name_f2)
{
    int num_blocks = 0;             /* Number of 'blocks' to check */
    int num_tsp = 0;                /* Number of threads spawns */
    int tsp_iter = 0;               /* Iterator for threads spawns */
    pthread_t *tsp_threads = NULL;
    thread_arg *tsp_threads_args = NULL;
    int tsp_threads_iter = 0;
    int thread_c_res = 0;           /* Thread creation result */
    int thread_j_res = 0;           /* Thread join res */
    int loop_res = 0;               /* Function result */
    int cursor;
    struct stat buf_f1;
    struct stat buf_f2;

    if (name_f1 == NULL || name_f2 == NULL) {
        /* Invalid input parameters */
        perror("INVALID FNAMES\t");
        return (-1);
    }

    if (stat(name_f1, &buf_f1) != 0 || stat(name_f2, &buf_f2) != 0) {
        /* Stat fails */
        char emsg[255];
        sprintf(emsg, "STAT() ERROR: %s %s\t", name_f1, name_f2);
        perror(emsg);
        return (-1);
    }

    if (buf_f1.st_size != buf_f2.st_size) {
        /* File have different sizes */
        return (1);
    }

    /* Files have the same size, function exec. is continued */
    num_blocks = (buf_f1.st_size / BLOCK_SIZE) + 1;
    num_tsp = (num_blocks / NUM_THREADS) + 1;
    cursor = 0;
    for (tsp_iter = 0; tsp_iter < num_tsp; tsp_iter++) {
        loop_res = 0;
        /* Create threads array for this spawn */
        tsp_threads = malloc(NUM_THREADS * sizeof(*tsp_threads));
        if (tsp_threads == NULL) {
            perror("TSP_THREADS ALLOC FAILURE\t");
            return (-1);
        }
        /* Create arguments for every thread in the current spawn */
        tsp_threads_args = malloc(NUM_THREADS * sizeof(*tsp_threads_args));
        if (tsp_threads_args == NULL) {
            perror("TSP THREADS ARGS ALLOCA FAILURE\t");
            return (-1);
        }
        /* Initialize arguments and create threads */
        for (tsp_threads_iter = 0; tsp_threads_iter < NUM_THREADS;
                tsp_threads_iter++) {
            if (cursor >= buf_f1.st_size) {
                break;
            }
            tsp_threads_args[tsp_threads_iter].name_f1 = name_f1;
            tsp_threads_args[tsp_threads_iter].name_f2 = name_f2;
            tsp_threads_args[tsp_threads_iter].cursor = cursor;
            thread_c_res = pthread_create(
                               &tsp_threads[tsp_threads_iter],
                               NULL,
                               check_block_dup,
                               (void*)&tsp_threads_args[tsp_threads_iter]);
            if (thread_c_res != 0) {
                perror("THREAD CREATION FAILURE");
                return (-1);
            }
            cursor+=BLOCK_SIZE;
        }
        /* Join last threads and get their status */
        while (tsp_threads_iter-->0) {
            void *thread_res = NULL;
            thread_j_res = pthread_join(tsp_threads[tsp_threads_iter],
                                        &thread_res);
            if (thread_j_res != 0) {
                perror("THREAD JOIN FAILURE");
                return (-1);
            }
            if (strcmp((char*)thread_res, "notdup")==0) {
                loop_res++;
                /* Closing other threads and exiting by condition
                 * from loop. */
                while (tsp_threads_iter-->0) {
                    pthread_cancel(tsp_threads[tsp_threads_iter]);
                }
            }
        }
        free(tsp_threads);
        free(tsp_threads_args);
        if (loop_res > 0) {
            break;
        }
    }
    return (loop_res > 0) ? 1 : 0;
}

The function works fine (at least for what I've tested). Still, some guys from #C (freenode) suggested that the solution is overly complicated, and it may perform poorly because of parallel reading on hddisk.

What I want to know:

• Is the threaded approach flawed by default ?
• Is fseek() so slow ?
• Is there a way to somehow map the files to memory and then compare them ?

LATED EDIT:

Today I had some time, and I've followed your advices. You were right, this threaded version actually performs worse than a single threaded version, and all because of the parallel readings on hard disk.

Another thing is that I've written a function that uses mmap(), and until now is the optimal one. Still the biggest drawback of that function is that it fails, when the files are getting really big.

Here is the new implementation (a very brute and direct code):

#include <errno.h>
#include <fcntl.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include "dupf.h"

/**
* Safely assures that a file is opened. 
* If cannot open file, the flow of the program is interrupted.
* The error code returned is -1.
**/
FILE *safe_fopen(const char *fname, const char *mode)
{
    FILE *f = NULL;
    f = fopen(fname, mode);
    if (f == NULL) {
        char emsg[1024];
        sprintf(emsg, "Cannot open file: %s\t", fname);
        perror(emsg);
        exit(-1);
    }
    return (f);
}

/**
* Check if two files have the same size.
* Returns:
* -1    Error.
* 0 If they have the same size.
* 1 If the don't have the same size.
**/
int check_same_size(const char *f1_name, const char *f2_name, off_t *f1_size, off_t *f2_size)
{
    struct stat f1_stat, f2_stat;
    if((f1_name == NULL) || (f2_name == NULL)){
        fprintf(stderr, "Invalid filename passed to function [check_same_size].\n");
        return (-1);
    }
    if((stat(f1_name, &f1_stat) != 0) || (stat(f2_name, &f2_stat) !=0)){
        fprintf(stderr, "Cannot apply stat. [check_same_size].\n");
        return (-1);
    }
    if(f1_size != NULL){
        *f1_size = f1_stat.st_size;
    }
    if(f2_size != NULL){
        *f2_size = f2_stat.st_size;
    }
    return (f1_stat.st_size == f2_stat.st_size) ? 0 : 1;
}

/**
* Test if two files are duplicates.
* Returns:
* -1    Error.
* 0 If they are duplicates.
* 1 If they are not duplicates.
**/
int check_dup_plain(char *f1_name, char *f2_name, int block_size)
{
    if ((f1_name == NULL) || (f2_name == NULL)){
        fprintf(stderr, "Invalid filename passed to function [check_dup_plain].\n");
        return (-1);
    }
    FILE *f1 = NULL, *f2 = NULL;
    char f1_buff[block_size], f2_buff[block_size];
    size_t rch1, rch2;
    if(check_same_size(f1_name, f2_name, NULL, NULL) == 1){
        return (1);
    }
    f1 = safe_fopen(f1_name, "r");
    f2 = safe_fopen(f2_name, "r");
    while(!feof(f1) && !feof(f2)){
        rch1 = fread(f1_buff, 1, block_size, f1);
        rch2 = fread(f2_buff, 1, block_size, f2);
        if(rch1 != rch2){
            fprintf(stderr, "Invalid reading from file. Cannot continue. [check_dup_plain].\n");
            return (-1);
        }
        while(rch1-->0){
            if(f1_buff[rch1] != f2_buff[rch1]){
                return (1);
            }
        }
    }
    fclose(f1);
    fclose(f2);
    return (0);
}

/**
* Test if two files are duplicates.
* Returns:
* -1    Error.
* 0 If they are duplicates.
* 1 If they are not duplicates.
**/
int check_dup_memmap(char *f1_name, char *f2_name)
{
    struct stat f1_stat, f2_stat;
    char *f1_array = NULL, *f2_array = NULL;
    off_t f1_size, f2_size;
    int f1_des, f2_des, cont, res;
    if((f1_name == NULL) || (f2_name == NULL)){
        fprintf(stderr, "Invalid filename passed to function [check_dup_memmap].\n");
        return (-1);    
    }
    if(check_same_size(f1_name, f2_name, &f1_size, &f2_size) == 1){
        return (1);
    }
    f1_des = open(f1_name, O_RDONLY);
    f2_des = open(f2_name, O_RDONLY);
    if((f1_des == -1) || (f2_des == -1)){
        perror("Cannot open file");
        exit(-1);       
    }
    f1_array = mmap(0, f1_size * sizeof(*f1_array), PROT_READ, MAP_SHARED, f1_des, 0);
    if(f1_array == NULL){
        fprintf(stderr, "Cannot map file to memory [check_dup_memmap].\n");
        return (-1);
    }
    f2_array = mmap(0, f2_size * sizeof(*f2_array), PROT_READ, MAP_SHARED, f2_des, 0);
    if(f2_array == NULL){
        fprintf(stderr, "Cannot map file to memory [check_dup_memmap].\n");
        return (-1);
    }
    cont = f1_size;
    res = 0;
    while(cont-->0){
        if(f1_array[cont]!=f2_array[cont]){
            res = 1;
            break;
        }
    }
    munmap((void*) f1_array, f1_size * sizeof(*f1_array));
    munmap((void*) f2_array, f2_size * sizeof(*f2_array));
    return res;
}

int main(int argc, char *argv[])
{
    printf("result: %d\n",check_dup_memmap("f2","f1"));
    return (0);
}

I am planning now to extend this code, by re-adding the threaded functionality, but this time the reading will be on memory.

Thanks for your answers.

Answer 1

Because you're using pthreads, I assume you're working in a Unix environment -- in which case you could mmap(2) both files into memory and compare the memory arrays directly.

Answer 2

The limiting factor will be disk reads, which (assuming that both files are on the same disk) will be serialized anyway, so I don't think threading will help much at all.

Answer 3

It's hard to guess about performance without a real system to test against (for example if you're using a solid state drive, there's no head seek time and the cost of reading different sectors from different threads is almost zero).

If this is running against a reasonably standard computer with regular (spinning platter) hard drives, having multiple threads contend for the part of the disk they want to read from will possibly slow things down (depending, again, on the hardware and also the size of the chunks).

If the time it takes to compute the "sameness" of a chunk is fast compared to the time it takes to read that chunk from disk, having a separate thread will not help much since the second (or third...) thread would spend most of it's time waiting for IO to complete anyway.

Another factor is the cache size of the CPU. If all of the memory you're processing at one time fits in the CPU cache, things will be much faster than if different threads cause different chunks of memory to be loaded into cache as they execute instructions.

If you have more threads than you have CPU cores, you will just slow things down by making unnecessary context switches (since a thread needs a core to run on).

After reading all of that, if you still think multithreading is going to help for your target system, consider one thread that does IO only, places the data in a queue, and has two or more worker threads taking data off of the queue to process. That way, you optimize disk IO and can take advantage of multiple cores to crunch the numbers.

Steve suggested you can memory map you files on Unix. That will speed up access to the underlying data a bit by leveraging low level OS functionality (the same kind used to manage swap files). That will give you some performance improvement as the OS will handle loading the parts of the file you are working on into memory efficiently, as long as the file fits into available address space. FYI you can do the same thing on Windows.

Answer 4

Well, there is the standard memory mapping mmap() function that maps a file to memory. You should be able to do something like

int fd1;
int fd2;
int size1;
int size2;

fd1 = open(name1, O_RDONLY);
size1 = lseek(fd1, 0, SEEK_END); 

fd2 = open(name2, O_RDONLY);
size2 = lseek(fd2, 0, SEEK_END);

if ( size1 == size2 )
{
   char * data1 = mmap(0, size1, PROT_READ, MAP_SHARED, fd1, 0);
   char * data2 = mmap(0, size1, PROT_READ, MAP_SHARED, fd2, 0);
   int i;

   /* ...and this is, obviously, where you'd do something more clever */
   for ( i = 0; i < size1 && *data1 == *data2; i++, data1++, data2++ );

   if ( i == size1 )
       printf("Equal\n");
}

close(fd1);
close(fd2);

Other than that, yes, your solution looks overly complicated ;-) The threaded approach is not necessarily flawed, but you might not see that parallel access improves performance. For SAN drives or ramdisks it might improve performance, for normal spinning platter drives it might impede it. But simpler is usually better, unless you really have a performance issue.

Regarding fseek() vs other methods, it depends on the operating system you use. Google is you friend here, you can easily find articles at least for Solaris and Linux.

Answer 5

You could probably simplify your code greatly by using hashes, instead of doing a byte-by-byte comparison. Assuming you're not doing anything important, like deleting, an md5 or similar hash function should be plenty. Boost provides quite a few, and they're usually pretty fast.

if fileA.size == fileB.size
    if fileA.hash() == fileB.hash()
        flag(fileA, fileB, same);

I wouldn't delete files after that comparison, but it's plenty safe to move them to a temporary directory for further review or just build a list of possible duplicates.

Answer 6

Even if disk access was not the limiting factor (it will be), unless you have a multi-core processor that could hand off different threads to different cores, you would not see a speed-up from going multi-threaded. Basically, you have to compare all N bytes of the file one way or another, and even if you use threads, if they execute in the same core, it will take the same amount of time as without using threads.

There are some environments that could spread the workload across cores, but even so, the CPU will be able to process so much faster than the data can be pulled in from disk that the disk I/O system will be the limiting factor.

Answer 7

Before even considering the performance effects of parallel disk reads and thread overhead and such...

Is there any reason to believe that scanning the files in chunks will find the differences any quicker than straight through? Is the data contained in the files predominantly in a certain format, and if so, is the splitting scheme tailored to it? If not, I don't see how scanning the files by skipping over every n bytes (which is all the multithreaded splitting is effectively doing) could offer any improvement over reading the bytes in the order they are on disk.

Think of the two limiting cases -- "splitting" the file into one block, and splitting the file into as many one-byte "blocks" as there are bytes in the file. Will either of those cases be more efficient than the other, or some in-between value? If there is no in-between value that you know you should optimize to, then you know nothing about how the data is stored in the files, so it should make no difference how you scan them.

Even if you set the split to optimize to the disk's performance like block size, you're still going to have to go back to read the next byte, which will likely be at an extremely non-optimal position. And in the end you're going to have to read every single byte in the file, no matter how you split it.

Answer 8

I see there's crap ones online that want $30, so I figured I'd look for a C# version I could compile myself: luckily someone made one using hashing back in 2008.

Code Project I found tonight about this very subject