11
$\begingroup$

I am trying to write a highly optimised limit order book and I wondered what sort of size I can expect for:

  • Range of limit prices
  • Number of orders at each limit price

I am developing custom hardware (FPGA) and thus have very limited amounts of memory available and very different data structures. (The typical pointer-based data structure is normally quite inefficient in an FPGA).

The application is an equities HF market-making strategy in which I require the current top of book from an ITCH data feed to decide inside prices.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
5
$\begingroup$

A correct answer would depend on the instruments and markets you're trading, and whether this is for handling public or propietary orders. For example, if I were to design for the simple case, US equities and a public market, I'd want the queue size at each price level to be able to handle at least the maximum daily volume of, say, QQQ. I know that's in no way "highly optimized", but the worst time for your shiny fast book to have a meltdown is when something unexpected has happened somewhere. Likewise for price ranges -- you need to be able to support prices that are at least several orders of magnitude higher than the highest price ever printed in that market. Again taking equities as an example, some of the highly leveraged inverse ETFs have the potential to do things we've never seen before.

If you're dealing in currency pairs, for example, there are way too many ways that a series of political events can blow up your code if you try to make data structures too tight. Use Hungary or Zimbabwe as your model when you're thinking this through; it's possible that squaring the total current value of a given country's money supply might not be a big enough number for a currency pair's future numerator or denominator.

Maybe the real correct answer is the one you probably don't want: Optimize your data structures for speed by using the right algorithms, but don't try to optimize them for size if you want your code to survive interesting times. You might even want to use the maximum size your platform comfortably allows; if you're trading anything that might be subject to hyperinflation, even 64 bits might not be enough for a price field.

It also comes down to the business model that you're planning on supporting; at some point the business needs to know where these limits are and when they might need to exit certain markets before their own systems fail catastrophically.

Another way of approaching this would be to look at the data sizes of the applications which talk to the order book. If you plan on supporting smaller data sizes than those client apps, then you'll want to guard against what will happen when a larger-than-expected value does arrive. The worst case might not be a core dump -- it might be a large order filled at a price that overflowed and wrapped. ;-)

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Its unlikely that a price will ever exceed 18,446,744,073,709,551,615 even with assuming its representing cents. It would be unwise to use 128 bit integers or arbitrary precision integers due to the performance loss incurred. $\endgroup$
    – Steve Severance
    Mar 13, 2012 at 16:58
  • $\begingroup$ I did say "comfortably allows". ;-) I wouldn't use 128 bits, but I also wouldn't use anything less than 64 bits without first having a conversation with one or more traders. $\endgroup$
    – stevegt
    Mar 13, 2012 at 20:20
7
$\begingroup$

If you're writing a "highly-optimized" book then you should be tailoring that book to the venues from which you will be receiving data. Max price, for example, is published in NASDAQ's Itch spec: 200,000.0000.

If you plan on trading US equities you better go read each of the venues depth of book specs very carefully. You'll find all sorts of ways to optimize your book implementation. Same goes for other markets and instruments.

Improve this answer
$\endgroup$
0
2
$\begingroup$

In regards to size: I assume that you would most likely want to structure the software to implement each 'book' as a unit of orders representing that particular security, and possibly (as mentioned above) further divide these structures into individual pricing structures such-structures.

You would want to be able to scale each individual 'unit' to a pretty arbitrarily large size, for safety reasons, and assume that the system they were running on would have extremely large provision resources.

Also you might want to consider the ability to 'buffer' large elements of the program's data by sending it to and from long-term storage, both for efficiency, and safety in the event of catastrophic failure at a memory level. The unit structure I'm alluding too lends itself to more quickly swapping elements in and out of memory, rather than having to write large contiguous sets of elements (orders, etc.) which is obviously a big resource suck.

I've been working (a little bit in my freetime) to generate source code for LOB's in various languages. I've also added some C++ implementations done by other authors (the quantcup entries from 2011)

Other issues I've considered for the basic structure are:

  • Concurrency (inserting or removing orders in the correct order)
  • Threading (this is where functional languages are valuable)

https://github.com/jordanbaucke/Limit-Order-Book

Improve this answer
$\endgroup$
9
  • $\begingroup$ Can you clarify how concurrency w.r.t insertion and removals arises in your implementation? I just have experience with futures LOB models, but (in sim mode) concurrency (from an input perspective) only arises when depths or trades arrive at the LOB. IMHO any messages that alter the state of the book should do this on the thread the LOB runs on, ie it's better to enqueue messages on at least one producer upon their arrival and then be consumed on a separate LOB thread. This way arrival time priority will always be maintained and you also don't have to lock any (otherwise) shared resources. $\endgroup$
    – emsfeld
    Mar 20, 2012 at 4:53
  • $\begingroup$ @emsfeld, I agree, I guess I sort of imagined my final implementation would allow the different portions of the 'array' to be locked simultaneously so as to allow for market orders to pull the 'top' orders (fifo) out of the list, while limit-orders would be inserted elsewhere by their own thread: [[head: .00][.01][.02][03]] Assumption: the head of the list is what "market orders" are matched too. Therefore, threads lock the order array in different segments, which would requires some concurrency and synchronization issues to be addressed. Ex. resetting the head of the list. $\endgroup$
    – jordan.baucke
    Mar 20, 2012 at 19:16
  • 1
    $\begingroup$ I see. I think matching trades to the front of the queue in a non pro-rata market is the right way to go. At least all the main CME products work that way (Minis and FX). I'm not sure though if you get the speed improvements you are hoping for. My guess would be that locking can become quite expensive - even within user space threading. If this is for backtesting then other aspects have to be considered where it might be better to process each new order on a single thread and also have your strategy run on the same thread. It can get extremely messy otherwise. $\endgroup$
    – emsfeld
    Mar 21, 2012 at 0:41
  • $\begingroup$ Cool, well I'm still just toying with with my adaptations from time to time when I get some extra minutes to program. @emsfeld any white-papers or places I could look for more info on the CME Products and how they are implemented as you described? $\endgroup$
    – jordan.baucke
    Mar 21, 2012 at 3:56
  • 1
    $\begingroup$ No links handy, but I read a white paper/ technical manual on CME's FIX implementation - it's public. They also have real sample data of what a day's worth of trading the eg ES looks like in raw format. Somewhere in there they tell you by examples how additions, cancellations and modifications are being treated by their matching engine. Obviously, you'll need to figure out/ infer yourself how and where the queue is affected. $\endgroup$
    – emsfeld
    Mar 21, 2012 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.