1kb and 2kb allocation "waste"

[Justin Lebar]

On Sat, Apr 21, 2012 at 10:23 AM, Jason Evans <jasone at canonware.com> wrote:
> On Apr 20, 2012, at 4:55 AM, Justin Lebar wrote:
>> It turns out that 1kb and 2kb allocations are responsible for upwards
>> of 1/3 of all wasted space in Firefox, where by "wasted space", I
>> mean: Open a bunch of tabs, close them, and call "waste" any heap
>> memory which is committed but not part of an active allocation.
>> (We've been calling this "external fragmentation", but that doesn't
>> quite match up with the common definition, as I understand it.)
>
> Do 1 and 2 KiB allocations make up substantially less than 1/3 of the memory devoted to small allocations?

No; in fact, in one run of the browser that I recorded, 1 and 2KiB
allocations together use 52% the memory devoted to small allocations
while accounting for only 35% of waste.  So that sounds pretty good!

On the other hand, it still doesn't tell me how to fix things, except
by saying that there's nothing to be fixed.  :)

> Yes, there are some systems that use 64 KiB pages by default, so any solutions need to be pretty pagesize-agnostic.

I guess supporting "medium" allocations of size pagesize/2 and
pagesize/4 would be feasible.

> Today has been a bunch of interleaved fire drills for me, so I'd better send this email before it gets lost forever.  I'm interested to hear your thoughts on the design space.  It's tempting to do an experiment that removes run headers, but the back-of-the-envelope calculations I did earlier weren't encouraging…

Yes, I suspect that for smaller allocations -- particularly when the
size of the allocation is not much larger than the size of the header
-- there isn't much to be gained by this approach.

It sounds like this might be worth digging into more.  I'll let you
know what I come up with.

-Justin