[m-rev.] For post-commit review: Finish the cost of recursive calls analysis for linear recursions.

Paul Bone pbone at csse.unimelb.edu.au
Fri Sep 24 00:05:28 AEST 2010


For post commit review by Zoltan,

Peter Schachte - you may be interested in the formulas in
deep_profiler/recursion_patterns.m.

 ---

Finish the cost of recursive calls analysis for linear recursions.

This code will be used by the automatic parallelisation analysis.  It is
accessible as a developer report in the deep profiler.

Thanks to Thibaut Feydy who helped me with the formula for the average cost of
recursive calls, and some missing parts in my maths knowledge :-).

deep_profiler/report.m:
    Add extra fields to the rt_single constructor for the recursion_type data
    type:
        The average total depth of recursion.

        The cost of a recursive call at the average recursion level.

        A higher-order value that gives the cost of recursive calls at a given
        level.

deep_profiler/recursion_patterns.m:
    Use a per-call cost for the recursive call site cost report.

    Document and code formulas for calculating the cost of recursive calls at
    any level and at the average level for linear recursion.

    Conform to changes in report.m.

deep_profiler/display_report.m:
    In the recursive call cost report:
        Print the average cost of recursive calls as well as the costs of
        levels 0, 1, 2, N/2, N-2, N-1 and N.

        Update text in column headers to indicate that costs are 'per call'.
    
        Conform to changes in report.m

    Fix a bug whereby visiting the menu screen and following some links from
    it reset the user's preferences.


Index: deep_profiler/display_report.m
===================================================================
RCS file: /home/mercury1/repository/mercury/deep_profiler/display_report.m,v
retrieving revision 1.28
diff -u -p -b -r1.28 display_report.m
--- deep_profiler/display_report.m	22 Sep 2010 12:56:53 -0000	1.28
+++ deep_profiler/display_report.m	23 Sep 2010 13:24:38 -0000
@@ -257,7 +257,7 @@ display_report_menu(Deep, Prefs, MenuRep
             "Exploring the call graph, starting at the root."),
         link_base(deep_cmd_root(yes(90)), yes(ActionPrefs),
             "Exploring the call graph, starting at the action."),
-        link_base(deep_cmd_program_modules, no,
+        link_base(deep_cmd_program_modules, yes(Prefs),
             "Exploring the program module by module.")
     ],
 
