This bounty is being pursued by @sardariuss
1 Like
Hi, Is this bounty already closed and assigned to someone? I still this as open bounty here icdevs[.]org/news
1 Like
Yes I am, I’ll be able to show you some progress soon.
1 Like
In that case is it possible to have it assigned, and not be it in the open bounties section?
I’d like to be able to transform Motoko basic types (essentially the Nat16/Nat32/Nat64 and resp. Int) types into an array of bytes. In rust this is done with to_le_bytes. Also if there is something that exists to convert a struct into such an array of bytes I’m taking it too. I think rust uses the trait #[repr(packed)] that allows to peform a safe cast into a pointer of u8, then converted into a vec. But I doubt something that straightforward is possible in Motoko.
Otherwise I might continue with my tricky structures in my AlignedStruct module for now. But at some point I think I will need to be able to convert everything in a vector of bytes anyway just to be able to test with a “fake” memory (like vec_mem.rs in the Rust implementation). I was curious to test directly with ExperimentalStableMemory, but it crashes at the compilation of the tests, which probably makes sense.
I have that logic in candy_library/conversion.mo at main · skilesare/candy_library · GitHub. You could adapt it…probably don’t need the whole candy library as you are trying to do something fast.
1 Like
Hey, small update for this bounty, the code is here: GitHub - sardariuss/MotokoStableBTree: https://forum.dfinity.org/t/icdevs-org-bounty-24-stablebtree-mokoko-up-to-10k/14867
I finished the implementation of the BTreeMap itself, I’ll start on the unit tests next week.
And thank you for the candy lib that’s exactly what I needed.
2 Likes
Hi Skilesare,
All Rust unit tests have been implemented in Motoko. As suggested by CanScale, I’m gonna continue with these 3 tests before jumping on the merkleizaton:
1 - A test that does random key insertion for ~ 5000 values
2 - A test that is always inserting a new value which is the new highest value in the tree ~ 5000 values
3 - A test that runs an upgrade, and then show they persisted through the upgrade
I have a question though: the conversion from type to bytes are done in little endianin Rust, whereas the conversions from the candy lib are in big endian, so should I convert my types in little endian instead ?
1 Like
Hey @sardariuss,
Nice to meet you online! I’m on the Motoko team at DFINITY and am working on extending data structures in the base library. I was wondering if you have any interest in contributing this to the motoko-base library when it is complete (with potentially some added QOL bells and whistles to make it very user friendly).
Let me know what you think.
4 Likes
Hi Kentosugama,
Nice to meet you too! Yes for sure, I’d be very happy to do that.
2 Likes
Hi,
I’ve done the few tests I was talking about before (testing with actual stable memory), it works well, for now it’s in a separate repo here:
I’m gonna put this in the original repo soon, with CI on top.
@kentosugama I’ve been thinking a bit on how to improve the public interface to make it more user friendly. As an example the current BTreeMap.init method looks like this:
/// Initializes a BTreeMap.
///
/// If the memory provided already contains a BTreeMap, then that
/// map is loaded. Otherwise, a new BTreeMap instance is created.
public func init<K, V>(
memory : Memory,
max_key_size : Nat32,
max_value_size : Nat32,
key_converter: BytesConverter,
value_converter: BytesConverter
) : BTreeMap<K, V> {
First, I could wrap the current BTreeMap class into a new StableBTreeMap (or just StableBTree?) that uses the stable memory as memory. This would remove the memory parameter from the init method. And we could only expose a few methods (e.g. insert, get, remove, size). I want to keep the rest public in the original BTreeMap so I can do unit tests.
Second, it would be great if the key_converter and value_converter could directly be deduced from the type of K and V. But AFAIK it’s not possible to do such thing in Motoko. I’m forced to have a method to convert types in bytes because the ExperimentalStableMemory has a specific method for each type. I guess I could create a StableBTreeVK class for each combination of K and V I want to support but this is super ugly. Note that converting in bytes also makes my life way easier to be able to test the BTreeMap with my VecMemory that is a buffer of bytes.
One alternative could be to not template any of this and use always use [Nat8] for keys and values, forcing the user to do the conversion beforehand and afterwards. But IMO I’d rather just have to give the converters in the init method.
What do you think? Is this some of the improvements you were thinking when talking about “QOL bells and whistles” ?
2 Likes
Hey!
This sounds great.
As a general point, I think it makes sense to fully complete the ICDevs bounty first, and then we can worry about merging into base.
By QOL, I mainly mean adding extra utility functions (e.g. motoko-base/Buffer.mo at master · dfinity/motoko-base · GitHub). I don’t think there will be as many functions for maps, but things like finding max value, min value, folding over maps, mapping a higher order function over the kv pairs, producing a text representation of the current entries, etc.
Serialization seems to be the most thorny problem. Right off the bat, do you think there’s a good way to have a non-stable version, where the user doesn’t have to pass in a memory (since it’s just stored in the normal heap), and there’s no max sizes or converters since serialization is not necessary?
As for the stable use case, I agree that having the users pass in the converters is the best approach at the moment. I would definitely not implement every combination of serializer by type 
A possible alternative: Not sure if you’ve considered using to_candid and from_candid primitives? These are Motoko operators that let you serialize any shareable type to Blobs and back. Could be useful as an out of box serializer, except for the fact that you need to convince the compiler that the generic types are shared. As far as I can tell, this is a bit tricky at the moment. Motoko Sharable Generics.
3 Likes
Hi guys,
Last updates:
- The MemoryManager has been added to be able to use many btrees in stable memory. All tests pass, but it seems that using the MemoryManager significantly slows down the execution of the BTree functions. I haven’t done any investigation yet.
- A version of the Btree using the heap instead of the stable memory is now available on the branch “heap_version”.
- Kentosugama will start PRs to gradually put the code (both stable and heap versions) into the motoko-base library. @skilesare Could somebody from ICDevs be involved in the reviews ? That could be a way to validate the first part of the bounty.
4 Likes
Awesome! I’ll take a look early next week. We’ll get the bounty closed out. Great Job!
Hey, icme made me realize I missed a few things: for the stable implementation, I missed a few recent commits from the rust repo, I’m gonna check that out. For example chore: Enhancements to the StableBTreeMap API. (#17) · dfinity/stable-structures@53d4f93 · GitHub I could do something similar in the motoko version, adding the max_size function in the BytesConverter, and probably exposing the bytesConverter for every common type (Nat8, Nat32, etc.).
Also for the heap_version, I need to use a buffer of the real K, V types instead of bytes, there is no need to convert in bytes indeed.
@kentosugama I will create new branches in my repo to do this to not impact the PR if that’s correct with you
1 Like
Small update: I implemented the max_size() function in the BytesConverter on the main branch and the K, V template arguments for the heap version.
@kentosugama I tried to understand what’s happening with the MemoryManager today.
First I noticed that the execution slows down or crashes:
- around 5k entries when using the MemoryManager (with stable memory)
- around 25k entries when using directly the stable memory
When it slows down or crashes, I usually have these messages in the console:
Nov 23 18:36:15.524 WARN s:za6i6-rsijm-wkhfy-76yge-w72zd-2mbch-4hjg5-6ieqy-alrnx-azwgk-iqe/n:evshh-lrotb-t5oeu-psqm7-fqz5h-zfyun-r5wdr-u5ugs-zqhrz-wc7rw-uae/ic_execution_environment/scheduler Finished executing message type “Ingress, method name insertMany,” on canister CanisterId(rrkah-fqaaa-aaaaa-aaaaq-cai) after 7.2521542 seconds, messaging: {“round”:41,“canister_id”:“rrkah-fqaaa-aaaaa-aaaaq-cai”,“message_id”:null}
Nov 23 18:36:32.719 WARN s:za6i6-rsijm-wkhfy-76yge-w72zd-2mbch-4hjg5-6ieqy-alrnx-azwgk-iqe/n:evshh-lrotb-t5oeu-psqm7-fqz5h-zfyun-r5wdr-u5ugs-zqhrz-wc7rw-uae/ic_consensus/consensus starvation detected: Notary has not been invoked for 4.1307306s
Also when I monitor the RAM, I see some spikes that seem to coincide with the moment these messages are emited. That RAM far exceeds the memory required for my entries to be stored in the btree.
My naïve guess is that the query/update methods I call take too much time (because I call a single canister method insert that inserts 5k entries at once in a motoko loop to reduce test time). This creates problems with the simulated consensus, which then requires more cpu and memory to perform, and ultimatly leads to the crash. But in my tests, when I tried to call the query/updates in 10 batches of 500 entries, it doesn’t quite solve the problem.
I’ll continue investigate tomorrow, but any feedback will be appreciated!
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.
2 Likes
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
2 Likes
This is really cool! Having a dedicated memory manager in the base module would make it easier to create stable memory collections.