How fast is your limit order book implementation?

Discussion in 'App Development' started by hft_boy, Dec 20, 2012.

  1. hft_boy

    hft_boy

    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.
     
  2. 2rosy

    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.
     
  3. hft_boy

    hft_boy

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

    2rosy

    so what is it?
    I can processes each message in about 209 ns :D
     
  5. hoppla

    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.
     
  6. hft_boy

    hft_boy

    It's really stupid. It's like a (dynamically sized) array of linked lists for each side :p. 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 ;)
     
  7. hft_boy

    hft_boy

    Yes, you do know the composition exactly.
     
  8. hoppla

    hoppla

    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.
     
  9. A fan of sorted dictionaries of sorted dictionaries right here..
     
  10. 2rosy

    2rosy

    is the map orderid->position in queue so you can handle order cancels in o(1)
     
    #10     Dec 23, 2012