Реальная производительность красно-черных против 2-3-4 деревьев, особенно учитывая производительность кеша?

Question

Один узел дерева 2-3-4 может быть создан с 8 указателями: указатели на до четырех дочерних узлов, указатели на до 3 фактических записей, содержащих ключи, которые либо будут соответствовать ключу поиска, либо определят, какой из 4 дочерних узла для рекурсии и указатель родительского узла.

Обычное оборудование сегодня имеет 8-байтовые указатели, что дает 64-байтовый узел. Кроме того, современные процессоры имеют 64-байтовые строки кэша. Если узлы выровнены по строкам кэша, то для каждого узла требуется только одно попадание в строку кэша: после обращения к первому из семи указателей все остальные будут в вашем кэше L1.

Хотя красно-черное дерево гораздо проще реализовать, и небольшой код должен быть быстрым кодом, каждый уровень спуска в дереве рискует пропустить кэш-память L1. Для 1023 объектов дерево 2-3-4 нуждается в наихудшем случае из 5 узлов для загрузки в кэш. Для идеально сбалансированного бинарного дерева потребуется 10, но из-за дисбаланса красно-черным может потребоваться больше (не уверен, что в худшем случае: 20?)

Небольшие тестовые наборы, которые просто забивают одну структуру данных, вероятно, сохранят все это в кэше, и поэтому могут сообщать о красно-черном дереве как о производительности, аналогичной 2-3-4. Но у меня есть ощущение, что сложное реальное приложение может видеть гораздо меньше времени настенных часов и меньшую задержку с 2-3-4 деревьями.

Есть ли консенсус или исследование по этому вопросу?

Answer 1

Ваши рассуждения, безусловно, верны - для холодных поисков дерево 2-3-4 будет работать лучше только потому, что оно встречает меньше строк кэша.

Если производительность дерева важна, то, как правило, это обычноозначает, что вы используете его часто .

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

Таким образом, реальное улучшение производительности, когда оно имеет значение, ограниченодо самых глубоких нескольких уровней в дереве.Вы можете все еще увидеть производительность с деревом 2-3-4, но это не бегло, и я думаю, что вам понадобится особая причина, чтобы судить о том, стоит ли дополнительная сложность кода (особенно в поискеи итерация).