[Enhancement] Bitmap-based key set for GC

[qouteall]

In the case of a complex changing graph, a tracing-based GC may be useful. If I want to do mark-and-sweep GC to a slot map, I can use another container to store all the keys that the slotmap contains, use another hash set for marking, recursively mark, then delete the keys that are not marked. Using a bitmap would be more efficient than using hash set.

Slotmap could provide a key set that's implemented by a bitmap. The key set will need these operations:

• Inserting a key.
• Test whether it contains a key.
• Clean a slotmap based on the keyset. The elements with keys that are not in the keyset are removed.
• The bitmap only cares about the index part of the key (if version is included, the bitmap will be too large). It may give wrong result for a stale key, as a performance tradeoff.

When I want to do a mark-and-sweep GC, I can create a new keyset, mark the elements, then clean the slotmap using the keyset.

Two slotmaps may reference each other. A GC process may involve multiple slotmaps and multiple keysets. To make the keyset convenient to use, it should not indirectly borrow the slotmap. It may contain invalid keys but that would still not break memory safety.

[qouteall]

Related article Tracing Garbage Collection for Arenas.

Could also provide mark-and-compact GC, given a bitset of living keys, output the a hash map of the moved keys. Having a compacting GC also reduces the need for HopSlotMap.