更多缓存友好链接列表或替代方案,具有限制订单簿的最佳附加,删除和有序遍历？

Question

我正在尝试用C++实现股票匹配引擎/订单簿,并且正在寻找更加缓存友好的架构.目前,我的数据结构如下:

• 极限价格的侵入式rb-tree.
• 用于以限价价格持有订单的侵入性双重链表.

我已经考虑过替换rb-tree的方法,例如本身链接的稀疏数组的稀疏数组,但我相信rb-tree是一个更好的用例,因为我正在处理一本稀疏的书.现在,对于双向链表,我考虑过使用数组.除了填充后调整大小,附加和遍历将是最佳的,但删除将需要移动或跳过删除的条目.我还考虑了一个展开的链表,但是从我的研究和测试来看,当条目是几个字节而不是更大的Order结构时,它似乎工作得更好.

是否还有其他人可以指出的数据结构,尤其是优化缓存友好性？

另一方面,如果我使用LIFO堆栈作为内存池并提供带有来自此堆栈的对象的双向链接引用列表以重用最近删除的引号,则它将保留缓存时间局部性,但不一定保留空间局部性.我的直觉在这方面是否正确？

另外,我试图在linux中使用perf stat进行相当多的测试和分析缓存,但这并不容易.如果有人有关于如何进行缓存分析的更多提示,那么他们将非常受欢迎.

最后,请不要对过早优化发表评论.我这样做主要是为了锻炼和学习更多.这个项目不用于生产,我没有完成时间表.谢谢!

编辑更清晰,这与我当前的实现类似,最初来自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在书中的当前位置是什么？"

一本书中的绝大多数活动通常由增加和取消操作组成,因为做市商争夺头寸,执行距离遥远(实际上我会争辩说许多股票的大部分有用信息,特别是在早上,是添加和取消的模式,而不是执行,但这是另一个帖子的主题).添加操作在要以特定限价执行的订单列表的末尾下订单,取消操作从书中的任何地方删除订单,并且执行从书的内部删除订单(内部该书定义为最高购买价格的最早买单和最低卖价的最早卖单.这些操作中的每一个都是一个id号(下面的伪代码中的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;

我们的想法是使用limitPrice排序的Limit对象的二叉树,每个对象本身都是Order对象的双向链接列表.本书的每一面,即购买限额和卖出限额,应该在不同的树中,以便书的内部分别对应于买入限价树的结束和开始,并且卖出限价树.每个订单也是一个键入idNumber的地图中的条目,每个限制也是一个键入limitPrice的地图中的条目.

使用此结构,您可以轻松实现这些关键操作并获得良好的性能:

• 添加 - O(log M)为限制的第一个订单,所有其他的O(1)
• 取消 - O(1)
• 执行 - O(1)
• GetVolumeAtLimit - O(1)
• GetBestBid/Offer - O(1)