[m-rev.] For review: Improvments to Stack Segments code.

[Paul Bone]

On Wed, Feb 23, 2011 at 07:58:27AM +1100, Zoltan Somogyi wrote:
> On 22-Feb-2011, Paul Bone <pbone at csse.unimelb.edu.au> wrote:
> > Non-segmented stack (32MB)
> >     asm_fast.gc                      average of 5 with ignore=1     18.16 (1.00)
> > 
> > With 512KB (normal) segments:
> >     asm_fast.gc.stseg and NO caching average of 5 with ignore=1     19.20 (1.06)
> >     asm_fast.gc.stseg WITH caching   average of 5 with ignore=1     19.16 (1.06)
> > 
> > With 4KB segments:
> >     asm_fast.gc.stseg and NO caching average of 5 with ignore=1     20.66 (1.14)
> >     asm_fast.gc.stseg WITH caching   average of 5 with ignore=1     19.66 (1.08)
> 
> >     Not all zones are added to the used list for the benefit of the memory
> >     error handlers.
> 
> I don't understand what this means.

Rewritten to say:

    To avoid an unnecessary sychronisation in parallel code some zones are not
    added to the used list.  The only zones put on the used list are those that
    are useful to have on the used list because they have a non-default signal
    handler or a redzone.

> >     Updates to used_memory_zones now use a pthread mutex so that only one
> >     thread may be updating the list at once.  This lock is shared with the
> >     free_memory_zones structure.
> > 
> >     Updates to used_memory_zones now use memory barriers to guarantee that
> >     concurrent reads always read a consistent, but possibly incomplete,
> >     data-structure.  This is necessary because it is read from a signal handler
> >     which cannot call pthread_mutex().
> 
> Do you mean that READS from used_memory_zones use barriers?

No.  Even though we take a lock to perform the update we have to ensure memory
writes are properly ordered so that a thread reading the list without taking a
lock will always see a valid linked list.

For example:

    new_head->next = head;
    MEMORY_WRITE_BARRIER;
    head = new_head;

These two memory locations are declared as volatile to ensure that the C
compiler doesn't re-order these instructions.

> 
> > runtime/mercury_stacks.c:
> >     Use MR_GC_NEW rather than MR_GC_malloc_uncollectable for the list of
> >     previous stack segments associated with a context.  The context is heap
> >     allocated so the list need not be uncollectable.
> 
> But if you know that it is never garbage until explicitly released, then
> you can spare unnecessary scanning.

Won't it still scan it in order to mark the objects that it points to?  Perhaps
uncollectable may make Boehm assume that this object is in the root set and
therefore make things more efficient.  I've undone this change.

> > runtime/mercury_wrapper.h:
> > runtime/mercury_wrapper.c:
> >     Disable redzones when using stack segments.  The settings here apply to
> >     the first segment on every stack.
> 
> What settings do you mean?

Reworded:
    Disable redzones when using stack segments.  The MR_(non)detstack_zone_size
    variables affect the first segment on every stack.  Regardless of the type
    of contaxt that owns that stack.

> > runtime/mercury_context.h:
> > runtime/mercury_context.c:
> >     Small contexts are only used in stack segment grades.
> 
> But what is the change?

Reworded:

    Small contexts are problematic since it's unclear to the programmer which
    computations will be executed on smaller contexts and therefore whether
    their stacks would overflow.

> > -    zone->MR_zone_name = name;
> > -    zone->MR_zone_id = id;
> > -    zone->MR_zone_desired_size = size;
> > -    zone->MR_zone_redzone_size = redsize;
> > +    zone->MR_zone_name = NULL;
> 
> Why ignore the name?

It's initialised by the caller, I've added a comment to this effect.

> 
> >  #ifdef  MR_CHECK_OVERFLOW_VIA_MPROTECT
> > -    zone->MR_zone_handler = handler;
> > +    zone->MR_zone_handler = NULL;
> >  #endif /* MR_CHECK_OVERFLOW_VIA_MPROTECT */
> 
> Why this change?

This is also initialized by the caller, I added another comment.

> > +    /*
> > +    ** XXX: Why use this value for new_total_size?
> > +    */
> >  #ifdef  MR_PROTECTPAGE
> >      new_total_size = new_size + 2 * MR_unit;
> >  #else
> 
> If you think it does not make sense, change it.

I've worked out why and changed the comment.  But we should be able to make it
smaller saving a page in every zone.  But that's a job for another day.

