- PVSM.RU - https://www.pvsm.ru -

[ В закладки ] Алгоритмы и структуры данных в ядре Linux, Chromium и не только

Многие студенты, впервые сталкиваясь с описанием какой-нибудь хитроумной штуки, вроде алгоритма Кнута – Морриса – Пратта или красно-чёрных деревьев, тут же задаются вопросами: «К чему такие сложности? И это, кроме авторов учебников, кому-нибудь нужно?». Лучший способ доказать пользу алгоритмов – это примеры из жизни. Причём, в идеале – конкретные примеры применения широко известных алгоритмов в современных, повсеместно используемых, программных продуктах.

[ В закладки ] Алгоритмы и структуры данных в ядре Linux, Chromium и не только - 1 [1]

Посмотрим, что можно обнаружить в коде ядра Linux, браузера Chromium и ещё в некоторых проектах.

Структуры данных и алгоритмы в ядре Linux

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

   1. Связный список [2], двусвязный список [3], неблокирующий связный список [4] (lock-free linked list).

   2. B+-дерево [5]. Обратите внимание на комментарии. В них есть ценные идеи, подсказанные практикой.

Сравнительно простая реализация B+-деревьев. Я написал её, когда разбирался с тем, как такие деревья работают. Потом довёл код до ума, чтобы им можно было пользоваться.

Тут применяется один нестандартный приём, которого не найти в книгах. А именно, значения возрастают справа налево, а не так, как принято в классической реализации – слева направо. Все занятые ячейки в узле расположены слева, все незанятые содержат значение NUL. При выполнении большинства действий производится однократный обход всех ячеек и остановка на первой ячейке, которая содержит NUL.

   3. Список с учётом приоритета элементов [6] (priority sorted list). Подобная структура данных используется, например, в реализации мьютексов [7] и драйверов [8].

   4. Красно-чёрные деревья [9] применяются в подсистемах планирования, для управления виртуально памятью, для отслеживания дескрипторов файлов, записей в директориях и в других случаях.

   5. Деревья интервалов [10] (interval tree).

   6. Деревья остатков [11] (radix tree) используются для управления памятью, в механизмах поиска NSF и в сетевых подсистемах.

Типичный пример использования деревьев остатков – хранение указателей на структуры, описывающие страницы памяти.

   7. Очередь с приоритетом [12] (priority heap) нашла применение в механизме распределения ресурсов (control groups).

Простая очередь с приоритетом на основе двоичной кучи. Поддерживает только вставку элементов, размер задаётся при создании и не меняется в ходе работы. Реализация основана на описании, которое можно найти в Главе 7 первого издания книги «Алгоритмы: построение и анализ», Т. Кормена, Ч. Лейзерсона и Р. Ривеста.

   8. Хэш-функции [13], в комментариях к реализации которых даются ссылки на работы Дональда Кнута и на исследование Чака Левера.

Дональд Кнут рекомендует использовать в мультипликативном хешировании простые числа, делящие некий интервал в соответствии с правилом золотого сечения. Верхняя граница интервала является максимальным целым числом, представленным машинным словом. Чак Левер подтверждает [14] эффективность такого подхода.

   9. В некоторых местах, например, в коде этого драйвера [15], задействуются собственные хэш-функции.

Хэш-функция, использующая алгоритм кольцевого хеширования (rotating hash). Глава 6.4. третьего тома «Искусства программирования» Д. Кнута.

   10. Хэш-таблицы используются для реализации индексных дескрипторов [16] (inode), для проверок целостности файловой системы [17] и в других случаях.

   11. Битовые массивы [18] применяются для работы с флагами, прерываниями и так далее. Подробности о них можно найти в четвёртом томе «Искусства программирования» Д. Кнута.

   12. Семафоры [19], циклические блокировки [20] (spin lock).

   13. Двоичный поиск [21] используется при обработке прерываний, поиске в кэше [22] и в других случаях.

   14. Двоичный поиск по B-деревьям [23] (binary search with B-trees).

   15. Поиск в глубину [24] (depth first search) и вариант алгоритма, используемый в конфигурации директории [25].

