[m-rev.] diff: Loop control review fixes.

Paul Bone pbone at csse.unimelb.edu.au
Tue Oct 4 14:19:21 AEDT 2011


This patch responds to Zoltan's review comments on one of my previous
patches.

---

Addressed Zoltan's review comments on the loop control primitives.

runtime/mercury_par_builtin.[ch]:
    Corrected some comments, cleaning up unclear prose and also correcting
    content.

    Use a hint for the next free slot in the loop control structure.  This will
    ensure that free slots are found more quickly.

    Corrected a case MR_fatal_error would have been called when there was no
    error.

Index: runtime/mercury_par_builtin.c
===================================================================
RCS file: /home/mercury1/repository/mercury/runtime/mercury_par_builtin.c,v
retrieving revision 1.5
diff -u -p -b -r1.5 mercury_par_builtin.c
--- runtime/mercury_par_builtin.c	27 Sep 2011 06:22:49 -0000	1.5
+++ runtime/mercury_par_builtin.c	4 Oct 2011 02:55:10 -0000
@@ -52,10 +52,10 @@ MR_lc_create(unsigned num_workers)
     for (i = 0; i < num_workers; i++) {
         /*
         ** We allocate contexts as necessary, so that we never allocate a
-        ** context we don't use. Also, by delaying the allocation of contexts,
-        ** all but the first may execute in parallel with one-another.
-        ** XXX I (zs) do not understand how the first half of the previous
-        ** sentence implies the seconf half; I don't think it does.
+        ** context we don't use.  Also, by allocating the contexts in
+        ** MR_lc_spawn_off, already spawned off computations can run in
+        ** parallel with the allocation of contexts for computations that are
+        ** about to be spawned off.
         */
         lc->MR_lc_slots[i].MR_lcs_context = NULL;
         lc->MR_lc_slots[i].MR_lcs_is_free = MR_TRUE;
@@ -64,6 +64,7 @@ MR_lc_create(unsigned num_workers)
     lc->MR_lc_master_context_lock = MR_US_LOCK_INITIAL_VALUE;
     lc->MR_lc_master_context = NULL;
     lc->MR_lc_finished = MR_FALSE;
+    lc->MR_lc_free_slot_hint = 0;
 
     return lc;
 }
