search

JuliaFinance / MarketObservables.jl

Provides standard types for financial markets
MIT License
5 stars 3 forks source link

Improve Orderbook implementation #12

Open femtotrader opened 5 years ago

femtotrader commented 5 years ago

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 https://github.com/JuliaFinance/Roadmap/issues/17

femtotrader commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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

lorrp1 commented 3 years ago

@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 commented 3 years ago

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 commented 3 years ago

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?