Bound memory usage #9

New Issue

andrew · 2024-03-09T00:52:10Z

andrew commented

2024-03-09 00:52:10 +00:00

For the bound on memory usage described in the ART paper, we need to maintain the following invariants.

All Node4's must have at least 2 1 children (let's defer implementing min 2 children since that turns out to be difficult)
All Node16's must have at least 5 children
All Node48's must have at least 17 children
All Node256's must have at least 49 children
max(numChildren, 1) * partialKeyLen >= partialKeyCapacity (for simplicity we'll only require that this one eventually hold)

I think the exact numbers of minimum children could be flexible based on the actual size of our nodes. We can redo the analysis and tinker if we want. We could even come up with a test property asserting bounded memory usage.

For the bound on memory usage described in the ART paper, we need to maintain the following invariants. - All Node4's must have at least ~~2~~ 1 children (let's defer implementing min 2 children since that turns out to be difficult) - All Node16's must have at least 5 children - All Node48's must have at least 17 children - All Node256's must have at least 49 children - max(numChildren, 1) * partialKeyLen >= partialKeyCapacity (for simplicity we'll only require that this one eventually hold) I think the exact numbers of minimum children could be flexible based on the actual size of our nodes. We can redo the analysis and tinker if we want. We could even come up with a test property asserting bounded memory usage.

andrew added this to the (deleted) project 2024-03-09 00:52:10 +00:00

andrew referenced this issue from a commit

2024-03-09 01:04:53 +00:00

Add an analysis on memory usage in static asserts

andrew referenced this issue from a commit

2024-03-12 00:33:16 +00:00

WIP downsize for Node{16,48,256} on erase

andrew referenced this issue from a commit

2024-03-12 00:33:16 +00:00

Merge Node4 with one child into child if favorable

andrew referenced this issue from a commit

2024-03-12 00:33:16 +00:00