Многие из них я выучил в университете, но либо не до конца понял, либо забыл из-за отсутствия практики. Использование его на работе изменило правила игры!

Для многих из нас, работающих в области компьютерных наук, наше раннее образование в этой области начинается с концепции большого O или большого Omega (Ω).

Большой O используется в информатике для описания производительности или сложности алгоритма. Big O используется для описания сложности алгоритмов в наихудшем случае, а Big Omega используется для описания сложности в наилучшем случае.

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

Одна проблема программирования может быть решена несколькими способами, поэтому ключевым аспектом часто является уменьшение сложности времени и пространства — большое О.

Быстрым примером этого может быть поиск элемента в отсортированном массиве.

  • Алгоритм грубой силы имеет сложность O(N).
  • OTOH, бинарный поиск будет иметь сложность O(logN).

Это означает, что если бы у вас было около 10⁶ элементов в отсортированном входном массиве

  • При подходе грубой силы в худшем случае потребуется 10⁶ итераций.
  • В то время как с бинарным поиском (оптимизированным) вам потребуется около log2(10^6) ~ 20 итераций.

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

К счастью, моя работа в Google позволяла мне уделять этому много времени. Я работаю над продуктом под названием Камера от Google. Это приложение Android Camera для недорогих устройств Android. Таким образом, моя работа связана с исследованием и внедрением высококачественных вычислительных алгоритмов фотографии, которые могут работать на слабом мобильном оборудовании.

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



Я работал в Microsoft Cloud и Google Mobile в течение 3 лет — вот различия в экосистемах
Почему работа в облаке и на мобильных устройствах (Edge) так отличается?betterprogramming.pub



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

В этой статье будет рассмотрено несколько примеров такой оптимизации с доказательствами.

Предисловие

В этой статье я буду использовать примеры кода Halide. Подробно я написал о Галиде в серии статей.

TL;DR; Halide – это предметно-ориентированный язык, упрощающий написание высокопроизводительного кода для обработки изображений и массивов на современных компьютерах.

Все числа, представленные в этой статье, измерены с использованием кода, написанного на Halide/C++, созданного с включенной оптимизацией компилятора и измеренного с использованием среды microbenchmark.

Тесты проводились на определенном восьмиъядерном устройстве среднего уровня с ОС arm64 Android. Все упомянутые подходы выполняются на ЦП.

Векторизация

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

Его можно выразить как f(x, y) = x + y или для двумерного массива как a[y][x] = x + y.

В нашем скалярном мышлении мы представляем, что он выполняется один раз для каждого пикселя WIDTH * HEIGHT раза, что дает временную сложность O(WIDTH * HEIGHT).

Раньше это было правдой. Раньше процессоры имели только возможности SISD. SISD расшифровывается как Single Instruction Single Data.

Напротив, современные ЦП имеют возможности SIMD. SIMD расшифровывается как Single Instruction Multiple Data.

Современные ЦП могут одновременно выполнять одну инструкцию для вектора данных (несколько данных) в одном цикле выполнения в зависимости от типа данных и размера регистра ЦП.

Допустим, вы выполняли операцию сложения, например a[i] = a[i] + b[i]. Вместо того, чтобы запускать его отдельно для каждого индекса, современный процессор может выполнять его как вектор:

a[i + 0] = a[i + 0] + b[i + 0];
a[i + 1] = a[i + 1] + b[i + 1];
a[i + 2] = a[i + 2] + b[i + 2];
a[i + 3] = a[i + 3] + b[i + 3];

За один присест.

Это также не ограничивается простым добавлением 4 чисел — в зависимости от типа данных (например, uint8 = 1 байт, int32 = 4 байта) и размера регистра процессора и поддерживаемых наборов инструкций — максимальное количество элементов данных может быть обработано за один раз. Цикл процессора может варьироваться.

Возможно, вы видели, как в наши дни появляется все больше и больше DSP (цифровых сигнальных процессоров) (например, Hexagon от Qualcomm). Среди прочего, они, как правило, имеют очень широкие регистры, предназначенные для поддержки широкой арифметики SIMD. Это позволило им поддерживать более эффективную параллельную работу с данными.

Визуализация

Если что-то еще не ясно, позвольте мне представить некоторые графики. Вот как будет выглядеть ваше скалярное выполнение градиента для изображения 4x4.

А вот как это будет выглядеть с SIMD (для изображения a4x8)

Сравнительные результаты

Я прекрасно знаю, что вы, голодные до цифр, не купитесь, пока я не покажу несколько цифр!

Код

Результат

