Memory Coalescing
Buddy Block
Classic, pretty easy, some limitations
Lazy Tree
This is mine.
Header
- 8*N : Handle Pointers
- 4*N+1 : Nodes between handles
- 8: First action
- 8: Last action
Free block layout
- 1: Tags LR (for threading) R/B (for tree) Action
- 8: L
- 8: R
- 8: Next Action
So we have a minimum block size of 24 bytes.
Under ideal circumstances, free blocks form a threaded tree. We keep handles to a fixed number of points in the tree and try to keep them evenly spaced. There is always one handle that points to the largest block.
When doing an insertion, we try to insert the best location provided by the handles. Since the number of handles is constant, this is a fixed time operation. Since the tree is threaded, we know if it's a correct insertion or not. And I believe we know if the tree is balanced - but I'll have to think about that.
If the insertion is not perfect, we tag the node for the actions it needs to perform and add it to the action list
- Out of Order : this node is not in the correct spot in the tree
- Rebalance : this node violates R/B rules
- Merge: this node may be able to merge with it's neighbors
When ever an insertion or deletion (allocation) happens, if there are actions to perform, we do some fixed number of actions.
This needs some refinement. The tree either needs to be a KT tree (which I don't know if that can be threaded) or we need two trees (one for size, one for location). I need to do some analysis on this.
I think I can show that the number of actions can be moderate (~32) and it would be difficult to impossible to get into a bad state. With 32 actions, if we're maintaining 2 balanced trees it might we can always maintain a tree of depth 8 in a single "turn". This is because we split the actions between the 2 trees for 16. Then we split the actions between searching the tree for the correct insertion and rebalancing the tree after. That would guarentee 256 nodes. But few cases will be the worst case scenario on both trees.
We can also prioritize the size tree. It's important to efficiently allocate the correct size. If the memory is highly fragmented, the order tree isn't going to do us any good. If it's not fragmented, the order tree is going to resolve itself down in very few steps.