Heap Based Order Expiries

Details on optimisations for order expiry processing with heap data structure

The original implementation of the TWAMM has one big issue, where if you stop interacting with the pool, there are good chances the pool may get into a bad state and may not recover. It practically becomes unusable to the level that even exit pool will not work.

This happens because the original implementation loops over all the expiry blocks while moving forward. So, if for example for pool

order block interval: 100 blocks

Current block: 1010 lastVirtualOrderBlock: 15

Now when interaction happens with the pool, the pool will iterate over 10 times checking for 100th, 200th, 300th and so on block till 1010th while moving forward and processing order, if any. This especially become a much bigger problem when the pool is new and there are not much interactions with it or placed long term orders. The later the interaction with the pool, higher the gas it is going to cost. Too late of interaction can cause the pool to be bricked.

To avoid such scenarios, we are using heap based storage for order expiry orders, the order expiring first is always on the top of the heap. To move forward the lastVirtualOrderBlock, we check which is the latest expiring block on the heap and then move the TWAMM to this block directly. This saves us from unnecessary iterations over the expiry blocks. So, for above example for following scenario:

Next Order Expiry: 1005

lastVirtualOrderBlock: 15

Current block: 1010

The TWAMM will check which is latest expiring block from the top of the heap, which is 1005 and directly moves lastVirtualOrderBlock to 1005.