I have been optimizing my order book implementation recently, and I'm curious as to how far behind the curve I am. Order book being a data structure which supports the operations Add / Cancel / Reduce / Replace / Execute as in ITCH messages. Say, it also has to have 'fast' (i.e. something like O(1)) access to the best buy and sell orders. Any volunteers? Since I started the thread, I guess I'll go first. Disregarding I/O, my implementation processes each message in about 210 ns. It doesn't slow down for orders near the BBO (theoretically it's actually faster, but it's hard to get an exact measurement). Benchmark was run on an Intel i5-2500 (3.3 GHz, 256 KB L1, 1MB L2), DDR3-1333, on the historical file at ftp://emi.nasdaq.com/ITCH/09142012.itch41.gz.
whats your data structure? I use a tree for bids and tree for asks. Each node/level is a list of orders. There's probably a lot of other places you can optimize other than the orderbook.
I originally used a tree, but I found out that a different, smaller structure is faster. And yes, of course there are .
Not familiar with the NASDAQ ITCH feed - is it order based as in you know the composition of the queue exactly? Personally I am more familiar with the CME FIFO markets where you need to infer queue composition and the more accurate you want to be the slower it'll be. In regards to data structures my implementation is very similar to 2rosy's. Though I also maintain an unordered_map (in addition to a list) within the queue representation.
It's really stupid. It's like a (dynamically sized) array of linked lists for each side . Lookup is even more stupid. In fact it's so stupid that I'm too embarrassed to say, so don't ask. Your timer probably has 1% jitter in it
Yeah it's hard to compare then, as I need to make a few assumptions as to where and how cancels, mods affect the queue and how I represent the data. I suppose with ITCH you will know exactly as it provides the order IDs.