Непонятное замедление конкатенации в цикле

#python #многопоточность #строки #циклы #производительность

Всем добра. 

Приходит строка байт buffered_img длиной 786'432 байта (Grayscale 8bit изображение
1024x768). Запускается обработчик в отдельном потоке (если считать в основном потоке,
то просто виснет окно). Алгоритм такой: берется 0-вой пиксель из оригинального изображения
(первый байт из строки buffered_img), проверяется его 7-ой бит, если он равен 0, то
к строке nine['img_7'] дописывается байт '\x00', если 1, то '\xff', затем берется 6-ой
бит 0-го пикселя, также проверяется и дописывается к nine['img_6'] и т.д. до 0 бита.
Эта операция повторяется для всех пикселей. В итоге получаем 9 изображений: оригинальное
+ 8 генерированных. 

Так вот, проблема в том, что с каждой операцией конкатенации, процесс замедляется,
ползунок QProgressBar (PyQt5), который завязан на сигнал generating, ползет все медленнее
и медленнее с каждым процентом, хотя поначалу все идет бодро. Если бы проценты капали
с самого начала медленно, претензий бы не возникло, но на лицо явное замедление процесса
конкатенации, и моего скудного опыта в программировании не хватает, для того, чтобы
объяснить это явление. Кто подскажет, в чем проблема? Вот кусочки кода:

# Глобальный словарь с байт-строками генерированных картинок
nine = {'img_7': b'', 'img_6': b'', 'img_5': b'', 'img_4': b'',
    'img_3': b'', 'img_2': b'', 'img_1': b'', 'img_0': b''}
b0 = pack('B', 0)
b255 = pack('B', 255)

# Метод run() QThread в котором buffered_img - байт строка с оригинальным изображением
def run(self):
    global nine, img_str
    self.start_gen.emit(len(buffered_img))
    pb_val = 0
    for img in nine:
        nine[img] = b''
    for byte_ in buffered_img:
        pb_val += 1
        self.generating.emit(pb_val)
        bit_str = self.by2bi(byte_)
        for i in range(8):
            if bit_str[i] == '0':
                nine['img_' + str(i)] += b0
            else:
                nine['img_' + str(i)] += b255
    self.stop_gen.emit()

