2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Have you considered storing Order structures in a cache-friendly heap, such as a B-heap? As an analogy, the B-heap generalizes the binary heap in the same way that a B-tree generalizes a binary search tree. It should make for fewer cache misses at the expense of only slightly more complicated parent/child calculations. The Order structure doesn't have to be very large (id, price, vol, ...), so the benefits of using a cache-friendly data structure may win out over the cost of copying structures around. $\endgroup$ – Tyler Olsen Aug 11 '15 at 16:51
  • $\begingroup$ I forgot to mention this before, but valgrind has a function called "cachegrind" that simulates first- and last-level caches, as well as giving you an idea of how well branch prediction works in your code. I have found this tool to be very easy to use. The only issue is that valgrind doesn't like some libraries that do their own memory management (eg, libhdf5). Careful if you're using any of those. Their page is: valgrind.org/docs/manual/cg-manual.html $\endgroup$ – Tyler Olsen Aug 15 '15 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.