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

Я пытаюсь реализовать стандартный механизм поиска / книгу заказов в C ++ и ищу более дружественную кеш архитектуру. В настоящее время мои структуры данных следующие:

• Навязчивое руб-дерево для предельных цен.
• Навязчивый двусвязный список для удержания ордеров по предельным ценам.

Я думал о способах замены rb-дерева, таких как разреженный массив предельных цен, которые сами по себе связаны, но я считаю, что rb-дерево — лучший вариант использования, так как я имею дело с разреженной книгой. Теперь для двусвязного списка я подумал об использовании массива. Помимо изменения размера, если он заполняется, добавление и обход будут оптимальными, но удаление потребует либо смещения, либо пропуска удаленных записей. Я также рассмотрел развернутый связанный список, но из моих исследований и испытаний кажется, что он работает намного лучше, когда записи представляют собой пару байтов, а не большую структуру Order.

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

С другой стороны, если бы я использовал стек LIFO в качестве пула памяти и предоставлял двусвязные списки кавычек с объектами из этого стека для повторного использования недавно удаленных кавычек, это сохраняло бы локальность кэша, но не обязательно пространственную. Верны ли мои инстинкты в этом?

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

Наконец, пожалуйста, не комментируйте преждевременную оптимизацию. Я делаю это в основном в качестве упражнения и узнать больше. Этот проект не для производства, и у меня нет графика работ. Спасибо!

редактировать для большей ясности это похоже на мою текущую реализацию, первоначально взятую из https://web.archive.org/web/20110219163448/http://howtohft.wordpress.com/2011/02/15/how-to-build-a-fast-limit-order-book/:

Существует три основных операции, которые должна выполнять книга предельных заказов (LOB): добавить, отменить и выполнить. Цель состоит в том, чтобы реализовать эти операции за O (1) время, позволяя торговой модели эффективно задавать вопросы, такие как «какова лучшая ставка и предложение?», «Какой объем существует между ценами A и B?» или «Какова текущая позиция X в книге?»

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

Order
int idNumber;
bool buyOrSell;
int shares;
int limit;
int entryTime;
int eventTime;
Order *nextOrder;
Order *prevOrder;
Limit *parentLimit;

Limit  // representing a single limit price
int limitPrice;
int size;
int totalVolume;
Limit *parent;
Limit *leftChild;
Limit *rightChild;
Order *headOrder;
Order *tailOrder;

Book
Limit *buyTree;
Limit *sellTree;
Limit *lowestSell;
Limit *highestBuy;

Идея состоит в том, чтобы иметь двоичное дерево объектов Limit, отсортированных по limitPrice, каждый из которых сам является двусвязным списком объектов Order. Каждая сторона книги, Лимиты на покупку и Лимиты на продажу, должны быть в отдельных деревьях, чтобы внутренняя часть книги соответствовала концу и началу дерева Лимита на покупку и Лимита на продажу соответственно. Каждый ордер также является записью на карте с ключом idNumber, и каждый Лимит также является записью на карте с ограничением limitPrice.

С помощью этой структуры вы можете легко реализовать следующие ключевые операции с хорошей производительностью:

• Добавить — O (log M) для первого порядка в пределе, O (1) для всех остальных
• Отмена — O (1)
• Выполнить — O (1)
• GetVolumeAtLimit — O (1)
• GetBestBid / Предложение — O (1)