Clojure勉強日記（その９ ３．２ 性能の最適化

こんにちは。

徐々に書けることが広がってきてはいますが、まだ４分の１。
とりあえず地道に続けます。

前章で述べたJavaの呼び出しで述べた方法を使ってJavaを呼ぶのがClojureでは普通。
これで基本的には十分に高速のはずだが、さらに高速化を行うことができる。
これは外部IFには影響を与えずに出来るため、後からチューニング・・・ということも可能。

1.性能のためにプリミティブを使う

これまではパラメータに型情報をつけていなかった。
＃メタデータで型ヒントをつけられるということについては書いてましたが。
これはコードをすっきりさせるが、その分データ型がわかりにくくなり、性能上のオーバヘッドも発生する。
　→　このやり方をダックタイピングという模様。

例として、１からｎまで足し合わせる関数を考える。

(defn sum-to [n] 
    (loop [i 1 sum 0]
        (if (<= i n)
            (recur (inc i) (+ i sum))
                sum)))
#'user/sum-to
user=> (sum-to 100)
5050

この関数の実行時間を計測する。計測には下記のdotimesマクロとtime関数が使用できる。
(dotimes bindings & body)
; bindings => name n
dotimesはnameを0〜n-1までバインドしながら繰り返し実行する。
今回の場合はname自体は用いないため_にバインドさせて実行する。

user=> (dotimes [_ 10](time (sum-to 100000)))
"Elapsed time: 1.228224 msecs"
"Elapsed time: 1.26989 msecs"
"Elapsed time: 1.176595 msecs"
"Elapsed time: 1.180218 msecs"
"Elapsed time: 1.123155 msecs"
"Elapsed time: 1.196522 msecs"
"Elapsed time: 1.542979 msecs"
"Elapsed time: 0.825156 msecs"
"Elapsed time: 0.706501 msecs"
"Elapsed time: 0.820627 msecs"
nil

※追記
更に、criteriumを使って計測を行う。
すると結果は下記の通り。

user=> (crit/bench (sum-to 100000))
WARNING: Final GC required 1.6129901392836168 % of runtime
Evaluation count : 49500 in 60 samples of 825 calls.
             Execution time mean : 1.260639 ms
    Execution time std-deviation : 47.370884 μs
   Execution time lower quantile : 1.210134 ms ( 2.5%)
   Execution time upper quantile : 1.382792 ms (97.5%)
                   Overhead used : 4.145950 ns

Found 6 outliers in 60 samples (10.0000 %)
        low-severe       5 (8.3333 %)
        low-mild         1 (1.6667 %)
 Variance from outliers : 23.8473 % Variance is moderately inflated by outliers

これを更に高速化するにはClojureの関数に対して追記し、int型であることを通知する。
※2013/04/20 下記のコードにバグがあったため更新済み

(defn sum-to-int [n] 
    (let [n (int n)]
    (loop [i (int 1) sum (int 0)]
        (if (<= i (int i) n (int n))
            (recur (inc i) (+ i sum))
                sum))))

こうすると実行時間は下記のようになる。

user=> (dotimes [_ 10](time (sum-to-int 100000)))
"Elapsed time: 20.259719 msecs"
"Elapsed time: 16.261216 msecs"
"Elapsed time: 10.265046 msecs"
"Elapsed time: 10.58161 msecs"
"Elapsed time: 10.351546 msecs"
"Elapsed time: 10.111971 msecs"
"Elapsed time: 10.428989 msecs"
"Elapsed time: 11.088387 msecs"
"Elapsed time: 10.124652 msecs"
"Elapsed time: 10.366943 msecs"

user=> (crit/bench (sum-to-int 100000))
Evaluation count : 4680 in 60 samples of 78 calls.
             Execution time mean : 13.179291 ms
    Execution time std-deviation : 450.355311 μs
   Execution time lower quantile : 12.837863 ms ( 2.5%)
   Execution time upper quantile : 14.645732 ms (97.5%)
                   Overhead used : 4.145950 ns

Found 7 outliers in 60 samples (11.6667 %)
        low-severe       2 (3.3333 %)
        low-mild         5 (8.3333 %)
 Variance from outliers : 20.6197 % Variance is moderately inflated by outliers

・・・・て、むしろ逆に遅くなった。というか何故こうなった。
・・・そのため、結局型明記による実行時間向上についてはさっぱりという状況。
動的に型を確定させる場合でも、一度確定させれば以後速くなるなどの措置があるんでしょうか・・・？

型明記の他に、Clojureの一般的な演算子は結果がオーバーフローしないかどうかチェックしている。
それを無視させるとさらに速度は上がる。
・・・とはいえ、型明記に比べると恩恵は随分小さくなるが。

