How fast is your limit order book implementation?

hft_boy · Dec 20, 2012

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.

2rosy · Dec 21, 2012

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.

hft_boy · Dec 22, 2012

Quote from 2rosy:

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

.

2rosy · Dec 22, 2012

Quote from hft_boy:

I originally used a tree, but I found out that a different, smaller structure is faster. And yes, of course there are .

so what is it?
I can processes each message in about 209 ns

hoppla · Dec 22, 2012

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.

hft_boy · Dec 23, 2012

Quote from 2rosy:

so what is it?
I can processes each message in about 209 ns

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

hft_boy · Dec 23, 2012

Quote from hoppla:

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.

Yes, you do know the composition exactly.

hoppla · Dec 23, 2012

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.

Rationalize · Dec 23, 2012

A fan of sorted dictionaries of sorted dictionaries right here..

2rosy · Dec 23, 2012

Quote from hoppla:

Though I also maintain an unordered_map (in addition to a list) within the queue representation.

is the map orderid->position in queue so you can handle order cancels in o(1)