Производится модифицированный проход поиска в глубину по дереву пространства имён, начинающийся (и заканчивающийся) в узле, заданном параметром start_handle. Функция-callback вызывается всякий раз, когда удаётся найти узел, соответствующий параметру, задающему тип. Если callback возвращает ненулевое значение, поиск немедленно прекращается и это значение возвращается туда, откуда был вызван поиск.

   16. Поиск в ширину [26] (breadth first search) применяется для проверки корректности блокировки во время выполнения кода.

   17. Сортировка слиянием [27] на связных списках используется в подсистеме сборки мусора [28], для управления файловой системой [29] и в других случаях.

   18. Сортировка пузырьком [30]. Удивительно, но она тоже используется.

   19. Алгоритм поиска подстроки в строке Кнута-Морриса-Пратта [31].

Реализован алгоритм сравнения строк Кнута-Морриса-Пратта, время его исполнения линейно зависит от входных данных. Подробности можно найти в книге «Алгоритмы: построение и анализ» Т. Кормена, Ч. Лейзерсона, Р. Ривеста и К. Штайна, в разделе «Алгоритм Кнута-Морриса-Пратта».

   20. Алгоритм поиска подстроки в строке Бойера-Мура [32] (Boyer-Moore) с пояснениями и рекомендациями, касающимися возможных альтернатив.

Теоретической основой реализации алгоритма Бойера-Мура стали следующие источники.

» A Fast String Searching Algorithm, R.S. Boyer and Moore. Communications of the Association for Computing Machinery, 20(10), 1977 [33].
» Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004 [34].

Структуры данных и алгоритмы в веб-браузере Chromium

Посмотрим, что интересного можно найти в коде Chromium.

   1. Косое дерево [35] (splay tree).

Дерево, кроме прочего, параметризуется аллокатором. Память под списки выделяется либо в зоне ускоренного доступа (реализуется в классе Zone, обратите внимание на zone.h), либо в обычном свободном пространстве.

   2. Диаграммы Вороного [36] задействованы в демонстрационном примере.

   3. Алгоритм Брезенхэма [37] (Bresenham) используется в подсистеме управления вкладками (tabs).

А вот некоторые алгоритмы и структуры данных, которые есть в коде сторонних разработчиков, включённом в Chromium.

   4. Двоичные деревья [38].

   5. Красно-чёрные деревья [39].

[ В закладки ] Алгоритмы и структуры данных в ядре Linux, Chromium и не только - 2

Джулиан Уокер о красно-чёрных деревьях:

Красно-чёрные деревья — интересная тема. Предполагается, что они проще AVL-деревьев (их непосредственного конкурента), и на первый взгляд так оно и есть. Всё дело в быстрой и простой вставке новых элементов. Однако, если вникнуть в алгоритмы удаления элементов, красно-чёрные деревья преподносят немало сюрпризов. В то же время, в противовес дополнительным сложностям, и вставку, и удаление элементов можно реализовать так, чтобы они выполнялись за один проход.

   6. АВЛ-деревья [40] (AVL tree).

   7. Алгоритм поиска строки Рабина – Карпа [41] (Rabin – Karp) используется для сжатия данных.

   8. Вычисление количества слов, допускаемых ациклическим конечным автоматом. [42]

   9. Фильтр Блума [43] (Bloom), реализованный Apple Inc.

   10. Алгоритм Брезенхэма [44].

Алгоритмы в стандартных библиотеках популярных языков программирования

Полагаем, на библиотечные реализации алгоритмов полезно обратить внимание. Создатели языков программирования, очевидно, считают, что это стоит потраченных времени и сил. К тому же, такие стандартные решения, тщательно протестированные, испытанные на практике множеством разработчиков, обычно предпочтительнее аналогичных «самописных». Хотя, конечно, всё зависит от потребностей программиста и от особенностей конкретного алгоритма или структуры данных.

   1. Если рассматривать, например, языки C и Java, то в первом случае можно встретить больше самостоятельных реализаций базовых вещей, во втором, благодаря обширному стандартному API, подобное встречается реже. В C++-библиотеке STL можно найти реализацию списков, стеков, очередей, карт, векторов и алгоритмов для сортировки, поиска и работы с кучей.

   2. Java API включает в себя реализацию огромного количества структур данных и алгоритмов.

   3. Библиотека Boost C++ содержит алгоритмы наподобие поиска подстроки в строке Бойера-Мура и Кнута-Морриса-Пратта.

