Question about bitmap code

[Jason Evans]

On Nov 8, 2012, at 2:17 AM, Mitchell Blank Jr <mitch-jemalloc-discuss at bodyfour.com> wrote:
> The other cacheline concern I have is aliasing.  Again, think about the cascading free(): thousands of frees coming from dozens of different arena_run's but in essentially random order.  The problem is that the arena_run_t is always on a page boundary, so they will heavily alias each other at all cache levels.  (is this true of arena_chunk_t as well?  I'm still working my way around that code)
> 
> It might be worth moving the header to a different place in the page, i.e. instead of having it at appear at
>    ptr &~PAGE_MASK,
> use something like:
>    (ptr &~ PAGE_MASK) | ((ptr >> (LG_PAGE-6)) & (PAGE_MASK &~ 63)) 
> 
> Of course this makes computing the address of each element in the page a little more complicated (since now some appear before the header and some after it) but I think it could be worth it.

Interesting, that seems like an approach worth experimenting with, though with a modification that preserves the alignment guarantees alignment constraints for aligned memory allocation.  Yehuda Afek, Dave Dice, and Adam Morrison published a paper at ISSM'11 about this issue, called "Cache index-aware memory allocation".  It proposes a different solution to the problem that has the unfortunate side effect of breaking how jemalloc implements aligned memory allocation, IIRC without an obvious workaround.

Jason