@@ -77,14 +78,20 @@ MR_lc_try_get_free_slot(MR_LoopControl *
     if (lc->MR_lc_outstanding_workers == lc->MR_lc_num_slots) {
         return NULL;
     } else {
-        unsigned i;
+        unsigned hint, offset, i;
 
         /*
-        ** XXX Optimize this by using a hint to start the search at.
+        ** We start indexing into the array starting at this hint, it is either
+        ** set to a known free slot or the next unchecked slot after finding a
+        ** free slot.
         */
-        for (i = 0; i<lc->MR_lc_num_slots; i++) {
+        hint = lc->MR_lc_free_slot_hint;
+
+        for (offset = 0; offset < lc->MR_lc_num_slots; offset++) {
+            i = (hint + offset) % lc->MR_lc_num_slots;
             if (lc->MR_lc_slots[i].MR_lcs_is_free) {
                 lc->MR_lc_slots[i].MR_lcs_is_free = MR_FALSE;
+                lc->MR_lc_free_slot_hint = (i+1) % lc->MR_lc_num_slots;
                 MR_atomic_inc_int(&(lc->MR_lc_outstanding_workers));
                 return &(lc->MR_lc_slots[i]);
             }
@@ -99,7 +106,7 @@ MR_lc_spawn_off_func(MR_LoopControlSlot 
 {
     if (lcs->MR_lcs_context == NULL) {
         /*
-        ** We need a new context.
+        ** Allocate a new context.
         */
         lcs->MR_lcs_context = MR_create_context("Loop control",
             MR_CONTEXT_SIZE_FOR_LOOP_CONTROL_WORKER, NULL);
@@ -119,6 +126,8 @@ MR_lc_join(MR_LoopControl *lc, MR_LoopCo
     MR_Context  *wakeup_context;
 
     lcs->MR_lcs_is_free = MR_TRUE;
+    lc->MR_lc_free_slot_hint = (((MR_Word)lcs - (MR_Word)lc - sizeof(MR_LoopControl)) /
+        sizeof(MR_LoopControlSlot)) + 1;
     /* Ensure the slot is free before we perform the decrement. */
     MR_CPU_SFENCE;
     last_worker =
Index: runtime/mercury_par_builtin.h
===================================================================
RCS file: /home/mercury1/repository/mercury/runtime/mercury_par_builtin.h,v
retrieving revision 1.10
diff -u -p -b -r1.10 mercury_par_builtin.h
--- runtime/mercury_par_builtin.h	27 Sep 2011 06:22:49 -0000	1.10
+++ runtime/mercury_par_builtin.h	4 Oct 2011 02:55:10 -0000
@@ -313,6 +313,12 @@ struct MR_LoopControl_Struct
     MR_THREADSAFE_VOLATILE MR_bool          MR_lc_finished;
 
     /*
+    ** When a slot becomes free its index is stored here so that when a free
+    ** slot is requested the slot with this index is checked first.
+    */
+    unsigned                                MR_lc_free_slot_hint;
+
+    /*
     ** MR_lc_slots MUST be the last field, since in practice, we treat
     ** the array as having as many slots as we need, adding the size of
     ** all the elements except the first to sizeof(MR_LoopControl) when
@@ -410,7 +416,7 @@ extern MR_LoopControlSlot   *MR_lc_try_g
 */
 #define MR_lc_wait_free_slot(lc, lcs, retry_label)                          \
     do {                                                                    \
-        unsigned    i;                                                      \
+        unsigned    hint, offset, i;                                        \
                                                                             \
         if ((lc)->MR_lc_outstanding_workers == (lc)->MR_lc_num_slots) {     \
             MR_US_SPIN_LOCK(&((lc)->MR_lc_master_context_lock));            \
@@ -439,25 +445,20 @@ extern MR_LoopControlSlot   *MR_lc_try_g
             MR_US_UNLOCK(&((lc)->MR_lc_master_context_lock));               \
         }                                                                   \
                                                                             \
-        /*                                                                  \
-        ** XXX Optimize this by using a hint to start the search at.        \
-        */                                                                  \
-        for (i = 0; i<(lc)->MR_lc_num_slots; i++) {                         \
+        hint = (lc)->MR_lc_free_slot_hint;                                  \
+                                                                            \
+        for (offset = 0; offset < (lc)->MR_lc_num_slots; offset++) {        \
+            i = (hint + offset) % (lc)->MR_lc_num_slots;                    \
             if ((lc)->MR_lc_slots[i].MR_lcs_is_free) {                      \
                 (lc)->MR_lc_slots[i].MR_lcs_is_free = MR_FALSE;             \
+                (lc)->MR_lc_free_slot_hint =                                \
+                    (i + 1) % (lc)->MR_lc_free_slot_hint;                   \
                 MR_atomic_inc_int(&((lc)->MR_lc_outstanding_workers));      \
                 (lcs) = &((lc)->MR_lc_slots[i]);                            \
                 break;                                                      \
             }                                                               \
         }                                                                   \
                                                                             \
-        /*                                                                  \
-        ** Since only one context can ever run MR_lc_wait_free_slot then we \
-        ** can never fail to find a since outstanding workers can never be  \
-        ** incremented by another engine.                                   \
-        ** XXX This comment is so mangled it does not make sense.           \
-        */                                                                  \
-        MR_fatal_error("No free slot found in loop control");               \
     } while (0);
 
 /*
-------------- 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/20111004/3eae8ed5/attachment.sig>


More information about the reviews mailing list