Алгоритмы выделения ресурсов и планирования

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

   1. Алгоритм вытеснения элементов, которые не использовались дольше всего (Last Recently Used, LRU) можно реализовать различными способами. В ядре Linux имеется реализация, основанная на списках [45].

   2. Среди других похожих алгоритмов можно выделить следующие. Это – алгоритм «первым вошёл – первым вышел» (First In First Out, FIFO), алгоритм вытеснения наименее часто используемых элементов (Last Frequently Used, LFU), алгоритм распределения нагрузки распределённой вычислительной системы методом перебора и упорядочения её элементов по круговому циклу (Round Robin, RR).

   3. В системе VAX/VMS применялся один из вариантов FIFO.

   4. «Часовой» алгоритм [46] (Clock) Ричарда Карра [47] нашёл применение в Linux для организации замещения страниц памяти.

   5. Процессор Intel i860 использует политику случайного замещения.

   6. Алгоритм кэширования с адаптивным замещением [48] (Adaptive Replacement Cache, ARC) применяется в некоторых контроллерах хранилищ данных IBM и до возникновения проблемы с патентом [49], использовался в PostgreSQL.

   7. Алгоритм двойников для выделения памяти [50] (buddy memory allocation), описанный Д. Кнутом в первом томе «Искусства программирования», применяется в ядре Linux, в параллельной системе выделения памяти jemalloc, используемой в FreeBSD и в Facebook [51].

Базовые утилиты *nix-систем

   1. Утилиты grep и awk реализуют алгоритм Томсона-Мак-нотона-Ямады (Thompson-McNaughton-Yamada) для построения недетерминированных конечных автоматов на основе регулярных выражений. Такой подход даже более эффективен, чем реализация соответствующих механизмов в Perl [52]

   2. В tsort применяется топологическая сортировка (topological sort).

   3. В коде утилиты fgrep можно обнаружить алгоритм поиска подстрок в строке Ахо – Корасик [53] (Aho-Corasick).

   4. Утилита GNU grep реализует алгоритм Бойера-Мура [54].

   5. В crypt(1) из Unix имеется вариант алгоритма шифрования, применявшийся в машине Enigma.

   6. Утилита Unix diff [55], созданная Дугласом Макилроем (Doug McIlroy), основана на прототипе, написанном совместно с Джеймсом Хантом (James Hunt), обладает более высокой производительностью, чем стандартный алгоритм динамического программирования, используемый для вычисления расстояния Левенштейна (Levenshtein distance).

Компиляторы

   1. Восходящий алгоритм синтаксического разбора [56] (Look-Ahead LR parser, LALR). Реализован в yacc и bison.

   2. Алгоритмы вычисления доминаторов (dominators) используются в большинстве оптимизирующих компиляторов, основанных на SSA.

   3. Утилиты lex и flex компилируют регулярные выражения в NFA.

Сжатие изображений и коррекция ошибок

   1. Алгоритмы сжатия Лемпеля-Зива [57] для графического формата GIF реализованы в различных приложениях для обработки изображений – от простой *nix-утилиты convert до гораздо более сложных программных комплексов.

   2. Алгоритм кодирования длин серий (run-length encoding, RLE) применяется при создании PCX-файлов (используется во всем известном Paintbrush), сжатых BMP и TIFF-файлов.

   3. Вейвлет-сжатие – это основа невероятно распространённого формата JPEG 2000. Каждый цифровой фотоаппарат, который умеет сохранять снимки в формате JPEG 2000, является «носителем» этого алгоритма.

[ В закладки ] Алгоритмы и структуры данных в ядре Linux, Chromium и не только - 3

   4. Алгоритм коррекции ошибок Рида-Соломона задействован в ядре Linux [58]. Кроме того, он используется при хранении информации на CD-дисках, в устройствах для чтения штрих-кодов. Да что там говорить, его, вместе с алгоритмом свёртки, использовали для передачи изображений с космического аппарата

Задача о выполнимости булевых формул

С 2000-го года время выполнения алгоритмов, решающих задачу выполнимости булевых формул, постоянно уменьшалось. Всё дело в применении новых подходов к решению таких задач. В частности, речь идёт об алгоритме управляемого конфликтами обучения дизъюнктам (Conflict Driven Clause Learning). Он является комбинацией алгоритма распространения булевых ограничений (Boolean Constraint propagation) из работы Дэвиса, Логемана и Лавленда (Davis, Logemann, Loveland) с методикой обучения дизъюнктам, которая берёт начало в технике программирования ограничениями (constraint programming) и в исследованиях, посвящённых искусственному интеллекту.

