[m-dev.] FYI: cell cache

[Peter Ross]

Hi,

I don't intend to check this in as it is a very quick and dirty hack for
testing an idea of mine.

Any comments about the idea appreciated.
Any comments about the code are pretty worthless because I don't intend
to implement the idea this way anyway.

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


Estimated hours taken: 16

Use the compile time garbage collection information to implement a
memory cell cache.

The idea behind the cell cache is that when a cell dies we add the
pointer to the cell the cell cache (possibly throwing away an old
pointer at the same time, it is a cache not a free list).  When we next
allocate memory we first check the cell cache to see if it has something
of the correct size, if so we use that pointer instead.

io__read_word_2 is an example of a bit of code that should benefit from
the cell cache.  Each call to read_char creates an ok/1 cell, which is
promptly consumed and become dead.  The cell cache allows the same cell
for ok/1 to be reused in the next call to io__read_char.

This optimization provides about a 5% speed up on a simplified version
of io__read_word_2.

compiler/ml_unify_gen.m:
    For each compile time garbage collectable variable add it to the
    cell cache.
    
compiler/mlds_to_c.m:
    Check the cell cache for an object of the correct size before
    allocating some memory for a new object.

runtime/mercury_memory.c:
runtime/mercury_memory.h:
    Routines to initialise and access the cell cache.

runtime/mercury_wrapper.c:
    Initialise the cell cache.


Index: compiler/ml_unify_gen.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/ml_unify_gen.m,v
retrieving revision 1.16.2.3
diff -u -r1.16.2.3 ml_unify_gen.m
--- compiler/ml_unify_gen.m	2000/09/27 14:59:50	1.16.2.3
+++ compiler/ml_unify_gen.m	2000/09/28 14:11:02
@@ -134,20 +134,34 @@
 	},
 	ml_gen_construct(Var, ConsId, Args, ArgModes, HowToConstruct, Context,
 		MLDS_Decls, MLDS_Statements).
-ml_gen_unification(deconstruct(Var, ConsId, Args, ArgModes, CanFail, _CanCGC),
+ml_gen_unification(deconstruct(Var, ConsId, Args, ArgModes, CanFail, CanCGC),
 		CodeModel, Context, MLDS_Decls, MLDS_Statements) -->
 	(
 		{ CanFail = can_fail },
 		{ require(unify(CodeModel, model_semi),
 			"ml_code_gen: can_fail deconstruct not semidet") },
 		ml_gen_semi_deconstruct(Var, ConsId, Args, ArgModes, Context,
-			MLDS_Decls, MLDS_Statements)
+			MLDS_Decls, MLDS_StatementsA)
 	;
 		{ CanFail = cannot_fail },
 		{ require(unify(CodeModel, model_det),
 			"ml_code_gen: cannot_fail deconstruct not det") },
 		ml_gen_det_deconstruct(Var, ConsId, Args, ArgModes, Context,
-			MLDS_Decls, MLDS_Statements)
+			MLDS_Decls, MLDS_StatementsA)
+	),
+	( { CanCGC = yes } ->
+		ml_gen_var(Var, VarLval),
+		{ String = string__format("MR_cache_cell(%d, MR_strip_tag(",
+				[i(list__length(Args))]) },
+		{ TargetCode = [raw_target_code(String),
+				target_code_input(lval(VarLval)),
+				raw_target_code("));\n")] },
+		{ Stmt = mlds__statement(
+				atomic(target_code(lang_C, TargetCode)),
+				mlds__make_context(Context)) },
+		{ MLDS_Statements = MLDS_StatementsA `list__append` [ Stmt ] }
+	;
+		{ MLDS_Statements = MLDS_StatementsA }
 	).
 
 ml_gen_unification(complicated_unify(_, _, _), _, _, [], []) -->
Index: compiler/mlds_to_c.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/mlds_to_c.m,v
retrieving revision 1.55.2.1
diff -u -r1.55.2.1 mlds_to_c.m
--- compiler/mlds_to_c.m	2000/09/25 17:03:57	1.55.2.1
+++ compiler/mlds_to_c.m	2000/09/28 14:11:06
@@ -2201,6 +2201,17 @@
 
 	mlds_indent(Context, Indent + 1),
 	mlds_output_lval(Target),
