[m-rev.] for review: [CTGC] direct structure reuse analysis (1/2)

[Nancy]

Hi Julian,

many thanks for your reviewing work! I'm starting to address your
feedback... here some responses...

>>Index: compiler/hlds_goal.m
>>===================================================================
>>RCS file: /home/mercury1/repository/mercury/compiler/hlds_goal.m,v
>>retrieving revision 1.155
>>diff -u -d -r1.155 hlds_goal.m
>>--- compiler/hlds_goal.m	20 Apr 2006 05:36:52 -0000	1.155
>>+++ compiler/hlds_goal.m	27 Apr 2006 09:29:59 -0000
>>@@ -769,6 +769,8 @@
>>                 hlds_goal   % goal to execute if match succeeds.
>>             ).
>>
>>+:- func case_get_goal(case) = hlds_goal.
>>+
> 
> 
> Why not just give the fields in the case structure names and use the
> automatically generated field access function to retrieve the goal.
> 
> e.g.
> 	:- type case --->
> 		case(
> 			case_functor :: cons_id,
> 			case_goal    :: hlds_goal
> 		).
> 

Just to be sure that I'm not missing anything and that I have understood
the documentation right:

Using these field names, this enables me to use the field access
functions "case_functor/1" and "case_goal/1". But these functions can
not be used in higher order calls as is, but must be part of a lambda
expression?
That doesn't help much with my code... I'm using case_get_goal only in
higher order calls, so now I've replaced them all with a copy/paste of
lambda expressions?
Where is the gain?


....

>>Index: compiler/options.m
>>===================================================================
>>RCS file: /home/mercury1/repository/mercury/compiler/options.m,v
>>retrieving revision 1.511
>>diff -u -d -r1.511 options.m
>>--- compiler/options.m	26 Apr 2006 03:05:38 -0000	1.511
>>+++ compiler/options.m	27 Apr 2006 09:30:36 -0000
>>@@ -530,6 +530,9 @@
>>     % Stuff for the CTGC system (structure sharing / structure reuse).
>>     ;       structure_sharing_analysis
>>     ;           structure_sharing_widening
>>+    ;       structure_reuse_analysis
>>+    ;           structure_reuse_constraint
>>+    ;           structure_reuse_constraint_arg
>>
>>     % Stuff for the new termination analyser.
>>     ;       termination2
>>@@ -1149,6 +1152,9 @@
>>     verbose_check_termination           -   bool(no),
>>     structure_sharing_analysis          -   bool(no),
>>     structure_sharing_widening          -   int(0),
>>+    structure_reuse_analysis            -   bool(no),
>>+    structure_reuse_constraint        -   string("within_n_cells_difference"),
>>+    structure_reuse_constraint_arg      -   int(0),
>>     termination                         -   bool(no),
>>     termination_single_args             -   int(0),
>>     termination_norm                    -   string("total"),
>>@@ -1981,6 +1987,12 @@
>> % CTGC related options.
>> long_option("structure-sharing",    structure_sharing_analysis).
>> long_option("structure-sharing-widening", structure_sharing_widening).
>>+long_option("structure-reuse",      structure_reuse_analysis).
>>+long_option("ctgc",                 structure_reuse_analysis).
>>+long_option("structure-reuse-constraint", structure_reuse_constraint).
>>+long_option("ctgc-constraint",      structure_reuse_constraint).
>>+long_option("structure-reuse-constraint-arg", structure_reuse_constraint_arg).
>>+long_option("ctgc-constraint-arg",  structure_reuse_constraint_arg).
> 
> 
> You must also update the predicate option_defaults_2 in order to
> provide default values for the new options.

Isn't that what is given a couple of lines above? Or am I missing
something?

