为什么 Racket 的实现比 MIT Scheme 快这么多?
Why is Racket implementation so much faster than MIT Scheme?
以下代码使用欧几里德算法计算 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 实现(共享相同的 code/algorithm)在性能上有很大差异。 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)))
球拍(仍然稍微优于 C,甚至包括它的准备时间):
real 0m7.544s
user 0m7.472s
sys 0m0.050s
MIT 方案
real 9m59.392s
user 9m57.568s
sys 0m0.113s
但是,关于 Scheme 实现之间的巨大差异(仍然很大)的问题仍然存在。我将单独询问此问题以忽略与先前错误的混淆。
您实际上并没有调用在 loop
的实现中调用计算的 thunk。这就是为什么它比 C 实现快得多的原因。你实际上并没有计算任何东西。
我不确定为什么 MIT Scheme 对此如此缓慢。只是从 1 亿开始倒数似乎应该像在 Racket 中一样快如闪电。
要真正冗余地计算 gcd,丢弃结果,并测量时间,像这样实现循环:
(define (loop n fn)
(if (= n 0) 0
(begin
(fn)
(loop (- n 1) fn))))
以下代码使用欧几里德算法计算 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 实现(共享相同的 code/algorithm)在性能上有很大差异。 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)))
球拍(仍然稍微优于 C,甚至包括它的准备时间):
real 0m7.544s
user 0m7.472s
sys 0m0.050s
MIT 方案
real 9m59.392s
user 9m57.568s
sys 0m0.113s
但是,关于 Scheme 实现之间的巨大差异(仍然很大)的问题仍然存在。我将单独询问此问题以忽略与先前错误的混淆。
您实际上并没有调用在 loop
的实现中调用计算的 thunk。这就是为什么它比 C 实现快得多的原因。你实际上并没有计算任何东西。
我不确定为什么 MIT Scheme 对此如此缓慢。只是从 1 亿开始倒数似乎应该像在 Racket 中一样快如闪电。
要真正冗余地计算 gcd,丢弃结果,并测量时间,像这样实现循环:
(define (loop n fn)
(if (= n 0) 0
(begin
(fn)
(loop (- n 1) fn))))