Как реализовать дружественное к кэшу динамическое двоичное дерево?

Question

Согласно нескольким источникам, в том числе Wikipedia, два наиболее часто используемых способов реализации двоичного дерева являются:

1. Узлы и указатели (или ссылки), где каждый узел явно держит своих детей.
2. Array где положение дочерних узлов задано неявно по индексу его родителя.

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

Предположим, что вы хотите поддерживать такие вставки и удаления. Как вы можете реализовать дерево таким образом, чтобы обход дерева эффективно использовал кэширование CPU.

Я думал о создании пула объектов для узлов и распределении их в массиве. Таким образом, узлы будут близки друг к другу -> следовательно, хорошая локальность ссылки.

Но если размер узла совпадает с размером строки кэша, имеет ли это смысл?

Если у вас есть размер линии L1, равный 64 байтам, и вы получаете доступ к первому члену std::vector<std::uint8_t>(64), вы, возможно, будете иметь все содержимое вектора в вашем кеше L1. Это означает, что вы можете получить доступ к любому элементу очень быстро. Но что, если размер элемента совпадает с размером строки кеша? Поскольку строка кэша likely not to be very different для кэшей L1, L2 и L3, похоже, здесь не может быть полезной локальность ссылок. Я ошибаюсь? Что еще можно сделать?

Answer 1

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

Если вы ищете общее ассоциативное хранение, существует множество кэша-дружественного (другие ключевые слова: «кэш-эффективный», «кэш-забывчивого») алгоритмы, такие как Judy arrays, для которых существует extensive explanation PDF.

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

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

Answer 2

Используйте блок-распределитель.

У вас есть одна или несколько горных континуальных «пулов» памяти, из которых вы получаете блоки фиксированного размера. Он реализован как связанный список.Так выделение просто

answer = head, 
head = head->next, 
return answer; 

Высвобождение просто

tofree->next = head; 
head = tofree; 

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