performance - Scheme:为什么Internal Definition比External Definition快？

Question

我试过运行下面的程序

(define (odd-internal x)
  (define (even x)
    (if (zero? x)
        #t
        (odd-internal (sub1 x))))
  (if (zero? x)
      #f
      (even (sub1 x))))

(define (odd-external x)
  (if (zero? x)
      #f
      (even (sub1 x))))

(define (even x)
  (if (zero? x)
      #t
      (odd-external (sub1 x))))

(begin (display "Using internal definition\n")
       (time (odd-internal 40000000)))

(begin (display "Using external definition\n")
       (time (odd-external 40000000)))

这是Racket中的结果

Using internal definition
cpu time: 166 real time: 165 gc time: 0
#f
Using external definition
cpu time: 196 real time: 196 gc time: 0
#f

您可以看到使用内部定义要快得多。我试过在 Chez Scheme 上运行，结果是相似的。这是为什么？

Answer 1

我很惊讶这与 Lexis 回答的评论有所不同，我在每个文件 internal.rkt 和 external.rkt 中拆分了两个版本并编译它们并以这种方式反编译它们:

raco make external.rkt
raco decompile compiled/external_rkt.zo

这比在宏步进器中查看完全展开的程序更进一步。它看起来非常不可读，所以我用机智的最重要的部分对其进行了美化:

(define (odd-external x1)
  (if (zero? x1)
      '#f
      (let ((x2 (sub1 x1)))
        (if (zero? x2)
            '#t
            (let ((x3 (sub1 x2)))
              (if (zero? x3)
                  '#f
                  (let ((x4 (sub1 x3)))
                    (if (zero? x4)
                        '#t
                        (let ((x5 (sub1 x4)))
                          (if (zero? x5) '#f (even (sub1 x5))))))))))))

(define (even x1)
  (if (zero? x1)
       '#t
       (let ((x2 (sub1 x1)))
         (if (zero? x2)
           '#f
           (let ((x3 (sub1 x2)))
             (if (zero? x3)
               '#t
               (let ((x4 (sub1 x3)))
                 (if (zero? x4)
                   '#f
                   (let ((x5 (sub1 x4)))
                     (if (zero? x5)
                       '#t
                       (let ((x6 (sub1 x5)))
                         (if (zero? x6)
                           '#f
                           (let ((x7 (sub1 x6)))
                             (if (zero? x7)
                               '#t
                               (odd-external (sub1 x7))))))))))))))))

这里没有什么特别的。它展开循环一定次数并不断折叠。请注意，我们仍然有相互递归，展开是 5 次和 7 次。常量甚至是常量折叠，所以它用 (even 399999995) 替换了我的调用，所以编译器也运行了代码 5 圈并放弃了。有趣的是内部版本:

(define (odd-internal x1)
  (if (zero? x1)
      '#f
      (let ((x2 (sub1 x1)))
        (if (zero? x2)
            '#t
            (let ((x3 (sub1 x2)))
              (if (zero? x3)
                  '#f
                  (let ((x4 (sub1 x3)))
                    (if (zero? x4)
                        '#t
                        (let ((x5 (sub1 x4)))
                          (if (zero? x5)
                              '#f
                              (let ((x6 (sub1 x5)))
                                (if (zero? x6)
                                    '#t
                                    (let ((x7 (sub1 x6)))
                                      (if (zero? x7)
                                          '#f
                                          (let ((x8 (sub1 x7)))
                                            (if (zero? x8)
                                                '#t
                                                (odd-internal
                                                 (sub1 x8))))))))))))))))))

它不再是相互递归，因为它在 8 次后调用了自己。每一轮进行 8 轮，而另一个版本进行 7 轮，然后 5 轮。在两轮中，内部版本进行了 16 轮，而另一轮进行了 12 轮。内部版本的初始调用是 (odd-internal '399999992 ) 所以编译器在放弃之前做了 8 轮。

我猜反编译器级别的函数中的代码是开放编码的，每一步的代码都非常便宜，这使得调用次数成为速度提高 25% 的原因。毕竟每次递归增加 4 次即增加 25%，这与计算时间的差异相吻合。这是基于观察的推测，因此 Lexi 对此发表评论会很有趣。