为什么Racket的实现比MIT Scheme快得多？

Question

以下代码使用欧几里得算法计算gcd(a,b)和整数s、t，使得sa+tb=gcd(a,b)(用于离散数学课程)。我在C语言中编写了它，并且这可能会清楚地说明算法。

gcd.c:

#include <stdio.h>

int gcd_st(int m, int n, int *s, int *t) {
  int a, b, res, tmp;
  a = m>n?m:n;
  b = m>n?n:m;
  if(!b) {
    *s = 1;
    *t = 0;
    return a;
  }
  res = gcd_st(b, a%b, s, t);
  tmp = *t;
  *t = *s - *t*(a/b);
  *s = tmp;
  return res;
}

int main() {
  int st[2];
  for(int i=0; i<100000000; i++)
    gcd_st(42, 56, st, st+1);
  for(int i=0; i<100000000; i++)
    gcd_st(273, 110, st, st+1);

  int res = gcd_st(42, 56, st, st+1);
  printf("%d %d %d\n", res, st[0], st[1]);

  res = gcd_st(273, 110, st, st+1);
  printf("%d %d %d\n", res, st[0], st[1]);
}

出于兴趣，我决定用Scheme（Lisp）编写它。首先，我在MIT Scheme的实现上进行了测试，然后使用Racket的实现。

gcd.scm（去掉前两行）; gcd.rkt（包括前两行）：

#!/usr/bin/racket
#lang racket/base

(define (gcd_st m n)
  (let ((a (max m n)) (b (min m n)))
    (if (= b 0) (list a 1 0)
      (let ((res (gcd_st b (remainder a b))))
        (let ((val (list-ref res 0))
          (s (list-ref res 1))
          (t (list-ref res 2)))
            (list val t (- s (* t (quotient a b)))))))))

(define (loop n fn)
  (if (= n 0) 0
      (loop (- n 1) fn)))

(loop 100000000 (lambda () (gcd_st 42 56)))
(loop 100000000 (lambda () (gcd_st 273 110)))

(display "a b: (gcd s t)\n42 56: ")
(display (gcd_st 42 56))
(display "\n273 110: ")
(display (gcd_st 273 110))
(display "\n")

这两个程序在两个样例上运行了10^8次迭代，并且生成了相同的输出。然而，这两个Scheme实现（共享相同的代码/算法）在性能上存在很大差异。Racket实现比C实现更快，后者又比MIT-Scheme实现更快。

时间差别如此之大，以至于我认为Racket可能会优化整个循环，因为结果从未使用过，但时间似乎仍然与循环迭代呈线性关系。它是否可能在进行一些内省并优化掉循环中的某些代码？

$ time ./gcd.rkt  # Racket
0
0
a b: (gcd s t)
42 56: (14 1 -1)
273 110: (1 27 -67)

real  0m0.590s
user  0m0.565s
sys 0m0.023s

$ time scheme --quiet <gcd.scm  # MIT-Scheme
a b: (gcd s t)
42 56: (14 1 -1)
273 110: (1 27 -67)

real  0m59.250s
user  0m58.886s
sys 0m0.129s

$ time ./gcd.out  # C 
14 1 -1
1 27 -67

real  0m7.987s
user  0m7.967s
sys 0m0.000s

为什么Racket实现的速度要快得多？

=====

更新：如果有人想知道，这里是使用纠正后的循环函数（考虑答案）的结果：

循环：

(define (loop n fn)
    (fn)
    (if (= n 1) 0
        (loop (- n 1) fn)))

Racket（即使包括其设置时间）仍然略胜于C：

real    0m7.544s
user    0m7.472s
sys 0m0.050s

MIT Scheme

real    9m59.392s
user    9m57.568s
sys 0m0.113s

关于Scheme实现之间的巨大差异问题仍然存在（非常大），然而该问题将被单独提出以避免与先前错误混淆。

- Jonathan Lam

---

难道标签[tag:C]也不应该包括在内吗？你还没有包括C语言的编译命令。 - Will Ness

你可能想使用Racket的time表单来获取仅运行函数的时间，而不包括启动时间等：https://docs.racket-lang.org/reference/time.html#(form._((lib._racket%2Fprivate%2Fmore-scheme..rkt)._time)) - LiberalArtist

Racket/Scheme并不是特别优化的。例如，考虑quotient/remainder和多个值：https://docs.racket-lang.org/reference/generic-numbers.html#(def._((quote._~23~25kernel)._quotient%2Fremainder)) - LiberalArtist

LiberalArtist，尽管在循环中没有调用quotient和remainder，但问题在于它没有被调用。请参阅我的答案以获取详细信息。此外，虽然Racket并不特别优化，但请记住，在这篇文章中，它的表现比MIT Scheme更好，而不是更慢。因此，Racket不太优化不能成为答案。我仍然想知道为什么MIT Scheme在简单地从100万倒数时如此缓慢。 - mmachenry

感谢@LiberalArtist的建议。我想知道mmachenry所说的是否正确，因为这在修正后的代码中仍然应该是正确的。但这是另一个问题了。 - Jonathan Lam

@WillNess 这是标准的GCC编译（没有额外的标志），但现在Racket/C性能差异已经解决，我想这个问题现在已经无关紧要了。 - Jonathan Lam

Answer 1

您实际上没有调用在loop实现中调用计算的thunk。这就是为什么它比C实现快得多的原因。您实际上没有计算任何内容。

我不确定为什么MIT Scheme对此如此缓慢。仅仅从1亿开始计数似乎应该像在Racket中一样闪电般快速。

要实际计算最大公约数，丢弃结果并测量时间，请像这样实现loop：

(define (loop n fn)
  (if (= n 0) 0
      (begin
        (fn)
        (loop (- n 1) fn))))

- mmachenry

---

哦，我的天啊。这就是睡眠不足的后果。我本来以为我之前已经写过了，但可能是因为我太专注于其他细节，把这个问题归咎于方案实现。谢谢你。 - Jonathan Lam