[PATCH v3] malloc: send freed small chunks to smallbin

[Wilco Dijkstra]

Hi,

> The only possible effect I could think of is the fact that the patch affects
> the order in which small chunks are (re)allocated. Previously, recently
> freed chunks had a chance to get realloacted (due to the unsorted) quickly, while
> with the patch they would always follow the LIFO that smallbin enforces.

Only in some cases. Both the smallbin and unsorted bin are LIFO. So freeing
several blocks of smallbin size and then allocating them will be LIFO both
before and after.

The difference would be if a malloc for a different size would start scanning most
of the unsorted bin and moving chunks to small bins. Then you end up with
2x LIFO = FIFO for the smallbin ordering.

> So possibly heuristics like "chunks that were freed close time-wise should be
> close memory-location wise" could come into play. Following that logic it makes
> sense to me that LIFO is benefitial, and if it was in reality bad for
> fragmentation, that would denote a bigger problem in the current implementation
> of malloc.

Agreed, pure LIFO is better than some random combination of LIFO and FIFO.

> In any case if there was any effect, positive or negative, it would be negligable.

> There's this project for benchmarking malloc implementations:
> https://github.com/daanx/mimalloc-bench . It's pretty cool and has neat tests
> like running redis, fraction factorization etc. You can read about them in the
> "Current benchmarks" section of the README if you want.

Yes that is a great idea, we should probably run that for every malloc change.
Mimalloc is also one of the best open source allocators.

> The results are in the attachment. My interpretation is that RSS isn't affected.
> Time is also bearly affected (both positively and negatively) except in the gs
> test case where the patch sees a significant positive impact (yay!). That's the
> "gs: have ghostscript process the entire Intel Software Developer’s Manual PDF, which is around 5000 pages." test.

Those graphs are hard to read, but yes it looks like there is either no change or
a good improvement.

> I wanted to reproduce Wilco's benchmark but it seems xalancbmk is proprietary :(

It is part of SPEC2017.

Cheers,
Wilco