[RFC] Implementation of Bitmap-managed Arena (arena3) for improved cache locality

[ByteMaster2003]

Overview

I am proposing a new Arena implementation (arena3) to replace the current linked-list-based storage (arena2). The goal is to move toward a more cache-friendly, memory-efficient allocation strategy by using a Bitmap to track object availability instead of a linked list of heap items.

Current Limitations (arena2)

• Metadata Overhead: Each object is wrapped in an ArenaHeapItem, adding a 64-bit next pointer. This increases memory pressure and padding requirements.
• Cache Locality: The "Sweep" phase requires chasing pointers through a linked list, which often results in cache misses and unpredictable memory access patterns.

Proposed Solution (Arena3)

The new BitmapArena treats the allocated memory buffer as a series of 64-byte aligned cells.

• Bitmap Management: Uses a Vec<u64> as the source of truth for allocation. Each bit represents a 64-byte block.
• Consolidated Header Model: We remove the ArenaHeapItem wrapper. The GcBox<T> is stored directly in the arena cells. This saves 8 bytes per object and simplifies the layout.
• Hardware Optimization: Allocation uses bitwise manipulation (e.g., trailing_zeros) to find free slots. This is highly efficient on modern architectures like ARM64 (Apple M1).
• Drop-in Compatibility: The alloc signature remains compatible with existing logic, allowing it to be integrated into the MarkSweepGarbageCollector with minimal refactoring.

Technical Details

• Alignment: 64-byte (configurable).
• Complexity: * Alloc: O(1) fast-path (scanning a single u64).
  Sweep: O(N/64) using bitwise AND/OR operations to reclaim memory.
• Next Steps: I am exploring a "Partitioned Recycling" strategy where empty arenas are swapped to the end of the management vector to be reused immediately, avoiding unnecessary deallocations.

Questions for Mentors

• Should the bitmap stay isolated in a Vec<u64> (as currently implemented), or is there a preference for an in-band header approach?