[m-rev.] [reuse] diff: cell cache implementation

[Peter Ross]

Hi,


===================================================================


Estimated hours taken: 8
Branches: reuse

Add the option --cell-cache.  When this option is enabled, we store
compile time gc'd cells into a cell cache for possible reuse, before
allocating a new cell we check the cell cache for a cell of the suitable
size first.

compiler/ml_unify_gen.m:
    Fix a bug in ml_primary_tag.

compiler/mlds_to_c.m:
    Generate code which access the cell cache.
    
compiler/options.m:
    Add the --cell-cache option.

library/benchmarking.m:
runtime/mercury_memory.c:
runtime/mercury_memory.h:
    Protect calls to the cell cache statistics routines with 
    #ifdef PROFILE_MEMORY, so that we only collect the statistics when
    memory profiling is turned on.


Index: compiler/ml_unify_gen.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_unify_gen.m,v
retrieving revision 1.16.2.16
diff -u -r1.16.2.16 ml_unify_gen.m
--- compiler/ml_unify_gen.m	2001/03/19 11:59:46	1.16.2.16
+++ compiler/ml_unify_gen.m	2001/03/21 14:26:19
@@ -1452,7 +1452,7 @@
 ml_primary_tag(base_typeclass_info_constant(_, _, _)) = no.
 ml_primary_tag(tabling_pointer_constant(_, _)) = no.
 ml_primary_tag(no_tag) = no.
-ml_primary_tag(shared_local_tag(_, _)) = no.
+ml_primary_tag(shared_local_tag(PrimaryTag, _)) = yes(PrimaryTag).
 
 
 	% Given a type and a cons_id, and also the types of the actual
Index: compiler/mlds_to_c.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mlds_to_c.m,v
retrieving revision 1.55.2.11
diff -u -r1.55.2.11 mlds_to_c.m
--- compiler/mlds_to_c.m	2001/03/19 11:59:48	1.55.2.11
+++ compiler/mlds_to_c.m	2001/03/21 14:26:21
@@ -2391,12 +2391,17 @@
 	% heap management
 	%
 mlds_output_atomic_stmt(Indent, _FuncInfo, delete_object(Rval, Size), _) -->
