Rearranging files by separating duplicates from unique ones

Question

I have several hundreds gigabytes of photos, approximately half of them are duplicates. Average photo's size is about 4 MB, but some files (video) have size more than 100 MB.

I want to do the following:

1. Find all duplicates and move them into the separate directory - "Trash_bin".
2. Move all unique files into a "Unique_pictures" directory, which will have sub-directories named according file's modification time - by year_month_day format, example: 2010_04_25.

An example of original directory structure

Picture_original_dir/
├── 001.JPG
├── 002.JPG
├── 003.JPG
├── 017.jpg
├── 033 - copy.jpg
├── 033.jpg
├── 070.JPG
├── 444 - copy (2).JPG
├── 444 - copy.JPG
├── 444.JPG
├── dir_1
│   ├── 001.JPG
│   ├── 002.JPG
│   ├── 003.JPG
│   └── sub_dir_1
│       └── 017.jpg
├── dir_2
│   ├── 001.JPG
│   ├── 002.JPG
│   ├── 003.JPG
│   ├── DSC009111.JPG
│   └── DSC00911.JPG
├── DSC00911.JPG
└── empty_dir_1
    └── sub_empty_dir_1

I want to rearrange them by this way:

Picture_test_dir/
├── Trash_bin
│   ├── 2010_04_25_00001.jpg_4
│   ├── 2010_04_25_00001.jpg_5
│   ├── 2013_07_09_00001.jpg_6
│   ├── 2013_07_09_00001.jpg_7
│   ├── 2013_08_09_00001.jpg_8
│   ├── 2013_08_09_00001.jpg_9
│   ├── 2013_08_27_00001.jpg_10
│   ├── 2014_09_17_00001.jpg_1
│   ├── 2014_09_17_00001.jpg_2
│   ├── 2014_10_09_00001.jpg_11
│   ├── 2014_10_09_00001.jpg_12
│   └── 2015_01_16_00001.jpg_3
└── Unique_pictures
    ├── 2010_04_25
    │   └── 00001.jpg
    ├── 2013_07_09
    │   └── 00001.jpg
    ├── 2013_08_09
    │   └── 00001.jpg
    ├── 2013_08_27
    │   └── 00001.jpg
    ├── 2014_09_17
    │   └── 00001.jpg
    ├── 2014_10_09
    │   └── 00001.jpg
    ├── 2014_10_14
    │   └── 00001.jpg
    └── 2015_01_16
        └── 00001.jpg

To accomplish this task I wrote a script.

The idea is to calculate a hash of every file and put files with same hash into a dictionary with the hash as a key and a list of paths of these files as value.

To improve performance the next trick is used - files with unique sizes skips hash calculation.

I am interested in:

1. Code review.
2. The program is running quite long time, for example 40 000 photos, 180 GB are processed by 40 minutes, so it will be good to improve performance somehow. I have increased performance by changing sha256 to md5 algorithm (in price of reliability), may be you know somewhat else. I have tried shortcuting os.path.getsize to getsize = os.path.getsize but didn't get any speedup.
3. Are all used modules optimal or more appropriate are existing? I wasn't use Path module because it is more slow comparing to os.path (by rumors on the internet). Also I have used sys.argv[1] instead of argparse module, because the program has just one argument at this moment.

Script

Usage: ./rearrange_photos.py root_dir

#!/usr/bin/python3

import os
from hashlib import sha256, md5
import sys

from time import time
from datetime import timedelta, datetime

def print_progress(message, interval):
    global prevtime
    global starttime
    new_time = time()
    if (new_time - prevtime) >= interval:
        print(message)
        print(f"Time has elapsed: {timedelta(seconds=new_time - starttime)}")
        prevtime = new_time

def delete_empty_dirs(source_dir):
    for path, dirs, files in os.walk(source_dir, topdown=False):
        if not os.listdir(path):
            os.rmdir(path)

def create_new_path(file_path, file_modification_time=None):
    global new_dir_counters
    if file_modification_time == None:
        file_modification_time = os.path.getmtime(file_path)

    timestamp = datetime.fromtimestamp(file_modification_time)
    new_dirname = timestamp.strftime('%Y_%m_%d')

    if new_dirname not in new_dir_counters:
        new_dir_counters[new_dirname] = 0
        os.makedirs(f"{dest_dir}/{new_dirname}", exist_ok=True)

    new_dir_counters[new_dirname] += 1
    ext = os.path.splitext(file_path)[1].lower()
    new_filename = f"{new_dir_counters[new_dirname]:0>5}{ext}"
    new_path = f"{dest_dir}/{new_dirname}/{new_filename}"

    return new_path

def get_oldest_file(paths):
    return min((os.path.getmtime(path), path) for path in paths)

def add_hash_to_dct(file_path, dct):
    with open(file_path, 'rb') as f_d: 
