昨晩の件 - yamanetoshi's diary

fold-right とか left とかの件。
定義が以下。

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

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

大量のデータを吸わせて簡単な演算させてみたら処理時間に大きな差があったとの事。試してみます。

gosh> (use srfi-1)
#<undef>
gosh> (use gauche.time)
#<undef>
gosh> (time (fold-left + 0 (iota 1000000)))
;(time (fold-left + 0 (iota 1000000)))
; real   0.750
; user   0.690
; sys    0.020
499999500000
gosh> (time (fold-right + 0 (iota 1000000)))
;(time (fold-right + 0 (iota 1000000)))
; real   6.851
; user   0.950
; sys    0.100
499999500000
gosh>

確かに全然違うな。disasm してみた。

gosh> (disasm (lambda ()  (if (null? seq)
      init
      (op (car seq)
	  (fold-right op init (cdr seq))))))
main_code (name=#f, code=0x47ec00, size=24, const=8, stack=14):
args: #f
     0 GREF #<identifier user#seq>; seq
     2 BNNULL 7                 ; (null? seq)
     4 GREF #<identifier user#init>; init
     6 RET 
     7 GREF #<identifier user#seq>; seq
     9 CAR-PUSH                 ; (car seq)
    10 PRE-CALL(3) 21
    12 GREF-PUSH #<identifier user#op>; op
    14 GREF-PUSH #<identifier user#init>; init
    16 GREF #<identifier user#seq>; seq
    18 CDR-PUSH                 ; (cdr seq)
    19 GREF-CALL(3) #<identifier user#fold-right>; (fold-right op init (cdr seq))
    21 PUSH-GREF-TAIL-CALL(2) #<identifier user#op>; (op (car seq) (fold-right op init (cdr s ...
    23 RET 
#<undef>
gosh> (disasm (lambda ()     (if (null? rest)
	result
	(iter (op result (car rest))
	      (cdr rest)))))
main_code (name=#f, code=0x47eae0, size=22, const=7, stack=12):
args: #f
     0 GREF #<identifier user#rest>; rest
     2 BNNULL 7                 ; (null? rest)
     4 GREF #<identifier user#result>; result
     6 RET 
     7 PRE-CALL(2) 16
     9 GREF-PUSH #<identifier user#result>; result
    11 GREF #<identifier user#rest>; rest
    13 CAR-PUSH                 ; (car rest)
    14 GREF-CALL(2) #<identifier user#op>; (op result (car rest))
    16 PUSH-GREF #<identifier user#rest>; rest
    18 CDR-PUSH                 ; (cdr rest)
    19 GREF-TAIL-CALL(2) #<identifier user#iter>; (iter (op result (car rest)) (cdr rest))
    21 RET 
#<undef>
gosh>

むむむ。これって現実トウヒの範疇を越えてるなぁ。データが大量になると再起で処理時間消費しちゃう、って理解で良いのかどうなのか。
上記がビンゴかどうかは上記のインストラクションの中身を確認してみないと何とも言えないかも。

インストラクション見ても

ボトルネックは不明。むむむ、と言いつつ色々ヤッてみたら実行するタイミングで計測された時間にばらつきがある模様。同じ値で連続して実行してみた。

gosh> (time (fold-right + 0 (iota 1000000)))
;(time (fold-right + 0 (iota 1000000)))
; real   8.684
; user   0.630
; sys    0.090
499999500000
gosh> (time (fold-left + 0 (iota 1000000)))
;(time (fold-left + 0 (iota 1000000)))
; real   8.426
; user   0.460
; sys    0.070
499999500000
gosh> (time (fold-right + 0 (iota 1000000)))
;(time (fold-right + 0 (iota 1000000)))
; real  10.823
; user   3.350
; sys    0.090
499999500000
gosh> (time (fold-left + 0 (iota 1000000)))
;(time (fold-left + 0 (iota 1000000)))
; real   0.446
; user   0.430
; sys    0.000
499999500000
gosh> (time (fold-right + 0 (iota 1000000)))
;(time (fold-right + 0 (iota 1000000)))
; real   0.651
; user   0.600
; sys    0.010
499999500000
gosh> (time (fold-left + 0 (iota 1000000)))
;(time (fold-left + 0 (iota 1000000)))
; real   0.452
; user   0.430
; sys    0.000
499999500000
gosh> (time (fold-right + 0 (iota 1000000)))
;(time (fold-right + 0 (iota 1000000)))
; real   0.635
; user   0.610
; sys    0.010
499999500000
gosh> (time (fold-left + 0 (iota 1000000)))
;(time (fold-left + 0 (iota 1000000)))
; real   0.473
; user   0.430
; sys    0.000
499999500000
gosh> (time (fold-right + 0 (iota 1000000)))
;(time (fold-right + 0 (iota 1000000)))
; real   6.320
; user   5.870
; sys    0.050
499999500000
gosh> (time (fold-left + 0 (iota 1000000)))
;(time (fold-left + 0 (iota 1000000)))
; real   0.449
; user   0.430
; sys    0.010
499999500000
gosh> (time (fold-right + 0 (iota 1000000)))
;(time (fold-right + 0 (iota 1000000)))
; real   0.631
; user   0.600
; sys    0.000
499999500000
gosh> (time (fold-left + 0 (iota 1000000)))
;(time (fold-left + 0 (iota 1000000)))
; real   0.449
; user   0.440
; sys    0.010
499999500000
gosh>

fold-right
- 1 回目
  - ; real 8.684
  - ; user 0.630
  - ; sys 0.090
- 2 回目
  - ; real 10.823
  - ; user 3.350
  - ; sys 0.090
- 3 回目
  - ; real 0.651
  - ; user 0.600
  - ; sys 0.010
- 4 回目
  - ; real 0.635
  - ; user 0.610
  - ; sys 0.010
- 5 回目
  - ; real 6.320
  - ; user 5.870
  - ; sys 0.050
- 6 回目
  - ; real 0.631
  - ; user 0.600
  - ; sys 0.000

fold-left
- 1 回目
  - ; real 8.426
  - ; user 0.460
  - ; sys 0.070
- 2 回目
  - ; real 0.446
  - ; user 0.430
  - ; sys 0.000
- 3 回目
  - ; real 0.452
  - ; user 0.430
  - ; sys 0.000
- 4 回目
  - ; real 0.473
  - ; user 0.430
  - ; sys 0.000
- 5 回目
  - ; real 0.449
  - ; user 0.430
  - ; sys 0.010
- 6 回目
  - ; real 0.449
  - ; user 0.440
  - ; sys 0.010

がつん、って沢山時間がかかるケイス以外の時間見てみると若干繰り返しの方が早い程度でさほどの差異は無いように見えます。
しかしこの振れは一体何が原因なのでしょうか。OSX が微妙とか?

ペースト位置

間違えていた件。(とほほ