> > +/* 16 zones per thread */
> > +#define MR_FREE_MEMORY_ZONES_NUM_HIGH   (16*MR_num_threads)
> > +/* 4 zones per thread */
> > +#define MR_FREE_MEMORY_ZONES_NUM_LOW    (4*MR_num_threads)
> > +/* 16MB per thread */
> > +#define MR_FREE_MEMORY_ZONES_PAGES_HIGH (((16*1024*1024)/MR_page_size)*MR_num_threads)
> > +/* 4MB per thread */
> > +#define MR_FREE_MEMORY_ZONES_PAGES_LOW  (((4*1024*1024)/MR_page_size)*MR_num_threads)
> 
> You may want to control these via MERCURY_OPTIONS, and doing that would be
> simpler if the multiplication by MR_num_threads was done by the code using
> these constants, not parts of the constants themselves.

I should have implemented this earlier.  I'll make a note and come back to it
later.

> > +/*
> > +** A pointer into the list of free zones that always points to sub-list (when
> > +** valid) with the least-recently-used zones.
> 
> I don't understand what this is trying to say.
> 
> Certain actions can invalidate
> > +** this pointer, if this happens it is set to NULL.  Therefore this can be
> > +** thought of as 'cached information'.
> 
> Cached from what?

Reworded:

    This value is used to maintain a position within the list of free zones.
    If it is null then no position is maintained.  Otherwise it points to a
    position within the list, in this case it represents a sub-list of free
    zones.  This sub list always contains the least-recently-used zones.

    Some actions can invalidate this pointer, in these cases it should be set
    to NULL.

    When this value is non-null, it can be used to quickly find the least
    recently used zones.  This is used by the garbage collection loop.

> > +                ** This zone list had the least recently used zone on it,
> > +                ** invalidate the lru_free_memory_zones pointer.
> 
> Why is that OK to do? Why can't you set it to point to the next least recently
> used zone?

The garbage collection loop will notice that the pointer is NULL and
re-initialize it.  I've added a comment.

> > +            /*
> > +            ** Because no lists currently exist, this new list must be the list
> > +            ** with the lru zone on it.
> 
> According to a comment a couple of dozen or so lines ago, the assumption
> here seems to be incorrect; some lists MAY currently exist.

Yes, that assumption is false, I've removed this code.

> > +
> > +    zone->MR_zone_next = cur_list->MR_zonesfree_minor_head;
> > +    cur_list->MR_zonesfree_minor_head = zone;
> > +    if (!cur_list->MR_zonesfree_minor_tail) {
> > +        /*
> > +        ** This is the first zone on this list, so we set the tail to it to
> > +        ** track it as the least-recently-used zone on the list
> > +        */
> > +        cur_list->MR_zonesfree_minor_tail = zone;
> 
> Don't you need the tail pointer set up correctly anyway? And end the sentence
> with a period.

Yes, the comment is superfluous and misleading.  I've corrected it.

> > +static MR_bool
> > +MR_should_stop_gc_memory_zones(void)
> > +{
> > +    return (free_memory_zones_num < MR_FREE_MEMORY_ZONES_NUM_LOW) ||
> > +        (free_memory_zones_pages < MR_FREE_MEMORY_ZONES_PAGES_LOW);
> > +}
> 
> Didn't your comment above say this || should be &&?

Thanks :-)

> > +struct MR_MemoryZonesFree_Struct {
> > +    size_t              MR_zonesfree_size;
> > +    MR_MemoryZonesFree  *MR_zonesfree_major_next;
> > +    MR_MemoryZonesFree 	*MR_zonesfree_major_prev;
> > +    MR_MemoryZone       *MR_zonesfree_minor_head;
> > +    MR_MemoryZone       *MR_zonesfree_minor_tail;
> 
> Align the fields' indentation.

An editor hint for vim was messing from the top of the file.

> > +    MR_release_zone(MR_CONTEXT(MR_ctxt_detstack_zone));
> >  
> >      list = MR_CONTEXT(MR_ctxt_prev_detstack_zones);
> >      MR_CONTEXT(MR_ctxt_detstack_zone) = list->MR_zones_head;
> >      MR_CONTEXT(MR_ctxt_prev_detstack_zones) = list->MR_zones_tail;
> >      MR_CONTEXT(MR_ctxt_sp) = orig_sp;
> > +    /* XXX: GC will get this */
> >      MR_GC_free(list);
> 
> Yeah, so? Why the XXX?

To remind me that I could remove the explicit free.  But now this is
allocated as uncollectable so I've removed the comment.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 490 bytes
Desc: Digital signature
URL: <http://lists.mercurylang.org/archives/reviews/attachments/20110404/ca68bc9f/attachment.sig>