Quantitative Finance Stack Exchange is a question and answer site for finance professionals and academics. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
Implement both, and profile. The same as any other performance question. – Matthias Dec 10 '13 at 6:56
up vote 6 down vote accepted

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.

share|improve this answer
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.

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:

share|improve this answer
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?"

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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