>>@@ -3197,7 +3209,23 @@
>>         "--structure-sharing-widening <n>",
>>         "\tPerform widening when the set of structure sharing pairs becomes",
>>         "\tlarger than <n>. When n=0, widening is not enabled.",
>>-        "\t(default: 0)."
>>+        "\t(default: 0).",
>>+        "--structure-reuse, --ctgc",
>>+        "\tPerform structure reuse analysis for all encountered",
>>+        "\tpredicates (Compile Time Garbage Collection).",
> 
> 
> Just "Perform structure reuse analysis" would be sufficient, I'm not
> sure what you mean by "encountered predicates" anyway.
> 
> 
>>+        "--structure-reuse-constraint, --ctgc-constraint",
>>+        "\tConstraint on the way we allow structure reuse. Either reuse",
>>+        "\tis only allowed for terms with the same type and same constructor",
>>+        "\t(option same_cons_id), or reuse is allowed between terms of",
>>+        "\tdifferent constructors as long as the difference between the",
>>+        "\tarities does not exceed a certain threshold (option ",
>>+        "\twithin_n_cells_difference(n), where n specifies the threshold,",
>>+        "\tn needs to be set using --structure-reuse-constraint-arg).",
>>+        "\t(default: within_n_cells_difference(0))",
> 
> 
> To be consistent with the way the rest of the options are documented,
> that should really be something like:
> 
>     --structure-reuse-constraint {same_cons_id, within_n_cells_difference(n)}
> 
> (See the documentation of the option `--termination-norm' for an
> example.)
> 
> 
>>+        "--structure-reuse-constraint-arg, --ctgc-constraint-arg",
>>+        "\tSpecify the allowed difference in arities between the terms that",
>>+        "\tcan be reused, and the terms that reuse these terms.",
>>+        "\t(default: 0)"
>>     ]).
> 
> 
> So the arities of the terms are allowed to differ up to that limit?
> In that case I suggest "Specify the maximum difference in arities ...".

The new diff for options.m is in attachment (sorry about that, darn
thunder... )

...

>>Index: compiler/structure_reuse.direct.choose_reuse.m
>>===================================================================
>>RCS file: compiler/structure_reuse.direct.choose_reuse.m
>>diff -N compiler/structure_reuse.direct.choose_reuse.m
>>--- /dev/null	1 Jan 1970 00:00:00 -0000
>>+++ compiler/structure_reuse.direct.choose_reuse.m	27 Apr 2006 09:30:40 -0000
>>@@ -0,0 +1,1363 @@
>>+%-----------------------------------------------------------------------------%
>>+% vim: ft=mercury ts=4 sw=4 et
>>+%-----------------------------------------------------------------------------%
>>+% Copyright (C) 2006 The University of Melbourne.
>>+% This file may only be copied under the terms of the GNU General
>>+% Public License - see the file COPYING in the Mercury distribution.
>>+%-----------------------------------------------------------------------------%
>>+%
>>+% File: structure_reuse.direct.choose_reuse.m
>>+% Main authors: nancy
>>+%
>>+% Given a dead cell table listing the deconstructions that may leave garbage
>>+% (dead cells), we compute the concrete assignements of which constructions can
> 
> 
> s/assignements/assignments/
> 
> 
>>+% profit of these dead cells. Obviously, we want to find those assignments
> 
> 
> s/of/from/
> 
> 
>>+% which result in the 'best' form of memory reuse possible for the given goals.
>>+%
>>+% Hence, the assignment problem is translated into a mapping problem (inspired
>>+% from Debray's paper: "On copy avoidance in single assignment languages", and
>>+% restricted to reuse of dead cells by at most one new cell).
>>+%
>>+% When assigning constructions to dead deconstructions, a table is first
>>+% computed. For each dead cell, a value is computed that reflects the gain
>>+% a reuse might bring, and the list of constructions involved with reusing it.
>>+% The cell with highest value is selected first, the according constructions
>>+% are annotated, and the table is recomputed. This process is repeated until
>>+% no reusable dead deconstructions are left.
>>+%
>>+% The value of a dead cell (a specific deconstruction) is computed taking
>>+% into account the call graph which can be simplified to take only into account
>>+% construction-unifications, conjunctions, and disjunctions.
> 
> 
> Does it also take calls into account?

No. What exactly do you mean?
In this setting dead cells can only be reused within the same procedure
as where it dies. So we're focussing on the construction unifications only.


> 
> 
>>+% The source of the graph is the deconstruction, the leaves are
>>+% either constructions, or empty. The branches are either conjunctions
>>+% or disjunctions.
> 
> 
> ...
> 
> 
>>+% The value of the dead cell is then computed as follows:
>>+% 	- value of a conjunction = maximum of the values of each of the
>>+%		conjunct branches.
>>+% 		Intuitively: if a dead deconstruction is followed by
>>+%		two constructions which might reuse the dead cell: pick
>>+%		the one which allows the most potential gain.
>>+%	- value of a disjunction = average of the value of each of the
>>+%		disjunct branches.
>>+%		Intuitively: if a dead deconstruction is followed by
>>+% 		a disjunction with 2 disjuncts. If reuse is only possible
>>+% 		in one of the branches, allowing this reuse means that
>>+% 		a priori reuse will occur in only 50% of the cases.
>>+%		The value of the disjunct should take this into account.
>>+%		Without precise notion of which branches are executed
>>+%		more often, taking the simple average of the values is
>>+%		a good approximation.
>>+%	- value of a construction = a value that takes into account
>>+%	 	the cost of constructing a new cell and compares it
>>+%		to the cost of updating a dead cell. If the arities
>>+%		between the dead and new cell differ, a penalty cost
>>+%		is added (approximated as the gain one would have had if
>>+%		the unusable words would have been reused too).
>>+%		Weights are used to estimate all of these costs and are
>>+%		hard-coded. I don't think there is any need in making
>>+%		these values an option.
>>+%
>>+% Once the table is computed, usually the cell with highest value is selected.
> 
> 
> usually? - when would the one with highest values not be selected.
> 

you're right ;-)

...


>>+:- type reuse_type
>>+	---> 	reuse_type(
>>+			same_cons	:: bool,
>>+			reuse_fields 	:: list(needs_update),
>>+                % States whether the corresponding argument in the list of
>>+                % arguments of the reused cons needs to be updated when reused
>>+                % or not.
>>+				% Note that list.length(reuse_fields) is the arity of the
>>+                % reused term.
>>+			tmp_value	:: float
>>+                % A metrics measuring the value of the reuse. A high value
>>+                % should represent a 'good' reuse (yielding possibly good
>>+                % results on the general memory behaviour of the procedure)
>>+                % compared to a reuse with a lower value.
> 
> 
> tmp_value is not a good field name, perhaps reuse_value instead?

you're right.

...

>>+:- func deconstruction_specs(prog_var, list(match_table)) =
>>+    list(deconstruction_spec).

> 
> Perhaps the equivalence dead_var == prog_var should be defined
> somewhere?

That is a good idea. I will do that.

Thanks!
Nancy



Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm

-------------- next part --------------
A non-text attachment was scrubbed...
Name: options.diff
Type: text/x-patch
Size: 3603 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/reviews/attachments/20060503/1ac13b45/attachment.bin>