[m-rev.] for review: smaller stacks for parallel conjuncts
Peter Wang
wangp at students.csse.unimelb.edu.au
Fri Sep 29 12:59:03 AEST 2006
Estimated hours taken: 6
Branches: main
A common way to use parallel conjunction can cause a lot of Mercury contexts
to be allocated, e.g.
map([], []).
map([H0|T0], [H|T]) :-
( p(H0, H) % contains no parallel conjunctions
& map(T0, T)
).
When the left parallel conjunct completes, the engine that was executing it
must suspend the context in which it was run, waiting for the right conjunct
to finish. The engine is then idle and will attempt to find further work to
execute in a _new_ context. To avoid excessive memory consumption due to
contexts we currently limit the number of contexts we allocate. However,
that severely limits the parallelism we can exploit in this example (and
similar patterns of work distribution). There are a lot of contexts
allocated but most of them are simply suspended.
Assuming that most parallel conjuncts contain small sub-computations, we can
allow many contexts to be allocated without excessive memory consumption by
just giving them smaller stacks. This patch creates a simple variant of a
MR_Context structure which has smaller stacks than the initial MR_Context
structure and executes parallel conjuncts in the smaller contexts if
larger contexts are unavailable.
runtime/mercury_memory.c:
runtime/mercury_wrapper.c:
runtime/mercury_wrapper.h:
doc/user_guide.texi:
Add globals to hold the desired sizes of small det and nondet stacks.
Add `--small-detstack-size' and `--small-nondetstack-size'
options for the MERCURY_OPTIONS environment variable to set the
desired sizes.
runtime/mercury_context.h:
Add a MR_ctxt_size field to MR_Context to indicate whether it has
regular or small sized stacks.
runtime/mercury_context.c:
Add an argument to MR_create_context() specifying whether we want a
regular or small context.
Ask for small stacks when creating new contexts to begin execution
from a spark (i.e. parallel conjuncts).
Create a new free-list to hold unused small contexts.
runtime/mercury_thread.c:
extras/concurrency/spawn.m:
Match the interface change to MR_create_context(). We give the
initial context and contexts created due for explicit Mercury threads
regular-sized stacks.
Index: doc/user_guide.texi
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/doc/user_guide.texi,v
retrieving revision 1.493
diff -u -r1.493 user_guide.texi
--- doc/user_guide.texi 25 Sep 2006 08:00:38 -0000 1.493
+++ doc/user_guide.texi 28 Sep 2006 05:31:03 -0000
@@ -8537,6 +8537,36 @@
multiplied by the word size in bytes.
@sp 1
+ at item --small-detstack-size @var{size}
+ at findex --small-detstack-size (runtime option)
+Sets the size of the det stack used for executing parallel conjunctions
+to @var{size} kilobytes.
+The regular det stack size should be equal or greater to avoid surprises.
+
+ at sp 1
+ at item --small-detstack-size-kwords @var{size}
+ at findex --small-detstack-size-kwords (runtime option)
+Sets the size of the det stack used for executing parallel conjunctions
+to @var{size} kilobytes
+multiplied by the word size in bytes.
+The regular det stack size should be equal or greater to avoid surprises.
+
+ at sp 1
+ at item --small-nondetstack-size @var{size}
+ at findex --small-nondetstack-size (runtime option)
+Sets the size of the nondet stack for executing parallel computations
+to @var{size} kilobytes.
+The regular nondet stack size should be equal or greater to avoid surprises.
+
+ at sp 1
+ at item --small-nondetstack-size-kwords @var{size}
+ at findex --small-nondetstack-size-kwords (runtime option)
+Sets the size of the nondet stack for executing parallel computations
+to @var{size} kilobytes
+multiplied by the word size in bytes.
+The regular nondet stack size should be equal or greater to avoid surprises.
+
+ at sp 1
@item --solutions-heap-size @var{size}
@findex --solutions-heap-size (runtime option)
Sets the size of the solutions heap to @var{size} kilobytes.
Index: extras/concurrency/spawn.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/extras/concurrency/spawn.m,v
retrieving revision 1.16
diff -u -r1.16 spawn.m
--- extras/concurrency/spawn.m 26 Sep 2006 03:54:43 -0000 1.16
+++ extras/concurrency/spawn.m 28 Sep 2006 05:33:23 -0000
@@ -61,7 +61,7 @@
"
#ifndef MR_HIGHLEVEL_CODE
MR_Context *ctxt;
- ctxt = MR_create_context(""spawn"", NULL);
+ ctxt = MR_create_context(""spawn"", MR_CONTEXT_SIZE_REGULAR, NULL);
ctxt->MR_ctxt_resume = &&spawn_call_back_to_mercury_cc_multi;
/* Store the closure on the top of the new context's stack. */
*(ctxt->MR_ctxt_sp) = Goal;
Index: runtime/mercury_context.c
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_context.c,v
retrieving revision 1.48
diff -u -r1.48 mercury_context.c
--- runtime/mercury_context.c 26 Sep 2006 03:53:20 -0000 1.48
+++ runtime/mercury_context.c 28 Sep 2006 05:32:47 -0000
@@ -58,13 +58,13 @@
#endif
/*
-** free_context_list is a global linked list of unused context
-** structures. If the MR_MemoryZone pointers are not NULL,
-** then they point to allocated MR_MemoryZones, which will
-** need to be reinitialized, but have space allocated to
-** them. (see comments in mercury_memory.h about MR_reset_zone())
+** free_context_list and free_small_context_list are a global linked lists
+** of unused context structures, with regular and small stacks respectively.
+** If the MR_MemoryZone pointers are not NULL, then they point to allocated
+** MR_MemoryZones.
*/
static MR_Context *free_context_list = NULL;
+static MR_Context *free_small_context_list = NULL;
#ifdef MR_THREAD_SAFE
static MercuryLock free_context_list_lock;
#endif
@@ -106,6 +106,11 @@
MR_init_context_maybe_generator(MR_Context *c, const char *id,
MR_Generator *gen)
{
+ const char *detstack_name;
+ const char *nondstack_name;
+ size_t detstack_size;
+ size_t nondstack_size;
+
c->MR_ctxt_id = id;
c->MR_ctxt_next = NULL;
c->MR_ctxt_resume = NULL;
@@ -116,14 +121,29 @@
#ifndef MR_HIGHLEVEL_CODE
c->MR_ctxt_succip = MR_ENTRY(MR_do_not_reached);
+ switch (c->MR_ctxt_size) {
+ case MR_CONTEXT_SIZE_REGULAR:
+ detstack_name = "detstack";
+ nondstack_name = "nondetstack";
+ detstack_size = MR_detstack_size;
+ nondstack_size = MR_nondstack_size;
+ break;
+ case MR_CONTEXT_SIZE_SMALL:
+ detstack_name = "small_detstack";
+ nondstack_name = "small_nondetstack";
+ detstack_size = MR_small_detstack_size;
+ nondstack_size = MR_small_nondstack_size;
+ break;
+ }
+
if (c->MR_ctxt_detstack_zone == NULL) {
if (gen != NULL) {
c->MR_ctxt_detstack_zone = MR_create_zone("gen_detstack",
0, MR_gen_detstack_size, MR_next_offset(),
MR_gen_detstack_zone_size, MR_default_handler);
} else {
- c->MR_ctxt_detstack_zone = MR_create_zone("detstack",
- 0, MR_detstack_size, MR_next_offset(),
+ c->MR_ctxt_detstack_zone = MR_create_zone(detstack_name,
+ 0, detstack_size, MR_next_offset(),
MR_detstack_zone_size, MR_default_handler);
}
}
@@ -135,8 +155,8 @@
0, MR_gen_nonstack_size, MR_next_offset(),
MR_gen_nonstack_zone_size, MR_default_handler);
} else {
- c->MR_ctxt_nondetstack_zone = MR_create_zone("nondetstack",
- 0, MR_nondstack_size, MR_next_offset(),
+ c->MR_ctxt_nondetstack_zone = MR_create_zone(nondstack_name,
+ 0, nondstack_size, MR_next_offset(),
MR_nondstack_zone_size, MR_default_handler);
}
}
@@ -221,7 +241,7 @@
}
MR_Context *
-MR_create_context(const char *id, MR_Generator *gen)
+MR_create_context(const char *id, MR_ContextSize ctxt_size, MR_Generator *gen)
{
MR_Context *c;
@@ -229,9 +249,26 @@
MR_num_outstanding_contexts_and_sparks++;
- if (free_context_list == NULL) {
- MR_UNLOCK(&free_context_list_lock, "create_context i");
+ /*
+ ** We assume regular contexts have stacks at least as big as
+ ** small contexts, so we can return a regular context in place of
+ ** a small context if one is already available.
+ */
+ if (ctxt_size == MR_CONTEXT_SIZE_SMALL && free_small_context_list) {
+ c = free_small_context_list;
+ free_small_context_list = c->MR_ctxt_next;
+ } else if (free_context_list != NULL) {
+ c = free_context_list;
+ free_context_list = c->MR_ctxt_next;
+ } else {
+ c = NULL;
+ }
+
+ MR_UNLOCK(&free_context_list_lock, "create_context i");
+
+ if (c == NULL) {
c = MR_GC_NEW(MR_Context);
+ c->MR_ctxt_size = ctxt_size;
#ifndef MR_HIGHLEVEL_CODE
c->MR_ctxt_detstack_zone = NULL;
c->MR_ctxt_nondetstack_zone = NULL;
@@ -239,10 +276,6 @@
#ifdef MR_USE_TRAIL
c->MR_ctxt_trail_zone = NULL;
#endif
- } else {
- c = free_context_list;
- free_context_list = c->MR_ctxt_next;
- MR_UNLOCK(&free_context_list_lock, "create_context ii");
}
MR_init_context_maybe_generator(c, id, gen);
@@ -269,8 +302,17 @@
MR_LOCK(&free_context_list_lock, "destroy_context");
MR_num_outstanding_contexts_and_sparks--;
- c->MR_ctxt_next = free_context_list;
- free_context_list = c;
+
+ switch (c->MR_ctxt_size) {
+ case MR_CONTEXT_SIZE_REGULAR:
+ c->MR_ctxt_next = free_context_list;
+ free_context_list = c;
+ break;
+ case MR_CONTEXT_SIZE_SMALL:
+ c->MR_ctxt_next = free_small_context_list;
+ free_small_context_list = c;
+ break;
+ }
MR_UNLOCK(&free_context_list_lock, "destroy_context");
}
@@ -528,7 +570,8 @@
/* Grab a new context if we haven't got one then begin execution. */
if (MR_ENGINE(MR_eng_this_context) == NULL) {
- MR_ENGINE(MR_eng_this_context) = MR_create_context("from spark", NULL);
+ MR_ENGINE(MR_eng_this_context) = MR_create_context("from spark",
+ MR_CONTEXT_SIZE_SMALL, NULL);
MR_load_context(MR_ENGINE(MR_eng_this_context));
}
MR_parent_sp = spark->MR_spark_parent_sp;
Index: runtime/mercury_context.h
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_context.h,v
retrieving revision 1.31
diff -u -r1.31 mercury_context.h
--- runtime/mercury_context.h 26 Sep 2006 03:53:20 -0000 1.31
+++ runtime/mercury_context.h 28 Sep 2006 05:18:31 -0000
@@ -69,6 +69,13 @@
** id A string to identify the context for humans who want to
** debug the handling of contexts.
**
+** size Whether this context has regular-sized stacks or smaller
+** stacks. Some parallel programs can allocate many contexts
+** and most parallel computations should not require very
+** large stacks. We allocate contexts with "smaller" stacks
+** for parallel computations (although whether they are
+** actually smaller is up to the user).
+**
** next If this context is in the free-list `next' will point to
** the next free context. If this context is suspended waiting
** for a variable to become bound, `next' will point to the
@@ -119,8 +126,14 @@
typedef struct MR_Context_Struct MR_Context;
typedef struct MR_Spark_Struct MR_Spark;
+typedef enum {
+ MR_CONTEXT_SIZE_REGULAR,
+ MR_CONTEXT_SIZE_SMALL
+} MR_ContextSize;
+
struct MR_Context_Struct {
const char *MR_ctxt_id;
+ MR_ContextSize MR_ctxt_size;
MR_Context *MR_ctxt_next;
MR_Code *MR_ctxt_resume;
#ifdef MR_THREAD_SAFE
@@ -283,7 +296,8 @@
** Allocates and initializes a new context structure, and gives it the given
** id. If gen is non-NULL, the context is for the given generator.
*/
-extern MR_Context *MR_create_context(const char *id, MR_Generator *gen);
+extern MR_Context *MR_create_context(const char *id,
+ MR_ContextSize ctxt_size, MR_Generator *gen);
/*
** MR_destroy_context(context) returns the pointed-to context structure
Index: runtime/mercury_memory.c
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_memory.c,v
retrieving revision 1.37
diff -u -r1.37 mercury_memory.c
--- runtime/mercury_memory.c 12 Sep 2006 07:01:47 -0000 1.37
+++ runtime/mercury_memory.c 28 Sep 2006 02:50:42 -0000
@@ -162,10 +162,14 @@
#endif
MR_detstack_size = MR_round_up(MR_detstack_size * 1024,
MR_unit);
+ MR_small_detstack_size = MR_round_up(MR_small_detstack_size * 1024,
+ MR_unit);
MR_detstack_zone_size = MR_round_up(MR_detstack_zone_size * 1024,
MR_unit);
MR_nondstack_size = MR_round_up(MR_nondstack_size * 1024,
MR_unit);
+ MR_small_nondstack_size = MR_round_up(MR_small_nondstack_size * 1024,
+ MR_unit);
MR_nondstack_zone_size = MR_round_up(MR_nondstack_zone_size * 1024,
MR_unit);
#ifdef MR_USE_MINIMAL_MODEL_STACK_COPY
Index: runtime/mercury_thread.c
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_thread.c,v
retrieving revision 1.26
diff -u -r1.26 mercury_thread.c
--- runtime/mercury_thread.c 26 Sep 2006 03:53:22 -0000 1.26
+++ runtime/mercury_thread.c 28 Sep 2006 03:06:23 -0000
@@ -126,7 +126,8 @@
case MR_use_now :
if (MR_ENGINE(MR_eng_this_context) == NULL) {
MR_ENGINE(MR_eng_this_context) =
- MR_create_context("init_thread", NULL);
+ MR_create_context("init_thread",
+ MR_CONTEXT_SIZE_REGULAR, NULL);
}
MR_load_context(MR_ENGINE(MR_eng_this_context));
return MR_TRUE;
Index: runtime/mercury_wrapper.c
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_wrapper.c,v
retrieving revision 1.168
diff -u -r1.168 mercury_wrapper.c
--- runtime/mercury_wrapper.c 26 Sep 2006 03:53:21 -0000 1.168
+++ runtime/mercury_wrapper.c 28 Sep 2006 04:57:48 -0000
@@ -93,6 +93,8 @@
#endif
size_t MR_detstack_size = 1024 * sizeof(MR_Word);
size_t MR_nondstack_size = 64 * sizeof(MR_Word);
+size_t MR_small_detstack_size = 512 * sizeof(MR_Word);
+size_t MR_small_nondstack_size = 8 * sizeof(MR_Word);
size_t MR_solutions_heap_size = 256 * sizeof(MR_Word);
size_t MR_global_heap_size = 256 * sizeof(MR_Word);
size_t MR_trail_size = 32 * sizeof(MR_Word);
@@ -1004,6 +1006,10 @@
MR_DETSTACK_SIZE_KWORDS,
MR_NONDETSTACK_SIZE,
MR_NONDETSTACK_SIZE_KWORDS,
+ MR_SMALL_DETSTACK_SIZE,
+ MR_SMALL_DETSTACK_SIZE_KWORDS,
+ MR_SMALL_NONDETSTACK_SIZE,
+ MR_SMALL_NONDETSTACK_SIZE_KWORDS,
MR_SOLUTIONS_HEAP_SIZE,
MR_SOLUTIONS_HEAP_SIZE_KWORDS,
MR_TRAIL_SIZE,
@@ -1070,6 +1076,14 @@
{ "nondet-stack-size", 1, 0, MR_NONDETSTACK_SIZE },
{ "nondetstack-size-kwords", 1, 0, MR_NONDETSTACK_SIZE_KWORDS },
{ "nondet-stack-size-kwords", 1, 0, MR_NONDETSTACK_SIZE_KWORDS },
+ { "small-detstack-size", 1, 0, MR_SMALL_DETSTACK_SIZE },
+ { "small-det-stack-size", 1, 0, MR_SMALL_DETSTACK_SIZE },
+ { "small-detstack-size-kwords", 1, 0, MR_SMALL_DETSTACK_SIZE_KWORDS },
+ { "small-det-stack-size-kwords", 1, 0, MR_SMALL_DETSTACK_SIZE_KWORDS },
+ { "small-nondetstack-size", 1, 0, MR_SMALL_NONDETSTACK_SIZE },
+ { "small-nondet-stack-size", 1, 0, MR_SMALL_NONDETSTACK_SIZE },
+ { "small-nondetstack-size-kwords", 1, 0, MR_SMALL_NONDETSTACK_SIZE_KWORDS },
+ { "small-nondet-stack-size-kwords", 1, 0, MR_SMALL_NONDETSTACK_SIZE_KWORDS },
{ "solutions-heap-size", 1, 0, MR_SOLUTIONS_HEAP_SIZE },
{ "solutions-heap-size-kwords", 1, 0, MR_SOLUTIONS_HEAP_SIZE_KWORDS },
{ "trail-size", 1, 0, MR_TRAIL_SIZE },
@@ -1203,6 +1217,38 @@
MR_nondstack_size = size * sizeof(MR_Word);
break;
+ case MR_SMALL_DETSTACK_SIZE:
+ if (sscanf(MR_optarg, "%lu", &size) != 1) {
+ MR_usage();
+ }
+
+ MR_small_detstack_size = size;
+ break;
+
+ case MR_SMALL_DETSTACK_SIZE_KWORDS:
+ if (sscanf(MR_optarg, "%lu", &size) != 1) {
+ MR_usage();
+ }
+
+ MR_small_detstack_size = size * sizeof(MR_Word);
+ break;
+
+ case MR_SMALL_NONDETSTACK_SIZE:
+ if (sscanf(MR_optarg, "%lu", &size) != 1) {
+ MR_usage();
+ }
+
+ MR_small_nondstack_size = size;
+ break;
+
+ case MR_SMALL_NONDETSTACK_SIZE_KWORDS:
+ if (sscanf(MR_optarg, "%lu", &size) != 1) {
+ MR_usage();
+ }
+
+ MR_small_nondstack_size = size * sizeof(MR_Word);
+ break;
+
case MR_SOLUTIONS_HEAP_SIZE:
if (sscanf(MR_optarg, "%lu", &size) != 1) {
MR_usage();
Index: runtime/mercury_wrapper.h
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/runtime/mercury_wrapper.h,v
retrieving revision 1.75
diff -u -r1.75 mercury_wrapper.h
--- runtime/mercury_wrapper.h 26 Sep 2006 03:53:22 -0000 1.75
+++ runtime/mercury_wrapper.h 28 Sep 2006 02:48:47 -0000
@@ -195,6 +195,8 @@
extern size_t MR_heap_size;
extern size_t MR_detstack_size;
extern size_t MR_nondstack_size;
+extern size_t MR_small_detstack_size;
+extern size_t MR_small_nondstack_size;
extern size_t MR_solutions_heap_size;
extern size_t MR_trail_size;
extern size_t MR_global_heap_size;
--------------------------------------------------------------------------
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