user=> (defn sum-to-uncheck [n]
    (let [n (int n)]
    (loop [i (int 1) sum (int 0)]
        (if (<= i (int i) n (int n))
            (recur (inc i) (unchecked-add i sum))
                sum))))
#'user/sum-to-uncheck
user=> (dotimes [_ 10](time (sum-to-uncheck 100000)))
"Elapsed time: 18.555974 msecs"
"Elapsed time: 17.44641 msecs"
"Elapsed time: 10.129634 msecs"
"Elapsed time: 10.635956 msecs"
"Elapsed time: 10.423101 msecs"
"Elapsed time: 10.402721 msecs"
"Elapsed time: 10.794918 msecs"
"Elapsed time: 10.510054 msecs"
"Elapsed time: 11.55078 msecs"
"Elapsed time: 10.513225 msecs"

とはいえ、intでの型ヒントをつけた状態はごちゃごちゃしており、可読性が犠牲になる。
基本は型ヒントなしのバージョンで行い、ボトルネックとなった場合に対処する・・・くらいでいいらしい。

尚、sum-toの例はClojureとしてはばか正直な書き方で、実際はreduceを使用して書く。
シーケンスの総和を求めることはまず最初の２つの要素を加算し、それを次の要素に加算し・・・
と繰り返すことだから。
reduceを使用すると同様の処理は下記のようになる。
・・・なのだが、実は遅い（汗

user=> (defn better-sum [n] (reduce + (range 1 (inc n))))
#'user/better-sum
user=> (dotimes [_ 10](time (better-sum 100000)))
"Elapsed time: 7.456752 msecs"
"Elapsed time: 7.226687 msecs"
"Elapsed time: 3.628515 msecs"
"Elapsed time: 3.518917 msecs"
"Elapsed time: 3.718639 msecs"
"Elapsed time: 4.544701 msecs"
"Elapsed time: 3.505783 msecs"
"Elapsed time: 3.466834 msecs"
"Elapsed time: 3.611758 msecs"
"Elapsed time: 3.701429 msecs"

実際のところ、ここで行うべきは「正しいアルゴリズムを選択する」ということ。
今回の場合1〜nの合計はn * (n + 1) / 2 で求められる。
その場合型ヒントを使わなくても繰り返しを行うどんなバージョンより早い。

user=> (defn best-sum [n] (/ (* n (inc n)) 2))
#'user/best-sum
user=> (dotimes [_ 10](time (best-sum 100000)))
"Elapsed time: 0.072461 msecs"
"Elapsed time: 0.00951 msecs"
"Elapsed time: 0.014945 msecs"
"Elapsed time: 0.009057 msecs"
"Elapsed time: 0.009058 msecs"
"Elapsed time: 0.009058 msecs"
"Elapsed time: 0.008605 msecs"
"Elapsed time: 0.014039 msecs"
"Elapsed time: 0.008604 msecs"
"Elapsed time: 0.009057 msecs"

性能というのは厄介だが、速度をあげようとしてコードをいたずらにごちゃごちゃさせるのが一番NG。
まず適切なアルゴリズムを選んで正しく動くコードを書く。
・・・これについては、Clojureだろうが、他の言語だろうが変わらない模様。

2.型ヒントの付与

Clojureでは関数の仮引数、letのバインド、変数名、式に型ヒントをつけることができる。
型ヒントは下記の役目を持つ。

1. 性能上クリティカルなパスの最適化

ClojureとJava世界のやり取りはリフレクションを用いた型変換を用いているが、
それを一部省略させることが可能。

1. 要求されている型のドキュメント

docの返り値？

1. 要求された型をランタイムに強制する

結果、１つ目の性能の件もあるが、安全性も増す。

スペシャル変数*warn-on-reflection*にtrueをセットすると、ClojureがJavaとの間でどれくらい情報を推測しているかを知ることができる。
その上で、関数を定義すると下記のようなwarningが出る。

user=> (set! *warn-on-reflection* true)
true
user=> (defn describe-class [clazz] {:name (. clazz getName) :final (java.lang.reflect.Modifier/isFinal (. clazz getModifiers)) })
Reflection warning, NO_SOURCE_PATH:3:37 - reference to field getName can't be resolved.
Reflection warning, NO_SOURCE_PATH:3:98 - reference to field getModifiers can'tbe resolved.

これはClojureが変数clazzの型が関数定義時点では分からないために発生しているエラーである模様。
リードメタデータを用いて型ヒントを指定してやると警告は発生されなくなる。

