Implement mass cancel quotes (first pass)

[jarry-xiao]

Here is an initial implementation of a mass cancel instruction. It's by no means rigorously tested yet, but I did add to the test file to test basic functionality. Note that if you remove either of the mass_cancel calls, the test will fail.

I don't know what the team's conventions are regarding style, but open to any and all feedback.

[dr497]

Have you made any measurements to see what compute budget you save by adding this? I am afraid the overhead you save is pretty small

[jarry-xiao]

Haven’t made measurements yet, was just putting this out here as an idea. I’m guessing you would save at least the CPI cost (for programs that call into the AOB contract), but it is probably worth it to find the exact increase in throughput.

IMO it’s not so much about compute budget as wanting the mass cancel operation to be atomic. It’d be much easier to call this instruction than to call cancel in a loop in an upstream program or client. I think it also gets around potential tx size limitations.

Any other major opposition? I don’t think adding this hurts any existing functionality. There no urgency to merge it right now, but there might be future features that could benefit from having this instruction.

[jarry-xiao]

I think you're right that it's not too much better as of right now. I was able to mass cancel 35 orders while using ~192k compute units. Not great.

Each leaf removal seems to take ~4k, and the initial in-order traversal took almost 60k! Maybe there's nothing much to gain here, but I think this is still probably 2-3x the number of cancels that you can fit into a normal instruction.

It might be possible to optimize the critbit data structure for removal by making it easier to access the leaves directly, but that would be bigger change.

[dr497]

Can you describe a bit more how you would optimize the critbit?

[jarry-xiao]

Haven't thought it through 100%, but the potential idea would be:

1. Create a sorted doubly linked list in the LeafNode struct to allow for easier access. When you call get_min or get_max this will then return the head or tail of a linked list that can be traversed when handling new_orders or mass_cancels. Accessing the next node becomes a constant time lookup with this scheme. Reorganizing the inner nodes might be a little tricky here admittedly.
2. Potentially just mark nodes as removed instead of actually deleting them from the tree. You would need to have a some sort of scheme to reorder/cleanup.

These are somewhat half-baked thoughts, but I'll continue thinking about how to make some of them more concrete.

[Henry-E]

Is the serum implementation of prune any use as a reference? https://github.com/project-serum/serum-dex/blob/master/dex/src/state.rs#L2567-L2610

prune is essentially the same as what's being proposed here, remove all orders for a given user's open order account

[jarry-xiao]

Is the serum implementation of prune any use as a reference? https://github.com/project-serum/serum-dex/blob/master/dex/src/state.rs#L2567-L2610

prune is essentially the same as what's being proposed here, remove all orders for a given user's open order account

This totally works with Serum-v3, but I don't think it will work here because there are no open orders accounts in the AOB. Orders/accounting are all managed by calling programs, so prune would have to be implemented in a higher level program. It would look roughly like this:

for order in user.orders {
    invoke_signed(
         &aaob_cancel_order(order, &cancel_order_accounts), &cancel_order_accounts, &[market_signer_seeds]
    )?;
}

This is undesirable due to the CPI overhead required. I think it would make a lot more sense to natively support the mass cancel operation on the tree level.

[Henry-E]

Ah, based on reading the serum v4 code it looked like the AOB was used as a crate rather than via CPI. Honestly, it seems like a really bad idea to use the AOB via CPI and not as a crate. It's adding unnecessary compute cost and an additional account. Account + compute efficiency is going to become even more important as solana starts changing its fee model and as more professional market makers are on boarded to the ecosystem.

[dr497]

The AOB is used as a lib in dex v4