[m-dev.] Tabling [3/3]

[Fergus Henderson]

On 09-Mar-1998, Oliver Hutchison <ohutch at students.cs.mu.oz.au> wrote:
> New File: compiler/table_gen.m
> % Copyright (C) 1996-1998 

Has it really been that long? ;-)

> %	Given the following code for left recursive transitive closure :
> %	
> %	:- pred p(int, int).
> %	:- mode p(in, out) is nondet 
> %
> %	p(A, B) :- e(A, B).
> %	p(A, B) :- p(A, C), e(C, B).
> %	
> %	The transformed code would be :
> %
> %
> %	p(A, B) :-
> %			% Code to get a handle on the table
> %		c_code("
> %			static Word Table = 0;
> %			T0 = &Table;
> %		"),

`T0' here is an undeclared variable.

> table_gen__process_proc(EvalMethod, PredId, ProcId, ProcInfo0, PredInfo0, 
> 		Module0, Module) :-
> 	% grab the appropriate fields from the pred_info and proc_info
> 	pred_info_name(PredInfo, _PredName),
> 	proc_info_interface_code_model(ProcInfo0, CodeModel),
> 	proc_info_headvars(ProcInfo0, HeadVars),
> 	proc_info_varset(ProcInfo0, VarSet0),
> 	proc_info_vartypes(ProcInfo0, VarTypes0),
> 	proc_info_goal(ProcInfo0, OrigGoal),
> 	proc_info_argmodes(ProcInfo0, ArgModes),
> 
> 	(
> 		CodeModel = model_det
> 	->
> 		table_gen__create_new_det_goal(EvalMethod, OrigGoal, 
> 			Module0, HeadVars, ArgModes, VarTypes0, VarTypes, 
> 			VarSet0, VarSet, Goal)
> 	;
> 		CodeModel = model_semi
> 	->
> 		table_gen__create_new_semi_goal(EvalMethod, OrigGoal, 
> 			Module0, HeadVars, ArgModes, VarTypes0, VarTypes, 
> 			VarSet0, VarSet, Goal)
> 	;
> 		CodeModel = model_non
> 	->
> 		table_gen__create_new_non_goal(EvalMethod, OrigGoal, 
> 			Module0, HeadVars, ArgModes, VarTypes0, VarTypes, 
> 			VarSet0, VarSet, Goal)
> 	;
> 		error(
>     "table_gen__process_proc: unsupported code model for tabled pred/func")
> 	),

Better to use a switch rather than an if-then-else.
Then there's no need for the call to error/1.

> 		%
> 		% Transform deteministic procedures.
> 		%
> :- pred table_gen__create_new_det_goal(eval_method, hlds_goal, module_info, 

s/deteministic/deterministic/

If recent experience is anything to go on,
that word sure is hard to spell ;-)

> table_gen__create_new_non_goal(EvalMethod, OrigGoal, Module, HeadVars, 
> 		HeadVarModes, VarTypes0, VarTypes, VarSet0, VarSet, Goal) :-
> 	map__init(StoreMap),
> 	(
> 		EvalMethod = eval_memo
> 	->
> 		WorkingOnAnsGoal = SuspendGoal
> 	;
> 		EvalMethod = eval_minimal
> 	->
> 		WorkingOnAnsGoal = FailGoal
> 	;
> 		error(
>     "table_gen__create_new_non_goal: unsupported evaluation model")
> 	),

Why isn't eval_loopcheck supported here?

> generate_get_table_goals(VarTypes0, VarTypes, VarSet0, VarSet, Module, 
> 		TableVar, Goal) :-
> 	generate_new_table_var(VarTypes0, VarTypes, VarSet0, VarSet, 
> 		TableVar),
> 		
> 	module_info_get_predicate_table(Module, PredTable),
> 	(
> 		predicate_table_search_pred_m_n_a(PredTable,
> 			"mercury_builtin", "get_table", 1, [PredId0])

This will need to change when you merge in my recent changes...

> 		error(
> 		    "to many modes for predicate mercury_builtin:get_table/1")

s/to/too/

> 	GoalEx = pragma_c_code(will_not_call_mercury, PredId, ProcId,
> 			[TableVar], [yes("TableVar" - TableVarMode)], 
> 			[TableVarType], ordinary( 
> "	{
> 		static Word Table = 0;
> 		TableVar = (Word)&Table;
> 	}
> ", 
> 		no)), 

Declaring a static variable inside the code for a
`pragma c_code' predicate is dangerous.
At very least you need to mark the predicate with
`pragma no_inline'.

> gen_lookup_call_for_type(TypeCat, Type, TableVar, ArgVar, Module, VarTypes0,
> 		VarTypes, VarSet0, VarSet, NextTableVar, Goal) :-
> 	(
> 		TypeCat = pred_type
> 	->
> 		error("gen_lookup_call_for_type: pred types not supported")

Hmm, ideally this should be checked for at an earlier stage,
with an appropriate error message issued.  Is it?
You should include a test case for this in tests/invalid.

...
> 				error(
>     "gen_lookup_call_for_type: unsuported type in tabled predicte/function")

s/unsuported/unsupported/
s/predicte/predicate/

> New File: runtime/mercury_table_any.c

The code here seems to be very similar to the code for something
else (ML_expand(), I think).  You should put comments in both
places saying that if you modify one then you may need to modify
the other.

> static Word get_base_type_layout_entry(Word data, Word *type_info);
> static Word * make_type_info(Word *term_type_info, Word *arg_pseudo_type_info,
> 	bool *allocated);
... [200 lines later] ...
> Word 
> get_base_type_layout_entry(Word data_tag, Word *type_info)
...
> Word *
> make_type_info(Word *term_type_info, Word *arg_pseudo_type_info,
> 	bool *allocated) 

It would be helpful to the reader to include `static' on the
definitions, not just the declarations.

But actually, aren't those routines exactly the same as the ones
of the same name somewhere else?  If so, you should make them
`extern' rather than `static' and just define them in only one place.

> New File: runtime/mercury_table_any.h
> ===================================================================
> #ifndef _MERCURY_TABLE_ANY_H
> #define _MERCURY_TABLE_ANY_H
> 
> Word ** mercury_table_type(Word *type_info, Word data_value, 
>     Word ** Table);

The usual prefix for things in the runtime is `MR_', not `mercury_'.

The header file should document what the function does.

> New File: runtime/mercury_table_enum.h
> ===================================================================
> #ifndef _MERCURY_TABLE_ENUM_H
> #define _MERCURY_TABLE_ENUM_H
> 
> Word ** int_index_lookup_or_add(Word **, Integer, Integer);

Needs an MR_ prefix, and should be documented.

> typedef struct {
> 	Word Key;
> 	Word * Data;
> } TableNode;
> 
> typedef struct {
> 	Word Size;
> 	Word UsedElements;
> 	Word Elements;
> } TableRoot;

Struct fields should be lower-case.

> static Word next_prime(Word);
> static Word * create_hash_table(Word);
> static void re_hash(Word *, Word, TableNode * Node);
> 
> /*
>  *  Prime numbers which are close to powers of 2.  Used for choosing
>  *  the next size for a hash table.
>  */
> 
> #define NUM_OF_PRIMES 16
> static Word primes[NUM_OF_PRIMES] =
>     {127, 257, 509, 1021, 2053, 4099, 8191, 16381, 32771, 65537, 131071,
>        262147, 524287, 1048573, 2097143, 4194301};

This list should probably be a little bit longer.
It's possible that someone might want a table bigger than 42M entries.
I suggest you go up to 4G.

Uh, never mind -- I see that you do something reasonable even if you
get past the end of the table.

> /* Create a new empty hash table */
> static Word * 
> create_hash_table(Word TableSize)

Function arguments should be lower-case.

> {
>    	Word i;
> 	TableRoot * Table =
> 		table_allocate(sizeof(Word)*2+TableSize*sizeof(TableNode *));

Some whitespace between operators please:
	s/*/ * /
	s/+/ + /

> 	/* Rehash the table if it has grown to full */
> 	if ((float)ELEMENTS(Table) / (float)SIZE(Table) > MAX_EL_SIZE_RATIO) {

s/(float)/(float) /g

> 	/* Rehash the table if it has grown to full */
> 	if ((float)ELEMENTS(Table) / (float)SIZE(Table) > MAX_EL_SIZE_RATIO) {

Ditto.

I detect some duplicate code there around that part;
you should abstract it out into a subroutine.

> New File: runtime/mercury_table_int_float_string.h
> ===================================================================
> #ifndef _MERCURY_INT_FLOAT_STRING_H
> #define _MERCURY_INT_FLOAT_STRING_H
> 
> Word ** int_hash_lookup_or_add(Word ** Table, Integer Key);
> Word ** float_hash_lookup_or_add(Word ** Table, Float Key);
> Word ** string_hash_lookup_or_add(Word ** Table, String Key);

Need MR_ prefixes and documentation.

> void
> table_dump_profile()
> {

s/()/(void)/

> 	printf("	Profilng stats for table operation\n");
> 	
> 	printf(" Number of calls to TableHasFailed = %d \n",
> 		(int) MR_Table_Prof_HasFailed_Call); 
> 	printf(" Number of calls to TableCreateAnsBlock = %d \n",
> 		(int) MR_Table_Prof_CreateAnsBlock_Call); 
> 	printf(" Number of calls to TableSaveIntAns = %d \n",
> 		(int) MR_Table_Prof_SaveIntAns_Call); 
> 	printf(" Number of calls to TableSaveCharAns = %d \n",
> 		(int) MR_Table_Prof_SaveCharAns_Call); 
> 	printf(" Number of calls to TableSaveStringAns = %d \n",
> 		(int) MR_Table_Prof_SaveStringAns_Call); 
> 	printf(" Number of calls to TableSaveFloatAns = %d \n",
> 		(int) MR_Table_Prof_SaveFloatAns_Call); 
> 	printf(" Number of calls to TableSaveAnyAns = %d \n",
> 		(int) MR_Table_Prof_SaveAnyAns_Call); 
> 	printf(" Number of calls to TableSaveFailure = %d \n",
> 		(int) MR_Table_Prof_SaveFailure_Call); 
> 	printf(" Number of calls to TableRestoreInt = %d \n",
> 		(int) MR_Table_Prof_RestoreInt_Call); 
> 	printf(" Number of calls to TableRestoreChar = %d \n",
> 		(int) MR_Table_Prof_RestoreChar_Call); 
> 	printf(" Number of calls to TableRestoreString = %d \n",
> 		(int) MR_Table_Prof_RestoreString_Call); 
> 	printf(" Number of calls to TableRestoreFloat = %d \n",
> 		(int) MR_Table_Prof_RestoreFloat_Call); 
> 	printf(" Number of calls to TableRestoreAny = %d \n",
> 		(int) MR_Table_Prof_RestoreAny_Call); 
> 	printf(" Number of calls to TableSetup = %d \n",
> 		(int) MR_Table_Prof_Setup_Call); 
> 	printf(" Number of calls to TableRetAllAns = %d \n",
> 		(int) MR_Table_Prof_RetAllAns_Call); 
> 	printf(" Number of calls to TableGenAnsTable = %d \n",
> 		(int) MR_Table_Prof_GenAnsTable_Call); 
> 	printf(" Number of calls to TableHaveAllAns = %d \n",
> 		(int) MR_Table_Prof_HaveAllAns_Call); 
> 	printf(" Number of calls to TableHaveSomeAns = %d \n",
> 		(int) MR_Table_Prof_HaveSomeAns_Call); 
> 	printf(" Number of calls to TableNewAns = %d \n",
> 		(int) MR_Table_Prof_NewAns_Call); 
> 	printf(" Number of calls to TableMarkHaveAllAns = %d \n",
> 		(int) MR_Table_Prof_MarkHaveAllAns_Call); 
> 	printf(" Number of calls to TableMarkHaveSomeAns = %d \n",
> 		(int) MR_Table_Prof_MarkHaveSomeAns_Call); 
> 	printf(" Number of calls to TableMarkAsReturned = %d \n",
> 		(int) MR_Table_Prof_MarkAsReturned_Call); 
> 	printf(" Number of calls to TableSuspend = %d \n",
> 		(int) MR_Table_Prof_Suspend_Call); 
> 	printf(" Number of calls to TableResume = %d \n",
> 		(int) MR_Table_Prof_Resume_Call); 
> 	printf(" Number of calls to TableNewAnsSlot = %d \n",
> 		(int) MR_Table_Prof_NewAnsSlot_Call); 
> 	printf(" Number of calls to TableMemCpy = %d Bytes moved %d\n",
> 		(int) MR_Table_Prof_MemCpy_Call, 
> 		(int) MR_Table_Prof_Moved_Mem); 
> 	printf(" Number of calls to TableMalloc = %d Bytes allocated %d\n",
> 		(int) MR_Table_Prof_Malloc_Call, 
> 		(int) MR_Table_Prof_Malloc_Mem); 
> 	printf(" Number of calls to TableReallc = %d Bytes reallocated %d\n",
> 		(int) MR_Table_Prof_Reallc_Call, 
> 		(int) MR_Table_Prof_Realloc_Mem); 
> 	printf(" Number of calls to TableFree = %d \n",
> 		(int) MR_Table_Prof_Free_Call); 

s/ \n/\n/g

> New File: runtime/mercury_table_profile.h
> ===================================================================
> #ifndef _MERCURY_TABLE_PROFILE
> #define _MERCURY_TABLE_PROFILE
> 
> extern Word MR_Table_Prof_WorkingOnAns_Call;
> extern Word MR_Table_Prof_MarkWorkingOnAns_Call;
> extern Word MR_Table_Prof_LookupInsertInt_Call;
> extern Word MR_Table_Prof_LookupInsertChar_Call;
> extern Word MR_Table_Prof_LookupInsertString_Call;
> extern Word MR_Table_Prof_LookupInsertFloat_Call;
> extern Word MR_Table_Prof_LookupInsertEnum_Call;
> extern Word MR_Table_Prof_LookupInsertUser_Call;
> extern Word MR_Table_Prof_LookupInsertPoly_Call;
> extern Word MR_Table_Prof_HaveAns_Call;
> extern Word MR_Table_Prof_HasFailed_Call;
> extern Word MR_Table_Prof_CreateAnsBlock_Call;
> extern Word MR_Table_Prof_SaveIntAns_Call;
> extern Word MR_Table_Prof_SaveCharAns_Call;
> extern Word MR_Table_Prof_SaveStringAns_Call;
> extern Word MR_Table_Prof_SaveFloatAns_Call;
> extern Word MR_Table_Prof_SaveAnyAns_Call;
> extern Word MR_Table_Prof_SaveFailure_Call;
> extern Word MR_Table_Prof_RestoreInt_Call;
> extern Word MR_Table_Prof_RestoreChar_Call;
> extern Word MR_Table_Prof_RestoreString_Call;
> extern Word MR_Table_Prof_RestoreFloat_Call;
> extern Word MR_Table_Prof_RestoreAny_Call;
> extern Word MR_Table_Prof_Setup_Call;
> extern Word MR_Table_Prof_RetAllAns_Call;
> extern Word MR_Table_Prof_GenAnsTable_Call;
> extern Word MR_Table_Prof_HaveAllAns_Call;
> extern Word MR_Table_Prof_HaveSomeAns_Call;
> extern Word MR_Table_Prof_NewAns_Call;
> extern Word MR_Table_Prof_MarkHaveAllAns_Call;
> extern Word MR_Table_Prof_MarkHaveSomeAns_Call;
> extern Word MR_Table_Prof_MarkAsReturned_Call;
> extern Word MR_Table_Prof_Suspend_Call;
> extern Word MR_Table_Prof_Resume_Call;
> extern Word MR_Table_Prof_NewAnsSlot_Call;
> extern Word MR_Table_Prof_MemCpy_Call;
> extern Word MR_Table_Prof_Malloc_Call;
> extern Word MR_Table_Prof_Reallc_Call;
> extern Word MR_Table_Prof_Free_Call;
> extern Word MR_Table_Prof_Moved_Mem;
> extern Word MR_Table_Prof_Malloc_Mem;
> extern Word MR_Table_Prof_Realloc_Mem;

These should all be lower case (except for the MR_ prefix),
not mixed case.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.