Idea for reducing array allocations in functions that use `shrink`

[sjakobi]

In functions like filter and intersection we allocate a mutable array, fill it as needed, then shrink it and return it as a BitmapIndexed or Full node.

I wonder whether we could reduce these allocations by starting out with a bitmap that records which subnodes we keep or remove. Only once we encounter a node that is changed, e.g. a BitmapIndexed node reduced to a Leaf, we allocate an array for the result.

[sjakobi]

We could also try something like this when operating on Collision arrays. Not sure what would be best to do when a Collision array has more than 64 elements though.

[treeowl]

I don't really understand. Where do we put the new subtrees while we're waiting to find out which ones we'll have?

[sjakobi]

The premise is that due to the large fan-out, the vast majority of nodes are Leaf nodes, which we either keep or drop. To record this, a bitmap and an index are sufficient. But once we encounter a subtree that has changed, we allocate an array and switch to recording the new subtrees in the array directly.

EDIT: The idea is that when we allocate the array, we can use the bitmap to tell that some nodes are removed, so we can use a smaller size than we currently do.