SBCL statistische Profiler keinen Eintrag aufgerufen für jede Funktion

Question

besagen

mir die statistischen Profiler von SBCL Verwendung dieser Funktionen zum Profil:

(defun fact-rec (n) 
    (if (zerop n) 
     1 
     (* n (fact-rec (1- n))))) 

(defun fact-call (n) 
    (fact-rec n)) 

(defun fact-iter (n) 
    (loop :with accu = 1 
    :for i :upfrom 2 :to n 
    :doing (setf accu (* i accu)) 
    :finally (return accu))) 

(defun fact-opti-iter (n) 
    (let ((accu 1)) 
    (tagbody 
    loop 
     (unless (zerop n) 
     (setf accu (* n accu)) 
     (decf n) 
     (go loop))) 
    accu)) 

Um das Gewicht der rekursiven Version zu bewerten, definierte ich eine Funktion fact-call, die auf dem Stapel unter allen fact-rec Aufrufen bleibt, damit es ordnungsgemäß überwacht werden kann. Hier ist mein Profil Code:

(sb-sprof:profile-call-counts 'fact-rec 'fact-call 'fact-iter 'fact-opti-iter) 
(sb-sprof:with-profiling (:max-samples 1000 
        :loop nil 
        :report :flat) 
     (dotimes (i 1500) 
     (fact-call i) 
     (fact-iter i) 
     (fact-opti-iter i))) 

auf diese Weise ausgehend stellt sicher, dass fact-rec wird nie direkt aufgerufen also, wenn es über den Bericht der Profiler angezeigt wird, dann ist es unbedingt von fact-call genannt. Aber hier ist der Bericht, den ich bekommen:

 
Profiler sample vector full (70 traces/10000 samples), doubling the size 
Profiler sample vector full (133 traces/20000 samples), doubling the size 

Number of samples: 195 
Sample interval:  0.01 seconds 
Total sampling time: 1.9499999 seconds 
Number of cycles: 0 
Sampled threads: 
# 

      Self  Total  Cumul 
    Nr Count  % Count  % Count  % Calls Function 
