Improve Orderbook implementation

[femtotrader]

Improving orderbook implementation to support dynamic features (insertion, deletion, cancellation, and modification of orders) might be considered

AVL tree
https://en.wikipedia.org/wiki/AVL_tree
seems to be a quite common used datastructure for implementing such features (thanks @brilhana for sharing this)

See also
https://csce.ucmss.com/cr/books/2018/LFS/CSREA2018/FCS3665.pdf
https://www.doc.ic.ac.uk/~wl/papers/17/fpl17ch.pdf

Related issue
Implementing a limit order book matching engine JuliaFinance/Roadmap#17

[femtotrader]

Julia doesn't seem to have currently an AVL tree implementation (except https://github.com/torgausen/JuliaAVL which is 7 years old)

Maybe a first step could be add such an implementation to DataStructures.jl

[StephenVavasis]

DataStructures.jl already has balanced trees: 2-3 trees are the basis for SortedDict, SortedSet and SortedMultiDict. Their performance is comparable (same up to constant factors) to AVL trees. My testing, now several years old, seemed to indicate that the main performance bottleneck with SortedDict, SortedSet and SortedMultiDict is poor memory locality of reference. There is work on "cache oblivious" balanced B-trees by Bender, Demaine and Farach-Colton, which have superior memory locality, but to the best of my knowledge this work has not been implemented in Julia.

[femtotrader]

Hi @StephenVavasis thanks for this comment but maybe comments about AVL tree implementation should occurred in DataStructures.jl repository.

[lorrp1]

@femtotrader the repository is 2 years old and there is no documentation, I’m looking to create an order book as well but I’m not sure if this is a good place to start since it’s pretty old

[p-casgrain]

I have begun working on an LOB implementation using AVL trees. I am roughly following along the lines of this Python implementation . I have found the implementation of the AVL tree in DataStructures.jl to be list-like so I have opted to use the following dict-like implementation which is closer to what is needed. Should the current DataStructures.jl implementation be replaced or amended in the future, it should be easy to modify the code accordingly. I have found both libraries have comparable performance anyways.

The current implementation is intended to be relatively barebones: i.e. trading a single asset, with no built-in message parsing. I am also a Julia novice, so I will definitely require a code review once completed.

[p-casgrain]

I am at the point of forking and uploading my changes but I realize that the OB implementation has a dependency on the AVLTrees package hosted in the following repo. It's not currently listed in Pkg.jl, do any of you have some tips on how to go forward?