I am trying to implement a stock matching engine/order book in C++, and am searching for a more cache friendly architecture. Currently, my data structures are as follows:
An intrusive rb-tree for the limit prices. An intrusive doubly linked list for holding the orders at the limit prices. I have thought about ways to replace the rb-tree, such as a sparse array of limit prices which are themselves linked, but I believe the rb-tree is a better use case as I'm dealing with a sparse book. Now, for the doubly linked list, I have thought about using an array. Aside from resizing it if it fills up, appending and traversing would be optimal, but deletion would require either shifting or skipping deleted entries. I have also considered an unrolled linked list, but from my research and testing, it seems that it works much better when entries are a couple of bytes instead of larger Order structure.
Are there any other data structures anyone could point me to, particularly to optimize the cache friendliness?
On another note, if I used a LIFO stack as a memory pool and provided the doubly linked quote lists with objects from this stack to reuse recently deleted quotes, it would preserve cache-time locality, but not necessarily spatial locality. Are my instincts correct in this?
Also, I've tried to do quite a bit of testing and analyzing the cache with perf stat in linux, but it hasn't been easy. If someone has any more tips on how to do cache analysis, they would be more than welcome.
Lastly, please no comments on premature optimization. I am doing this largely as an exercise and to learn more. This project is not for production and I don't have a completion timeline. Thanks!