[m-rev.] Post commit review: Remove available-space field from region struct

Zoltan Somogyi zs at csse.unimelb.edu.au
Thu Dec 20 18:36:38 AEDT 2007


On 19-Dec-2007, Quan Phan <quan.phan at cs.kuleuven.be> wrote:
> Zoltan, can you take a look at the diff to make sure I do not introduce
> any clear problems. It turns out that we do not need to move the
> next_page field in the MR_RegionPage struct as the first field because the
> pointer to last word of the data area can be computed by
> last_page->MR_regionpage_space + MR_REGION_PAGE_SPACE_SIZE - 1.

Yes, it can. However, when you allocate a new region page, you will be
(a) initializing the pointer to the next page (to null)
(b) filling in the first cell allocated from that region page.

If the pointer to the next page is at the end of the region page, you are
guaranteed to get separate cache misses for (a) and (b). If the pointer
to the next page is at the start of the region page, a single cache miss
will handle both, provided the cell is small enough. I would say that the
conditionally included profiling field, MR_regionpage_allocated_size,
should also be put near the start.

Note that the code currently has several casts between MR_Region and
MR_RegionPage, all of which will need updating if you move the fields.
However, the casts should be replaced anyway by a conversion macro,
and this can be updated to apply any required adjustments by casting
not the region page, but its MR_regionpage_space field.

I think there is another potential performance problem in the current value
of MR_REGION_PAGE_SPACE_SIZE. We want every MR_RegionPage structure to have a
power of two size, since that makes both allocators and caches as efficient
as possible. However, MR_RegionPage's size is now 257 words (258 with RBMM
profiling).

For now, I suggest setting MR_REGION_PAGE_SPACE_SIZE to 255. In the longer
term, I would suggest replacing MR_REGION_PAGE_SPACE_SIZE with another macro,
MR_REGION_PAGE_SIZE (set to a power of two), and defining MR_RegionPage like
this:

struct MR_RegionPage_Struct {
	MR_RegionPage	*MR_regionpage_next;
#if ...
	MR_Integer	MR_regionpage_allocated_size;
#endif
	MR_Word		MR_regionpage_space[1];
}

The size of the array would of course be a lie, but C doesn't mind, and
we can easily specify MR_REGION_PAGE_SIZE * sizeof(MR_Word) in the call
to malloc. Or we could set the array size at MR_REGION_PAGE_SIZE minus one
or two words.

> --- runtime/mercury_region.c	7 Dec 2007 10:36:34 -0000	1.5
> +++ runtime/mercury_region.c	19 Dec 2007 16:06:25 -0000
> @@ -149,15 +149,14 @@
>      page = MR_region_get_free_page();
>  
>      /*
> -    ** In the first page we will store region information, which occupies
> -    ** word_sizeof(MR_Region) words from the start of the first page.
> +    ** In the first page, we will store the region header, which occupies
> +    ** word_sizeof(MR_Region) words from the start of the data area of the
> +    ** page.

I think we should call this structure the region header in the code as well
as in the paper. I am doing that change right now.

>      region = (MR_Region *) (page->MR_regionpage_space);
>      region->MR_region_next_available_word = (MR_Word *)
>          (page->MR_regionpage_space + word_sizeof(MR_Region));
>      region->MR_region_last_page = page;
> -    region->MR_region_available_space =
> -        MR_REGION_PAGE_SPACE_SIZE - word_sizeof(MR_Region);
>      region->MR_region_removal_counter = 1;
>      region->MR_region_sequence_number = MR_region_sequence_number++;
>      region->MR_region_logical_removed = 0;

>  /*
>  ** This method is to be called at the start of the then part of an ite with
>  ** semidet condition (most of the times).
> -** At that point we will only check if the region is disj-protected or not.
> +** XXX At that point we will only check if the region is disj-protected or not.
> +** At that point we do not have to check whether this ite-protected region is 
> +** disj-protected or not. It is because the region is protected for this ite
> +** only if it has not been protected before the ite and from the start of
> +** this ite to the point when this method is called, i.e., the condition, the
> +** region cannot be disj-protected by any disjunctions because this condition
> +** is semidet.
>  */

The idea of a more detailed comment is good, but I don't understand it;
the sentence structure is too complex

>  void
>  MR_remove_undisjprotected_region_ite_then_semidet(MR_Region *region)
>  {
> +    /*
>      MR_region_debug_try_remove_region(region);
>      if ( !MR_region_is_disj_protected(region) ) {
>          MR_region_destroy_region(region);
> @@ -293,6 +299,9 @@
>          region->MR_region_logical_removed = 1;
>          MR_region_debug_logically_remove_region(region);
>      }
> +    */
> +    MR_region_destroy_region(region);
> +    MR_region_debug_destroy_region(region);
>  }

Why comment out the code? If not needed now, you should delete it.
If you ever need to resurrect it, you can do so using the old versions
in CVS.


> +#define     MR_region_available_space(region_last_page, next_available_word)\
> +            ((region_last_page->MR_regionpage_space) +                      \
> +             MR_REGION_PAGE_SPACE_SIZE - next_available_word)               \

This parenthesization doesn't make the structure clear; I rewrote it.

> -                    protected_region->MR_region_ite_protected =             \
> -                        top_ite_frame->MR_riff_previous_ite_frame;          \
> +                    protected_region->MR_region_ite_protected = NULL;       \

This is because we don't re-protect previously protected regions, right?

The diff is otherwise fine. I will post my diff to mercury-reviews in a
minute for you to review after commit. If you find any problems with it,
you can commit a fix without a review.

I got no work done on the paper so far today, due to problems with the
trains here following a small storm, and a pile of admin stuff landing
on my desk. Tomorrow I will have to work on my talk for PADL 08. However,
I intend to work on section 4 as soon as it is done. The university will
shut down at the end of tomorrow for the christmas break, but I intend
to come in once or twice between the holidays to work on the paper.
I want to get the abstract finished before I leave for San Francisco
on Jan 2. The paper as a whole is I think already only about a week's worth
of concentrated work away from being submittable, and I expect to get it
significantly closer than that before Jan 2.

And now I must leave to do some christmas shopping. Happy holidays to you,
Gerda and your families.

Zoltan.
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------



More information about the reviews mailing list