Investigate if we can re-use allocated memory after Map.Clear()

[ValarDragon]

In btree.Map, when we do btree.Map.Clear(), we are removing references to all old internal memory, which will cause it to be garbage collected.

If you then proceeded to build a similarly sized tree again, you'd have to re-allocate memory. If you use Clear() you should be expecting that the caller will at minimum, have to re-allocate the root. (Though to me the use case reads as wanting to preserve memory, vs instantiating a new map)

I feel like it'd be worth while to investigate if we can keep "spare allocated map nodes" around, for ability to re-use after Clear().

My intuition for an architecture here, is to have an MapNodeMemoryPool field in Map, and we move map nodes to there during a clear.

This lets us:

• Re-use memory after a clear
• Potentially re-use for MapNodes that get unallocated during normal operation
• Ensure theres never cross-thread dependencies if multiple maps are used in parallel. (As all memory pooling is done on a per-struct basis)

Please say if this is deemed as a not-desired complexity tradeoff!

[tidwall]

It may be worth experimenting. Perhaps a simple sync.Pool for nodes would suffice.

Ensure theres never cross-thread dependencies if multiple maps are used in parallel. (As all memory pooling is done on a per-struct basis)

One concern is the btree.Map.Copy method performs is a copy-on-write operations where the original and newly copied Map initially share the same nodes. A freelist style memory pool would need to be aware of node ownership. Right now the GC takes care of the bookkeeping.