@@ -270,9 +270,9 @@ display_report_menu(Deep, Prefs, MenuRep
             cost_time, self_and_desc, overall),
 
         LinksTopProcsByLimitTime = [
-            link_base(Top100SelfCmd, no,
+            link_base(Top100SelfCmd, yes(Prefs),
                 "Top 100 most expensive procedures: time, self."),
-            link_base(Top100SelfAndDescCmd, no,
+            link_base(Top100SelfAndDescCmd, yes(Prefs),
                 "Top 100 most expensive procedures: time, self+descendants.")
         ]
     ;
@@ -290,13 +290,13 @@ display_report_menu(Deep, Prefs, MenuRep
         cost_words, self_and_desc, overall),
 
     LinksTopProcsByLimit = [
-        link_base(TopLimitCallSeqsSelf, no,
+        link_base(TopLimitCallSeqsSelf, yes(Prefs),
             "Top 100 most expensive procedures: callseqs, self."),
-        link_base(TopLimitCallSeqsSelfAndDesc, no,
+        link_base(TopLimitCallSeqsSelfAndDesc, yes(Prefs),
             "Top 100 most expensive procedures: callseqs, self+descendants."),
-        link_base(TopLimitWordsSelf, no,
+        link_base(TopLimitWordsSelf, yes(Prefs),
             "Top 100 most expensive procedures: words, self."),
-        link_base(TopLimitWordsSelfAndDesc, no,
+        link_base(TopLimitWordsSelfAndDesc, yes(Prefs),
             "Top 100 most expensive procedures: words, self+descendants.")
     ],
 
@@ -310,11 +310,11 @@ display_report_menu(Deep, Prefs, MenuRep
             cost_time, self_and_desc, overall),
 
         LinksTopProcsByPercentTime = [
-            link_base(TimeAbove01PercentCmd, no,
+            link_base(TimeAbove01PercentCmd, yes(Prefs),
                 "Procedures above 0.1% threshold: time, self."),
-            link_base(TimeAbove1PercentCmd, no,
+            link_base(TimeAbove1PercentCmd, yes(Prefs),
                 "Procedures above 1% threshold: time, self+descendants."),
-            link_base(TimeAbove1SecondCmd, no,
+            link_base(TimeAbove1SecondCmd, yes(Prefs),
                 "Procedures above 1 second threshold: time, self+descendants.")
         ]
     ;
@@ -338,18 +338,18 @@ display_report_menu(Deep, Prefs, MenuRep
         cost_words, self_and_desc, overall),
 
     LinksTopProcsByPercent = [
-        link_base(CallSeqsAbove01PercentCmd, no,
+        link_base(CallSeqsAbove01PercentCmd, yes(Prefs),
             "Procedures above 0.1% threshold: callseqs, self."),
-        link_base(CallSeqsAbove1PercentCmd, no,
+        link_base(CallSeqsAbove1PercentCmd, yes(Prefs),
             "Procedures above 1% threshold: callseqs, self+descendants."),
-        link_base(CallSeqsAboveMillionCmd, no,
+        link_base(CallSeqsAboveMillionCmd, yes(Prefs),
             ("Procedures above 1,000,000 callseqs threshold: callseqs, " ++
                 "self+descendants.")),
-        link_base(WordsAbove01PercentCmd, no,
+        link_base(WordsAbove01PercentCmd, yes(Prefs),
             "Procedures above 0.1% threshold: words, self."),
-        link_base(WordsAbove1PercentCmd, no,
+        link_base(WordsAbove1PercentCmd, yes(Prefs),
             "Procedures above 1% threshold: words, self+descendants."),
-        link_base(WordsAbove2Megawords, no,
+        link_base(WordsAbove2Megawords, yes(Prefs),
             "Procedures above 2M words threshold: words, self+descendants.")
     ],
     
@@ -367,7 +367,7 @@ display_report_menu(Deep, Prefs, MenuRep
     RecursionTypeFrequenciesCmd = deep_cmd_recursion_types_frequency,
     
     LinksDeveloperCmds = [
-        link_base(RecursionTypeFrequenciesCmd, no,
+        link_base(RecursionTypeFrequenciesCmd, yes(Prefs),
             "Frequencies of different types of recursion used in the program.")
     ],
     list.map(make_link, LinksDeveloperCmds, DeveloperLinksList),
@@ -742,26 +742,50 @@ display_recursion_type(RecursionType, It
             yes("Unknown, error(s) occured"), ErrorItems)]
     ;
         (
-            RecursionType = rt_single(BaseLevel, RecLevel),
+            RecursionType = rt_single(BaseLevel, RecLevel, AvgDepth, 
+                AvgRecCost, AnyRecCost),
             RowData = [
                 {"Base case", BaseLevel}, 
                 {"Recursive case", RecLevel}],
-            Text = "Single-recursion:"
+            Text = "Single-recursion:",
+
+            MaxDepthI = round_to_int(AvgDepth),
+            ExtraTableRows0 = 
+                [{"Average recursion depth:", AvgDepth}, 
+                 {"Average recursive call cost (excluding the call it's self):",
+                    AvgRecCost}] ++
+                map(
+                    (func(Level) =
+                        {format("Cost at depth %d:", [i(Level)]), 
+                            AnyRecCost(Level)}),
+                    [0, 1, 2, round_to_int(AvgDepth / 2.0),
+                     MaxDepthI - 2, MaxDepthI - 1, MaxDepthI]),
+            ExtraTableRows = map((func({Label, Value}) = table_row(
+                    [table_cell(td_s(Label)), table_cell(td_f(Value))])),
+                ExtraTableRows0)
         ;
             RecursionType = rt_divide_and_conquer(BaseLevel, RecLevel),
             RowData = [
                 {"Base case", BaseLevel},
                 {"Doubly-recursive case", RecLevel}],
-            Text = "Double-recursion (Probably Divide and Conquer):"
+            Text = "Double-recursion (Probably Divide and Conquer):",
+
+            ExtraTableRows = []
         ; 
             RecursionType = rt_other(Levels),
             RowData = map((func(Level) = {Label, Level} :-
                     Label = format("Case for %d recursive calls", 
                         [i(Level ^ rlr_level)])
                 ), Levels), 
-            Text = "Unknown recursion type:"
+            Text = "Unknown recursion type:",
+
+            ExtraTableRows = []
         ),
         Rows = map(make_recursion_table_row, RowData),
+            
+        ExtraTable = display_table(table(table_class_do_not_box, 2, no, 
+            ExtraTableRows)),
+
         Header = table_header(map(
             (func({Name, Class}) = 
                 table_header_group(table_header_group_single(td_s(Name)),
@@ -769,13 +793,15 @@ display_recursion_type(RecursionType, It
             ), 
             [{"Recursion type", table_column_class_field_name},
              {"Exec count", table_column_class_number},
-             {"Non recursive calls cost", table_column_class_callseqs},
-             {"Recursive calls cost (ex children)", 
+             {"Non recursive calls per-call cost", table_column_class_callseqs},
+             {"Recursive calls per-call cost (ex children)", 
                 table_column_class_callseqs}])),
         Table = display_table(table(table_class_box_if_pref, 4, yes(Header), 
             Rows)),
         Description = display_text(Text),
-        Items = [Description, display_paragraph_break, Table]
+        Items = [Description, 
+            display_paragraph_break, Table,
+            display_paragraph_break, ExtraTable]
     ).
 
 :- func make_recursion_table_row({string, recursion_level_report}) = table_row.
Index: deep_profiler/recursion_patterns.m
===================================================================
RCS file: /home/mercury1/repository/mercury/deep_profiler/recursion_patterns.m,v
retrieving revision 1.2
diff -u -p -b -r1.2 recursion_patterns.m
--- deep_profiler/recursion_patterns.m	22 Sep 2010 12:56:54 -0000	1.2
+++ deep_profiler/recursion_patterns.m	23 Sep 2010 13:55:15 -0000
@@ -102,11 +102,7 @@ proc_get_recursion_type(Deep, ThisClique
     lookup_pd_own(Deep ^ pd_own, PDPtr, PDOwn),
     Calls = calls(PDOwn),
     lookup_proc_dynamics(Deep ^ proc_dynamics, PDPtr, PD), 
-    PSPtr = PD ^ pd_proc_static, 
-    % TODO: Don't use coverage information here, it's computationally expensive
-    % and shouldn't be necessary.  But more importantly it is per proc static
-    % and therefore not suitable for calculating the depths of recursion.
-    create_static_procrep_coverage_report(Deep, PSPtr, MaybeCoverageReport),
+    create_dynamic_procrep_coverage_report(Deep, PDPtr, MaybeCoverageReport),
     (
         MaybeCoverageReport = ok(CoverageReport),
         ProcRep = CoverageReport ^ prci_proc_rep, 
@@ -125,7 +121,7 @@ proc_get_recursion_type(Deep, ThisClique
 
 :- type cost_and_callees
     --->    cost_and_callees(
-                cac_cost            :: int,
+                cac_cost            :: cs_cost_csq,
                 cac_callees         :: set(clique_ptr)
             ).
 
@@ -139,10 +135,11 @@ build_call_site_cost_and_callee_map(Deep
     ( valid_call_site_dynamic_ptr(Deep, CSDPtr) ->
         call_site_dynamic_get_callee_and_costs(Deep, CSDPtr, CalleeCliquePtr, 
             Own, Inherit),
-        % XXX: Should this be per call?
-        Cost = callseqs(Own) + inherit_callseqs(Inherit),
-        CostAndCallees = cost_and_callees(Cost, set([CalleeCliquePtr])),
-        lookup_call_site_static_map(Deep ^ call_site_static_map, CSDPtr, CSSPtr),
+        CostCsq = build_cs_cost_csq(calls(Own), 
+            float(callseqs(Own) + inherit_callseqs(Inherit))),
+        CostAndCallees = cost_and_callees(CostCsq, set([CalleeCliquePtr])),
+        lookup_call_site_static_map(Deep ^ call_site_static_map, CSDPtr,
+            CSSPtr),
         lookup_call_site_statics(Deep ^ call_site_statics, CSSPtr, CSS),
         goal_path_from_string_det(CSS ^ css_goal_path, GoalPath),
         svmap.det_insert(GoalPath, CostAndCallees, !CallSitesMap)
@@ -163,8 +160,9 @@ build_call_site_cost_and_callee_map(Deep
             CalleeCliquePtrs, Owns, Inherits),
         Own = sum_own_infos(Owns),
         Inherit = sum_inherit_infos(Inherits),
-        Cost = callseqs(Own) + inherit_callseqs(Inherit),
-        CostAndCallees = cost_and_callees(Cost, set(CalleeCliquePtrs)),
+        CostCsq = build_cs_cost_csq(calls(Own), 
+            float(callseqs(Own) + inherit_callseqs(Inherit))),
+        CostAndCallees = cost_and_callees(CostCsq, set(CalleeCliquePtrs)),
 
         % The goal path of the call site will be the same regardless of the
         % callee, so we get it from the first.
@@ -196,9 +194,11 @@ recursion_data_to_recursion_type(CallsI,
     Calls = float(CallsI),
     ( search(Levels, 0, RLBase) ->
         RLBase = recursion_level(BaseCost, BaseProb),
-        BaseCount = round_to_int(probability_to_float(BaseProb) * Calls)
+        BaseCountF = probability_to_float(BaseProb) * Calls,
+        BaseCount = round_to_int(BaseCountF)
     ;
         BaseCost = 0.0,
+        BaseCountF = 0.0,
         BaseCount = 0,
         BaseProb = impossible
     ),
@@ -213,12 +213,17 @@ recursion_data_to_recursion_type(CallsI,
                 RLRec = recursion_level(RecCost, RecProb),
                 RecCountF = probability_to_float(RecProb) * Calls,
                 RecLevel = recursion_level_report(1, round_to_int(RecCountF),
-                    RecProb, RecCost, RecCountF)
+                    RecProb, RecCost, 1.0)
             ;
                 error(format("%smaximum level %d not found", 
                     [s(this_file), i(1)]))
             ),
-            Type = rt_single(BaseLevel, RecLevel)
+            AvgMaxDepth = RecCountF / BaseCountF,
+            AvgRecCost = single_rec_average_recursion_cost(BaseCost, RecCost,
+                AvgMaxDepth),
+            AnyRecCost = single_rec_recursion_cost(BaseCost, RecCost),
+            Type = rt_single(BaseLevel, RecLevel, AvgMaxDepth, AvgRecCost,
+                AnyRecCost)
         ;
             Maximum = 2,
             not search(Levels, 1, _)
@@ -253,6 +258,53 @@ recursion_level_report(TotalCalls, Level
     Calls = round_to_int(CallsF),
     CostExChild = float(Level) * CallsF.
 
+    % This uses the formula.
+    %
+    % Base + Shared + Level (Rec + Shared) = Cost.
+    %
+    % To calculate the Cost of a recursive call at a depth of Level in a singly
+    % recursive procedure from:
+    %   Base - The cost of the base case.
+    %   Rec - The cost of the recursive call except for the recursive call
+    %         itself.
+    %   Shared - The cost of code common to both cases.
+    %
+    % The + 1.0 counts for the cost of the recursive call itself, The Shared
+    % variable has already been factored into BaseCost and RecCost.
+    %
+:- func single_rec_recursion_cost(float, float, int) = float.
+
+single_rec_recursion_cost(BaseCost, RecCost, LevelI) = 
+        BaseCost + (Level * (RecCost + 1.0)) :-
+    Level = float(LevelI).
+    
+    % This formula is derived as follows.
+    %
+    % It's the average (sum of all recursion levels divided by number of
+    % levels).
+    %
+    %   Sum l in 0..MaxLevel ( Base + l * Rec ) / ( MaxLevel + 1 )
+    %
+    % Factor out the cost of the base case and start the sum from level 1 in
+    % the recursive case. 
+    %
+    %   ( Base(MaxLevel + 1) + Sum l in 1..MaxLevel ( l * Rec ) ) /
+    %     ( MaxLevel + 1 )
+    %
+    % Simplify.
+    %
+    %   Base + Sum l in 1..MaxLevel ( i * Rec ) / (MaxLevel + 1)
+    %
+    % Recall that Sum i in 1..N (i) = (N^2 + N) / 2
+    %
+    %   Base + (((L^2 + L) * Rec) / 2) / (MaxLevel + 1)
+    %
+:- func single_rec_average_recursion_cost(float, float, float) = float.
+
+single_rec_average_recursion_cost(BaseCost, RecCost, AvgMaxDepth) = 
+        BaseCost + ( (Sum) / (AvgMaxDepth + 1.0) ) :-
+    Sum = 0.5 * RecCost * ((AvgMaxDepth * AvgMaxDepth) + AvgMaxDepth).
+
 %----------------------------------------------------------------------------%
 
 :- type recursion_data
@@ -493,9 +545,10 @@ atomic_goal_recursion_data(ThisClique, C
 
         % Get the cost of the call.
         ( map.search(CallSiteMap, GoalPath, CostAndCallees) ->
-            CostAndCallees = cost_and_callees(Cost, Callees)
+            CostAndCallees = cost_and_callees(Cost, Callees),
+            CostPercall = cs_cost_get_percall(Cost)
         ;
-            Cost = 0,
+            CostPercall = 0.0,
             set.init(Callees)
         ),
 
@@ -504,7 +557,7 @@ atomic_goal_recursion_data(ThisClique, C
             % calculate this later.
             RecursionLevel = 1 - recursion_level(0.0, certain)
         ;
-            RecursionLevel = 0 - recursion_level(float(Cost), certain)
+            RecursionLevel = 0 - recursion_level(CostPercall, certain)
         )
     ),
     RecursionLevel = RecursiveCalls - _,
@@ -873,7 +926,7 @@ update_procs_map(FirstProcInfo, !Map) :-
     recursion_type_simple::out) is multi.
 
 recursion_type_to_simple_type(rt_not_recursive, rts_not_recursive).
-recursion_type_to_simple_type(rt_single(_, _), rts_single).
+recursion_type_to_simple_type(rt_single(_, _, _, _, _), rts_single).
 recursion_type_to_simple_type(rt_divide_and_conquer(_, _),
     rts_divide_and_conquer).
 recursion_type_to_simple_type(rt_mutual_recursion(NumProcs),
Index: deep_profiler/report.m
===================================================================
RCS file: /home/mercury1/repository/mercury/deep_profiler/report.m,v
retrieving revision 1.23
diff -u -p -b -r1.23 report.m
--- deep_profiler/report.m	21 Sep 2010 01:09:16 -0000	1.23
+++ deep_profiler/report.m	23 Sep 2010 13:45:34 -0000
@@ -220,7 +220,12 @@
     --->    rt_not_recursive
     ;       rt_single(
                 rts_base                    :: recursion_level_report,
-                rts_recursive               :: recursion_level_report
+                rts_recursive               :: recursion_level_report,
+                rts_avg_max_depth           :: float,
+                rts_avg_rec_cost            :: float,
+
+                % The cost at any level is Cost = func(Level).
+                rts_any_rec_cost            :: (func(int) = float)
             )
     ;       rt_divide_and_conquer(
                 rtdsc_base                  :: recursion_level_report,
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 489 bytes
Desc: Digital signature
URL: <http://lists.mercurylang.org/archives/reviews/attachments/20100924/0c043654/attachment.sig>


More information about the reviews mailing list