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

Answer

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.