Re: [musl] mallocng progress and growth chart

[Rich Felker <dalias@libc.org>]

On Fri, May 15, 2020 at 08:29:13PM -0400, Rich Felker wrote:
> On Sun, May 10, 2020 at 02:09:34PM -0400, Rich Felker wrote:
> >  4668:   2x5440   2x5440   2x5440   2x5440   2x5440   5x4672   5x4672   5x4672   5x4672   5x4672   5x4672   7x4672   ...
> 
> This turns out to be just about the worst edge case we have, and in a
> sense one that's fundamental. Sadly there are a number of
> applications, including bash, that do a lot of malloc(4096). The ones
> that just allocate and don't have any complex malloc/free patterns
> will see somewhat higher usage with mallocng, and I don't think
> there's any way around that. (Note: oldmalloc also has problems here
> under certain patterns of alloc/free, due to bin_index vs bin_index_up
> discrepancy!)

Actually oldmalloc "cheats" for the exact case mentioned here, 4096,
because it's an exact size class boundary where
bin_index(4096)==bin_index_up(4096). For any other size (e.g. 4080 or
4097) the catastrophic non-reusable-chunk thing will happen.

This actually suggests that, if trying to improve/salvage a dlmalloc
type design, it would be useful to round up to size classes before
allocating, and to avoid trimming down to exact size. Of course this
would use considerably more memory initially (just like mallocng uses
more than oldmalloc) for straight bump allocation with no free, but it
should give less fragmentation and more-stable usage over time. Of
course there might be new failure modes too when doing that,
especially since split/merge won't preserve the property of being
exact size classes.

An interesting experiment would be to hack up oldmalloc to round up to
size classes, then compare memory usage with mallocng. I suspect we'd
then find mallocng almost always uses less memory.