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

[Paul Bone]

On Mon, Oct 10, 2016 at 09:13:46AM +1300, Bruce Hoult wrote:
> On Sun, Oct 9, 2016 at 4:40 PM, Paul Bone <paul at bone.id.au> wrote:
> 
> > 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?
> 
> 
> Right.
> 
> In fact there is an existing API which would be useful for this:
> 
> void* GC_malloc_many(size_t objSz)
> 
> ... which is implemented by ...
> 
> void GC_generic_malloc_many(size_t objSz, int objKind, void **result)
> 
> It might make sense to have GC_malloc_many_atomic() or the uncollectable
> variants, but they din't exist at the moment and you can get the effect now
> by a direct call to GC_generic_malloc_many.
> 
> This call returns some number of objects of the same size (rounded up
> minimally -- just to the next multiple of 16 bytes), all of which are
> located in the same gc/VM page. The first bytes of each object point to the
> next object, and the return value is a pointer to the first object.
> 
> The function tries to find an existing block of objects of that size,
> allocating an entire new block only if one can't be found. It might make
> sense to add a parameter (or another function) to force always using an
> entire (new or reclaimed) VM page for the returned list.

Cheers.

>  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?
> >
> 
> First, the free list for objects of a particular size (and kind) always[1]
> contain only objects from a single gc/VM page. The objects are ordered by
> memory address within the gc page.
> 
> When the free list for objects of a particular size is empty, a single page
> of objects of the same size is swept and any objects that were not marked
> (reachable) at the previous GC are added to the free list. Some objects in
> the page may have since become unreachable and this is not detected, but
> it's impossible for a previously unreachable object to become referenced --
> since it was unreachable by the app :-)

I have no problems understanding that last point ;-)  If I doubted it I
wonder how I could cope with memory management at all!  Actually, since
BoehmGC is conservative maybe you're asserting an extra assurance, that in
this situation BoehmBC won't misunderstand a value that looks like a pointer
to previously used but not yet swept memory as a pointer.  This is an edge
case that I hadn't thought of before but now seems pretty obvious.

> If a page is "nearly full" then it is skipped, on the assumption that it
> takes a lot of time for little benefit (speed/space tradeoff).

That's a reasonable assumption.  Has anyone tested different policies here?
As I understand it, sweeping should be relatively fast, especially for mostly
full pages.  It starts by checking the mark bits (a medium-sized but
sequential memory read) and finding any unmarked objects it threads them
together in a linked list (writes to a number of different cache lines).

    SweepCost    = ReadMarkBits + N*WriteLinks
    SweepBenifit = N

Sweeping a mostly full page is the cheapest sweep, but has little benifit.
Sweeping a mostly empty page has a higher cost (but writes are amortized if
there is more than one per cache line) and a great benifit.  It seems that
skipping mostly full objects mostly reduces how frequently sweeping is
required, and only affects the cost/benifit of sweeping slightly.  Please
tell me if you disagree, this is the most I've actually worked with memory
management.

> The order in which pages are swept is determined by the ok_reclaim_list for
> blocks with that size of object, linked together by the hb_next field. This
> is set up by GC_apply_to_all_blocks() after each GC, which processes pages
> in order of memory address.
> 
> [1] unless you use GC_free(), in which case anything freed by GC_free() is
> at the start of the free list and will be the first object(s) of that
> size(&kind) to be returned from GC_malloc().

Cheers.

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