------------------------------------------------------------------------ 
    1 193 99.0 193 99.0 193 99.0  - SB-BIGNUM:MULTIPLY-BIGNUM-AND-FIXNUM 
    2  1 0.5 195 100.0 194 99.5  - SB-KERNEL:TWO-ARG-* 
    3  1 0.5  1 0.5 195 100.0  - SB-BIGNUM::%NORMALIZE-BIGNUM 
    4  0 0.0 195 100.0 195 100.0  - "Unknown component: #x100317AB30" 
    5  0 0.0 195 100.0 195 100.0  - SB-INT:SIMPLE-EVAL-IN-LEXENV 
    6  0 0.0 195 100.0 195 100.0  - EVAL 
    7  0 0.0 195 100.0 195 100.0  - SWANK::EVAL-REGION 
    8  0 0.0 195 100.0 195 100.0  - (LAMBDA NIL :IN SWANK-REPL::REPL-EVAL) 
    9  0 0.0 195 100.0 195 100.0  - SWANK-REPL::TRACK-PACKAGE 
    10  0 0.0 195 100.0 195 100.0  - SWANK::CALL-WITH-RETRY-RESTART 
    11  0 0.0 195 100.0 195 100.0  - SWANK::CALL-WITH-BUFFER-SYNTAX 
    12  0 0.0 195 100.0 195 100.0  - SWANK-REPL::REPL-EVAL 
    13  0 0.0 195 100.0 195 100.0  - SWANK:EVAL-FOR-EMACS 
    14  0 0.0 195 100.0 195 100.0  - SWANK::PROCESS-REQUESTS 
    15  0 0.0 195 100.0 195 100.0  - (LAMBDA NIL :IN SWANK::HANDLE-REQUESTS) 
    16  0 0.0 195 100.0 195 100.0  - SWANK/SBCL::CALL-WITH-BREAK-HOOK 
    17  0 0.0 195 100.0 195 100.0  - (FLET SWANK/BACKEND:CALL-WITH-DEBUGGER-HOOK :IN "/Users/vleo/quicklisp/dists/quicklisp/software/slime-v2.19/swank/sbcl.lisp") 
    18  0 0.0 195 100.0 195 100.0  - SWANK::CALL-WITH-BINDINGS 
    19  0 0.0 195 100.0 195 100.0  - SWANK::HANDLE-REQUESTS 
    20  0 0.0 195 100.0 195 100.0  - (LABELS SWANK/SBCL::RUN :IN SWANK/BACKEND:ADD-FD-HANDLER) 
    21  0 0.0 195 100.0 195 100.0  - SB-IMPL::SUB-SUB-SERVE-EVENT 
    22  0 0.0 195 100.0 195 100.0  - SB-IMPL::SUB-SERVE-EVENT 
    23  0 0.0 195 100.0 195 100.0  - SB-SYS:WAIT-UNTIL-FD-USABLE 
    24  0 0.0 195 100.0 195 100.0  - SB-IMPL::REFILL-INPUT-BUFFER 
    25  0 0.0 195 100.0 195 100.0  - SB-IMPL::INPUT-CHAR/UTF-8 
    26  0 0.0 195 100.0 195 100.0  - (LAMBDA (&REST REST) :IN SB-IMPL::GET-EXTERNAL-FORMAT) 
    27  0 0.0 195 100.0 195 100.0  - READ-CHAR 
    28  0 0.0 195 100.0 195 100.0  - SB-IMPL::%READ-PRESERVING-WHITESPACE 
    29  0 0.0 195 100.0 195 100.0  - READ 
    30  0 0.0 195 100.0 195 100.0  - SB-IMPL::REPL-READ-FORM-FUN 
    31  0 0.0 195 100.0 195 100.0  - SB-IMPL::REPL-FUN 
    32  0 0.0 195 100.0 195 100.0  - (LAMBDA NIL :IN SB-IMPL::TOPLEVEL-REPL) 
    33  0 0.0 195 100.0 195 100.0  - SB-IMPL::%WITH-REBOUND-IO-SYNTAX 
    34  0 0.0 195 100.0 195 100.0  - SB-IMPL::TOPLEVEL-REPL 
    35  0 0.0 195 100.0 195 100.0  - SB-IMPL::TOPLEVEL-INIT 
    36  0 0.0 195 100.0 195 100.0  - (FLET #:WITHOUT-INTERRUPTS-BODY-74 :IN SAVE-LISP-AND-DIE) 
    37  0 0.0 195 100.0 195 100.0  - (LABELS SB-IMPL::RESTART-LISP :IN SAVE-LISP-AND-DIE) 
    38  0 0.0  69 35.4 195 100.0  1500 FACT-OPTI-ITER 
    39  0 0.0  65 33.3 195 100.0 1125750 FACT-REC 
    40  0 0.0  61 31.3 195 100.0  1500 FACT-ITER 
------------------------------------------------------------------------ 
      0 0.0          elsewhere 

Es gibt keine Erwähnung von fact-call obwohl es genannt sicher ist. Außerdem gibt es einen Eintrag für fact-rec. Wenn der Anruf fact-call tiefer im Stapel ist und fact-rec aufgezeichnet wird, sollte es nicht auch aufgezeichnet werden?

Danke

Answer 1

Bist Du sicher, dass der Anruf zu fact-call Aufenthalte auf dem Stapel? Hast du das überprüft?

Der SBCL-Compiler kann TCO (Tail Call-Optimierung) tun. Die Funktion fact-call ruft fact-rec in Endposition auf. Dieser Funktionsaufruf kann durch einen Sprung ersetzt werden, wobei der aktuelle Stapelrahmen wiederverwendet wird.

TCO

Lasst uns fact-rec ändern, so dass es break ruft und wir können auf dem Stapel aussehen:

(defun fact-rec (n) 
    (if (zerop n) 
     (progn (break) 1) 
    (* n (fact-rec (1- n))))) 

(defun fact-call (n) 
    (fact-rec n))  ; tail call to FACT-REC 

des Lassen Sie rufen von test:

(defun test() 
(fact-call 4)) 

Der Backtrace sieht so aus - no fact-call.

Backtrace: 
    0: (FACT-REC 0) 
    1: (FACT-REC 1) 
    2: (FACT-REC 2) 
    3: (FACT-REC 3) 
    4: (FACT-REC 4) 

Keine TCO

Nun sagen wir den SBCL Compiler TCO nicht in fact-call zu verwenden:

(defun fact-call (n) 
    (declare (optimize (debug 3))) ; debug level 3 does no TCO 
    (fact-rec n)) 

Nun ist dies das Call-Stack:

Backtrace: 
    0: (FACT-REC 0) 
    1: (FACT-REC 1) 
    2: (FACT-REC 2) 
    3: (FACT-REC 3) 
    4: (FACT-REC 4) 
    5: (FACT-CALL 4) 

Wie Sie können sehen, der Anruf an FACT-CALL bleibt auf dem Stapel.