Как я могу оптимизировать производительность скрипта сравнения изображений?

Question

Я написал сценарий, который сравнивает огромный набор изображений (более 4500 файлов) друг против друга с использованием среднеквадратичного сравнения. Сначала он изменяет размер каждого изображения до 800x600 и берет гистограмму. После этого он создает массив комбинаций и равномерно распределяет их по четырем потокам, которые вычисляют средний квадрат корня каждой комбинации. Изображения с RMS ниже 500 будут перемещены в папки, которые будут вручную отсортированы позже.

#!/usr/bin/python3 

import sys 
import os 
import math 
import operator 
import functools 
import datetime 
import threading 
import queue 
import itertools 
from PIL import Image 


def calc_rms(hist1, hist2): 
    return math.sqrt(
     functools.reduce(operator.add, map(
      lambda a, b: (a - b) ** 2, hist1, hist2 
     ))/len(hist1) 
    ) 


def make_histogram(imgs, path, qout): 
    for img in imgs: 
     try: 
      tmp = Image.open(os.path.join(path, img)) 
      tmp = tmp.resize((800, 600), Image.ANTIALIAS) 
      qout.put([img, tmp.histogram()]) 
     except Exception: 
      print('bad image: ' + img) 
    return 


def compare_hist(pairs, path): 
    for pair in pairs: 
     rms = calc_rms(pair[0][1], pair[1][1]) 
     if rms < 500: 
      folder = 'maybe duplicates' 
      if rms == 0: 
       folder = 'exact duplicates' 
      try: 
       os.rename(os.path.join(path, pair[0][0]), os.path.join(path, folder, pair[0][0])) 
      except Exception: 
       pass 
      try: 
       os.rename(os.path.join(path, pair[1][0]), os.path.join(path, folder, pair[1][0])) 
      except Exception: 
       pass 
    return 


def get_time(): 
    return datetime.datetime.now().strftime("%H:%M:%S") 


def chunkify(lst, n): 
    return [lst[i::n] for i in range(n)] 


def main(path): 
    starttime = get_time() 
    qout = queue.Queue() 
    images = [] 
    for img in os.listdir(path): 
     if os.path.isfile(os.path.join(path, img)): 
      images.append(img) 
    imglen = len(images) 
    print('Resizing ' + str(imglen) + ' Images ' + starttime) 
    images = chunkify(images, 4) 
    threads = [] 
    for x in range(4): 
     threads.append(threading.Thread(target=make_histogram, args=(images[x], path, qout))) 

    [x.start() for x in threads] 
    [x.join() for x in threads] 

    resizetime = get_time() 
    print('Done resizing ' + resizetime) 

    histlist = [] 
    for i in qout.queue: 
     histlist.append(i) 

    if not os.path.exists(os.path.join(path, 'exact duplicates')): 
     os.makedirs(os.path.join(path, 'exact duplicates')) 
    if not os.path.exists(os.path.join(path, 'maybe duplicates')): 
     os.makedirs(os.path.join(path, 'maybe duplicates')) 

    combinations = [] 
    for img1, img2 in itertools.combinations(histlist, 2): 
     combinations.append([img1, img2]) 

    combicount = len(combinations) 
    print('Going through ' + str(combicount) + ' combinations of ' + str(imglen) + ' Images. Please stand by') 
    combinations = chunkify(combinations, 4) 

    threads = [] 

    for x in range(4): 
     threads.append(threading.Thread(target=compare_hist, args=(combinations[x], path))) 

    [x.start() for x in threads] 
    [x.join() for x in threads] 

    print('\nstarted at ' + starttime) 
    print('resizing done at ' + resizetime) 
    print('went through ' + str(combicount) + ' combinations of ' + str(imglen) + ' Images') 
    print('all done at ' + get_time()) 

if __name__ == '__main__': 
    main(sys.argv[1]) # sys.argv[1] has to be a folder of images to compare 

Это работает, но сравнение выполняется в течение нескольких часов после завершения изменения размеров в течение 15-20 минут. Сначала я предположил, что это была очередь блокировки, из которой рабочие получили свои комбинации, поэтому я заменил ее заранее определенными кусками массива. Это не уменьшило время выполнения. Я также запускал его, не перемещая файлы, чтобы исключить возможную проблему с жестким диском.

Профилирование с использованием cProfile предоставляет следующий вывод.

Resizing 4566 Images 23:51:05 
Done resizing 00:05:07 
Going through 10421895 combinations of 4566 Images. Please stand by 

