代码之家 › 专栏 › 技术社区 › dharmatech

Chez方案分配:--程序vs-脚本

chez-scheme scheme

4

dharmatech · 技术社区 · 16 年前

想想这一点 Chez Scheme 代码:

(import (chezscheme))

(define (list-enumerate ls val proc)
  (let loop ((ls ls) (return? #f) (val val))
    (if (or (null? ls)
            return?)
        val
        (call-with-values (lambda () (proc val (car ls)))
          (lambda (return? val)
            (loop (cdr ls) return? val))))))

(define (list-index ls proc)
  (list-enumerate ls
                  0
                  (lambda (i elt)
                    (if (proc elt)
                        (values #t i)
                        (values #f (+ i 1))))))

(define n 100000)

(define data (iota n))

(time (list-index data (lambda (elt) (= elt (- n 1)))))

运行它:

~ $ scheme --script ~/scratch/_list-enumerate-allocation-test-chez-a.sps 
(time (list-index data ...))
    no collections
    3 ms elapsed cpu time
    4 ms elapsed real time
    8 bytes allocated

哇,报告说只分配了8个字节。

让我们使用 --program 选择而不是 --script :

~ $ scheme --program ~/scratch/_list-enumerate-allocation-test-chez-a.sps 
(time (list-index data ...))
    no collections
    3 ms elapsed cpu time
    3 ms elapsed real time
    800000 bytes allocated

是的,分配了800000字节。

有什么不同吗?

预计起飞时间

1 回复 | 直到 8 年前

1

5

dharmatech 16 年前

以下是Kent Dybvig的回复:

这是个有趣的问题。

当使用--script(使用REPL语义)运行时,变量脚本中定义的列表枚举和列表索引是可变的, 它抑制了过程间的优化,包括内联。什么时候? 但是,变量是不可变的,这允许程序间优化。

在这种情况下,--程序允许编译器将列表枚举内联到列表索引的主体,然后是列表索引中的lambda表达式 body into list枚举的body。最终结果是有条件的调用中的表达式,值为producer表达式。这会导致编译器为使用者创建一个闭包,以避免代码沿着条件的then和else分支重复。这个每次通过list枚举的循环创建闭包,结果额外的分配开销。这就是优化经常采用的方式。多数情况下你赢了,但有时你输了。好消息是,总的来说即使在你的项目中,收益也大于成本。我打电话给在循环中列出索引(修改后的代码如下),并发现 --程序,代码运行速度大约快30%。

肯特

(import (chezscheme))

(define (list-enumerate ls val proc)
  (let loop ((ls ls) (return? #f) (val val))
    (if (or (null? ls)
            return?)
        val
        (call-with-values (lambda () (proc val (car ls)))
          (lambda (return? val)
            (loop (cdr ls) return? val))))))

(define (list-index ls proc)
  (list-enumerate ls
                  0
                  (lambda (i elt)
                    (if (proc elt)
                        (values #t i)
                        (values #f (+ i 1))))))

(define n 100000)

(define data (time (iota n)))

(let ()
(define runalot
  (lambda (i thunk)
    (let loop ([i i])
      (let ([x (thunk)])
        (if (fx= i 1)
            x
            (loop (fx- i 1)))))))

(time
  (runalot 1000
    (lambda ()
      (list-index data (lambda (elt) (= elt (- n 1))))))))