方案:为什么内部定义比外部定义更快? [英] Scheme: why is Internal Definition faster than External Definition?

问题描述

我尝试运行下面的程序

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

这是球拍的结果

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 上运行，结果是相似的.这是为什么?

There you can see using internal definition is quite a bit faster. I've tried running on Chez Scheme and the result is similar. Why is that?

推荐答案

我很惊讶这是不同的，所以从 Lexis 的回答中我将两个版本分开在每个文件中 internal.rkt 和 external.rkt 并以这种方式编译和反编译它们:

I was amazed that it was a difference so from the commens of Lexis answer I split the two version in each their file internal.rkt and external.rkt and compiled them and decompiled them in this way:

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

这比在宏步进器中查看完全扩展的程序更进一步.它看起来非常不可读，所以我用机智的最重要的部分来修饰它:

This goes one step further than looking at the fully expanded program in the macro stepper. It looks very non human readable so I have prettyfied it with the most important parts in tact:

(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 次.常量甚至是常量折叠，所以它用 (甚至 399999995) 替换了我的调用，所以编译器也运行了代码 5 圈并放弃了.有趣的是内部版本:

Nothing special here. It unrolls the loop a certain times and constant folds. Notice we still have mutual recursion and that the unrolling is 5 and 7 times. The constant was even constant folded so it had replaced my call with (even 399999995) so the compiler had also run the code 5 turns and given up. The interesting thing is the internal version:

(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 轮才放弃.

It is no longer mutual recursion since it calls itself after 8 times. An each round does 8 turns while the other version did 7, then 5.. In two rounds the internal one has done 16 rounds while the other has 12. The initial call on the internal one is (odd-internal '399999992) so the compiler did 8 rounds before giving up.

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

I guess the code in side the functions at the decompiler level are open coded and the code at each step is very cheap making the number of calls the reason for the 25% speed increase. After all 4 more is 25% more per recursion that coincides with the difference in computing time. This is speculations based on observation so it would be interesting to have a comment from Lexi on this.

这篇关于方案:为什么内部定义比外部定义更快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！