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。这个函数调用可以用跳转代替，重用当前栈帧。

总拥有成本

让我们修改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 的调用保留在堆栈中。

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

SBCL's statistical profiler does not show an entry for each function called

lisp

common-lisp

profiler

sbcl