started at 23:51:05 
resizing done at 00:05:07 
went through 10421895 combinations of 4566 Images 
all done at 03:09:41 
     10584539 function calls (10584414 primitive calls) in 11918.945 seconds 

    Ordered by: cumulative time 

    ncalls tottime percall cumtime percall filename:lineno(function) 
    16/1 0.001 0.000 11918.945 11918.945 {built-in method exec} 
     1 2.962 2.962 11918.945 11918.945 imcomp.py:3(<module>) 
     1 19.530 19.530 11915.876 11915.876 imcomp.py:60(main) 
     51 11892.690 233.190 11892.690 233.190 {method 'acquire' of '_thread.lock' objects} 
     8 0.000 0.000 11892.507 1486.563 threading.py:1028(join) 
     8 0.000 0.000 11892.507 1486.563 threading.py:1066(_wait_for_tstate_lock) 
     1 0.000 0.000 11051.467 11051.467 imcomp.py:105(<listcomp>) 
     1 0.000 0.000 841.040 841.040 imcomp.py:76(<listcomp>) 
10431210 1.808 0.000 1.808 0.000 {method 'append' of 'list' objects} 
    4667 1.382 0.000 1.382 0.000 {built-in method stat} 

Полный выход профилировщика можно найти here.

Учитывая четвертую строчку, я предполагаю, что потоки как-то блокируются. Но почему и почему ровно 51 раз независимо от количества изображений?

Я запускаю это на Windows 7 64 бит.

Заранее благодарен.

Answer 1

Одна из основных проблем заключается в том, что вы используете потоки для выполнения работы, которая по крайней мере частично связана с ЦП. Из-за блокировки Global Interpreter Lock может работать только один поток CPython за раз, что означает, что вы не можете воспользоваться преимуществами нескольких процессорных ядер. Это обеспечит многопоточную производительность для задач, связанных с процессором, в лучшем случае не отличающихся от одноядерных и, вероятно, даже хуже, из-за дополнительных накладных расходов, добавленных потоками. Это отмечено в threading documentation:

CPython деталь реализации: В CPython, из-за глобальной интерпретатора Блокировка, только один поток может выполнять код Python сразу (даже несмотря на некоторые показатели, ориентированные библиотеки могут преодолеть это ограничение). Если вы хотите, чтобы ваше приложение использовало вычислительные ресурсы многоядерных машин, рекомендуется использовать multiprocessing. Тем не менее, потоки по-прежнему являются подходящей моделью , если вы хотите одновременно запускать несколько задач, связанных с вводом-выводом.

Чтобы обойти ограничения на GIL, вы должны сделать, как говорят документы, а также использовать multiprocessing библиотеку вместо threading библиотеки:

import multiprocessing 
... 

qout = multiprocessing.Queue() 

for x in range(4): 
    threads.append(multiprocessing.Process(target=make_histogram, args=(images[x], path, qout))) 

... 
for x in range(4): 
    threads.append(multiprocessing.Process(target=compare_hist, args=(combinations[x], path))) 

Как вы можете видеть, multiprocessing для наиболее часть - замена на threading, поэтому изменения не должны быть слишком сложными. Единственное осложнение было бы, если бы какой-либо из аргументов, которые вы проходили между процессами, не был сорван, хотя я думаю, что все они в вашем случае. Существует также повышенная стоимость IPC для отправки структур данных Python между процессами, но я подозреваю, что польза от действительно параллельных вычислений перевешивает дополнительные накладные расходы.

Все, что сказало, вы можете быть здесь несколько в/в, связанным здесь, из-за зависимости от чтения/записи на диск. Параллелизация не приведет к ускоренному вводу/выводу вашего диска, поэтому там не так много.

Answer 2

С 4500 изображениями для сравнения я бы предложил многопроцессорную обработку на уровне файла, а не (обязательно) многопоточность внутри изображения. Как отметил @dano, GIL будет мешать этому. Моей стратегией было бы:

1. один рабочий процесс на ядро ​​(или настроенное число);
2. один процесс оркестровки, который развивает выше; делает некоторые МПК для координации рабочих мест с рабочими.

Взгляд (на короткое время) на ваш код выглядит так, как будто это будет полезно для ленивого языка; Я не вижу, что делает попытку коротких замыканий. Например, если вы сравниваете RMS для каждого сегмента изображения, вы можете прекратить сравнивать, как только вы закончите сравнивать куски, как только вы определите, что они достаточно разные. Тогда вы также можете изменить способ, которым вы итерации через куски, и размер/форму кусков.

Помимо этого, я хотел бы рассмотреть возможность использования более дешевых механизмов, позволяющих избежать множества квадратных корней; возможно, используя что-то, что создает «приблизительный» квадратный корень, возможно, используя справочную таблицу.

Если я не ошибаюсь, вы также можете создать промежуточную форму (гистограмму), которую вы должны хранить временно. Не нужно сохранять изображение 800x600.

Также было бы полезно узнать, что вы имеете в виду как «равный» в отношении этого упражнения.