Rewriting bitmap_allocator

[Dhruv Matani]

Hello!

With increasing memory sizes, and increasing difference between the
size of CPU caches and main memory, improving locality and reducing
the per-object allocation overhead seems to have become an important
idea. The current bitmap_allocator has been crashing on me (even
though it provides excellent cache locality).

With that in mind, I would like to propose a re-write of the
bitmap_allocator<> now that I have a better idea of how it can be
implemented. I would be happy to present a proposal for the same (with
details) if it is a thing of interest.

As a reminder, the bitmap_allocator<> is an allocator that optimizes
memory requests for single object allocations of a homogeneous size.
i.e. Nodes of a linked list, RB-Tree, etc... Since these structures
are used fairly heavily in many applications, it becomes important to
reduce the fragmentation caused by using these containers and also
ensuring that the per-object allocator overhead is kept low. IIRC, the
current bitmap_allocator<> manages to achieve an overhead of 1-bit per
object.

Regards,
-Dhruv.