# Подсмотренный где-то код, на выходе выдает строку типа ('10110100' для
# входного байта '\xb4'
def by2bi(self, bytestring):
    try:
        bits = bin(int(hexlify(bytestring), 16))[2:]
        data = bits.zfill(8 * ((len(bits) + 7) // 8))
        del bits
        return data
    except ValueError:
        print 'Error bytes2bits decode!'

    

Ответы

Ответ 1

Основная проблема в том, что вы используете квадратичный алгоритм O(n2):

байтовая_строка = b""
for byte_ in buffered_img:
    байтовая_строка += b"data" * byte_


Байтовые строки в Питоне неизменяемы, поэтому каждая += операция создаёт новую всё
бо́льшую строку (O(n) операция, требующая времени пропорционально текущей длине строки)
— как маляр из анекдота: "Ничего не могу поделать—Каждый день я ухожу все дальше и
дальше от банки!" (перевод). n умножить на O(n) операций делает весь цикл O(n2) алгоритмом.

Первое улучшение: используйте линейный алгоритм O(n):

result = bytearray()
for byte_ in buffered_img:
    result += b"data" * byte_
байтовая_строка = bytes(result)


В этом случае += операция добавляет от 0 до 4*255 байт в конец одного и того же result
массива, не создавая его каждый раз заново. += операция в этом случае O(1) (амортизировано)
— требует постоянного времени, не зависящего от длины buffered_img, поэтому весь цикл
занимает n умножить на  O(1), то есть O(n), что гораздо лучше чем O(n2). Для обычных
строк (str), можно использовать список вместо bytearray() и добавив отдельные строки
с помощью list_of_strings.append(s), результат ''.join(list_of_strings) (это гарантирует
линейный алгоритм).

В обоих примерах (c байтовой строкой и с bytearray) память растёт, и не смотря на
идентичный код в цикле, один пример это квадратичный алгоритм, а другой линейный. Разница
в том по какому алгоритму выделяется память — в одном случае всегда ровно сколько нужно
(под новую байтовую строку) на каждой итерации, а в другом на величину пропорциональную
текущему размеру (увеличивается место для массива), только когда размер дорастает до
ёмкости. К примеру, ArrayList в Java в полтора раза увеличивает ёмкость каждый раз
при заполнении, Python list ~1.125 — именно это позволяет избежать квадратичного поведения
(если бы к массив увеличивался на каждой итерации, то получился бы O(n2)  алгоритм
из-за O(n) худшего случая для realloc() — фактическая производительность зависит от
реализации realloc() на выбранной платформе, к примеру, выключение 1.125 умножения
для bytearray() на моей Linux машине не изменило существенно результаты измерений).
Уже для умеренных размеров порядка 106 возможно появление квадратичного поведения из-за
отсутствия overallocation при вызове realloc() для строк: Why does naive string concatenation
become quadratic above a certain length?

Подробнее о конкатенации строк от создателя Питона. Статья очень старая, поэтому
детали, связанные с реализацией, могут отличаться на современном Питоне (к примеру,
CPython может иногда автоматически оптимизировать конкатенацию строк), но общие принципы
оптимизации остались прежними: не пытайтесь оптимизировать  без измерений производительности,
используйте profiler, проверяйте на квадратичность ваши алгоритмы, меньше кода — лучше,
перемещайте «горячие циклы» в C.

Сравнение производительности

Квадратичный алгоритм:

$ python3 -m perf timeit -s 'buffered_img = b"\x01" * 10_000' '
байтовая_строка = b"" 
for byte_ in buffered_img:
    байтовая_строка += b"data" * byte_'
.....................
Mean +- std dev: 14.2 ms +- 0.5 ms


Линейный:

$ python3 -m perf timeit -s 'buffered_img = b"\x01" * 10_000' '
result = bytearray()
for byte_ in buffered_img:
    result += b"data" * byte_
байтовая_строка = bytes(result)'
.....................
Mean +- std dev: 932 us +- 18 us


Если увеличить размер buffered_img в десять раз, то время исполнения линейного алгоритма
увеличится примерно в десять раз (с 0.9 ms до 9 ms):

$ python3 -m perf timeit -s 'buffered_img = b"\x01" * 100_000' '
result = bytearray()
for byte_ in buffered_img:
    result += b"data" * byte_
байтовая_строка = bytes(result)'
.....................
Mean +- std dev: 9.43 ms +- 0.35 ms


Время для квадратичного алгоритма увеличивается примерно в сто раз (с 0.014s до 2s):

$ python3 -m perf timeit -s 'buffered_img = b"\x01" * 100_000' '
байтовая_строка = b""  
for byte_ in buffered_img: 
    байтовая_строка += b"data" * byte_' 
.....................
Mean +- std dev: 2.05 sec +- 0.06 sec


Чем длиннее buffered_img тем хуже квадратичный алгоритм по сравнению с линейным (для
len(buffered_img) ~ 100_000 на два порядка разница ~10ms против ~2000 ms).



В CPython, "+=" реализуется INPLACE_ADD инструкцией интерпретатора и для аргументов
str типа, на которые нет ссылок в других частях кода, используется оптимизация (realloc()
вызывается) и, даже без экспоненциального роста размера новой памяти, измерения демонстрируют
линейное поведение для str типа на моей Linux машине (увеличение длины в 10 раз увеличивает
время примерно в 10 раз):

$ python3  -mtimeit $'s = ""\nfor _ in range(10000): s+= "a"'
200 loops, best of 5: 1.21 msec per loop
$ python3  -mtimeit $'s = ""\nfor _ in range(100000): s+= "a"'
20 loops, best of 5: 12.1 msec per loop
$ python3  -mtimeit $'s = ""\nfor _ in range(1000000): s+= "a"'
2 loops, best of 5: 120 msec per loop


О том как realloc() на Linux реализован A Story of Realloc (and Laziness)(перевод).

Для unicode типа на Питоне 2 и для bytes типа на Питоне 3 на текущих версиях нет
оптимизации "+=" (исходная строка всегда копируется в PyUnicode_Concat() и bytes_concat()
соответственно) — квадратичное поведение (увеличение длины в 10 раз, увеличивает время
примерно в 100 раз):

$ python3  -mtimeit $'s = b""\nfor _ in range(10000): s+= b"a"'
100 loops, best of 5: 3.81 msec per loop
$ python3  -mtimeit $'s = b""\nfor _ in range(100000): s+= b"a"'
1 loop, best of 5: 352 msec per loop
$ python3  -mtimeit $'s = b""\nfor _ in range(1000000): s+= b"a"'
1 loop, best of 5: 46.6 sec per loop


Другие улучшения

Использование правильного алгоритма как правило важнее других факторов, но ещё можно
улучшить константу алгоритма (функция роста времени та же, но каждая операция быстрее),
используя numpy, чтобы выполнять операцию над несколькими байтами одновременно, пример:
a_out[::2] = a_in << 2. Или перенести эти операции в Сython, пример. Ещё пример кода,
который заменяет Питон-цикл, кодом, который на уровне C с отдельными байтами работает.
Ещё пример, где улучшение производительности тем же способом достигается.

Перенос Питон-цикла в С расширения (numpy, Cython, random.getrandbits(), bin(), bytes.translate()
в примерах) также позволяет несколько CPU ядер задействовать при использовании потоков
 в СPython (GIL может освобождаться на время вычислений в C).