deque

[bitdivine]

Thank you for the stable structures.

Would it be possible to add a deque to the set of structures? Either simulated under the hood as a BTreeMap or as a separate implemementation?

If you are short of time, I can definitely provide a PR with a BTreeVecDeque. For a native implementation I would have to spend some time reading through your code before I could make an offer.

[ielashi]

Hey @bitdivine, a deque would certainly be a nice addition. I can see it being implemented either on top of BTreeMap or on top of our Vec/BaseVec implementations. Can you share your use-case? Maybe that can help guide the discussion on which implementation would be more suitable.

[bitdivine]

Hello @ielashi . Thank you for the response.

The nns-dapp has a queue of transactions. New transactions are added to the front, old ones are removed from the back. Transactions have sequential numerical indices from N to N+K. The current implementation is a VecDeque that is serialized and deserialized on every upgrade; I am looking at moving that into a stable structure. Off the top of my head every entry is about 120 bytes and there are half a million entries. I don't have any throughput numbers at the tips of my fingers.

I guess that stable structures also have to be stable in the sense that an implementation has to be compatible with earlier versions, so switching from one implementation to another might not work but if the implementations have different names, developers have to make a conscious choice to move from one to the other.

Best wishes, Max

[ielashi]

Thanks for the context @bitdivine. As discussed, we have a few options:

Build a deque based on stable Vec.

• (+) Performance: push and pop would be O(1).
• (-) Can only use bounded types (i.e. types that implement BoundedStorable)

Build a deque based on stable BTreeMap.

• push and pop would be O(log(n)).
• (+) Can (very soon!) support unbounded types.

If unbounded types is helpful to you and performance isn't as critical to you, then maybe a BTreeMap would be the better choice here. We do not have timeline for supporting unbounded types in Vec at the moment.

[bitdivine]

Thank you for the update. For this deque I am pretty sure we won't need variable sizes, but on the other hand performance is not a constraint either so a deque built on BTreeMap would work well, as far as I can see.

[witter-deland]

Build a deque based on stable Vec.

• (+) Performance: push and pop would be O(1).
• (-) Can only use bounded types (i.e. types that implement BoundedStorable)

It is not a FIFO, pop is to remove items at the end of the vector.

I'm using MinHeap instead, but I'm expecting a queue structure like:

1. Performance: push and pop would be O(1).
2. Support unbounded types.