user=> (defn describe-class [#^Class clazz] {:name (. clazz getName) :final (java.lang.reflect.Modifier/isFinal (. clazz getModifiers)) })
#'user/describe-class

警告が表示されない状態ではClojureのコードはJavaのコードと同等にコンパイルされ、同等のスピードを持つ。
その上で、当然ながらClass以外のものを渡すとClassCastExceptionが投げられる。

user=> (describe-class "Test")
ClassCastException java.lang.String cannot be cast to java.lang.Class  user/describe-class (NO_SOURCE_FILE:4)
user=> (describe-class :class)
ClassCastException clojure.lang.Keyword cannot be cast to java.lang.Class  user/describe-class (NO_SOURCE_FILE:4)
user=> (describe-class 10)
ClassCastException java.lang.Long cannot be cast to java.lang.Class  user/describe-class (NO_SOURCE_FILE:4)

あとは性能的にはどれほど差分が出るかを確認する。
■型ヒントなし

user=> (defn describe-class [clazz] {:name (. clazz getName) :final (java.lang.reflect.Modifier/isFinal (. clazz getModifiers)) })
Reflection warning, NO_SOURCE_PATH:20:37 - reference to field getName can't be resolved.
Reflection warning, NO_SOURCE_PATH:20:98 - reference to field getModifiers can't be resolved.
#'user/describe-class
user=> (time (dotimes [_ 10000] (describe-class (. "Test" getClass))))
"Elapsed time: 73.380385 msecs"
"Elapsed time: 74.76939 msecs"
"Elapsed time: 178.357795 msecs"
"Elapsed time: 128.481343 msecs"
"Elapsed time: 64.758774 msecs"
"Elapsed time: 86.242378 msecs"
"Elapsed time: 73.174775 msecs"
"Elapsed time: 85.438503 msecs"

■型ヒントあり

user=> (defn describe-class [#^Class clazz] {:name (. clazz getName) :final (java.lang.reflect.Modifier/isFinal (. clazz getModifiers)) })
#'user/describe-class
user=> (time (dotimes [_ 10000] (describe-class (. "Test" getClass))))
"Elapsed time: 3.446923 msecs"
"Elapsed time: 3.702352 msecs"
"Elapsed time: 2.0235 msecs"
"Elapsed time: 4.013033 msecs"
"Elapsed time: 3.946005 msecs"
"Elapsed time: 3.884413 msecs"
"Elapsed time: 3.621738 msecs"
"Elapsed time: 3.367668 msecs"

かなり大きな違いが出ることがわかる。
今回の場合メソッドの規模が小さいためにリフレクションによる負荷の割合が大きいのかもしれないが、２０倍程の処理時間の差分が発生している。
・・・とりあえず、呼び出し回数が非常に多くなると推測される場合は利用者側で書きにくくならない程度に
型ヒントを付与するのが無難・・・に思える今日この頃。
とはいえ、これも静的型付け言語に慣れ過ぎたからなのかもしれないが。

尚、先ほどは型ヒントによってクラスキャストを避けることができたが、
型ヒントを付与したオブジェクトに対してJavaのメソッド呼び出しを一切行わなければClojureはキャストも挿入しない。

user=> (defn wants-a-string [#^String target] (println target))
#'user/wants-a-string
user=> (wants-a-string :keyword)
:keyword
nil
user=> (wants-a-string 11111)
11111
nil
user=> (wants-a-string "Test")
Test
nil

ちなみに型ヒントを付与せずに実行しても警告も発生しない。

user=> (defn wants-a-string [target] (println target))
#'user/wants-a-string

Clojure側はwants-a-stringが引数を文字列として扱っていないことを解析できる（printlnはどんなオブジェクトでも出力しようとする）。
そのため、Clojureはtargetを文字列にキャストしようとせず、結果問題も発生しない。
尚、Javaのメソッドを呼び出すと例えObject型のメソッドを用いた場合でも警告は発生する。

user=> (defn wants-a-string [target] (.toString target))
Reflection warning, NO_SOURCE_PATH:42:31 - reference to field toString can't beresolved.
#'user/wants-a-string

ただ、この場合型ヒントをつければ何を引数として渡そうがObject型という条件は満たされることとなるため、
警告は発生しないし、当然ながらClassCastExceptionも発生しない。
ということはObject型を引数として受け取ることを想定する場合はとりあえず型ヒントをつけておく・・・
というのもありかもしれない。そんな状況があるのかどうかはまた別の話になるが。

user=> (defn wants-a-string [#^Object target] (.toString target))
#'user/wants-a-string
user=> (wants-a-string "Test")
"Test"

内部でClojureがどうやってクラス変換を試みているかが若干垣間見えた章なので中々面白い話でした。