Rewriting bitmap_allocator

[Benjamin Kosnik]

> >> 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).
> >
> > Maybe step one is to add a test that crashes on you when you
> > use it.
> 
> I've been on it, but it seems hard to reproduce. I am beginning to
> think that it's been caused as a result of the application corrupting
> the bitmap.

I like where you are going with this. The move to describing this as a
segment tree is a huge win in terms of concrete useful detail for
users IMHO.

I see you are thinking of adding a debug-mode overlay to diagnose these
problems with greater ease. Seems like a win.... validating integrity
seems like a great place to start.

Another thing you may think about is adding locality/"hotness" to
profile mode or thinking of some way to measure this.

> >> 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.
> >
> > Please. Bonus if you can figure out a way to remove __mini_vector or
> > scope it such that it is clearly and implementation detail.
> 
> Sure. Let me know other things that strike you as kludgy, and I'll try
> to iron them out. I am guessing an anonymous namespace is what you
> have in mind.
> 
> Here is a link to the pdf (list didn't allow attachments):
> http://dhruvbird.com/bitmap_allocator_proposal.pdf

You may want to address C++11 allocator conformance/issues.

best,
-benjamin