fold-right とか fold-left とかその後

直前エントリに shiro さんからフォロー頂いた。起動して 10 日経ってるマシンで負荷試験するなよ、って話な模様 (わら
色々教えて頂いたので試してみます。

とりあえず

自宅 thinkpad R61e なでびあん号で試してみます。以下なファイルを用意してます。
fold-right.scm

(use srfi-1)

(define (fold-rignt op init seq)
  (if (null? seq)
      init
      (op (car seq)
	  (fold-right op init (cdr seq)))))

(define (main args)   ;entry point
  (fold-right + 0 (iota 1000000)))

fold-left.scm

(use srfi-1)

(define (fold-left op init seq)
  (define (iter result rest)
    (if (null? rest)
	result
	(iter (op result (car rest))
	      (cdr rest))))
  (iter init seq))

(define (main args)   ;entry point
  (fold-left + 0 (iota 1000000)))

で、何度か実行。

$ time gosh ./fold-left.scm

real    0m1.143s
user    0m0.856s
sys     0m0.024s
$ time gosh ./fold-right.scm

real    0m2.012s
user    0m1.380s
sys     0m0.092s
$ time gosh ./fold-left.scm

real    0m0.823s
user    0m0.712s
sys     0m0.012s
$ time gosh ./fold-right.scm

real    0m3.670s
user    0m1.112s
sys     0m0.104s
$ time gosh ./fold-left.scm

real    0m1.233s
user    0m0.864s
sys     0m0.024s
$ time gosh ./fold-right.scm

real    0m4.018s
user    0m1.300s
sys     0m0.108s
$ time gosh ./fold-left.scm

real    0m1.195s
user    0m0.856s
sys     0m0.020s
$ time gosh ./fold-right.scm 

real    0m1.949s
user    0m1.348s
sys     0m0.088s
$ time gosh ./fold-left.scm 

real    0m1.150s
user    0m0.860s
sys     0m0.016s
$

shiro さん曰く

realが大きくてuserもsysも上がってないということは、OSが他のプロセスにかまけていたか、外部要因(ディスクのIOなど)を待っていた、ということです。

との事ですが OS 周り含め、time が戻すソレをきちんと確認した方が良さげ。

-fcollect-stats オプション

これも面白そう。それぞれ試してみました。以下。

$ gosh -fcollect-stats ./fold-left.scm 

;; Statistics (*: main thread only):
;;  GC: 14086144bytes heap, 47258872bytes allocated
;;  stack overflow*: 0times, 0.00ms total/0.00ms avg
$ gosh -fcollect-stats ./fold-right.scm 

;; Statistics (*: main thread only):
;;  GC: 92938240bytes heap, 96465640bytes allocated
;;  stack overflow*: 1101times, 597.18ms total/0.54ms avg
$

非末尾再起な fold-right はがっつり overflow してますな。そーゆー意味では fold-right の性能が fold-left と比べてさほど良くないのはこのあたりが影響してる可能性は大きい模様。