+	io__write_string(" = MR_get_cached_cell("),
+	io__write_int(list__length(Args)),
+	io__write_string(");\n"),
+
+	mlds_indent(Context, Indent + 1),
+	io__write_string("if ("),
+	mlds_output_lval(Target),
+	io__write_string(" == (MR_Word) NULL) {\n"),
+
+	mlds_indent(Context, Indent + 2),
+	mlds_output_lval(Target),
 	io__write_string(" = "),
 	( { MaybeTag = yes(Tag0) } ->
 		{ Tag = Tag0 },
@@ -2244,6 +2255,10 @@
 	io__write_string(")"),
 	io__write_string(EndMkword),
 	io__write_string(";\n"),
+
+	mlds_indent(Context, Indent + 1),
+	io__write_string("}\n"),
+
 	mlds_output_init_args(Args, ArgTypes, Context, 0, Target, Tag,
 		Indent + 1),
 	mlds_indent(Context, Indent),
Index: runtime/mercury_memory.c
===================================================================
RCS file: /home/mercury1/repository/mercury/runtime/mercury_memory.c,v
retrieving revision 1.19.4.1
diff -u -r1.19.4.1 mercury_memory.c
--- runtime/mercury_memory.c	2000/09/25 17:09:11	1.19.4.1
+++ runtime/mercury_memory.c	2000/09/28 14:11:12
@@ -330,3 +330,77 @@
 }
 
 /*---------------------------------------------------------------------------*/
+
+/*
+** Compile time garbage collection cache.
+** When structure reuse infers that a cell dies and is available for reuse,
+** we insert it into a cache of cells available for reuse.  When allocating
+** new memory first check if there is a cell already in the cache of the
+** correct size and use that saving the cost of the GC.
+**
+** For an example of when this cache should be a win, just look at the
+** following very common code.
+**	
+**	io__read_char(Result),
+**	{
+**		Result => ok(Char) % the ok(_) cell dies.
+**		...,
+**	;	
+**		Result => eof,
+**		...
+**	...
+**	}
+**
+** The ok(_) cell is very short lived being generated inside
+** io__read_char and almost always immediately dieing, now imagine if we
+** read a few characters in a row, we are going to need to create a new
+** ok(_) cell for the next character however there is already one in the
+** cache and hey presto we have a win!
+*/
+#define MR_MAX_CACHED_CELL_SIZE	10
+static void *MR_cell_cache[MR_MAX_CACHED_CELL_SIZE+1];
+
+void
+MR_cell_cache_init(void)
+{
+	int i;
+
+	for(i = 0; i <= MR_MAX_CACHED_CELL_SIZE; i++) {
+		MR_cell_cache[i] = (MR_Word) NULL;
+	}
+}
+
+void *
+MR_get_cached_cell(size_t size)
+{
+	void *cell;
+
+	/* 
+	** We never have to worry about the garbage collector freeing
+	** the cached blocks because there is always at least one reference
+	** to the cell from the cache!
+	*/
+	if (size > MR_MAX_CACHED_CELL_SIZE) {
+		return (MR_Word) NULL;
+	} else {
+		cell = MR_cell_cache[size];
+		MR_cell_cache[size] = (MR_Word) NULL;
+		return cell;
+	}
+}
+
+/*
+** Whenever a cell becomes available for compile time garbage
+** collection, insert it into the cache of cells available for
+** reuse.
+**
+** XXX Would it be better to first check if the cache is empty?
+*/
+void MR_cache_cell(size_t size, void *cell)
+{
+	if (size <= MR_MAX_CACHED_CELL_SIZE) {
+		MR_cell_cache[size] = cell;
+	}
+}
+
+/*---------------------------------------------------------------------------*/
Index: runtime/mercury_memory.h
===================================================================
RCS file: /home/mercury1/repository/mercury/runtime/mercury_memory.h,v
retrieving revision 1.12
diff -u -r1.12 mercury_memory.h
--- runtime/mercury_memory.h	2000/08/03 06:18:49	1.12
+++ runtime/mercury_memory.h	2000/09/28 14:11:12
@@ -171,4 +171,13 @@
 
 /*---------------------------------------------------------------------------*/
 
+/*
+** Memory cell cache functions.
+*/
+void MR_cell_cache_init(void);
+void *MR_get_cached_cell(size_t size);
+void MR_cache_cell(size_t size, void *cell);
+
+/*---------------------------------------------------------------------------*/
+
 #endif /* not MERCURY_MEMORY_H */
Index: runtime/mercury_wrapper.c
===================================================================
RCS file: /home/mercury1/repository/mercury/runtime/mercury_wrapper.c,v
retrieving revision 1.70.2.1
diff -u -r1.70.2.1 mercury_wrapper.c
--- runtime/mercury_wrapper.c	2000/09/25 17:09:35	1.70.2.1
+++ runtime/mercury_wrapper.c	2000/09/28 14:11:15
@@ -956,6 +956,7 @@
 
 	for (repcounter = 0; repcounter < repeats; repcounter++) {
 #ifdef MR_HIGHLEVEL_CODE
+		MR_cell_cache_init();
 		do_interpreter();
 #else
 		debugmsg0("About to call engine\n");

--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------