dfinity
feat: Support memory freeing
Problem: Stable structures do not support memory freeing.
Solution: To free memory, we’d need to add the following API to the memory manager:
fn free(memory: MemoryId) -> ();
Post Conditions:
- The size of memory is zero.
- The buckets used by memory are unallocated.
- Currently, the memory manager allocates new buckets by growing its underlying memory. Instead, we should ensure that allocations of new buckets by the memory manager use all the unallocated buckets of memory first before growing the underlying memory.
To do: Maybe in the future remove the external dependency BitVec and use bit operations instead.
Thanks @dragoljub-duric. I left some comments. Additionally, the PR description I think can be improved, where we concisely write the problem and the solution. It's currently more of a checklist on how to implement this PR.
@ielashi @dragoljub-duric Hey guys, this has been open for quite a while. Should we try to wrap it up?
@ielashi @dragoljub-duric Hey guys, this has been open for quite a while. Should we try to wrap it up?
I'm now nearly done with the BTreeMap changes. I'll schedule time to wrap up the review of this tomorrow.
Do we want to include this change in the upcoming 0.6.0 release?
No, ideally this would follow in a minor release, so that we have had time to test thoroughly before releasing it.
@ielashi I saw that we have a new release. Can you please approve it now?
@ielashi I saw that we have a new release. Can you please approve it now?
Hey @dragoljub-duric, I'd like to do some more testing given that we found a number of bugs previously in the PR, and given how important this code is, it's better to err on the side of caution.
@ielashi Can you please take another look?
@dragoljub-duric Thanks! From a code standpoint this looks good. The remaining concern I have is related to performance. Prior to this PR, memory performance operations were O(1), but with this change they would be O(# buckets used), correct? I don't yet know exactly how big of a deal this is, as we don't have benchmarks for that.
Let's discuss more in our 1:1 about next steps.
At a high-level, I think we should work on:
-
Verifying the correctness of this change. For that, I think we need stronger test-cases for the MemoryManager. I suggest we (in a separate PR), add a fuzz test, in a way that's similar to this one, and we can run this for a couple of days with these changes to ensure things are working as expected.
-
Understanding the performance impact of this change.
- For that, I think we need to introduce (also in separate PR) the CI changes to track our benchmarks, just as we did with the
bitcoin-canisterrepo. - We can then also add a benchmark where we allocate a large number of buckets and see how this current PR affects the performance of that benchmark.
We had a discussion offline and agreed that this approach may not be the best approach. This design was intended to keep the memory manager header bound to 64KiB to make migration from V1 simple, but that came with the additional complexity of using 15-bits for bucket indexes, and also a performance degradation where the grow memory operation can be up to 3 orders of magnitude more expensive.
In the future, we’ll likely need to expand the memory manager header beyond 64KiB in order to, for example, support a larger number of buckets. If that’s going to happen eventually, then there are simpler and more efficient ways to implement memory freeing. For example, we won’t need to store the bucket IDs as 15-bits, and we can use linked lists to make growing and freeing at O(# buckets), as opposed to O(max number of buckets) with the current approach.
There hasn’t been a lot of pressure on us to deliver this feature, so we can park this for now, close the ticket, and revisit with a more comprehensive design in the future.