Completed: - Bounty 24 - StableBtree Mokoko - up to $10k

Maybe try importing the library and using it on the Motoko playground if you think it’s an issue with the local replica and want to reproduce the behavior.


Small update, concerning the limitations observed with the memory manager, the same things happen on the main net. I didn’t spend more time investigating because:

After discussing with @kentosugama, it seems that dfinity is or will be working on unifying a memory manager implementation to be able to use different custom stable data structures simultaneously (maybe it will be through a change of the ExperimentalStableMemory api). I don’t have much more information about it for now.

Also the merge request to put the BTree in the standard library is still in draft


This is really cool! Having a dedicated memory manager in the base module would make it easier to create stable memory collections.

I’m shifting my focus to this now myself, after coordinating with @kentosugama earlier today. I am only now catching up on this thread; I apologize for being late to the discussion.

My first impressions are that this BTree implementation in Motoko will be ideal for testing the more modular version of the (currently experimental) stable memory API, which I’ll explain briefly here. I apologize for revisiting what’s already discussed above.

In the current API, there is conceptually a single monolithic array with low-level read and write operations, and a procedure to grow the array into a larger one. Without more work, this only supports a single (monolithic) data structure.

As a first implementation to generalize this, I propose offering a class in Motoko that comes with the same API as the current (experimental) module.
Each constructor call would create a distinct (initially-empty) “memory instance”, corresponding to a distinct growable array.

Under the hood, the class would use a dedicated allocator for stable memory to manage the monolithic space and give the abstraction of these distinct arrays, rather than a single shared one (still the reality at that lowest level). As a first implementation of the allocator, we could reimplement this Rust implementation of the idea entirely in Motoko, using the currently-experimental API, with the intention of eventually hiding it entirely behind this new (non-experimental) class.

There will still be the same caveats as today: The experimental API is very low-level, and it’s still possible to clobber yourself within an array. The benefit of the new class would be that two (or more) stable structures would:

  • coexist without clobbering each other
  • not consume any space as “reserve” (no padding space is needed)

Looking more closely at the existing implementation in Motoko by @sardariuss it seems that this route is exactly what’s already done here.

And it seems to give a big slowdown, based on reading comments above and in the repo itself.

Perhaps the next step here is to look more carefully at this implementation, with an eye towards improving the performance, if possible. Using an RBTree from base for the buckets is conceptually clean but could be less than optimal in terms of performance, for instance.


Update: After more discussion today with my colleagues, it seems like there’s a strong interest in pursuing the inclusion of this stable memory allocator feature within the Motoko runtime system itself, to leverage the leaner, lower-level performance available there. I’ll be shifting focus to that now, with more updates to follow.


Thanks for the updates.

Now that I think about it I should have compared the performance of the motoko implementation with the Rust’s one. Also I’m curious to see what kind of improvements you will do (e.g. for the RBTree).

1 Like

This PR gives some initial thoughts. Specifically, the design proposal in the markdown file reflects some ideas from last week that are still evolving this week as we continue to discuss tradeoffs of different approaches.

While we want to start with something similar to the Rust version, we are also looking towards generalizations of it, though that will come later.

The main generalization of interest is supporting GC-based reclamation of “stable regions” for reuse by others. That consideration is affecting some of our current thinking, since we want to support it eventually, somehow.


The design/ document in the PR is now “stable” (no pun intended).

I’ve moved on to trying to implement the primitives described there.

In the meantime, we can discuss the design and the way it could be used for building things like the StableBtree described in this thread. If anyone sees issues or has questions, please let us know.

1 Like