В этом примере векторизованный код в среднем на ~3 times быстрее, чем не векторизованный код.

Цифры могут быть разными в зависимости от алгоритма и типа данных. Например, для простого алгоритма повышения яркости, такого как f(x, y) = g(x, y) + b, я обнаружил, что векторизованный код на ~5.3 times быстрее, чем не векторизованный код для u8 типа данных в той же среде.

Как это использовать?

Иногда компилятор автоматически векторизует ваш код. Это зависит от используемого компилятора и от того, как спроектированы циклы. Иногда это невозможно, например, если он не может определить, что ваши циклы не зависят от данных.

Такой цикл, как a[i] = a[i-1] — 1, трудно векторизовать, так как результат для каждого индекса зависит от результата предыдущего индекса.

Чтобы использовать векторизацию в своем коде, вы можете

  • Позвольте компилятору автоматически решить, довольны ли вы текущей производительностью.
  • Укажите компилятору, что ваши циклы можно векторизовать.
  • Явно векторизовать код, используя встроенные функции, доступные для разных семейств процессоров (например, ARM Neon).
  • Используйте такие решения, как Halide Language, чтобы легко векторизовать код на разных платформах.

Кэширование и память

Вы читали — Показатели задержки, которые должен знать каждый инженер? Если нет, то прочтите!

Загрузка данных из основной памяти (DRAM) в регистры ЦП может быть до ~200 times медленнее, чем чтение данных из кэша L1.

Еще в мои облачные дни любая операция, выполняемая в основной памяти, имела обыкновение быть божественной скоростью, а ввод-вывод считался сатанинским.

Небольшой совет: как разработчик, при оценке производительности устройства тактовая частота процессора и общий объем оперативной памяти являются не единственными важными показателями. Также следует обратить внимание на тип микросхемы оперативной памяти на устройстве. Пропускная способность чтения и записи основной памяти является важной частью того, насколько быстро ваши алгоритмы могут работать на данном устройстве, если им необходимо работать с большими данными. Посмотрите разницу между LPDDR3 и LPDDR4 для получения дополнительной информации.

Давайте немного освежим в памяти курс по архитектуре ЦП, который мы проходили в студенческие годы. Кэш L1 — это кэш-память, встроенная в микропроцессор. Это личное для каждого ядра процессора.

Проще говоря, кэши ЦП должны хранить информацию, которая, скорее всего, понадобится ЦП в следующий раз. Таким образом, довольно медленная загрузка данных из основной памяти заменяется сверхбыстрой загрузкой данных из кеша. Когда данные, необходимые процессору, находятся в кеше — это называется Cache Hit.

Если он не найден, данные необходимо извлечь из основной памяти (в худшем случае), и это называется промахом кеша. Кроме того, он часто носит иерархический характер. Если данные не найдены в кэш-памяти L1, а устройство имеет кэш-память L2, выполняется попытка поиска в кэш-памяти L2. То же самое касается кеша L3, если он доступен. Если информация не найдена ни в одном из кешей, она извлекается из основной памяти.

Как упоминалось в числах задержки, которые должен знать каждый инженер, скажем, поиск в кэше L1 занимает ~0.5ns to 1ns, а поиск в основной памяти занимает ~100ns — должно быть легко выяснить пагубное влияние промаха в кэше на производительность алгоритмов.

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

Временная и пространственная локализация

Кэши часто следуют двум принципам для оценки данных, которые потребуются ЦП в ближайшем будущем.

  • Принцип временной локальности ссылки гласит, что текущие данные или обрабатываемые инструкции могут вскоре понадобиться, поэтому мы должны хранить их в кэшах данных или инструкций соответственно, чтобы избежать их повторной загрузки из основной памяти.
  • Принцип локальности в пространстве гласит, что две последовательные инструкции будут ссылаться на непрерывную ячейку памяти. Например, если массив обрабатывается в a[i], по этому принципу вскоре может использоваться a[i + 1].

Можете ли вы сказать, почему теперь следует хранить большие изображения в виде массива, а не связанного списка?

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

# Loop 1
for (int y = 0; y < height; ++y) {
  for (int x = 0; x < width; ++x) {
    output(x, y) = input(x, y) + b;
  }
}
# Loop 2
for (int x= 0; x < width; ++x) {
  for (int y= 0; y < height; ++y) {
    output(x, y) = input(x, y) + b;
  }
}

Любые предположения о разнице в производительности между циклом 1 и циклом 2?

Основные циклы строк на этом устройстве выполняются в ~15.6 times раз быстрее, чем основные циклы столбцов, и именно поэтому промахи кэша могут дорого обойтись.

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

