Question about bitmap code

[Jason Evans]

On Nov 5, 2012, at 3:53 AM, Mitchell Blank Jr wrote:
> I've been looking through some of the jemalloc code and had a question about bitmap.h.
> 
> Testing on a 64-bit machine, the arena bin with the most elements is size=8 with 501 items.  Since a cacheline is commonly 64 bytes = 512 bits, a simpler single-level bitmap would seem to win just on memory effects.
> 
> It's not clear to me if its advantageous on a branching basis, at least on 64-bit.  On average you'd need to look at 4 words to find an unused 8-byte entry, and fewer for other size bins.  I guess on a 32-bit platform, it might be a different story.  Still, I wonder if it is worth touching another cache line to avoid the comparisons.
> 
> Are there cases where the bitmap code is used for more than 512 items in it?


Older versions of jemalloc (2009 and earlier) used a single-level bitmap and also kept track of the lowest/highest indexes at which free regions might be found.  In practice this worked okay, but there are pathological access patterns that can cause n^2 overhead for a series of allocations, so there was always pressure to keep the bitmaps small that was in conflict with other constraints.  You're probably right that for 8-entry bitmaps, the multi-level bitmap code is overkill.  However, there are combinations of heap profiling settings that can cause the bitmap to contain thousands of items.

Jason