#       hsh = sha256(f_d.read()).hexdigest()
        hsh = md5(f_d.read()).hexdigest()
        dct.setdefault(hsh, [])
        dct[hsh].append(file_path)

def make_dir_unique(name):
    while os.path.exists(name):
        name = name + '1'

    os.makedirs(name, exist_ok=True)
    return name

def file_uniqness(root_dir):
    unique_size_files = {}
    non_unique_size_files = {}

    non_unique_sizes = set()
    file_cnt = 0

    for path, dirs, files in os.walk(root_dir):
        # Have put this line here for perfomance reasons, despite it makes
        # calculating of progress less accurate.
        # It would be more accurate inside the inner loop.
        print_progress(f"{file_cnt} files have checked", 5.0)

        # Firstly, check every file by size, if the size hasn't appeared before,
        # then no copy of this file was found so far, otherwise an additinal check is
        # needed - by hash.
        for filename in files:
            file_1 = f"{path}/{filename}"
            file_size = os.path.getsize(file_1) 
            file_cnt += 1
            
            # if two or more files with same size exists
            if file_size in non_unique_sizes:
                # Calculate a hash and put it into the dictionary
                add_hash_to_dct(file_1, non_unique_size_files)
            # if only one file with same size exists, so this file was considered as unique
            # until the current file has appeared
            elif file_size in unique_size_files:
                file_2 = unique_size_files.pop(file_size)
                non_unique_sizes.add(file_size)

                add_hash_to_dct(file_1, non_unique_size_files)
                add_hash_to_dct(file_2, non_unique_size_files)
            # if files with the same size doesn't exist
            else:
                unique_size_files[file_size] = file_1

    return unique_size_files, non_unique_size_files

def process_files(unique_files, non_unique_files):
    for old_path in unique_files.values():
        new_path = create_new_path(old_path)
        os.rename(old_path, new_path)

    trash_cnt = 1
    for paths in non_unique_files.values():
        # Some duplicate files have different dates, which was happend
        # because of updating the modification time by some programs while backuping 
        # So, I want to find and apply the first/oldest date of file, because it is
        # most likely the original date.
        file_modification_time, oldest_file_path = get_oldest_file(paths)
        new_path = create_new_path(oldest_file_path, file_modification_time)
        os.rename(oldest_file_path, new_path)

        # I don't want to remove other duplicates immediately, so I just move them
        # into a "trash" directory.
        for same_file_path in paths:
            if same_file_path != oldest_file_path:
                path_to_original_file = '_'.join(new_path.split('/')[-2:])
                os.rename(same_file_path, f"{trash_dir}/{path_to_original_file}_{trash_cnt}")
                trash_cnt += 1

def print_summary(all_files_num, duplicate_files_num):
    print("\n{:#^80}".format("Result"))
    print("{:<20s}{:d}".format("number of files:", all_files_num))
    print("{:<20s}{:d}".format("number of duplicates:", duplicate_files_num))
    print("{:<20s}{:d}".format("number of different files:", all_files_num - duplicate_files_num))

source_dir = sys.argv[1]
dest_dir = f"{source_dir}/Unique_pictures"
trash_dir = f"{source_dir}/Trash_bin"
new_dir_counters = {}

starttime = time()
prevtime = starttime

# Guarantee that new directories are unique.
dest_dir = make_dir_unique(dest_dir)
trash_dir = make_dir_unique(trash_dir)

unique_files, non_unique_files = file_uniqness(source_dir) 

non_unique_files_num = sum(len(val) for val in non_unique_files.values())
all_files_num = len(unique_files) + non_unique_files_num
duplicate_files_num = non_unique_files_num - len(non_unique_files)

# Files movement happens here
process_files(unique_files, non_unique_files)

delete_empty_dirs(source_dir)

print_summary(all_files_num, duplicate_files_num)

Answer 1

Are all used modules optimal or more appropriate are existing? I wasn't use Path module because it is more slow comparing to os.path (by rumors on the internet).

I once saw someone complain when I used an implicit generator expression rather than a list comprehension, as 'the former is slower'. Whilst in this case they were correct, the performance difference was so small most people would think there was no difference and many people that test the performance would think it's down to the margin of error.

Additionally what you have described is called a premature optimization. This is commonly known to be bad as it causes you to use tricks that are harder to understand and makes your code hard to work with; normally with no gain. Whilst you may get a gain, you don't know if that gain was just ridiculously small.

When improving performance you should:

1. Identify the source of the problem.
2. Fix the problem.
3. Test your fix actually fixes the problem.

You should notice that the core problem to premature optimizations is that you're not doing (3). So you're left with poor code, and you don't know how much you gain from that. The worst part is most of the time the performance is negligible or the added complexity has a performance hit. Here it's likely to be negligible.

