Просмотров: 10291

Заметки об оптимизации: 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.

~

Окончание этой серии статей читайте здесь, а напоследок, чтобы немного понизить градус заумности, забавное видео: Java-программист, который явно не в себе — деинсталлировал MS Visual Studio у всех коллег по офису. Забавно, хоть и на испанском (если кто не понимает, то там поток проклятий в адрес .NET):

Да уж, Java до хорошего не доведёт... Пойдет теперь по статье "нарушение общественного порядка или мелкое хулиганство".

twitter.com facebook.com vkontakte.ru odnoklassniki.ru mail.ru ya.ru pikabu.ru blogger.com liveinternet.ru livejournal.ru google.com bobrdobr.ru yandex.ru del.icio.us

Подписка на обновления блога → через RSS, на e-mail, через Twitter
Теги: , , , ,
Эта запись опубликована: Понедельник, 2 января 2012 в рубрике ПрограммированиеМнения.

10 комментариев

Следите за комментариями по RSS
  1. Во-первых, O(n) - это верхняя граница асимптотики, то есть утверждение, что сложность сортировки пузырьком - O(n^3), является математически верным. Понятное дело, что в большинстве случаев под O подразумевают Theta.

    Во-вторых, есть довольно четкое определение:

    Вычислительная сложность алгоритма T(n) равна O(f(n)), если существует С > 0, и n0, такие что T(n) n0.

    Поэтому утверждение, что O(f(n)) - обозначает С1 + С2*f(n) не совсем корректно.

  2. master, так и есть. Теоретически Вы правы. Но на практике...

    С практической точки зрения для малых n С1 может тоже иметь важное значение в случае, если алгоритм требует много предварительных вычислений. Например, tls handshake ( http://en.wikipedia.org/wiki/Transport_Layer_Security), если в качестве n брать объем данных, переданных по зашифрованному каналу связи.

    Более подробно я отвечу в третьей части этой статьи.

  3. Всё верно.

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

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

  4. Не забывайте про наличие нескольких уровней кэша с различными размерами cache line, про аппаратную подгрузку данных ( http://en.wikipedia.org/wiki/Prefetch_buffer ) и про подгрузку страниц виртуальной памяти на уровне операционной системы при последовательном обращении к данным ( http://en.wikipedia.org/wiki/Paging#Anticipatory_paging ).

    Не следует также забывать, что первый же context-switch поломает нам всю стройную картину и с кэшами, и с TLB, и со всем остальным

    Принудительное переключение между процессами на современных ОС происходит не более 100 раз в секунду. Это означает, что код, исполняющийся в одном процессе, имеет в наличии 10 миллионов тактов процессора на частоте 1ГГц перед тем, как произойдет принудительное переключение на другой процесс. То же самое справедливо и для прерываний.

  5. Можно всегда говорить про максимальный кэш-лайн, это в районе 64 байт, плюс-минус. Строка в памяти около 256 байт, но даже из них последовательно что-то выбрать не получится, потому что параллельно с выборкой данных идет еще выборка инструкций, у которых свои адреса и для которых нужен свой RAS#. Инструкции могут оказаться в кэше, а могут и не оказаться, и повлиять на это мы не можем. И это я еще молчу про NUMA и про DMA, которые тоже лезут в память. Подгрузка страниц на уровне ОС происходит так или иначе по PF#, т.к. ОС лишена знания о том, обращаются ли внутри страницы последовательно. То есть если мы полезем в другую страницу (не смежную с текущей), ОС подгрузит ее, и накладные расходы одинаковы.

    А про 10 миллионов тактов, я говорю о том, что если уж спускаемся на такой уровень что считаем буферы DRAM и сколько тактов между переключениями контекста, то лучше писать под конкретный процессор на ассемблере, учитывая всё, от глубины буферов до количества портов исполнения инструкций. Рекомендовать так писать всегда, это примерно как рекомендовать писать конспекты по всем правилам китайской каллиграфии.

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

  6. 2 filin: рад видеть у себя, Федя, а по делу:

    Во-первых, суть cache aware оптимизации не такая уж и сложная - отдавать предпочтение последовательному доступу к данным вместо произвольного доступа. Для проведения этой оптимизации не нужно знать ассемблер и тонкости железа. Более того, ее можно проводить даже на высокоуровневых языках программирования вроде javascript, C#, java.

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

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

    - последовательное обращение к элементам массива;

    - произвольное обращение к элементам массива.

    Пусть:

    - в cache line помещается n элементов массива;

    - элемент массива, находящийся в кэше, считывается за Ts с;

    - подгрузка новой cache line происходит за m*Ts с.

    Тогда N элементов массива при последовательном доступе будут считаны за N*Ts*(1 + m/n) секунд, а при произвольном доступе - за N*Ts*m секунд. Тогда скорость последовательного доступа будет отличаться от скорости произвольного доступа в A = m*n/(m + n) раз. Для современных процессоров m находится в районе 100. Пусть n равно 16. Тогда A = 100*16/116 = 13.8 раз. Даже если n равно 2 (т.е. в cache line помещается хотя бы 2 элемента массива), то скорость последовательного доступа будет больше скорости произвольного доступа в 200/102 = 2 раза. Рассмотрите классический пример - умножение матриц. В теории скорость умножения матриц не зависит от порядка, в котором происходит доступ к элементам матриц. На практике скорость может отличаться в десятки раз. И все из-за кэшей. http://en.wikipedia.org/wiki/Cache-oblivious_algorithm .

    Если подняться на один уровень вверх, т.е. в качестве cache line взять блок данных, считываемый/записываемый за раз на жесткий диск (сейчас это 512 байт или 4 Кбайт), то m будет уже в районе миллиона (время произвольного доступа 10 мс, скорость последовательного чтения 100 Мб/с, т.е. за 10 мс можно прочитать 1 Мб последовательных данных).

    > В общем случае нужно писать понятный код на языке высокого уровня, который, по возможности, имеет наименьшую сложность. Гнаться за двумя зайцами одновременно не стоит. Я согласен с Макконнеллом в том, что понятность кода важнее его производительности, а "оптимизация" на ровном месте (того, что не является ботлнеком) - вредна.

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

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

  7. нравится

    Для иллюстрации полезности, хотелось бы конечно, чтобы статья приводила несколько примеров "из реальной жизни". Что-то вроде - было так, работало медленно, разобрались, сделали так, стало работать быстро, причины были такие-то и такие-то, всем выписали премию! :)

  8. нравится: Спасибо за конструктивную критику - это всегда приветствуется.

    > Что-то вроде - было так, работало медленно, разобрались, сделали так, стало работать быстро

    Я как то переписал обычный hash table в варианте linear probing[1] на cuckoo hashing[2][3] в двух вариантах, 1) четыре хэш функции, одна ячейка в корзине; 2) две хэш функции, четыре ячейки в корзине. Так вот, потребление памяти, как и ожидалось снизилось значительно, примерно в два раза. Это одно из ключевых свойств алгоритма cuckoo hashing. Но вместе с тем, на больших объемах данных (1500000 уникальных объектов) значительно упала скорость поиска элементов, примерно в 3-4 раза. Это при том, что алгоритм гарантирует константное максимальное количество сравнений. Замедление не связано с расчетом дополнительных хэш-кодов, они были просчитаны заранее. Единственное возможное объяснение - непопадание данных в кэш, ведь cuckoo hashing разбрасывает элементы по ячейкам, которые могут отставать друг от друга на значительное расстояние.

    На эту тему есть публикация How Caching Affects Hashing[4], в которой сравнивается производительность разных реализаций хэш таблиц на разных объемах данных. У них там результаты подтверждают мои наблюдения для большого количества маленьких элементов. Но вместе с тем авторы делают вывод, что на малых объемах данных или для больших элементов double hashing предпочтительнее, чем linear probing.

    [1] http://en.wikipedia.org/wiki/Linear_probing

    [2] http://en.wikipedia.org/wiki/Cuckoo_hashing

    [3] http://www.ru.is/faculty/ulfar/CuckooHash.pdf

    [4] http://www.siam.org/meetings/alenex05/papers/13gheileman.pdf

    А вообще, вот САМЫЙ яркий пример того, как удалось увеличить производительность алгоритма удаления устаревших записей в кэше Varnish ( http://en.wikipedia.org/wiki/Varnish_(software) ) до 10 раз путем модификации стандартной структуры данных heap ( http://en.wikipedia.org/wiki/Heap_(data_structure)).

    http://queue.acm.org/detail.cfm?id=1814327

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

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

    - почему http://en.wikipedia.org/wiki/Unrolled_linked_list быстрее обычного http://en.wikipedia.org/wiki/Linked_list ?

    - почему в базах данных и файловых системах предпочитают использовать http://en.wikipedia.org/wiki/B-tree вместо остальных видов binary search tree?

    - почему http://en.wikipedia.org/wiki/Merge_sort быстрее других видов сортировки для больших объемов данных?

    - почему для сортировки маленьких объемов данных используют http://en.wikipedia.org/wiki/Insertion_sort ? Например, см. http://en.wikipedia.org/wiki/Quicksort#Optimizations .

    - почему СУБД предпочитают использовать full table scan ( http://en.wikipedia.org/wiki/Full_table_scan ) вместо поиска по индексу для таблиц с небольшим количеством записей?

    Тут ещё много чего по теме написать можно - но сил нету всё это набивать.

  10. > Какая структура данных будет работать быстрее при организации стека — linked list или динамический массив?

    Тут вы 2 раза сослались на одну и ту же статью http://en.wikipedia.org/wiki/Singly_linked_list

Оставьте комментарий!

Не регистрировать/аноним

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

Зарегистрировать/комментатор

Для регистрации укажите свой действующий email и пароль. Связка email-пароль позволяет вам комментировать и редактировать данные в вашем персональном аккаунте, такие как адрес сайта, ник и т.п. (Письмо с активацией придет в ящик, указанный при регистрации)

(обязательно)


⇑ Наверх
⇓ Вниз