Заметки об оптимизации программ. Часть 2: Big O notation и скорость алгоритмов

Это вторая часть из серии заметок об оптимизации программ. Первая часть находится здесь. Сегодня мы поговорим о том, как правильно выбирать алгоритмы и структуры данных, основываясь на Big O notation.

Теория

Какой алгоритм быстрее - O(n) или O(1)? Правильный ответ - "это зависит от набора данных, над которым работает алгоритм, и от платформы, на которой работает данный алгоритм". При выборе алгоритма следует помнить, что O(f(n)) означает C1 + C2*f(n), где:

• С1 - время, необходимое на "старт" алгоритма. Это время не зависит от n. Это время может быть существенным для алгоритмов, требующих большого объема предварительных вычислений.
• С2 - время, затрачиваемое на каждую итерацию алгоритма. В теории C2 не зависит от n, но на практике это не так. C2 для маленьких n часто бывает меньше, чем C2 для больших n. Также C2 может сильно варьироваться для одного и того же набора данных в зависимости от того, где эти данные расположены и в каком порядке осуществляется к ним доступ. Основной вклад в варьирование C2 вносит прозрачное кэширование на различных уровнях. Например, если весь набор данных плотно сгруппирован в небольшой области памяти (например, на одной странице памяти), то C2 может быть на несколько порядков меньше, чем если бы этот же набор данных был разбросан по произвольным адресам памяти. Это объясняется следующими причинами:
  • Прозрачное кэширование основано на принципе locality of reference, поэтому велика вероятность, что данные, плотно сгруппированные в небольшой области памяти, окажутся в самом быстром кэше.
  • Translation lookaside buffer (TLB) может не содержать записей для некоторых страниц памяти с нашими данными, поэтому CPU будет вынужден тратить дополнительное время на поиск физических адресов страниц, отсутствующих в TLB.
  • Некоторые страницы памяти могут быть вытеснены из основной памяти, поэтому при обращении к ним будет затрачено много времени на поиск и чтение страниц из более медленной памяти.
  Если записи о страницах из working set (WS) не помещаются в TLB, либо размер WS превышает resident set size (RSS), то могут начаться тормоза. От этого иногда страдают некоторые алгоритмы garbage collection (GC), которые вынуждены периодически обращаться к большому количеству страниц памяти во время циклов очистки памяти. Это также может замедлить работу основной программы, т.к. ее WS может быть вытеснен из TLB и основной памяти при работе GC, после чего потребуется много времени на обратную загрузку WS в основную память. Наиболее эффективный метод борьбы с тормозами GC - не создавать много долгоживущих, но редко используемых объектов. Например, плохо спроектированный кэш. Что-то мы отвлеклись от основной темы :) Чтобы было понятнее, насколько сильно C2 может зависеть от набора и расположения обрабатываемых данных, воспользуемся вот этой таблицей.
  • Если весь набор данных находится в кэше L1, то время доступа к нему находится в районе 0.5 нс.
  • Если набор данных помещается лишь в кэш L2, то время доступа становится равным 7 нс, т.е. увеличивается в 14 раз. Во столько же раз может возрасти и C2 для нашего алгоритма.
  • Если набор данных раскидан по основной памяти и целиком находится в RSS, то время доступа к произвольному элементу этого набора увеличивается до 100 нс, т.е. C2 возрастает в 200 раз по сравнению с самым первым вариантом.
  • Если набор данных не помещается в RSS, то время доступа может увеличиться до 10.000.000 нс, т.е. С2 увеличивается в 20 миллионов раз по сравнению с первым вариантом.
  Этот список дает наглядное представление о том, как достичь бОльшей скорости алгоритмов - лучше затратить лишний миллион тактов CPU на вычисление каких-нибудь данных, чем читать эти данные с жесткого диска либо запрашивать их по сети. Это утверждение верно лишь в случае, если вы хотите минимизировать лишь время выполнения алгоритма. Если же ваша цель - минимизировать нагрузку на CPU, то лучше подождать загрузки данных из внешних источников, нежели тратить такты CPU на вычисление данных. Это классический случай Throughput vs Latency.

Почему же С1 и С2 редко упоминаются при анализе вычислительной сложности алгоритмов при помощи Big O notation? Потому что этот анализ производится для n, стремящихся к бесконечности. В таких случаях константа C1 имеет смысл только для O(1) алгоритмов, а C2 принимается во внимание лишь при сравнении алгоритмов с одинаковой сложностью согласно Big O notation. Т.е. если алгоритмы требуют С11*f(n) и С12*f(n) времени, то можно сказать, что скорость первого алгоритма отличается от скорости второго алгоритма в C12/С11 раз.

Практика

Рассмотрим три классических алгоритма.

• Поиск по ключу Всем известно, что время поиска по ключу в хэш-таблице в общем случае не зависит от количества элементов, среди которых осуществляется поиск, т.е. оно эквивалентно O(1). Означает ли это, что хэш-таблицы нужно использовать во всех случаях, когда требуется осуществить поиск по ключу? Нет! Если количество элементов, по которым производится поиск, невелико, то полный перебор всех элементов может оказаться быстрее поиска в хэш-таблице. Время поиска в хэш-таблице является константой C11, которая в общем случае включает в себя три составляющие:
  • время, затрачиваемое на вычисление хэш-функции от ключа
  • время, затрачиваемое на доступ к элементу в хэш-таблице по индексу
  • время, затрачиваемое на сравнение ключа для выбранного из таблицы элемента с заданным ключом
  Время поиска в обычном массиве путем полного перебора можно представить как O(n) = C12 + C22*n, где n - количество элементов в массиве, С12=0, а С22 включает в себя следующее:
  • время, затрачиваемое на последовательный доступ к следующему элементу массива
  • время, затрачиваемое на сравнение ключа для выбранного из массива элемента с заданным ключом
  Поиск по массиву будет быстрее, если C11 > C22*n. Это возможно, если вычисление хэш-функции занимает много времени либо если произвольный доступ к элементу по индексу занимает больше времени по сравнению с последовательным чтением всех элементов.
• Сортировка Какой метод сортировки быстрее - heapsort или сортировка пузырьком? Согласно Big O notation, heapsort имеет вычислительную сложность O(n*ln(n)), а сортировка пузырьком - O(n*n). Очевидно, что heapsort должна одержать победу при сравнительно больших n :) Но это не так. Если сравнить последовательности обращения к элементам в этих алгоритмах, то можно увидеть, что heapsort обращается к элементам в "произвольном" порядке, а сортировка пузырьком проходит все элементы последовательно. Отсюда напрашивается вывод, что сортировка пузырьком победит в случае, если произвольный доступ к элементам существенно медленнее последовательного доступа. Это бывает на практике, если вспомнить про locality of reference и data prefetching.
• Стек Какая структура данных будет работать быстрее при организации стека - linked list или динамический массив? Обе структуры данных позволяют добавлять и удалять элементы со стека за O(1) в общем случае, но динамический массив иногда требует дополнительное время O(n) на расширение и сжатие. Обычно на практике побеждает динамический массив, т.к. при работе со стеком обращение к его элементам в памяти осуществляется последовательно. Значит, высока вероятность, что эти элементы уже будут находиться в самом быстром кэше. При работе же с linked list элементы могут быть разбросаны по всей памяти, что может привести к тормозам.

Заключение

При выборе алгоритмов и структур данных для ваших программ обращайте внимание не только на Big O notation, но и на типичный размер набора данных, с которым предстоит работать, а также не забывайте про вышеупомянутые C1 и C2.

Место солидарности беларусского ИТ-комьюнити

Далучайся!