Применения подобных алгоритмов (SAT-решателей) весьма обширны. Например – это автоматическое доказательство теорем, тестирование аппаратного и программного обеспечения. IBM, Intel и многие другие компании имеют собственные реализации SAT-решателей. Многие менеджеры пакетов так же использует подобный алгоритм для разрешения зависимостей.

Выводы

Существует великое множество алгоритмов и примеров их практического применения. Хочется верить, наш рассказ о некоторых из них убедил тех, кто задавался вопросом: «Зачем это всё?», в том, что алгоритмы стоят того, чтобы потратить время на знакомство с ними. А если алгоритмы и структуры данных – ваши давние друзья, надеемся, вы нашли здесь что-нибудь новое и полезное для себя.

О, а приходите к нам работать? :)

wunderfund.io [59] — молодой фонд, который занимается высокочастотной алготорговлей [60]. Высокочастотная торговля — это непрерывное соревнование лучших программистов и математиков всего мира. Присоединившись к нам, вы станете частью этой увлекательной схватки.

Мы предлагаем интересные и сложные задачи по анализу данных и low latency разработке для увлеченных исследователей и программистов.
Гибкий график и никакой бюрократии, решения быстро принимаются и воплощаются в жизнь.

Присоединяйтесь к нашей команде: wunderfund.io [59]

Автор: Wunder Fund

Источник [61]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/razrabotka/112307

Ссылки в тексте:

[1] Image: https://habrahabr.ru/company/wunderfund/blog/277143/

[2] Связный список: https://github.com/mirrors/linux-2.6/blob/master/lib/llist.c

[3] двусвязный список: https://github.com/mirrors/linux-2.6/blob/master/include/linux/list.h

[4] неблокирующий связный список: https://github.com/mirrors/linux-2.6/blob/master/include/linux/llist.h

[5] B+-дерево: https://github.com/mirrors/linux-2.6/blob/39caa0916ef27cf1da5026eb708a2b8413156f75/lib/btree.c

[6] Список с учётом приоритета элементов: https://github.com/mirrors/linux-2.6/blob/master/include/linux/plist.h

[7] мьютексов: https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/include/linux/rtmutex.h

[8] драйверов: https://github.com/mirrors/linux-2.6/blob/f0d55cc1a65852e6647d4f5d707c1c9b5471ce3c/drivers/powercap/intel_rapl.c

[9] Красно-чёрные деревья: https://github.com/mirrors/linux-2.6/blob/master/include/linux/rbtree.h

[10] Деревья интервалов: https://github.com/mirrors/linux-2.6/blob/master/include/linux/interval_tree.h

[11] Деревья остатков: https://github.com/mirrors/linux-2.6/blob/master/include/linux/radix-tree.h

[12] Очередь с приоритетом: https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/include/linux/prio_heap.h

[13] Хэш-функции: https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/include/linux/hash.h

[14] подтверждает: http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf

[15] этого драйвера: https://github.com/mirrors/linux-2.6/blob/0b1e73ed225d8f7aeef96b74147215ca8b990dce/drivers/staging/lustre/lustre/lov/lov_pool.c

[16] индексных дескрипторов: https://github.com/mirrors/linux-2.6/blob/42a2d923cc349583ebf6fdd52a7d35e1c2f7e6bd/fs/inode.c

[17] целостности файловой системы: https://github.com/mirrors/linux-2.6/blob/ff812d724254b95df76b7775d1359d856927a840/fs/btrfs/check-integrity.c

[18] Битовые массивы: https://github.com/mirrors/linux-2.6/blob/master/include/linux/bitmap.h

[19] Семафоры: https://github.com/mirrors/linux-2.6/blob/master/include/linux/semaphore.h

[20] циклические блокировки: https://github.com/mirrors/linux-2.6/blob/master/include/linux/spinlock.h

[21] Двоичный поиск: https://github.com/mirrors/linux-2.6/blob/master/lib/bsearch.c

[22] поиске в кэше: https://github.com/mirrors/linux-2.6/blob/10d0c9705e80bbd3d587c5fad24599aabaca6688/drivers/base/regmap/regcache.c

[23] Двоичный поиск по B-деревьям: https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/fs/befs/btree.c

[24] Поиск в глубину: https://github.com/mirrors/linux-2.6/blob/a9238741987386bb549d61572973c7e62b2a4145/drivers/acpi/acpica/nswalk.c

[25] конфигурации директории: https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/fs/configfs/dir.c

[26] Поиск в ширину: https://github.com/mirrors/linux-2.6/blob/4fbf888accb39af423f271111d44e8186f053723/kernel/locking/lockdep.c

[27] Сортировка слиянием: https://github.com/mirrors/linux-2.6/blob/master/lib/list_sort.c

[28] сборки мусора: https://github.com/mirrors/linux-2.6/blob/42a2d923cc349583ebf6fdd52a7d35e1c2f7e6bd/fs/ubifs/gc.c

[29] файловой системой: https://github.com/mirrors/linux-2.6/blob/ff812d724254b95df76b7775d1359d856927a840/fs/btrfs/raid56.c

[30] Сортировка пузырьком: https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/drivers/media/common/saa7146/saa7146_hlp.c

[31] Кнута-Морриса-Пратта: https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/lib/ts_kmp.c

[32] Бойера-Мура: https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/lib/ts_bm.c

[33] A Fast String Searching Algorithm, R.S. Boyer and Moore. Communications of the Association for Computing Machinery, 20(10), 1977: http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf

[34] Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004: http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf

[35] Косое дерево: https://code.google.com/p/chromium/codesearch#chromium/src/v8/src/splay-tree.h

[36] Диаграммы Вороного: https://code.google.com/p/chromium/codesearch#chromium/src/native_client_sdk/src/examples/demo/voronoi/index.html

[37] Алгоритм Брезенхэма: https://code.google.com/p/chromium/codesearch#chromium/src/chrome/browser/ui/cocoa/tabs/tab_strip_controller.mm

[38] Двоичные деревья: https://code.google.com/p/chromium/codesearch#chromium/src/third_party/bintrees/bintrees/bintree.py

[39] Красно-чёрные деревья: https://code.google.com/p/chromium/codesearch#chromium/src/third_party/bintrees/bintrees/rbtree.py

[40] АВЛ-деревья: https://code.google.com/p/chromium/codesearch#chromium/src/third_party/bintrees/bintrees/avltree.py

[41] Рабина – Карпа: https://code.google.com/p/chromium/codesearch#chromium/src/third_party/zlib/deflate.c

[42] Вычисление количества слов, допускаемых ациклическим конечным автоматом.: https://code.google.com/p/chromium/codesearch#chromium/src/native_client/src/trusted/validator_ragel/dfa_traversal.py

[43] Фильтр Блума: https://code.google.com/p/chromium/codesearch#chromium/src/third_party/WebKit/Source/wtf/BloomFilter.h

[44] Алгоритм Брезенхэма: https://code.google.com/p/chromium/codesearch#chromium/src/third_party/libvpx/source/libvpx/vp8/common/textblit.c

[45] основанная на списках: https://github.com/mirrors/linux-2.6/blob/master/include/linux/list_lru.h

[46] «Часовой» алгоритм: http://en.wikipedia.org/wiki/Page_replacement_algorithm#Clock

[47] Ричарда Карра: http://dl.acm.org/citation.cfm?id=4750

[48] Алгоритм кэширования с адаптивным замещением: http://en.wikipedia.org/wiki/Adaptive_Replacement_Cache

[49] проблемы с патентом: http://www.varlena.com/GeneralBits/96.php

[50] Алгоритм двойников для выделения памяти: http://en.wikipedia.org/wiki/Buddy_memory_allocation

[51] Facebook: http://www.facebook.com/notes/facebook-engineering/scalable-memory-allocation-using-jemalloc/480222803919

[52] реализация соответствующих механизмов в Perl: http://swtch.com/~rsc/regexp/regexp1.html

[53] Ахо – Корасик: http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm

[54] реализует алгоритм Бойера-Мура: http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html

[55] Unix diff: http://www.cs.dartmouth.edu/~doug/diff.pdf

[56] Восходящий алгоритм синтаксического разбора: http://en.wikipedia.org/wiki/LALR_parser

[57] Лемпеля-Зива: http://en.wikipedia.org/wiki/Lempel_Ziv

[58] ядре Linux: https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/lib/reed_solomon/reed_solomon.c

[59] wunderfund.io: http://wunderfund.io

[60] высокочастотной алготорговлей: https://en.wikipedia.org/wiki/High-frequency_trading

[61] Источник: https://habrahabr.ru/post/277143/