Take the 2-minute tour ×
Quantitative Finance Stack Exchange is a question and answer site for finance professionals and academics. It's 100% free, no registration required.

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
add comment

4 Answers

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
add comment

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

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

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
add comment

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
add comment

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
add comment

Your Answer

 
discard

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.