5

考虑一下Chez Scheme代码：

（进口（chezscheme））

(define (list-enumerate ls val proc)
  (让循环 ((ls ls) (return?#f) (val val))
    （如果（或（null？ls）
            返回？）
        值
        （带值调用（lambda（）（proc val（car ls）））
          (lambda (return?val)
            （循环（cdr ls）返回？val））））））

（定义（列表索引 ls proc）
  （列表枚举ls
                  0
                  （拉姆达（我 elt）
                    (如果 (proc elt)
                        （值#ti）
                        (值 #f (+ i 1))))))

（定义 n 100000）

（定义数据（iota n））

（时间（列表索引数据（lambda (elt) (= elt (- n 1)))））

运行：

~ $ 方案 --script ~/scratch/_list-enumerate-allocation-test-chez-a.sps
（时间（列表索引数据...））
    没有收藏
    3 毫秒经过的 CPU 时间
    4 毫秒经过的实时时间
    分配了 8 个字节

哇，它报告只分配了 8 个字节。

--program让我们使用选项而不是再次运行它--script：

~ $ 方案 --program ~/scratch/_list-enumerate-allocation-test-chez-a.sps
（时间（列表索引数据...））
    没有收藏
    3 毫秒经过的 CPU 时间
    3 毫秒经过的实时时间
    分配了 800000 字节

哎呀，分配了 800000 字节。

有什么区别？

埃德

4

1 回答 1

8

以下是 Kent Dybvig 的回应：

这是一个有趣的问题。

当使用使用 REPL 语义的 --script 运行时，脚本中定义的变量（如 list-enumerate 和 list-index）是可变的，这会抑制包括内联在内的过程间优化。然而，当使用 --program 运行时，变量是不可变的，这允许过程间优化。

在这种情况下，--program 允许编译器将 list-enumerate 内联到 list-index 的正文中，然后将 list-index 正文中的 lambda 表达式内联到 list-enumerate 的正文中。最终结果是 call-with-values 生产者表达式中的条件表达式。这会导致编译器为使用者创建一个闭包，以避免沿着条件的 then 和 else 分支重复代码。每次通过 list-enumerate 的循环创建这个闭包，导致额外的分配开销。这就是优化经常采用的方式。大多数时候你会赢，但有时你会输。好消息是，总的来说，即使在您的计划中，收益也超过了他的成本。我将 list-index 的调用放在一个循环中（修改后的代码如下），发现使用 --program 后，代码运行速度提高了 30% 左右。

肯特

（进口（chezscheme））

(define (list-enumerate ls val proc)
  (让循环 ((ls ls) (return?#f) (val val))
    （如果（或（null？ls）
            返回？）
        值
        （带值调用（lambda（）（proc val（car ls）））
          (lambda (return?val)
            （循环（cdr ls）返回？val））））））

（定义（列表索引 ls proc）
  （列表枚举ls
                  0
                  （拉姆达（我 elt）
                    (如果 (proc elt)
                        （值#ti）
                        (值 #f (+ i 1))))))

（定义 n 100000）

（定义数据（时间（iota n）））

（让 （）
（定义 runalot
  （拉姆达（我 thunk）
    （让循环（[ii]）
      (让 ([x (thunk)])
        (如果 (fx=​​ i 1)
            X
            (循环 (fx- i 1)))))))

（时间
  (runalot 1000
    （拉姆达（）
      (列表索引数据 (lambda (elt) (= elt (- n 1))))))))
于 2010-03-04T16:56:08.763 回答