[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