为什么 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 实现快得多，而 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 的实现速度如此之快？

======

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

loop：

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

Racket（仍然略胜于 C，甚至包括它的设置时间）：

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

麻省理工学院计划

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

然而，关于 Scheme 实现之间的巨大差异（仍然很大）的问题仍然存在。我会单独问这个问题，以忽略与上一个错误的混淆。

Answer 1

您实际上并没有调用在您的loop. 这就是为什么它比 C 实现快得多的原因。你实际上并没有计算任何东西。

我不确定为什么麻省理工学院计划这么慢。仅仅从 1 亿倒数似乎应该像在 Racket 中一样快如闪电。

要实际冗余地计算 gcd，丢弃结果，并测量时间，实现如下循环：

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