question about Jemalloc purging order

[Jason Evans]

On Jan 7, 2016, at 6:46 PM, mmzsmm <mmzsmm at 163.com> wrote:
> [...] according to the code comments, the clean-dirty fragmentation is measured as,
> 
> * Order such that chunks with higher fragmentation are "less than"
> * those with lower fragmentation -- purging order is from "least" to
> * "greatest". 
>     mean current avail run size                 nruns_avail-nruns_adjac
> --------------------------------------------  =  ----------------------------------
> mean defragmented avail run size                  nruns_avail
> 
> So if I have a chunkA with avail_runs = 10, adjac = 1, and another chunkB with avail_runs = 20, adjac = 5.
> Obviously, the fragmentA(0.9) > fragmentB(0.75), so the A will be prior to B in the dirty chunk tree, and 
> will be purged first. But the chunkB truely has more adjacs than the A, and the performace gain after purging 
> chunkA is also less than the other(0.1 vs 0.25). Why we prefer to purge the chunk with "less adjacs"? 
> Shouldn't we purge more adjacs or clean-dirty fragments to acquire more continuous unalloc pages?

We actually do purge B first, but it's hard to see unless you follow the calculations in the code.  Note that a_val=0.45 and b_val=1.5 in this case, which means that the comparison function returns 1, causing A to come after B in the in-order tree traversal.

> Another question is, I notice that before the git node e3d13060 there are two avail-trees, one is for dirty, 
> and another for clean,
>     arena_avail_tree_t    runs_avail_clean;
>     arena_avail_tree_t    runs_avail_dirty;
> After that, the two became one. So how to ensure the new runs allocaction to prefer to dirty pages? 

IIRC, there were versions of jemalloc that did not prefer dirty pages.

Note that you're looking at jemalloc 3.x code, but 4.x uses substantially different algorithms that obsoleted the code that ordered chunks according to fragmentation.

Jason
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://jemalloc.net/mailman/jemalloc-discuss/attachments/20160111/f8833186/attachment.html>