Меня всегда интересовали реализации структура данных на практике. Возьмем к примеру AVL-tree. С точки зрения теории все довольно понятно - сбалансированное двоичное дерево, поиск за log n, вставка от константы до log n. Но кроме O(n) есть еще реальное время выполнения операций, и при не слишком большом N это время гораздо важнее чем теоретические выкладки. Да, если N - очень большое то O(n) решает, но в реальной жизни случаи с очень большими N не так часто встречаются. Поэтому практические приемы используемые при реализации той или иной структуры данных не менее важны чем сам алгоритм. Собственно, в чем особенности реализации AVL дерева в Solaris/ZFS ?
- Написано на голом C, без классов (как и все то что должно работать в ядре)
- Не полезная нагрузка "вставляется" в узлы дерева, а наоборот - структуры данных необходимые для реализации дерева внедряются в те объекты которые планируется класть в дерево. Если быть точным - это даже не объекты а структуры (в терминах C). В результате - и payload и сами структуры данных дерева образуют единых блок данных. В результате резко повышается memory cache locality, в два раза снижается фрагментация данных (в классической реализации узел дерева это одна структура данных, в ней сидит указатель на собственно payload)
- Рекурсия не используется, только итерации. Для этого каждый узел дерева содержит указатель на родительский узел. Даже на C рекурсия медленнее чем цикл. Другая причина - этот код должен работать в ядре, где размер стэка не большой.
- Реализация не содержит блокировок - предполагается что тот кто использует структуру данных сам знает - нужно ли синхронизировать доступ к ней и если это необходимо - взял нужную блокировку
- Реализация не содержит выделений памяти. Все функции принимают на вход указатели на предварительно выделенные блоки памяти там где это необходимо. За счет этого достигается:
- Предсказуемость времени выполнения того или иного вызова. Выделение памяти это довольно рискованная в парадигме kernel-программирования операция которая может занять непредсказуемое время и завершиться непредвиденным результатом
- Абстрагирование структуры данных от используемых механизмов выделения памяти.
- Используются разные структуры данных на 32 и 64 битных платформах. Вся работа с структурами данных ведется через макросы. На 64-битной платформе флаги и другие мелкие значения упаковываются в младшие биты указателей. На 64-битной платформе младшие биты указателей всегда равны нулю.
- Данные которые используются в наиболее часто вызываемых функциях, например avl_find() располагают в первых 64 битах структуры данных. Таким образом гораздо выше вероятность того что эти данные уже находятся в кэше процессора
- Вместо обычных конструкций ветвления if (больше) then {right} else {left} при обходе дерева используется node = node->child[compare(value, data)]. Почему так ? потому что branch prediction процессора обрабатывает if then конструкции хорошо только тогда когда вероятность переходя по одной из ветвей сильно выше, например при обработке ошибок. В случае прохода по дереву вероятность пойти по левой и правой ветки примерно одинакова, что будет приводить к miss-prediction и сбросу конвеера процессора. Конвеер современных CPU очень глубокий, поэтому сброс конвеера - это довольно затратная операция. Поэтому вместо этого указатели на левый и правый child помести в массив, и результат сравнения искомого значения с тем что хранится в текущей ноде используется как индекс для получения указателя на следующий элемент дерева. В исходном кода мне кажется это будет понятнее - https://github.com/zfsonlinux/zfs/blob/2476f103069e83e17d2c9cec4191af34a7996885/module/avl/avl.c#L256
Комментариев нет:
Отправить комментарий