Самое быстрое изменение размера изображения, готового к производству, часть 1: общие оптимизации

Во вводной статье я представил исчерпывающее изложение задачи. Рассказ получился довольно длинным и немного недоработанным: в нем не было ни единой строчки кода. Однако сложно говорить о конкретных оптимизациях без предыдущего резюме. Конечно, можно применить некоторые техники к любому доступному коду. Например, кеширование вычислений или уменьшение ветвления. Я считаю, что некоторые вещи невозможно сделать без общего понимания проблемы, с которой вы имеете дело. Это то, что отличает живого человека от оптимизирующего компилятора. И поэтому ручная оптимизация по-прежнему играет важную роль: компиляторы работают с кодом, люди - с проблемами. Компилятор не может решить, что число достаточно случайное, в то время как человек может.

Напомним, мы говорим об оптимизации изменения размера изображения с помощью сверточной передискретизации в библиотеке Python Pillow. В этой статье Общая оптимизация я расскажу вам об изменениях, которые я внедрил несколько лет назад. Это не дословная история: я оптимизировал порядок оптимизации повествования. Еще я создал отдельную ветку версии 2.6.2 в репо, это наша отправная точка.

Тестирование

Если вы хотите, чтобы это стало интерактивным и не просто читалось, а запускалось несколько тестов, вот репозиторий Pillow-perf.

Поскольку Pillow состоит из множества модулей и не может быть скомпилирован постепенно, мы используем утилиту ccache для значительного ускорения повторяющихся сборок. pillow-perf позволяет тестировать множество различных операций, но нас интересует именно scale, где -n 3 задает количество запусков теста. Хотя код довольно медленный, давайте воспользуемся меньшим числом -n, чтобы не уснуть. Вот результаты для начальной производительности commit bf1df9a:

Приведенные выше результаты отличаются от официальной версии. 2.6 эталонная производительность. На то есть две причины:

  • В официальном тесте используется 64-разрядная версия Ubuntu 16.04 с GCC 5.3, в то время как для этой статьи я использовал 32-разрядную версию Ubuntu 14.04 с GCC 4.8. К концу вы поймете, почему я это сделал.
  • В этой серии статей я начинаю с фиксации с исправления ошибки, которая не имеет прямого отношения к оптимизации, но влияет на производительность.

Структура кода

Значительная часть кода, который мы собираемся изучить, находится в Antialias.c файле, точнее в функции ImagingStretch. Код функции можно разделить на три части:

Как я подчеркивал в предыдущей статье, изменение размера на основе свертки можно выполнить в два прохода: первый касается изменения ширины изображения, а второй - высоты или наоборот. Функция ImagingStretch обрабатывает одно из измерений за один вызов. Здесь видно, что функция вызывается дважды для каждой операции изменения размера. Сначала идет пролог, а затем та или иная операция в зависимости от входных параметров. Довольно необычный способ избавиться от повторяющегося кода: пролог в данном случае. Внутри функции оба прохода выглядят одинаково с учетом направления обработки. Для краткости вот код одного из проходов:

Мы можем видеть ветвление для форматов изображений, поддерживаемых Pillow: одноканальный 8-битный, оттенки серого; многоканальный 8-битный, RGB, RGBA, LA, CMYK и другие; одноканальные 32-битные и 32-битные с плавающей запятой. Нас особенно интересует многоканальный 8-битный формат, поскольку это наиболее распространенный формат изображений.

Оптимизация 1: эффективное использование кеша

Несмотря на то, что я упомянул, что два прохода выглядят одинаково, есть существенная разница. Давайте сначала посмотрим на вертикальный проход:

И горизонтальный:

В то время как на вертикальном проходе мы перебираем столбцы полученного изображения, на горизонтальном мы имеем дело с строками. Таким образом, горизонтальный проход представляет собой серьезную проблему для кеш-памяти процессора. Каждый шаг встроенного цикла обращается к одной нижней строке, таким образом запрашивая значение, которое далеко от значения, необходимого для предыдущего шага. Это проблема при работе со сверткой меньшего размера. Дело в том, что современные процессоры способны читать только 64-байтовую строку кэша из ОЗУ. Это означает, что когда мы сворачиваем менее 16 пикселей, чтение некоторой части данных из ОЗУ в кеш будет пустой тратой. Теперь представьте, что мы перевернули циклы: теперь каждый свернутый пиксель находится не в следующей строке, а в следующем пикселе текущей строки. Следовательно, большая часть необходимых пикселей уже будет в кеше.

