可以加快这个 Chez Scheme 微基准测试吗？

Question

这个双循环在 Chez Scheme 中比在 C++ 中慢 50 倍（分别用 --optimize-level 3 和 -O3 编译）

(import
  (rnrs)
  (rnrs r5rs))


(let* ((n (* 1024 16))
       (a (make-vector n))
       (acc 0))

  (do ((i 0 (+ i 1)))
    ((= i n) #f)
    (vector-set! a i (cons (cos i) (sin i))))

  (do ((i 0 (+ i 1)))
    ((= i n) #f)
    (do ((j 0 (+ j 1)))
      ((= j n) #f)
      (let ((ai (vector-ref a i))
            (aj (vector-ref a j)))
        (set! acc (+ acc (+ (* (car ai) (cdr aj))
                            (* (cdr ai) (car aj))))))))

  (write acc)
  (newline))

(exit)

对

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

typedef std::pair<double, double> pr;

typedef std::vector<pr> vec;

double loop(const vec& a)
{
    double acc = 0;
    const int n = a.size();

    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
        {
            const pr& ai = a[i];
            const pr& aj = a[j];
            acc += ai .first * aj.second + 
                   ai.second * aj .first;
        }

    return acc;
}

int main()
{
    const int n = 1024 * 16;

    vec v(n);

    for(int i = 0; i < n; ++i)
        v[i] = pr(std::cos(i), std::sin(i));

    std::cout << loop(v) << std::endl;
}

我意识到 Scheme 中的内存间接比 C++ 多，但性能差异仍然令人惊讶...

有没有简单的方法可以加快Scheme版本的速度？（没有将内存布局更改为完全不合常理的东西）

Answer 1

因此，尽管这些程序看起来确实相同，但它们并不相同。您在 C 版本中使用 fixnum 算法，而 Scheme 版本使用标准数字塔。要使 C 版本更像 Scheme，请尝试使用 bignum 库进行计算。

作为测试，我用 (rnrs arithmetic flonums) 和 (rnrs arithmetic fixnums) 替换了算术，它使 DrRacket 的执行时间减半。我希望在任何实施中都会发生同样的情况。

现在我的初步测试表明，C 代码的执行速度大约快 25 倍，而不是预期的 50 倍，通过更改为浮点运算，我发现 C 代码的执行速度大约快 15 倍。

我想我可以通过使用不安全的过程使它更快，因为 Scheme 确实在运行时检查每个参数的类型，它在每个过程之前执行操作，这在 C 版本中不会发生。作为测试，我将其更改为在我的实现中使用不安全的过程，现在它只慢了 10 倍。

希望它对 Chez 也有帮助 :)

编辑

这是我修改后的源代码，速度提高了 2 倍：

#!r6rs
(import
 (rnrs)
 ;; import the * and + that only work on floats (which are faster, but they still check their arguments)
 (only (rnrs arithmetic flonums) fl+ fl*))


(let* ((n (* 1024 16))
       (a (make-vector n))
       (acc 0.0)) ; We want float, lets tell Scheme about that!

  ;; using inexact f instead of integer i
  ;; makes every result of cos and sin inexact
  (do ((i 0 (+ i 1))
       (f 0.0 (+ f 1)))
    ((= i n) #f)
    (vector-set! a i (cons (cos f) (sin f))))

  (do ((i 0 (+ i 1)))
    ((= i n) #f)
    (do ((j 0 (+ j 1)))
      ((= j n) #f)
      (let ((ai (vector-ref a i))
            (aj (vector-ref a j)))
        ;; use float versions of + and *
        ;; since this is where most of the time is used
        (set! acc (fl+ acc
                       (fl+ (fl* (car ai) (cdr aj))
                            (fl* (cdr ai) (car aj))))))))

  (write acc)
  (newline))

具体的实现（锁定）只是为了说明在运行时完成的类型检查确实有影响此代码的运行速度比之前的优化快 30%：

#lang racket

;; this imports import the * and + for floats as unsafe-fl* etc. 
(require racket/unsafe/ops)

(let* ((n (* 1024 16))
       (a (make-vector n))
       (acc 0.0)) ; We want float, lets tell Scheme about that!

  (do ((i 0 (+ i 1))
       (f 0.0 (+ f 1)))
    ((= i n) #f)
    ;; using inexact f instead of integer i
    ;; makes every result of cos and sin inexact
    (vector-set! a i (cons (cos f) (sin f))))

  (do ((i 0 (+ i 1)))
    ((= i n) #f)
    (do ((j 0 (+ j 1)))
      ((= j n) #f)
      ;; We guarantee argument is a vector
      ;; and nothing wrong will happen using unsafe accessors
      (let ((ai (unsafe-vector-ref a i))
            (aj (unsafe-vector-ref a j)))
        ;; use unsafe float versions of + and *
        ;; since this is where most of the time is used
        ;; also use unsafe car/cdr as we guarantee the argument is
        ;; a pair.
        (set! acc (unsafe-fl+ acc
                              (unsafe-fl+ (unsafe-fl* (unsafe-car ai) (unsafe-cdr aj))
                                          (unsafe-fl* (unsafe-cdr ai) (unsafe-car aj))))))))

  (write acc)
  (newline))

我努力保持原代码的风格。这不是很惯用的 Scheme。例如。我根本不会使用set!，但它不影响速度。

可以加快这个 Chez Scheme 微基准测试吗？

Can one speed up this Chez Scheme microbenchmark?

scheme

chez-scheme