SBCL的统计分析器不显示每个被调用函数的条目

Question

我正在使用SBCL的统计分析器来分析这些功能:

(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))

为了评估递归版本的权重,我定义了一个fact-call在所有fact-rec调用之下保留在堆栈上的函数,以便可以正确监视它.这是我的分析代码:

(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)))

继续这样做可以确保fact-rec永远不会直接调用它,如果它出现在探查器的报告中,则必然会被调用fact-call.但这是我得到的报告:

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

fact-call尽管它确实被称为,但没有提及.此外还有一个条目fact-rec.如果fact-call呼叫在堆栈中更深并且fact-rec被记录,那么它是否也不应该被记录？

谢谢

Answer 1

你确定呼叫fact-call留在堆栈上吗？你检查过了吗？

SBCL编译器可以执行TCO(尾调用优化).该函数fact-call调用fact-rec中的末尾位置.此函数调用可以由跳转替换,重用当前堆栈帧.

TCO

让我们修改fact-rec,以便它调用break,我们可以查看堆栈:

(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

我们来自test:

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

回溯看起来像这样 - 没有fact-call.

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

没有TCO

现在我们告诉SBCL编译器不要在里面使用TCO fact-call:

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

现在这是调用堆栈:

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)

正如您所看到的,呼叫FACT-CALL停留在堆栈上.