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

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

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

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

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

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

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

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

2 4
c++ binary-tree data-structures memory-management cpu-cache

2 ответа:

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

Если вы ищете универсальное ассоциативное хранилище, существует несколько удобных для кэша (другие ключевые слова: "Cache-efficient", "cache-oblivious") алгоритмов, таких как массивы Judy , для что есть обширное объяснение PDF .

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

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

4

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

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

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

Освобождение-это просто 

tofree->next = head;
head = tofree;

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

1