[m-rev.] for review: build subtrees based on desired nodes, instead of desired depth

Julien Fischer juliensf at cs.mu.OZ.AU
Mon Apr 18 18:20:49 AEST 2005
Previous message: [m-rev.] for review: build subtrees based on desired nodes, instead of desired depth
Next message: [m-rev.] for review: build subtrees based on desired nodes, instead of desired depth
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
On Sat, 16 Apr 2005, Ian MacLarty wrote:

> For review by anyone.
>
> Estimated hours taken: 30
> Branches: main
>
> In the declarative debugger, instead of building new explicit subtrees down to
> a fixed depth, allow the desired number of nodes in the subtree to be given and
> estimate the depth that would produce such a subtree.  This depth can be
> estimated from the average branching factor of the tree and the desired number
> of nodes to generate.  The average branching factor, in turn, can be calculated
s/to generate/to be generated/

> from the maximum depth of the subtree and the total number of events in the
> subtree.
>
> This is the first stage of a new method for determining how much of a
> subtree to build in one go.  The next stage will try to estimate how many
> nodes should be in each subtree by considering how much memory is available
> and how much memory each node consumes (this will be based on the nodes we have
> materialized so far).
>
> browser/declarative_debugger.m:
> 	Accept a new argument from the C backend, DesiredSubtreeWeight, which
> 	indicates how many nodes should be in newly materialized subtrees.
> 	Pass this argument around where needed.
>
> 	Calculate the maximum depth to build a new subtree to using the
> 	given desired subtree weight and the average branching factor of the
> 	implicit subtree.  The average branching factor is calculated from
> 	the number of events in the subtree and its maximum depth.
>
> 	Return this maximum weight to the C backend.
>
> browser/declarative_execution.m:
> 	Instead of storing a boolean flag at CALL events to indicate that the
> 	call is the root of an implicit subtree, store a maybe type,
> 	which holds some information about the implicit subtree (at the moment
> 	only the maximum depth).
>
> 	Export a function to update the maximum call depth of an implicit
> 	subtree.
>
> browser/declarative_tree.m:
> 	Add a predicate to retrieve information about an implicit subtree.
>
> 	Export the predicate which calculates the weight of a subtree, to be
> 	used in the calculation of the average branching factor of the
> 	subtree.
>
> trace/mercury_trace_declarative.c:
> 	Hardcode the number of desired nodes in any subtree for now.  The
> 	next step will be to work this out from a desired amount of memory
> 	usage.
>
> 	Add a global variable, MR_edt_implicit_tree_max_depth which keeps
> 	track of the maximum call depth in an implicit subtree.
> 	Add a function to update the above global variable.
>
> 	Update the maximum depth of the an implicit subtree for the
> 	corresponding CALL node when an EXIT, FAIL or EXCP node is found
> 	which is at the depth limit.
>
> 	If a new explicit subtree is requested, set the step size to
> 	the maximum required depth returned by the declarative debugger.
>
> 	Fix a bug which caused the dd_dd command not to interactively trace
> 	through the events generated by the declarative debugger.
>
> Index: browser/declarative_debugger.m
> ===================================================================
> RCS file: /home/mercury1/repository/mercury/browser/declarative_debugger.m,v
> retrieving revision 1.55
> diff -u -r1.55 declarative_debugger.m
> --- browser/declarative_debugger.m	6 Apr 2005 01:11:29 -0000	1.55
> +++ browser/declarative_debugger.m	16 Apr 2005 06:52:38 -0000
> @@ -250,15 +250,27 @@
>
>  			% The analyser requires the back end to reproduce
>  			% part of the annotated trace, with a greater
> -			% depth bound.  The event number and sequence
> -			% number are for the final event required (the
> -			% first event required is the call event with
> -			% the same sequence number).
> -			% R is the node preceeding the call node.  This is
> -			% needed so the root of the new tree can have the
> -			% correct preceding node.
> +			% depth bound.
>  			%
> -	;	require_subtree(event_number, sequence_number, R)
> +	;	require_subtree(
> +				%
> +				% The event number and sequence
> +				% number are for the final event required (the
> +				% first event required is the call event with
> +				% the same sequence number).
> +				%
> +			require_subtree_final_event	:: event_number,
> +			require_subtree_seqno		:: sequence_number,
> +
> +				% The node preceeding the call node.  This
s/preceeding/preceding/

> +				% is needed so the root of the new tree can
> +				% have the correct preceding node.
> +			require_subtree_call_preceeding_node	:: R,
> +
> +				% The maximum depth to build the new subtree
> +				% to.
> +			require_subtree_max_depth		:: int
> +		)
>
>  			% The analyser requires events before and after the
>  			% current set of materialized events to be generated.
> @@ -274,7 +286,7 @@
>  	diagnoser_state(R)::out) is det.
>
>  :- pred diagnosis(S::in, analysis_type(edt_node(R))::in, int::in, int::in,
> -	int::in, diagnoser_response(R)::out,
> +	int::in, int::in, diagnoser_response(R)::out,
>  	diagnoser_state(R)::in, diagnoser_state(R)::out,
>  	browser_info.browser_persistent_state::in,
>  	browser_info.browser_persistent_state::out,
> @@ -309,7 +321,13 @@
>  :- import_module mdb.util.
>  :- import_module mdbcomp.prim_data.
>
> -:- import_module exception, int, map, bool.
> +:- import_module exception.
> +:- import_module float.
> +:- import_module int.
> +:- import_module map.
> +:- import_module bool.
> +
This list of module imports should be sorted.

> +
>
>  unravel_decl_atom(DeclAtom, TraceAtom, IoActions) :-
>  	(
> @@ -363,8 +381,7 @@
>  	Diagnoser = diagnoser(Analyser, Oracle).
>
>  diagnosis(Store, AnalysisType, UseOldIoActionMap, IoActionStart, IoActionEnd,
> -		Response, !Diagnoser, !Browser,
> -		!IO) :-
> +		DesiredSubtreeWeight, Response, !Diagnoser, !Browser, !IO) :-
>  	mdb.declarative_oracle.set_browser_state(!.Browser, !.Diagnoser ^
>  		oracle_state, Oracle),
>  	!:Diagnoser = !.Diagnoser ^ oracle_state := Oracle,
> @@ -380,7 +397,8 @@
>  			Analyser0, Analyser1),
>  		!:Diagnoser = !.Diagnoser ^ analyser_state := Analyser1
>  	),
> -	try_io(diagnosis_2(Store, AnalysisType, !.Diagnoser), Result, !IO),
> +	try_io(diagnosis_2(Store, AnalysisType, DesiredSubtreeWeight,
> +		!.Diagnoser), Result, !IO),
>  	(
>  		Result = succeeded({Response, !:Diagnoser})
>  	;
> @@ -397,34 +415,39 @@
>  	!:Browser = mdb.declarative_oracle.get_browser_state(
>  		!.Diagnoser ^ oracle_state).
>
> -:- pred diagnosis_2(S::in, analysis_type(edt_node(R))::in,
> +:- pred diagnosis_2(S::in, analysis_type(edt_node(R))::in, int::in,
>  	diagnoser_state(R)::in,

I suggest defining the equivalence desired_weight == int, or something
similar, and using that in the predicate declarations rather than
just int.

...

> +%-----------------------------------------------------------------------------%
> +
> +:- func max_build_depth(implicit_tree_info, int, int) = int.
> +
> +max_build_depth(implicit_tree_info(MaxDepth), TotalWeight, DesiredWeight)
> +		= Depth :-
> +	BranchingFactor = average_branching_factor(MaxDepth, TotalWeight),
> +	Depth = depth_for_desired_weight(DesiredWeight, BranchingFactor).
> +
> +:- func average_branching_factor(int, int) = float.
> +
> +average_branching_factor(Depth, Weight) =
> +	%
> +	% The relationship between the number of nodes in a tree, n,
> +	% the average branching factor of a tree, b, and the depth of the
> +	% tree, d, is given by n = 1 + b + b^2 + ... + b^(d-1),
> +	% so to find b, we must find the root of
> +	% f(b) = 1 - n + b + b^2 + ... + b^(d-1).
> +	%
> +	binary_converge_to_root(
> +		poly_with_unit_coefficients(Depth - 1, 1.0 - float(Weight)),
> +		0.1, 1.0, 10.0, 1000.0, 50).
> +
> +:- func depth_for_desired_weight(int, float) = int.
> +
> +depth_for_desired_weight(Weight, BranchingFactor) =
> +	%
> +	% To find the depth of a tree given it's average branching
s/it's/its/

(You've just posted another version of this bit, so I'll ignore this one).

...

> @@ -801,6 +838,18 @@
>
>  	call = MR_trace_matching_call(prev);
>  	MR_decl_checkpoint_match(call);
> +
> +	/*
> +	** We need to add 1 to MR_edt_depth since this is an EXIT
> +	** event, so 1 would already have been subtracted from MR_edt_depth
s/would/should/  (and below)

> +	** in MR_trace_calculate_event_depth.
> +	*/
> +	if (MR_edt_depth + 1 == MR_edt_max_depth) {
> +		MR_DD_call_node_update_implicit_tree_info(call,
> +			MR_edt_implicit_tree_max_depth
> +			- event_info->MR_call_depth);
> +	}
> +
>  	MR_TRACE_CALL_MERCURY(
>  		last_interface = MR_DD_call_node_get_last_interface(
>

Julien.
 				(MR_Word) call);
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------
Previous message: [m-rev.] for review: build subtrees based on desired nodes, instead of desired depth
Next message: [m-rev.] for review: build subtrees based on desired nodes, instead of desired depth
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the reviews mailing list