-	mlds_indent(Indent),
-	io__write_string("MR_compile_time_gc("),
-	mlds_output_rval(Rval),
-	io__write_string(", "),
-	io__write_int(Size),
-	io__write_string(");\n").
+	globals__io_lookup_bool_option(cell_cache, CellCache),
+	( { CellCache = yes } ->
+		mlds_indent(Indent),
+		io__write_string("MR_compile_time_gc("),
+		mlds_output_rval(Rval),
+		io__write_string(", "),
+		io__write_int(Size),
+		io__write_string(");\n")
+	;
+		[]
+	).
 
 mlds_output_atomic_stmt(Indent, FuncInfo, NewObject, Context) -->
 	{ NewObject = new_object(Target, MaybeTag, Type, MaybeSize,
@@ -2404,53 +2409,52 @@
 	mlds_indent(Indent),
 	io__write_string("{\n"),
 
-	mlds_indent(Context, Indent + 1),
-	io__write_string("MR_update_cell_cache_statistics("),
-	( { MaybeSize = yes(LSize) } ->
-		mlds_output_rval(LSize)
+	{ MaybeSize = yes(Size0) ->
+		Size = Size0
 	;
 		% XXX what should we do here?
-		io__write_int(-1)
-	),
-	io__write_string(");\n"),
+		Size = const(int_const(-1))
+	},
 
 	{ FuncInfo = func_info(FuncName, _) },
 	mlds_maybe_output_heap_profile_instr(Context, Indent + 1, Args,
 			FuncName, MaybeCtorName),
+
+	globals__io_lookup_bool_option(cell_cache, CellCache),
+
+	( { CellCache = yes } ->
+		mlds_indent(Context, Indent + 1),
+		mlds_output_lval(Target),
+		io__write_string(" = MR_check_cell_cache("),
+		mlds_output_rval(Size),
+		io__write_string(");\n"),
+
+		mlds_indent(Context, Indent + 1),
+		io__write_string("if ("),
+		mlds_output_lval(Target),
+		io__write_string(" == (MR_Word) NULL) {\n"),
+
+		{ NewIndent = Indent + 2 }
+	;
+		{ NewIndent = Indent + 1 }
+	),
 
-	mlds_indent(Context, Indent + 1),
+	mlds_indent(Context, NewIndent),
 	mlds_output_lval(Target),
 	io__write_string(" = "),
-	( { MaybeTag = yes(Tag0) } ->
-		{ Tag = Tag0 },
-		mlds_output_cast(Type),
-		io__write_string("MR_mkword("),
-		mlds_output_tag(Tag),
-		io__write_string(", "),
-		{ EndMkword = ")" }
-	;
-		{ Tag = 0 },
+
 		%
 		% XXX we shouldn't need the cast here,
 		% but currently the type that we include
 		% in the call to MR_new_object() is not
 		% always correct.
 		%
-		mlds_output_cast(Type),
-		{ EndMkword = "" }
-	),
+	mlds_output_cast(Type),
 	io__write_string("MR_new_object("),
 	mlds_output_type(Type),
-	io__write_string(", "),
-	( { MaybeSize = yes(Size) } ->
-		io__write_string("("),
-		mlds_output_rval(Size),
-		io__write_string(" * sizeof(MR_Word))")
-	;
-		% XXX what should we do here?
-		io__write_int(-1)
-	),
-	io__write_string(", "),
+	io__write_string(", ("),
+	mlds_output_rval(Size),
+	io__write_string("* sizeof(MR_Word)), "),
 	( { MaybeCtorName = yes(QualifiedCtorId) } ->
 		io__write_char('"'),
 		{ QualifiedCtorId = qual(_ModuleName, CtorDefn) },
@@ -2459,10 +2463,30 @@
 		io__write_char('"')
 	;
 		io__write_string("NULL")
+	),
+	io__write_string(");\n"),
+
+	( { CellCache = yes } ->
+		mlds_indent(Context, Indent + 1),
+		io__write_string("}\n")
+	;
+		[]
+	),
+
+	( { MaybeTag = yes(Tag0) } ->
+		{ Tag = Tag0 },
+		mlds_indent(Context, Indent + 1),
+		mlds_output_lval(Target),
+		io__write_string(" = "),
+		mlds_output_cast(Type),
+		io__write_string("MR_mkword("),
+		mlds_output_tag(Tag),
+		io__write_string(", "),
+		mlds_output_lval(Target),
+		io__write_string(");\n")
+	;
+		{ Tag = 0 }
 	),
-	io__write_string(")"),
-	io__write_string(EndMkword),
-	io__write_string(";\n"),
 	mlds_output_init_args(Args, ArgTypes, Context, 0, Target, Tag,
 		Indent + 1),
 	mlds_indent(Context, Indent),
Index: compiler/options.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/options.m,v
retrieving revision 1.288.2.11
diff -u -r1.288.2.11 options.m
--- compiler/options.m	2001/03/20 17:34:45	1.288.2.11
+++ compiler/options.m	2001/03/21 14:26:23
@@ -360,6 +360,7 @@
 		;	structure_reuse_constraint
 		;	structure_reuse_constraint_arg
 		;	structure_reuse_selection
+		;	cell_cache
 		; 	possible_alias_widening
 	%	- HLDS->LLDS
 		;	smart_indexing
@@ -550,6 +551,7 @@
 	infer_modes		-	bool(no),
 	infer_possible_aliases  - 	bool(no),
 	infer_structure_reuse   - 	bool(no),
+	cell_cache		-	bool(no),
 	infer_det		-	bool(yes),
 	infer_all		-	bool_special,
 	type_inference_iteration_limit	-	int(60),
@@ -974,6 +976,7 @@
 long_option("infer-modes",		infer_modes).
 long_option("infer-possible-aliases",	infer_possible_aliases).
 long_option("infer-structure-reuse",	infer_structure_reuse).
+long_option("cell-cache",		cell_cache).
 long_option("infer-determinism",	infer_det).
 long_option("infer-det",		infer_det).
 long_option("type-inference-iteration-limit",
@@ -1914,6 +1917,10 @@
 		"--structure-reuse-selection",
 		"\tStrategy to decide which of the possible cells available",
 		"\tfor reuse is reused.  Currently lifo or random.",
+
+		"--cell-cache",
+		"\tTurn on a cache of compile time garbage collected cells.",
+		"\tThis cache will be checked before allocating new memory.",
 
 		"--pa-widening, --possible-alias-widening <n>", 
 		"\tEnable widening when deriving possible aliases.",
Index: library/benchmarking.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/benchmarking.m,v
retrieving revision 1.34.4.4
diff -u -r1.34.4.4 benchmarking.m
--- library/benchmarking.m	2001/03/19 06:28:14	1.34.4.4
+++ library/benchmarking.m	2001/03/21 14:26:26
@@ -257,12 +257,12 @@
 		ML_overall_counter.words_at_period_end
 	);
 
-#endif /* PROFILE_MEMORY */
-
 	/*
 	** Cell cache statistics.
 	*/
 	MR_output_cell_cache_stats();
+
+#endif /* PROFILE_MEMORY */
 
 	fprintf(stderr, ""]\\n"");
 }
Index: runtime/mercury_memory.c
===================================================================
RCS file: /home/mercury1/repository/mercury/runtime/mercury_memory.c,v
retrieving revision 1.19.4.5
diff -u -r1.19.4.5 mercury_memory.c
--- runtime/mercury_memory.c	2001/03/19 06:28:18	1.19.4.5
+++ runtime/mercury_memory.c	2001/03/21 14:26:27
@@ -367,33 +367,70 @@
 
 /*
 ** Compile time garbage collection code.
-** Currently this just records statistics.
 */