Параллелизм на уровне ЦП

Это более известная область.

Мы все знаем, что современные SoC (System on Chip) имеют более одного ядра ЦП общего назначения, доступного для обработки. Таким образом, вместо того, чтобы запускать наши алгоритмы на одном ядре, мы можем использовать преимущества нескольких доступных ядер и запускать части нашего алгоритма на разных ядрах.

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

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

Для простой программы яркости f(x, y) = g(x, y) + b циклы, распараллеленные по y-axis, дают примерно ~2.5 times ускорения.

Для восьмиядерного устройства, почему мы не получили 8-кратную производительность с многопоточностью, это обсуждение в другой раз!

Результаты были сгенерированы для невекторизованного кода с размером пула потоков 8. Производительность алгоритмов на многоядерных устройствах с включенным параллелизмом также зависит от размера пула потоков. Для этого алгоритма я наблюдал следующую зависимость размера пула потоков от эталона задержки.

Лучшее место было найдено для количества потоков = 16.

Как это использовать?

Распараллеливание алгоритмов обычно доступно во всех языках программирования и средах. Вы часто можете легко создавать пулы потоков и планировать свои задачи на них. В зависимости от размера пула потоков и количества свободных потоков новая задача выполняется напрямую или ожидает освобождения потока.

Сокращение инструкций

Перед тем, как сделать мне покерфейс, сначала ознакомьтесь с примерами!

Я знаю, что в этом нет ничего нового! Вся игра большого О тоже была об этом. Но здесь я говорю о сокращении инструкций для более реалистичного прироста производительности, а не о безумной разнице между O(N) vs O(logN).

Для изображений размером до 13 000 000 пикселей любой алгоритм с O(N^2) в любом случае невозможен!

Развертывание цикла

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

f(x, y, c) = g(x, y, c) + b

Для этой задачи циклы без и с развертыванием циклов последнего измерения (каналов) будут выглядеть так

В первом случае для большого изображения (например, 13-мегапиксельного изображения с 13 миллионами пикселей) самый внутренний цикл должен инициализировать variablec, выполнить сравнение и увеличить 13 миллионов раз. Для этой проблемы я увидел следующие результаты бенчмаркинга.

Тот, у которого цикл разворачивается в среднем на ~1.4 times быстрее для этого примера.

Как это использовать?

Разные примеры

Раньше подобных советов было больше. С современными компиляторами разработчикам часто не нужно делать это явно. Некоторые примеры включают

Деление против умножения

Умножение с плавающей запятой занимает меньше циклов, чем деление с плавающей запятой.

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

Уменьшение ветвления

Эта тема требует большого количества предварительных объяснений и в идеале могла бы стать темой для другой статьи, дайте мне знать, если вы заинтересованы!

Процессор должен выполнить ряд подготовительных работ для выполнения любой инструкции. В него входят — fetching, decoding, executing и writing. Для повышения пропускной способности процессоры конвейеризируют эти этапы. Таким образом, они могут выполнять больше инструкций в течение ограниченного времени.

В случае условных переходов

if (some condition) {
   // set of instructions
} else {
   // other conditions
}

ЦП становится сложно конвейеризировать инструкции, поскольку может выполняться более одного возможного набора инструкций. Современные процессоры используют прогнозирование ветвлений, где они предсказывают результат логики с помощью некоторых эвристик, а затем начинают их конвейерную обработку. Если прогноз действительно верен, позже используются результаты (экономится немного времени :)), в противном случае результаты отбрасываются и выполняется другой набор инструкций.

Таким образом, за неправильное предсказание ветвления приходится платить, и как программист, если вы можете заменить условия какой-либо более простой арифметикой, это может иногда привести к повышению производительности (нажми и попробуй :))

Заключительные заметки для читателей

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

Мне нравится, что мой код работает медленно — никто никогда не говорил!

Если вы обнаружите, что ваши алгоритмы работают медленнее, чем требуется, следуйте простой схеме:

  • Бенчмарк — Сравните свой код. Не начинайте без этого!
  • Разбивка — разбейте тесты на более мелкие компоненты, чтобы изолировать дорогостоящую часть кода. Профилирование может быть действительно полезным здесь!
  • Оптимизируйте — оптимизируйте часть кода, которая приведет к значительному увеличению, начните с легко висящих плодов!
Want to Connect?
Find me on Twitter or LinkedIn!

Рекомендации

Если вам это интересно, вы можете прочитать другие статьи по теме из прошлого: