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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Компиляторы

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

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

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

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

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

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

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

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

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

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

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

Выводы

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

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

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

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

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

Автор: Wunder Fund

Источник