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 _______________________________________________ jemalloc-discuss mailing list [email protected] http://www.canonware.com/mailman/listinfo/jemalloc-discuss