Второй негативный фактор такой организации кода связан с длинной линией свертки: в случае значительного даунскейлинга. Дело в том, что для соседних сверток исходные пиксели существенно пересекаются, и было бы здорово, если бы эти данные остались в кеше. Но когда мы движемся сверху вниз, данные для старых сверток постепенно заменяются из кеша данными для новых. В результате после встроенного цикла при запуске следующего внешнего шага в кеше нет верхних строк, все они заменяются нижними. Следовательно, мы должны снова прочитать эти верхние строки из ОЗУ. А когда дело доходит до нижних строк, все данные уже заменены более высокими строками в кеше. Получается цикл, в котором никакие нужные данные никогда не находятся в кеше.

Почему это так? В псевдокоде выше мы видим, что вторая строка в обоих случаях предназначена для вычисления коэффициентов свертки. Для вертикального прохода коэффициенты зависят только от значений yy в строке результирующего изображения, а для горизонтального - от значений xx в текущем столбце. Следовательно, мы не можем просто поменять местами два цикла в горизонтальном проходе: мы должны вычислить коэффициенты внутри цикла для xx. Если мы начнем считать коэффициенты во встроенном цикле, мы получим снижение производительности. Особенно, когда мы используем фильтр Ланцоша для вычислений: он использует тригонометрические функции.

Таким образом, нам не следует вычислять коэффициенты на каждом шаге, даже если они идентичны для каждого пикселя в столбце. Однако мы можем заранее рассчитать коэффициенты для всех столбцов и использовать их во встроенном цикле. Давай сделаем это.

Есть строка для выделения памяти для коэффициентов:

k = malloc(kmax * sizeof(float));

Теперь нам понадобится массив таких массивов. Мы можем упростить, выделив плоский фрагмент памяти и эмулируя два измерения с помощью адресации:

kk = malloc(imOut->xsize * kmax * sizeof(float));

Нам также понадобится хранилище для xmin и xmax, которые также зависят от xx. Сделаем массив для таких:

xbounds = malloc(imOut->xsize * 2 * sizeof(float));

Также внутри цикла для нормализации используется значение ww, ww = 1 / Σk. Нам вообще не нужно его хранить. Вместо этого мы можем нормализовать сами коэффициенты, а не результаты свертки. Итак, как только мы вычислим коэффициенты, мы снова перебираем их, деля каждое отдельное значение на сумму коэффициентов. В результате сумма всех коэффициентов становится 1.0:

Наконец, мы можем повернуть процесс на 90 градусов:

Вот результаты производительности, которые мы получаем, commit d35755c:

Четвертый столбец показывает улучшения производительности.

Оптимизация 2: ограничение значений выходных пикселей

В некоторых частях кода мы можем увидеть такую ​​конструкцию:

Фрагмент предназначен для ограничения значений пикселей в 8-битном диапазоне [0, 255] в случае, если результаты вычислений выходят за его пределы. Это может произойти, потому что сумма всех положительных коэффициентов свертки может быть больше единицы, а сумма всех отрицательных может быть меньше нуля. Так что иногда мы можем наткнуться на переполнение. Переполнение является результатом компенсации резких градиентов яркости и не является ошибкой.

Давайте посмотрим на код. Есть одна входная переменная ss и одна выходная imOut-> image[yy]. Выходные данные получают присвоенные значения в нескольких местах. Дело в том, что мы сравниваем числа с плавающей запятой, тогда как было бы более эффективно преобразовать значения в целые числа, а затем выполнить сравнение. Итак, это функция:

Использование:

imOut->image[yy][xx*4+b] = clip8(ss);

Эта оптимизация также дает нам прирост производительности, на этот раз умеренный, commit 54d3b9d:

Как видите, эта оптимизация больше влияет на фильтры с меньшими окнами и большим выходным разрешением, за единственным исключением 320x200 Bilinear; Я не исследовал, почему это сработало. Это логично, чем меньше окно фильтра и больше окончательное разрешение, тем больше наше ограничение значения влияет на общую производительность.

Оптимизация 3. Разворачивающиеся циклы с постоянным числом итераций.

Если мы снова просмотрим код горизонтального прохода, мы обнаружим четыре внутренних цикла:

