home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / lifeos2.zip / LIFE-1.02 / TOOLS / PROFILER.DOC < prev    next >
Text File  |  1996-06-04  |  17KB  |  551 lines
  1. #    $Id: Profiler.doc,v 1.3 1995/08/25 23:12:33 duchier Exp $    
  2.  
  3. Arnaud Venet                                                    Jan 14th 1994
  4.  
  5.  
  6.  
  7.  
  8.                           A simple profiler for LIFE
  9.                           ==========================
  10.  
  11.  
  12.  
  13.  
  14.  
  15. This document describes a small profiling module for LIFE. It works by reading
  16. and rewriting the clauses of the predicates and functions intended for profiling. 
  17. It gives all the informations allowed by this method, although the statistics
  18. for the functions are less detailed than for the predicates.
  19.  
  20.  
  21.  
  22. 1- Using the profiler
  23. ---------------------
  24.  
  25. The profiler is implemented as a module which must be imported by typing :
  26.  
  27.     > import("profiler")?
  28.  
  29. You can get on-line help by typing :
  30.  
  31.     > profile_help?
  32.  
  33. You can choose to register a predicate or a function for profiling through the
  34. predicate 'profile' :
  35.  
  36.     > profile(Name1, Name2 ... NameN, level => Level)?
  37.  
  38. where the Names are the names of the functions or predicates to profile. 
  39. 'Level' may be 'call', 'clause' or 'goal'. The default value for 'Level' is 
  40. 'call'. Read the next section for more information on the different levels of 
  41. profiling. All the clauses or rules attached to a predicate or function are 
  42. preserved and replaced by the rewritten ones.
  43. If one of the specified names does not refer to an existing predicate or
  44. function, an error message appears and the name is simply discarded.
  45.  
  46. You can restore the original clauses attached to 'Name' by simply typing :
  47. If 'Name' does not refer to a clause or function previously modified by the
  48. profiler nothing happens and the predicate succeeds.
  49. Like 'profile', 'unprofile' allows another syntax :
  50.  
  51.     > unprofile(Name1, Name2 ... NameN)?
  52.  
  53. To restore the original clauses of all functions and predicates registered for
  54. profiling type :
  55.  
  56.     > unprofile?
  57.  
  58. To display the statistics of use for a predicate or a function type :
  59.  
  60.     > write_stats(Name, verbosity => Verbosity, file => FileName)?
  61.  
  62. Verbosity may be 'normal' or 'verbose', default is 'normal'. See section 3 to
  63. have more information about display modes. 'FileName' is the name of the file
  64. where you want to store the statistics. Default is @, meaning that the standard
  65. output is used. If it is specified, as a string, the statistics are stored in
  66. the file whose name is 'FileName.log'.
  67.  
  68. To reset the statistics for Name1, ..., NameN just type :
  69.  
  70.     > clear_stats(Name1, Name2, ... , NameN)?
  71.  
  72. If no name is specified, the statistics of all the predicates and functions 
  73. registered for profiling are cleared.
  74.  
  75.  
  76. WARNING :
  77. ---------
  78. All the profiling statistics are contained in a persistent variable named 
  79. 'profile_stats'. You can read it as you want, but avoid to modify its contents
  80. directly. The persistent variables 'profile_backtracking' and 'profile_fail_occured'
  81. are made public because they are used by the predicates registered for profiling, 
  82. but DON'T MODIFY THEIR CONTENTS.
  83.  
  84.  
  85.  
  86. 2- Using the different levels
  87. -----------------------------
  88.  
  89. a) 'call' level
  90.    ------------
  91.    The informations given for a predicate are :
  92.    _ the number of calls
  93.    _ the number of successful calls
  94.    _ the rate of total failures (relatively to the number of calls)
  95.    _ the rate of explicit failures (relatively to the number of calls)
  96.    
  97.    The latter percentage is more precise than the former : it indicates 
  98.    the failures of a predicate whose origin is inner to the clauses of the 
  99.    predicate, i.e. a 'fail' into the goals of a clause or the exhaustion of all
  100.    the choice points. Then a failure of a predicate that previously succeeded
  101.    but has been retried, due to a backtrack, won't be counted as an explicit 
  102.    failure, unless a goal 'fail' is encountered during the backtrack. However 
  103.    it will be counted in the total number of failures.
  104.  
  105.    The informations given for a function are : 
  106.    _ the number of calls
  107.    _ the number of successful calls
  108.    _ the rate of total failures (relatively to the number of calls)
  109.    
  110.  
  111. b) 'clause' level
  112.    ---------------
  113.    This mode gives clause-by-clause informations, i.e., for each clause:
  114.    _ the number of calls
  115.    _ the number of successful head unifications
  116.    _ the number of successful calls
  117.    _ the rate of total failures (relatively to the number of calls)
  118.    _ the rate of explicit failures (relatively to the number of calls)
  119.  
  120.    Respectively for each function rule :
  121.    _ the number of calls
  122.    _ the number of successful head matchings
  123.    _ the rate of successful evaluations (relatively to the number of calls)
  124.    _ the number of successful calls (i.e. successful evaluation AND
  125.      execution of the function body, if any)
  126.    _ the rate of total failures (relatively to the number of calls)
  127.  
  128.  
  129.  
  130. c) 'goal' level
  131.    ------------
  132.    This mode adds statistics for each goal of the predicate (or function) body,
  133.    i.e. the number of times each goal has been tried and its success rate.
  134.    For the disjunction ';' and the 'cond' statements, statistics are added
  135.    recursively for each term of the disjunction or condition.
  136.  
  137.  
  138.    NOTE : in order to avoid confusions : empty bodies for clauses are
  139.    ----   interpreted by a single goal 'succeed'. So don't be surprised
  140.           to see a goal for clauses with empty bodies when you display the
  141.           statistics.
  142.  
  143.  
  144.  
  145. 3- Display modes
  146. ----------------
  147.  
  148. a) 'normal' mode
  149.    -------------
  150.    The statistics are displayed in a condensed fashion, as a chart, each line 
  151.    corresponding to a predicate(function), a clause(rule) or a goal.
  152.    The columns correspond to particular statistics. A cell can be filled with
  153.    "--", meaning that the corresponding statistics don't have sense at this
  154.    line(e.g. the Entries column for a line describing a goal) or that 
  155.    it cannot be calculated for the moment (e.g. a failure rate with a null
  156.    number of calls).
  157.    At the 'goal' level only the statistics for the goals appearing in a
  158.    conjunction are displayed. Disjunctions and conditions are then considered 
  159.    like single goals and the statistics for the goals appearing in their
  160.    subterms are not displayed. To visualize them use the 'verbose' mode.
  161.    In fact there are several charts displayed, each of them being sorted
  162.    relatively to the values of a particular column whose name is printed
  163.    between stars.
  164.    The titles of the columns can be modified by reassigning the persistent 
  165.    public variables provided for this effect :
  166.    'titles_for_functions' and 'titles_for_predicates'. They must contain five
  167.    strings representing the names of the columns in the order in which they
  168.    are displayed. Inconsistent assignments are detected. 
  169.  
  170.    Example :
  171.    ---------
  172.  
  173. > write_stats(app, f)?
  174.  
  175. Profiling statistics for predicates :
  176. -----------------------------------
  177.  
  178.   *Tries*    Entries    Success   %Tot.fail %Expl.fail   predicates
  179.      9         ---        14        55.55      11.11     app
  180.  
  181.   *Tries*    Entries    Success   %Tot.fail %Expl.fail   predicates
  182.      9          5          5         80          0       app#1
  183.      8          6          9         50          0       app#2
  184.  
  185.    Tries    *Entries*   Success   %Tot.fail %Expl.fail   predicates
  186.      8          6          9         50          0       app#2
  187.      9          5          5         80          0       app#1
  188.  
  189.    Tries     Entries   *Success*  %Tot.fail %Expl.fail   predicates
  190.      8          6          9         50          0       app#2
  191.      9          5          5         80          0       app#1
  192.  
  193. Profiling statistics for functions :
  194. ----------------------------------
  195.  
  196.   *Tries*     Match      %Eval    Successes  %Tot.fail   functions
  197.      3         ---        ---         2        66.66     f
  198.  
  199.    Tries     *Match*     %Eval    Successes  %Tot.fail   functions
  200.     ---         2        100          2         50       f#1
  201.     ---         1        100          0        100       f#2
  202.  
  203.  
  204.    The notations are :
  205.  
  206.     ... predicates/functions
  207.         Name       ---> statistics for the predicate/function
  208.         Name#1     ---> statistics for the first clause/rule of the 
  209.                         predicate/function
  210.  
  211.    The columns represent :
  212.  
  213.    i)  for the predicates :
  214.        ------------------
  215.        . Tries : number of tries of the predicate (resp. clause)
  216.        . Entries : rate of head unification for the clause, relatively to Tries
  217.        . Success : rate of success for the predicate (resp. clause), relatively to
  218.                    the number of tries (resp. head unifications)
  219.        . Tot.fail : rate of general failure (including failure on backtrack),
  220.                     relatively to the number of tries (head unifications)
  221.        . Expl.fail : rate of explicit failure, relatively to the number of
  222.                      tries (head unifications) 
  223.  
  224.    ii) for the functions :
  225.        -----------------
  226.        . Tries : number of tries of the function
  227.        . Match : number of times the pattern of the rule matches
  228.        . Eval : rate of successful evaluation for the rule, relatively
  229.                 to the number of pattern matchings
  230.        . Successes : rate of success for the function (or rule) relatively to
  231.                      Tries (or Match)
  232.        . Tot.fail : rate of general failure (including failure on backtrack),
  233.                     relatively to Tries (or Match)
  234.  
  235.  
  236. b) 'verbose' mode
  237.    --------------
  238.    The statistics are displayed in detail, without percentage (except for the
  239.    success rate) and recursively (for condition and disjunction at the goal
  240.    level).
  241.  
  242.    Example :
  243.    ---------
  244.  
  245. > write_stats(app, f, verbosity => verbose)?
  246.  
  247. Profiling statistics for predicates :
  248. -----------------------------------
  249.  
  250. Profile statistics for predicate 'app' :
  251. ----------------------------------------
  252. + Number of tries : 9
  253. + Number of explicit failures : 1
  254. + Total number of failures : 5
  255. + Number of successes : 14
  256. + Success rate : 155.556 %
  257.  
  258. CLAUSE #1 :
  259. ----------------------------------------
  260. + Number of tries : 9
  261. + Number of explicit failures : 0
  262. + Total number of failures : 4
  263. + Number of head unifications : 5
  264. + Number of successes : 5
  265. + Success rate : 100 %
  266.  
  267. Statistics for the goals :
  268. ----------------------------------------
  269. | G#1 <CALL> Tries: 5, Successes: 5
  270.  
  271.  
  272. CLAUSE #2 :
  273. ----------------------------------------
  274. + Number of tries : 8
  275. + Number of explicit failures : 0
  276. + Total number of failures : 3
  277. + Number of head unifications : 6
  278. + Number of successes : 9
  279. + Success rate : 150 %
  280.  
  281. Statistics for the goals :
  282. ----------------------------------------
  283. | G#1 <CALL> Tries: 6, Successes: 9
  284.  
  285.  
  286. **************************************************
  287.  
  288.  
  289. Profiling statistics for functions :
  290. ----------------------------------
  291.  
  292. Profile statistics for function 'f' :
  293. ----------------------------------------
  294. + Number of tries : 3
  295. + Number of failures : 2
  296. + Number of successes : 2
  297. + Success rate : 66.6667 %
  298.  
  299. RULE #1 :
  300. ----------------------------------------
  301. + Number of pattern matchings : 2
  302. + Number of failures : 1
  303. + Number of successful evaluations : 2
  304. + Number of successes : 2
  305. + Success rate : 100 %
  306.  
  307. RULE #2 :
  308. ----------------------------------------
  309. + Number of pattern matchings : 1
  310. + Number of failures : 1
  311. + Number of successful evaluations : 1
  312. + Number of successes : 0
  313. + Success rate : 0 %
  314.  
  315.  
  316. **************************************************
  317.  
  318.  
  319.  
  320. 4- Examples
  321. -----------
  322.  
  323. a) The difference between failure and explicit failure
  324.    ---------------------------------------------------
  325.  
  326.   > app(L, [], L).
  327.   > app([X | Ls], L, [X | La]) :- app(Ls, L, La).
  328.  
  329.   > profile(app, level => clause)?
  330.  
  331.   > app(A, B, [1, 2, 3])?
  332.  
  333.   *** Yes
  334.   A = [], B = [1,2,3].
  335.   --1> ;
  336.   
  337.   *** Yes
  338.   A = [1], B = [2,3].
  339.   --1> ;
  340.  
  341.   *** Yes
  342.   A = [1,2], B = [3].
  343.   --1> ;
  344.  
  345.   *** Yes
  346.   A = [1,2,3], B = [].
  347.   --1> ;
  348.  
  349.   *** No
  350.  
  351.   > write_stats(app)?
  352.  
  353. Profiling statistics for predicates :
  354. -----------------------------------
  355.  
  356.   *Tries*    Entries    Success   %Tot.fail %Expl.fail   predicates
  357.      4         ---        10        100          0       app
  358.  
  359.   *Tries*    Entries    Success   %Tot.fail %Expl.fail   predicates
  360.      4          4          4        100          0       app#1
  361.      4          3          6        100          0       app#2
  362.  
  363.    Tries    *Entries*   Success   %Tot.fail %Expl.fail   predicates
  364.      4          4          4        100          0       app#1
  365.      4          3          6        100          0       app#2
  366.  
  367.    Tries     Entries   *Success*  %Tot.fail %Expl.fail   predicates
  368.      4          3          6        100          0       app#2
  369.      4          4          4        100          0       app#1
  370.  
  371.  
  372.   The failures due to backtrack are not counted as explicit failures.
  373.   But if we type now :
  374.  
  375.   > app(1, [], X)?
  376.  
  377.   ** No
  378.  
  379.   > write_stats(app)?
  380.  
  381. Profiling statistics for predicates :
  382. -----------------------------------
  383.  
  384.   *Tries*    Entries    Success   %Tot.fail %Expl.fail   predicates
  385.      5         ---        10        100         20       app
  386.  
  387.   *Tries*    Entries    Success   %Tot.fail %Expl.fail   predicates
  388.      5          4          4        100          0       app#1
  389.      5          3          6        100          0       app#2
  390.  
  391.    Tries    *Entries*   Success   %Tot.fail %Expl.fail   predicates
  392.      5          4          4        100          0       app#1
  393.      5          3          6        100          0       app#2
  394.  
  395.    Tries     Entries   *Success*  %Tot.fail %Expl.fail   predicates
  396.      5          3          6        100          0       app#2
  397.      5
  398.  
  399.   The failure is counted as an explicit failure.
  400.  
  401.  
  402.  
  403. b) Functions
  404.    ---------
  405.  
  406.   > g(S:string) -> S + 1 | S $== "anything".
  407.   > g(N:int)    -> R | N =:= 0, !, R = "zero" ; R = "<> 0".
  408.  
  409.   > profile(g, level => goal)?
  410.  
  411.   > X = g(0)?
  412.  
  413.   *** Yes
  414.   X = "zero".
  415.   
  416.   --1> Y = g(1)?
  417.  
  418.   *** Yes
  419.   X = "zero", Y = "<> 0".
  420.  
  421.   ----2> Z = g("something")?
  422.   *** Warning: non-numeric argument(s) in '"something" + 1'.
  423.  
  424.   *** No
  425.   X = "zero", Y = "<> 0".
  426.  
  427.   > write_stats(g)?
  428.  
  429. Profiling statistics for functions :
  430. ----------------------------------
  431.  
  432.   *Tries*     Match      %Eval    Successes  %Tot.fail   functions
  433.      3         ---        ---         2        33.33     g
  434.  
  435.    Tries     *Match*     %Eval    Successes  %Tot.fail   functions
  436.     ---         2        100          2          0       g#2
  437.     ---         1          0          0        100       g#1
  438.  
  439.  
  440.   > write_stats(g, verbosity => verbose)?
  441.  
  442. Profiling statistics for functions :
  443. ----------------------------------
  444.  
  445. Profile statistics for function 'g' :
  446. ----------------------------------------
  447. + Number of tries : 3
  448. + Number of failures : 1
  449. + Number of successes : 2
  450. + Success rate : 66.6667 %
  451.  
  452. RULE #1 :
  453. ----------------------------------------
  454. + Number of pattern matchings : 1
  455. + Number of failures : 1
  456. + Number of successful evaluations : 0
  457. + Number of successes : 0
  458. + Success rate : 0 %
  459.  
  460. Statistics for the body :
  461. ----------------------------------------
  462. + Number of tries : 0
  463. + Number of successes : 0
  464. + Number of failures : 0
  465. + Success rate : ---%
  466.  
  467. | G#1 <CALL> Tries: 0, Successes: 0
  468.  
  469. RULE #2 :
  470. ----------------------------------------
  471. + Number of pattern matchings : 2
  472. + Number of failures : 0
  473. + Number of successful evaluations : 2
  474. + Number of successes : 2
  475. + Success rate : 100 %
  476.  
  477. Statistics for the body :
  478. ----------------------------------------
  479. + Number of tries : 2
  480. + Number of successes : 2
  481. + Number of failures : 0
  482. + Success rate : 100%
  483.  
  484. | G#1 <DISJUNCTION> Tries: 2, Successes: 2
  485. | <FIRST TERM> Tries: 2, Successes: 1
  486. | | G#1 <CALL> Tries: 2, Successes: 1
  487. | | G#2 <CUT> Tries: 1
  488. | | G#3 <CALL> Tries: 1, Successes: 1
  489. | <SECOND TERM> Tries: 1, Successes: 1
  490. | | G#1 <CALL> Tries: 1, Successes: 1
  491.  
  492.  
  493. **************************************************
  494.  
  495.  
  496.  
  497. 5- What the profiler does
  498. -------------------------
  499.  
  500. The profiler retracts the original clauses of predicates and rewrites them 
  501. by including directives which modify the corresponding terms in 'profile_stats'.
  502. The main point to know is the adjunction of choice points during the execution
  503. of the predicates. Two choice-points exactly are added for each call of a clause :
  504.  
  505.  _ one at the beginning of the execution of the clause. It is used when the
  506.    clause fails to determine the origin of the failure and to modify the field
  507.    'explicit_failures' in 'profile_stats' accordingly. It also updates the
  508.    variables 'profile_fail_occured' and 'profile_backtracking' which save the
  509.    informations about backtrack and failure, in order to handle correctly the
  510.    possible failure of the entire predicate.
  511.  
  512.  _ one at the end of the clause. This choice point is left when the clause
  513.    succeeds and is entered only when the clause is retried, i.e. when a
  514.    backtrack occurs outside of the predicate. This permits to handle explicit
  515.    failures correctly.
  516.  
  517. This can cause notable performance degradation and memory usage, particularly 
  518. in the case of recursive predicates.
  519.  
  520.  
  521. 6- Possible enhancements
  522. ------------------------
  523.  
  524.  _ extend function handling (currying, residuation)
  525.  
  526.  _ allow the profiling of private predicates/functions in modules
  527.  
  528.  
  529.  
  530.  
  531.  
  532.  
  533.  
  534.    
  535.  
  536.  
  537.  
  538.  
  539.  
  540.  
  541.  
  542.  
  543.  
  544.  
  545.  
  546.  
  547.  
  548.  
  549.  
  550.  
  551.