[m-dev.] [Gc] Article about memory fragmentation

[Paul Bone]

On Sun, Oct 09, 2016 at 08:50:45AM +1300, Bruce Hoult wrote:
> Good article, as far as it goes, but it just .. stops .. before the
> interesting analysis.

Thanks.  It might sound funny but I agree with you.  I initially did the
investigation in June and when I found some time recently to write it up I
found I couldn't reproduce the situation.  The article was written with the
data that I had collected in June.

If I was to continue, and I think I might, I would profile the same program
and show how the memory for each object size changes over time, as I agree
with you, it's very likely that we do use most of the 32 byte blocks, then
free them.

> 
> Btw "uncorrectable" should be "uncollectable".
> 
> Almost all those block sizes have excellent utilization ratios. A moving
> collector could scarcely do better!

Yeah, this is why I added a note about a semi-space copying collector, since
it would be worse in terms of utilisation.  It would be better for locality
however.  I'm not sure how well a mark-compact or
mark-sweep-and-sometimes-compact collector would go.  I'm aware that there
will always be less than perfect utilization, to give the heap space to grow
into.

> But there's definitely room for improvement with the 32 byte size.
> 
> I'm very curious what the memory allocation pattern in that makes you end
> up with so many blocks with so few live objects.
> 
> My best guess is that at some point you actually did have 60 MB of 32 byte
> objects, but then most of them became unreachable. But you're the one who
> can gather the object lifetime data.
>
> In a long-running program, you'd expect that space to get used again,
> multiple times, so it's not really a problem.

I'll try to do that.  We know that there are several stages while processing
a document where we throw away large structures that are no-longer needed.
Eg after styles have been computed but before pagination.  Prince will
process a document, then terminate and a new process is started for a new
document.  It's not a long running process, and therefore memory usage isn't
super-important, but of a client uses Prince very frequently, it can be
important.

> But it can also be that there is a usage peak for some object size during
> program startup, and then they are not needed again. Unfortunately, there's
> very little that a non-moving GC can do about that.

We will also be able to collect data about which constructors of which types
account for this allocation size.

> It might be possible to do something about that at a user level though: if
> there are interspersed allocations of short lived and long lived (or
> pemanent) objects of the same size, then you could pre-allocate a number of
> objects (4 KB worth or some multiple) and put them in your own freelist or
> some other collection, and then replace the current GC_malloc of them with
> taking one from the pre-allocated list. You could do this for either the
> short-lived or the long-lived objects, but I suspect that the long-lived
> ones might give the easiest benefit. Get them all onto the same memory
> pages, that will stay reasonably full, and let entire pages of short-lived
> objects get GC'd and those pages reused for objects of other sizes.
> 
> The GC can't be some kind of oracle and predict these usage patterns, but
> you might be able to.

I'd like to check that I understand.  By pre-allocating long lived items,
but not short lived items, we're more likely to guarantees that those objects
are allocated on the same blocks, and not interspersed on other blocks
preventing those blocks from being freed when the short-lived objects are
collected?

I can see the potential, but I'd want to collect more information and
understand which objects, of these sizes, are long or short lived.  We could
modify the profiler by adding a word to each object that points back the
call site information (available when profiling is enabled) and increments a
counter there each time that object survives a collection.  Then we could
know for each allocation site, whether it creates long or short lived
objects.

Can you or someone else on the BDWGC tell me in what order blocks are put on
the free lists.  Do the free spots in mostly-full blocks appear earlier on
the free lists?  If things are placed on the free list in the order they are
swept which blocks are swept sooner?

Cheers.

-- 
Paul Bone
http://paul.bone.id.au