Мы перебираем каждую строку и столбец выходного изображения: если быть точным, каждый пиксель. Встроенные циклы используются для перебора каждого пикселя входного изображения, которое нужно свернуть. А что насчет b? Он нужен для перебора полос вашего изображения. Совершенно очевидно, что количество полос изображений постоянно и не превышает четырех: это связано с тем, как Pillow представляет изображения. Следовательно, есть четыре возможных случая, один из которых касается одноканальных 8-битных изображений. Они представлены по-разному, поэтому окончательное количество дел - три. Теперь мы можем сделать три отдельных внутренних цикла: для 2-, 3- и 4-полосных изображений соответственно. Затем мы добавляем ветвление для переключения между режимами. Вот код для наиболее распространенного случая трехканального изображения, чтобы не занимать здесь много места:

Мы можем пойти еще дальше и развернуть ветвление еще раз, в цикл для xx:

Вот какие улучшения производительности мы получаем, commit 95a9e30.

Нечто подобное можно найти и для вертикального прохода. Вот исходный код:

Нет итераций по каналам. Вместо этого xx выполняет итерацию по ширине, умноженной на четыре, то есть xx проходит через каждый канал независимо от количества полос в изображении. FIXME в комментарии относится к этому исправлению. Мы делаем то же самое: добавляем ветвление для переключения в зависимости от количества полос входного изображения. Код можно найти в commit f227c35, вот результаты:

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

Оптимизация 4. Целочисленные итераторы.

Если мы посмотрим на встроенный цикл, то увидим, что ymin и ymax объявлены как числа с плавающей запятой. Однако на каждом этапе они преобразуются в целые числа. Более того, вне цикла, когда переменным присваиваются какие-либо значения, используются функции floor и ceil. Таким образом, каждое присвоенное им значение является целым числом, даже если переменные изначально объявлены как числа с плавающей запятой. То же самое можно применить к xmin и xmax. Давайте изменим это и проверим производительность, commit 57e8925:

Финал первого акта: битва с боссом

Признаюсь, я был доволен результатами. Мне удалось ускорить код в 2,5 раза, и вам не нужно использовать лучшее оборудование или что-то в этом роде, чтобы получить ускорение: такое же количество ядер одного и того же процессора. Единственным требованием было обновление Pillow до версии 2.7. До выхода обновления еще оставалось время, и я хотел протестировать новый код на сервере, для которого оно предназначалось. Я клонировал код, скомпилировал его, и сначала у меня даже появилось ощущение, что что-то не так:

Lolwut !? Все выполнялось так же, как и до любой оптимизации. Я перепроверил все десять раз и включил print, чтобы проверить, правильно ли я выполняю код. И это не было побочным эффектом Pillow или среды: проблему можно было легко воспроизвести даже на небольшом фрагменте кода из 30 строк. Я разместил вопрос на StackOverflow, и в конце концов мне удалось обнаружить такую ​​закономерность: код был медленным при компиляции с GCC для 64-битной платформы. И в этом была разница между системами, работающими на моем ноутбуке (32-разрядная версия) и сервером (64-разрядная версия), на который я клонировал код.

Что ж, Слава Муру, я не был сумасшедшим, это был настоящий баг в компиляторе. Более того, они исправили ошибку в GCC 4.9, но GCC 4.8 был включен в текущий дистрибутив Ubuntu 14.04 LTS. То есть GCC 4.8, скорее всего, был установлен большинством пользователей библиотеки. Игнорировать это было непрактично: как пользователи выиграют от оптимизации, если она не работает в большинстве случаев, включая тот, для которого она была сделана. Я обновил вопрос на StackOverflow и написал твит. Так мне на помощь пришел Вячеслав Егоров, бывший разработчик двигателя V8 и гений оптимизации.

Чтобы понять проблему, нам нужно глубже погрузиться в историю процессоров и их текущую архитектуру. Раньше процессоры x86 не работали с числами с плавающей запятой, сопроцессоры x87 с включенным набором команд сделали это за них. Они будут выполнять инструкции из того же потока, что и ЦП, но были установлены на материнской плате как отдельные устройства. Затем сопроцессоры встраивались в центральные и вместе физически составляли одно устройство. Рано или поздно в процессоре Pentium III Intel представила набор инструкций под названием SSE (Streaming SIMD Extensions). Кстати, третья статья серии будет посвящена SIMD-инструкции. Несмотря на свое название, SSE содержал не только инструкции SIMD для работы с числами с плавающей запятой, но и их эквиваленты для скалярных вычислений. То есть SSE содержал набор инструкций, дублирующих набор x87, но закодированных и действующих по-другому.