-#define MR_MAX_CACHED_CELL_SIZE		10
+#define MR_MAX_CACHE_SIZE		10
+#define MR_CACHE_ENTRIES		10
 
-typedef struct s_cell_cache_stats
-{
+static MR_Word 		MR_cell_cache[MR_MAX_CACHE_SIZE + 1][MR_CACHE_ENTRIES];
+static int 		MR_cell_cache_index[MR_MAX_CACHE_SIZE + 1];
+
+#ifdef PROFILE_MEMORY
+  typedef struct s_cell_cache_stats
+  {
 	int	length;
 	int 	hits;
 	int	misses;
 	int	sum_length;
 	int	max_length;
-} cell_cache_stats;
+  } cell_cache_stats;
 
-static cell_cache_stats stats[MR_MAX_CACHED_CELL_SIZE + 1];
+  static cell_cache_stats stats[MR_MAX_CACHE_SIZE + 1];
 
-void record_stats(size_t size);
+  void MR_update_cell_cache_statistics(size_t size);
+  void record_stats(size_t size);
+#endif
 
 void MR_compile_time_gc(MR_Word cell, size_t size)
 {
-	if (size <= MR_MAX_CACHED_CELL_SIZE) {
+	if (size <= MR_MAX_CACHE_SIZE) {
+		int ind = (MR_cell_cache_index[size] + 1) % MR_CACHE_ENTRIES;
+
+#ifdef PROFILE_MEMORY
 		record_stats(size);
+#endif
+		MR_cell_cache[size][ind] = cell;
+		MR_cell_cache_index[size] = ind;
 	}
 }
 
-void MR_update_cell_cache_statistics(size_t size)
+MR_Word MR_check_cell_cache(size_t size)
 {
-	if (size <= MR_MAX_CACHED_CELL_SIZE) {
+	MR_Word cell;
+
+#ifdef PROFILE_MEMORY
+	MR_update_cell_cache_statistics(size);
+#endif
+
+	if (size > MR_MAX_CACHE_SIZE) {
+		return (MR_Word) NULL;
+	} else {
+		int ind = MR_cell_cache_index[size];
+		cell = MR_cell_cache[size][ind];
+
+		if (ind == 0) {
+			MR_cell_cache_index[size] = MR_CACHE_ENTRIES - 1;
+		} else {
+			MR_cell_cache_index[size] = ind - 1;
+		}
+
+		return cell;
+	}
+}
+
+#ifdef PROFILE_MEMORY
+  void MR_update_cell_cache_statistics(size_t size)
+  {
+	if (size <= MR_MAX_CACHE_SIZE) {
 		stats[size].sum_length += stats[size].length;
 
 		if (stats[size].length == 0) {
@@ -403,26 +440,26 @@
 			stats[size].hits++;
 		}
 	}
-}
+  }
 
-void record_stats(size_t size)
-{
+  void record_stats(size_t size)
+  {
 	stats[size].length++;
 
 	if (stats[size].length > stats[size].max_length) {
 		stats[size].max_length = stats[size].length;
 	}
-}
+  }
 
-void MR_output_cell_cache_stats(void)
-{
+  void MR_output_cell_cache_stats(void)
+  {
 	int i = 0;
 	int hits, misses, total, sum_length, max_length;
 	float hit_proportion, average_cache_length;
 
 	printf("\n\n%6s %6s %6s %7s %7s %6s\n", "size", "avg",
 			"max", "hits", "total", "%");
-	for (i = 1; i <= MR_MAX_CACHED_CELL_SIZE; i++)
+	for (i = 1; i <= MR_MAX_CACHE_SIZE; i++)
 	{
 		hits = stats[i].hits;
 		misses = stats[i].misses;
@@ -441,6 +478,7 @@
 				average_cache_length, max_length,
 				hits, total, 100 * hit_proportion);
 	}
-}
+  }
+#endif /* PROFILE_MEMORY */
 
 /*---------------------------------------------------------------------------*/
Index: runtime/mercury_memory.h
===================================================================
RCS file: /home/mercury1/repository/mercury/runtime/mercury_memory.h,v
retrieving revision 1.12.2.3
diff -u -r1.12.2.3 mercury_memory.h
--- runtime/mercury_memory.h	2001/03/19 06:28:18	1.12.2.3
+++ runtime/mercury_memory.h	2001/03/21 14:26:28
@@ -190,8 +190,11 @@
 /*---------------------------------------------------------------------------*/
 
 void MR_compile_time_gc(MR_Word cell, size_t size);
-void MR_update_cell_cache_statistics(size_t size);
-void MR_output_cell_cache_stats(void);
+MR_Word MR_check_cell_cache(size_t size);
+
+#ifdef PROFILE_MEMORY
+  void MR_output_cell_cache_stats(void);
+#endif
 
 /*---------------------------------------------------------------------------*/
 

--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------