Implementing data-structures in a Limit order book

Question

I'm working on implementing a 'LOB' and I'm being very careful about choosing my data-structures so as to maximize performance.

Using F# as an example, I need to consider a List versus Array for holding 'Bids' and 'Asks'.

Because these lists are constantly being updated very rapidly, and the orders that need to be removed, added, updated quickly, I would think 'Array' because of 'efficient random access'.

That being said, Lists (singly-linked in a functional language like F#) seem to be more versatile, and faster for adding and subtracting from the 'head' of the list, but not necessary good for 'random access'?

Thoughts, am I on the right track?

Answer 1

i am not a F# expert but when it comes to performance and thread safety try sorted list or hashset. sorted list if the data needs to be sorted (it gets sorted when added to the list) otherwise hashset, no sorting hence better performance. they are both generic.

in addition i would think you need thread safety when reading/writing/updating your data in this case the above will give you performance and safety you need. if i remember correctly the hashtable will give you the identical or close to it times as listed on the page provided by bellamyj above.

Answer 2

Here's a blog post with a general overview of some possible implementations.

howtohft_howtobuildafastlimitorderbook - (mirror of the original posting)

The posting was originally on the website www.quantcup.org - this site is up for sale but I leave the broken URL to help future searchers:

Answer 3

F# provides you with many data structures for collections, but in functional programming, you try to have immutable data structures, such as the F# List. It becomes quite handy if you want to do some parallel computing, for example.

You can have a look at my post on SO which is probably where you could ask your question in a more generic way such as "What is the best data structure to use in F# if I need quick data access?"

Answer 4

I am not familiar with F#. I have implemented this many times in C++. I would go with fixed length arrays. Fr me performance is paramount. In C++, one is better off handling holes than allocating memory on the heap and add the complexity of a cache miss.

Answer 5

I would actually not bother with F# data structures for this - many of them are actually slower than ordinary .NET collections. My approach is to use SortedDictionary<price,volume> for bids and asks. That way, you always know the best prices on the market.

Of course, the above assumes that you're not concerned with thread safety and are building the order book on the same thread, which is generally a sensible assumption.