Однако компиляторы не торопились сгенерировать код SSE для вычислений с плавающей запятой, а продолжали использовать старый набор x87. В конце концов, существование SSE в процессоре не могло быть гарантировано, пока набор x87 был там десятилетиями. Все изменилось, когда отключился режим 64-битного процессора. Для этого режима набор инструкций SSE2 стал обязательным. Итак, если вы пишете 64-битную программу для x86, вам как минимум будет доступен набор инструкций SSE2. И это то, что используют компиляторы: они генерируют инструкции SSE для вычислений с плавающей запятой в 64-битном режиме. Опять же, я говорю об обычных скалярных вычислениях, без векторизации.

Так и произошло в нашем случае: для 32-битного и 64-битного режима использовались разные наборы инструкций. Однако это не объясняет, почему более поздний код SSE работал во много раз медленнее, чем устаревший код x87. Чтобы понять это явление, давайте поговорим о том, как процессоры выполняют инструкции.

Некоторое время назад процессоры действительно «выполняли» инструкции. Они получали инструкцию, декодировали ее, выполняли то, о чем она говорила, и помещали результаты туда, где они должны были. Те могли быть умнее, и это случилось. Современные процессоры умнее и сложнее: они состоят из десятков различных подсистем. На одном ядре без какой-либо параллельной обработки процессоры выполняют несколько инструкций за один такт. Это выполнение происходит на разных этапах для разных инструкций: пока одни декодируются, другие получают данные из кеша, другие передаются в арифметический блок. Каждая процессорная подсистема имеет дело со своей частью инструкции. Это называется конвейером ЦП.

На картинке цветами показаны разные подсистемы ЦП. Несмотря на то, что для выполнения инструкций требуется 4–5 циклов, благодаря конвейеру в каждом тактовом цикле одна инструкция может быть запущена, а другая завершена.

Трубопровод работает эффективнее, чем равномернее он заполняется и тем меньше подсистем простаивает. Есть даже подсистемы ЦП, которые планируют оптимальное наполнение конвейера: они меняют местами, разделяют или объединяют инструкции.

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

На рисунке показано, что вторая инструкция ожидает завершения первой. Большинство подсистем простаивают. Это замедляет выполнение всей цепочки инструкций.

А теперь, со всей информацией, давайте посмотрим на псевдокод инструкции, преобразующей целое число в число с плавающей запятой:

Результаты записываются в младшие 32 бита. Хотя далее написано, что младшие биты из регистра a передаются в регистр dst, это не то, что происходит. Глядя на подпись инструкции, мы видим, что она имеет дело только с одним xmm регистром, что означает, что и dst, и a относятся к одному и тому же регистру: старшие 96 бит никуда не перемещаются. И вот где у нас есть зависимость данных. Инструкция составлена ​​таким образом, чтобы гарантировать безопасность старших битов, и поэтому нам нужно дождаться результатов всех других операций, работающих с регистром, чтобы выполнить ее.

Однако дело в том, что мы не используем ни один из старших битов и заинтересованы в младших 32-битных числах с плавающей запятой. Нас не интересуют высшие биты, поэтому они не влияют на наши результаты. Это называется зависимостью от ложных данных.

К счастью, мы можем разорвать зависимость. Перед выполнением инструкции преобразования cvtsi2ss компилятор должен выполнить очистку реестра через xorps. Я не могу назвать это исправление интуитивным и даже логичным. Скорее всего, это не исправление, а взлом на уровне декодера, который заменяет xorps + cvtsi2ss некоторой внутренней инструкцией со следующим псевдокодом:

Исправление для GCC 4.8 довольно уродливое; он состоит из ассемблера и кода препроцессора, который проверяет, можно ли применить исправление. Я не буду показывать здесь код. Однако вы всегда можете проверить commit 81fc88e. Это полностью исправляет 64-битный код. Вот как это влияет на производительность на сервере:

Ситуация, которую я описал в этой части серии, довольно частая. Код, преобразующий целые числа в числа с плавающей запятой, а затем выполняющий некоторые вычисления, можно найти практически в любой программе. То же самое, например, с ImageMagick: его 64-разрядные версии, скомпилированные с помощью GCC 4.9, на 40% быстрее, чем версии, скомпилированные с использованием предыдущих версий GCC. На мой взгляд, это серьезный недостаток SSE.

Краткое заключение

Вот как мы достигли среднего улучшения в 2,5 раза без изменения подхода: с помощью общих оптимизаций. В моей следующей статье я покажу, как ускорить этот результат в 3,5 раза, применяя методы SIMD.

Так что следите за обновлениями: подписывайтесь на нас в Twitter, чтобы знать, когда выйдет следующая часть!

Автор Alex Karpinsky, инженер-программист @ Uploadcare, ознакомьтесь с вводной статьей к серии 🚀