Implementing data-structures in a Limit order book

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?

-
Implement both, and profile. The same as any other performance question. –  Matthias Dec 10 '13 at 6:56

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.

-
thanks I'm going to give this a shot I hadn't thought about hashsets –  jordan.baucke Jul 3 '11 at 23:57
when I consider 'thread' safety should I use the .NET 'Monitor' and or thread-safety protocols to lock the entire set while an order is being added, updated, or removed? That being said, I'm wondering if it's a performance hit for other threads to loose access to the the entire set of orders while the operation is taking place? At the same time, if the top of the bid or ask changes because a new order is added/removed and the array isn't locked another thread could potentially misplace the order... –  jordan.baucke Dec 13 '11 at 19:15

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

http://www.quantcup.org/home/howtohft_howtobuildafastlimitorderbook

-
thanks @bellamyj -- actually this project was very much inspired by the 'Quant Cup' challenge, although I'm not a student, and not entering. But I didn't think to look there for inspiration, it does list some important information about time sensitive requirements though...! –  jordan.baucke Jul 1 '11 at 3:17

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?"

-

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.

-