swift-collections icon indicating copy to clipboard operation
swift-collections copied to clipboard

[HashTreeCollections] Nodes should shrink themselves when possible

Open lorentey opened this issue 1 year ago • 0 comments

As the prefix tree grows, items inside nodes are slowly replaced with child references. For some Key/Value combinations, this reduces the size of the node; it would be nice if we allowed nodes to reallocate themselves to get rid of superfluous capacity.

(We should only do this when the load factor of a node shrinks below some predetermined minimum.)

Implementing this would likely slow down insertions somewhat, but in exchange it would allow better memory utilization -- which would probably be a worthwhile trade off to make.

lorentey avatar Oct 28 '22 01:10 lorentey