ソートのパフォーマンスチューニング
以下のsort1とsort2はパフォーマンスが2倍以上も違う。この速度差はどこから来るのか。
(use gauche.time) (define-class() *1 (define l '()) (define i 0) (while (< i 30000) (set! l (list* 1 2 3 4 5 6 7 8 9 0 l)) (inc! i)) (define (cmp a b c) (if (< a b) #t #f)) (define (sort1 seq x) (sort seq (lambda (a b) (cmp a b (ref x 'p))))) (define (sort2 seq x) (let1 xp (ref x 'p) (sort seq (lambda (a b) (cmp a b xp))))) (time (sort1 l dummy)) (time (sort2 l dummy))
sort1とsort2で違うところは先に(ref x 'p)の結果をxpに束縛しているかどうかだけだが、この差が劇的な効果をもたらす。考えてみれば当たり前の話で、sort1は比較関数を呼ぶたびに(ref x 'p)を実行している。比較関数はなんだかすごい何回も呼ばれるので、その中で無駄な呼出しをしていると遅くなるわけだ。
考えてみたら当たり前の話のような気がするんだけど、今日はここではまってなかなかチューニングがうまくいかなかったのでメモしておく。
