Hi, I recently added a mechanism for runtime active defragmentation in redis, for which i added some code to jemalloc so that the application can decide which pointers are worth moving, and which aren't.
this hint can be merged into jemalloc so that other applications can choose to use it, and with your assistance it can maybe be improved so that defragmentation is more efficient.

first i'll describe what i already did:
after checking that the allocation is in a small bin (not large or huge), we must make sure it's not in the current run (used for new allocations), and that it doesn't reside in a fully utilized run. then we need to decide which non-full runs to evict and which non-full runs to fill.
ideally, the least amount of "work" would be to move the allocations from runs with low %run_utilization into runs with high %run_utilization, or in other words, re-allocate pointers that reside in runs with %run_utilization that is smaller than the average (i.e. the %bin_utilization).
additionally when re-allocating, we must make sure to bypass the thread cache, otherwise we'll "end up eating our own shit".

if want, you can take a quick look at the raw code i added: https://github.com/antirez/redis/pull/3720/files
(it also contains a showcase with malloc_stats output)
this was currently implemented on top of jemalloc 4.0.3, but i can PR that into the latest.

improvements:

1. when calculating the % bin utilization, it may be good to excludes full runs. so that we know if a run is less utilized than average, only among the non full runs, and not the entire bin utilization. for that all we need is to know the count of non-full runs in the bin.

2. when we re-allocate a pointer, it always moves into the non full run with the lowest address. there's a chance that this allocation will move out of a run which is going to be the currun soon, and we'll end up moving another allocation to the place we just evicted.

consider these to be runs in a certain bin (sorted by address space)
[xxx-] [xxxx] [xa--] [bx--] [xxxx] [xxx-]
'x' = used, '-' = unused, 'a'/'b' used allocations that we'll want to move.

in this case, assuming we'll first try to consider moving 'a' before we consider moving 'b'. it would be more efficient if we didn't move the 'a' and then move 'b' into it's place, and instead move the just 'b' into the unused space in the first run.

in order to do that i think we need to sort all the non-full runs of each bin by their address, and divide that list into two groups: ones that reside in address that is lower than the relative point in the address space than a split point according to the average bin utilization (% utilization that excludes full runs), and ones above it.
then we need to move only pointers that reside in run above that address.

please note that even the form that i already implemented (for which i didn't change anything in existing parts of the code) is enough to be very beneficial to the application.
i exposed the % utilization to the application so that i can play with some algorithms, and measure statistics, but if we want an API that can be easily improved in the future, we need to expose a single boolean result and do the decision inside the function.

please let me know what you think.
thanks.