Looking at your question we can see that you've kinda followed the above steps twice before. (step 2&3)

I have increased performance by changing sha256 to md5 algorithm (in price of reliability), may be you know somewhat else. I have tried shortcuting os.path.getsize to getsize = os.path.getsize but didn't get any speed-up.

1. 2. You changed SHA256 to MD5 to improve performance.
   3. You noticed a speed up.
2. 2. You used getsize rather than os.path.getsize.
   3. you didn't notice a speed up.

The problem is you're currently playing hit the Piñata. You're flailing that stick around, and you may get lucky. But you're mostly just going to hit nothing. This is because you don't know the source of the problem.

There are three ways you can go about this.

1. An educated guess.

   I can guess where the performance is being sunk and see if you're hitting a bottleneck.

   The program is running quite long time, for example 40 000 photos, 180 GB are processed by 40 minutes

   $$\frac{180\ \text{GB} * 1000}{40\ \text{min} * 60} = 75 \text{MB/s}$$

   • SSD - An M.2 NVMe SSD has read speeds of ~2.5 - 3.5 GB/s.^[1] Even if this is not accurate to your SSD (if you have one) then it's so far past the speed we're getting we can assume sequential reads from an SSD is not the problem.
   • HDD - The fastest hard drives are getting ~150 - 200 MB/s sequential reads. ^[2]
   • MD5 - On some seriously older hardware this runs in ~400 MB/s. ^[3]

   If you're running a hard drive then it looks like you may be maxing out the performance of your disk. The speed is in sequential reads, and since you're going to be zipping back and forth from the lookup table (the sectors that say where the 40000 files are located) and the data in the files (that very may well also be fragmented). Running at 50% speed seems fair.

   Whilst a speed up from moving from SHA256 to MD5 may indicate that there is performance you can get out of a hard-drive I would guess the effort it'd take to get this performance would not be worth it.

2. Profile your code.

   This won't tell you the how fast a function is, but it'll tell you roughly where all the slowdown is. The timings are inaccurate and should only be used to see where slowness is. You then need to use another tool to verify that you have indeed increased performance.

   To use this is quite easy, you just use the profile library. Whilst you can profile the code from Python, it is likely easier to just use the command line interface.

   python -m cProfile rearrange_photos.py root_dir
   

3. Time small sections of your code.

   Once you have found a problem piece of code you can try to improve the performance by doing something differently. Like your getsize = os.path.getsize micro-optimization. You can use timeit to do this. I have previously written an answer about some issues this has, and how you can iteratively improve performance when using micro-optimizations.

---

Since I don't really want to emulate your images and I don't know your setup - are you using an SSD or a HDD? How fragmented are your files? What is the structure of your folders and files? - I cannot profile or time your code accurately. However I can make a couple of guesses on how to improve performance of your code.

• Micro-optimizations like os.path.getsize, os.path, etc. are, probably, absolutely useless to you. I don't think the bottleneck is Python - even if Python ran 100 times slower I don't think you'd notice at all. This is because most of the time is probably in IO (system) or the hash (C).

• You want to maximize sequential reads. Most partitions have a lookup table which stores the file structure, the data is then located elsewhere. This means we can at the least get data which we know should be close to each other if we only get the file structure completely before looking at the data.

  NOTE: This can exacerbate the TOCTOU bugs associated with file systems.

• Try to maximize drive usage. To do this I would employ multiprocessing.

  NOTE: You may get performance increases with asyncio or threading. Personally with a rather uneducated guess I think that the GIL will kill any performance you can get with threading. Additionally I'd be careful with asyncio whilst AFAIK async IO and the GIL play ball you may need to become rather educated on two/three technologies to solve this problem.

  To do this you want a 'master' process that has the list (or generator or whatever) of files to validate. From the master you spawn additional processes (commonly called 'slaves') that read the drive and hash the file.

  We can easily see that your file_uniqness fits the master and add_hash_to_dct fits the slave descriptions quite well.

Conclusion

If your data is on a hard-drive, then you time would be better allocated elsewhere. If you're using an SSD first profile your code, if the slowdowns come from what I assume then look into multiprocessing.

You should think about how the technology you're using interacts and influences each other. Yes Python is slow and micro-optimizations can get you some speed, but will they make a hard-drive or file system run faster?

Answer 2

In general use threads for IO bound code and processes for CPU bound code.

Here are two ideas to reduce IO load:

1. Try hashing just a small part of the photo files. For example, just hash the first 512 or 1024 bytes. If two files have the same size and hash, then just compare the two files.

   CHUNKSIZE = 512

   hsh = md5(f_d.read(CHUNKSIZE)).hexdigest()

2. Use stat() to get the file size and mtime in one system call rather than separate getsize() and getmtime() (they each make a call to os.stat())