recently made a project on solana.
perps matching & liquidation engines are not fully on-chain.
most of the times orderbooks are offline ( dydx ) or uses critbitbook (openbook)
but some of the most important operations :
- like how many orders need to be liquidated upon price change?
- how many levels needed to fill a big order?
are left O(n)
i provide a sample implementation of those queries in O(logn), completely on-chain.
benchmark: a matching order which took more than 200k CU executed in less than 8k CU !
tech behind it:
i used a fenwick tree instead of critbitbook which inherently stores sum for O(logn) queries in just 2x size.
had to do multiple workarounds like zero-copy implementation, scaling down all u128 to u64, etc to match solanas limits.
if you like it you go read more on my github and can star or follow me: https://t.co/lBJclpPF4c
made it for @SuperteamIN's fellowship.
CU Maxxing for life :)