Clojureプログラムを高速化するためのテクニック集です。
本稿に書いてある手法が全てではありません。個々の手法について細かく書いてはいないため、詳しい情報は他の文献を参照してください。また、Clojureプログラムの外側（JVMなど）については記述していません。
Premature optimization is the root of all evil.
-- Donald Knuth
過度なチューニングは保守性や可読性を犠牲にする場合があるので、注意が必要です。
Measure. Don't tune for speed until you've measured, and even then don't unless one part of the code overwhelms the rest.
-- Rob Pike
ボトルネックをきちんと調査した上で、適切なパフォーマンスチューニングを行いましょう。
Clojureのバージョンはv1.8、測定ツールとしてcriterium v0.4.4を使用しています。コード中に現れるbench関数はcriteriumのものです。benchは様々な情報を出力してくれますが、ここでは簡略化のため、平均実行時間と標準偏差のみを記します。
測定コードはtotakke/clj-perf-tipsで公開しています。自分の環境で測定してみたい場合はご利用ください。
(defn str-len [^String s] (.length s))
型ヒントを付けることでリフレクションを避け、高速化できます。
;; 型ヒントあり
(defn len-a [^String s] (.length s)) (bench (dotimes [_ 100000] (len-a "にゃんぱすー")))
;; mean: 662.186948 µs, sd: 25.343870 µs ;; 型ヒントなし
(defn len-b [s] (.length s)) (bench (dotimes [_ 100000] (len-b "にゃんぱすー")))
;; mean: 335.416292 ms, sd: 10.796219 ms
Javaの呼び出しを行っている箇所ではかなりの高速化を期待できます。
リフレクションが発生する箇所は、*warn-on-reflection*をtrueにしておくと警告してくれます。ただし、依存ライブラリの警告も出力してしまうので、ログが見づらくなる可能性があります。パフォーマンスの求められるプロジェクトや、他プロジェクトに影響を及ぼすライブラリでは、警告を有効化しておくとよいでしょう。
Leiningenを使っている場合、project.cljに、
:profiles {:dev {:global-vars {*warn-on-reflection* true}}}
を設定しておくと良いかもしれません。
(defn calc [^long x] (* (+ x 5) 2))
関数の引数に対してプリミティブヒントを付けることでBoxingを避け、高速化できます。
ただし、プリミティブヒントは関数の引数に対してのみ付けられ、最大4つまで、型は^long, ^doubleの2種類のみとなっています。
;; プリミティブヒントあり
(defn a [^long x] (* (+ x 5) 2)) (bench (dotimes [_ 10000000] (a 2)))
;; mean: 18.855526 ms, sd: 600.759563 µs ;; プリミティブヒントなし
(defn b [x] (* (+ x 5) 2)) (bench (dotimes [_ 10000000] (b 2)))
;; mean: 56.192936 ms, sd: 1.817249 ms
(loop [i n, v (transient [])] (if (pos? i) (recur (dec i) (conj! v i)) (persistent! v))))
transientを使うことで一時的にミュータブルなデータ構造を作成し、高速化できます。
;; transientあり
(defn a [n] (loop [i n, v (transient [])] (if (pos? i) (recur (dec i) (conj! v i)) (persistent! v)))) (bench (dorun (a 1000000)))
;; mean: 53.700572 ms, sd: 1.787463 ms ;; transientなし
(defn b [n] (loop [i n, v []] (if (pos? i) (recur (dec i) (conj v i)) v))) (bench (dorun (b 1000000)))
;; mean: 78.853684 ms, sd: 1.015361 ms
シーケンス処理の際、reduceなどの高階関数よりも、loop/recurを用いたほうが速くなることがあります。
(bench (loop [i 1, s 0] (if (< i 10000000) (recur (+ i 2) (+ s i)) s)))
;; mean: 7.564495 ms, sd: 127.632208 µs (bench (->> (range 10000000) (filter odd?) (reduce +)))
;; mean: 416.546250 ms, sd: 3.754950 ms
:constタグを使用することでvarをインライン化できます。
;; :constあり
(def ^:const a 10) (bench (dotimes [_ 10000000] (inc a)))
;; mean: 5.287694 ms, sd: 488.191900 µs ;; :constなし
(def b 10) (bench (dotimes [_ 10000000] (inc b)))
;; mean: 105.936600 ms, sd: 10.700749 ms
多重ディスパッチを行う場合、マルチメソッドよりプロトコルを使用したほうが速いようです。
;; マルチメソッド
(defmulti sum-a class) (defmethod sum-a clojure.lang.PersistentVector [coll] (reduce + coll)) (defmethod sum-a clojure.lang.PersistentList [coll] (reduce + coll)) (bench (dotimes [_ 100000] (sum-a (vec (range 10)))))
;; mean: 84.119469 ms, sd: 1.229922 ms ;; プロトコル
(defprotocol Summable (sum-b [this])) (extend-protocol Summable clojure.lang.PersistentVector (sum-b [coll] (reduce + coll)) clojure.lang.PersistentList (sum-b [coll] (reduce + coll))) (bench (dotimes [_ 100000] (sum-b (vec (range 10)))))
;; mean: 76.328384 ms, sd: 1.715700 ms
メモ化などにより過去の計算結果をキャッシュしておくことで、空間効率と引き換えに時間効率を高めることができます。
;; メモ化あり
(defn a [n] (reduce + (range (inc n)))) (def a (memoize a)) (bench (dotimes [_ 1000000] (a 10)))
;; mean: 157.453862 ms, sd: 4.522523 ms ;; メモ化なし
(defn b [n] (reduce + (range (inc n)))) (bench (dotimes [_ 1000000] (b 10)))
;; mean: 319.929337 ms, sd: 11.463727 ms
並列化することで高速化を図りましょう。
(defn inc-after [n] (Thread/sleep 10) (inc n)) ;; 並列化あり
(bench (dorun (pmap inc-after (range 100))))
;; mean: 50.175887 ms, sd: 936.942738 µs ;; 並列化なし
(bench (dorun (map inc-after (range 100))))
;; mean: 1.217942 sec, sd: 16.667079 ms
Clojureにはリスト、ベクタ、マップなど、様々なデータ構造が用意されています。各データ構造の特性を理解しておくことが大切です。
同じ処理関数でもデータ構造によって著しくパフォーマンスが異なる場合があります。たとえば、ベクタに対するnthは速いですが、リストに対するnthは遅いです。
(def alist (list* (range 1000)))
(def avec (vec (range 1000))) ;; リストに対するnth
(bench (dotimes [_ 100000] (nth alist 999)))
;; mean: 717.114923 ms, sd: 98.263191 ms ;; ベクタに対するnth
(bench (dotimes [_ 100000] (nth avec 999)))
;; mean: 817.346025 µs, sd: 14.691106 µs
また、同じ機能を持つ関数でも計算量が異なることがあります。たとえば、ベクタに対するlastとpeekはどちらも最後の要素を返しますが、peekのほうが高速です。
;; ベクタに対するlast
(bench (dotimes [_ 100000] (last avec)))
;; mean: 2.197115 sec, sd: 84.094077 ms ;; ベクタに対するpeek
(bench (dotimes [_ 100000] (peek avec)))
;; mean: 1.761301 ms, sd: 23.357396 µs
(defrecord Point [x y z])
キーがほとんど固定のマップを使用している場合、レコードを使うことで高速化できる場合があります。レコードのほうが要素へのアクセスが速いためです。
;; マップ
(def p1 {:x 10, :y 20, :z 30}) (bench (dotimes [_ 10000000] (:y p1)))
;; mean: 137.594371 ms, sd: 10.014844 ms ;; レコード
(defrecord Point [x y z])
(def p2 (->Point 10 20 30)) (bench (dotimes [_ 10000000] (:y p2)))
;; mean: 86.313934 ms, sd: 5.312125 ms
Javaのフィールドアクセスを用いるとさらに速くなります。
user> (bench (dotimes [_ 10000000] (.y ^Point p2)))
;; mean: 15.905680 ms, sd: 1.293925 ms
ネストしたシーケンスを平坦化するには通常flattenを使用しますが、ネストが1段階の場合はapply concatやmapcatを使うことで高速化できます。
(def coll [[1 2 3] [4 5 6]]) ;; flatten
(bench (dotimes [_ 10000] (flatten coll))) ;=> (1 2 3 4 5 6)
;; mean: 6.044534 ms, sd: 174.447276 µs ;; apply concat
(bench (dotimes [_ 10000] (apply concat coll))) ;=> (1 2 3 4 5 6)
;; mean: 946.066505 µs, sd: 26.963664 µs ;; mapcat
(bench (dotimes [_ 10000] (mapcat identity coll))) ;=> (1 2 3 4 5 6)
;; mean: 4.557187 ms, sd: 53.755322 µs
ただし、ネストが2段階以上、もしくは1段階目にシーケンス以外の要素が含まれる場合はflattenを使う必要があります。
(let [xf (comp (filter even?) (map inc))] (transduce xf + (range 100)))
複数のシーケンス操作を行う場合、Clojure 1.7で導入されたTransducersを用いることで高速化できます。Transducersは中間データを生成しないためです。
;; Transducersなし
(defn a [n] (->> (range n) (filter even?) (map inc) (remove #(zero? (mod % 3))) (map #(* % %)) (reduce +))) (bench (dotimes [_ 1000] (a 1000)))
;; mean: 126.482482 ms, sd: 4.383541 ms ;; Transducersあり
(defn b [n] (let [xf (comp (filter even?) (map inc) (remove #(zero? (mod % 3))) (map #(* % %)))] (transduce xf + (range n)))) (bench (dotimes [_ 1000] (b 1000)))
;; mean: 104.169563 ms, sd: 7.549028 ms