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で公開しています。自分の環境で測定してみたい場合はご利用ください。
1. 型ヒント
(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}}}
を設定しておくと良いかもしれません。
2. プリミティブヒント
(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
3. transient
(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
4. loop/recurを使う
シーケンス処理の際、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
5. varのインライン化
(def ^:const pi 3.14)
: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
6. マルチメソッド vs プロトコル
多重ディスパッチを行う場合、マルチメソッドよりプロトコルを使用したほうが速いようです。
;; マルチメソッド
(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
参考：Polymorphic performance - Inside Clojure
7. キャッシュする
(def f (memoize f))
メモ化などにより過去の計算結果をキャッシュしておくことで、空間効率と引き換えに時間効率を高めることができます。
;; メモ化あり
(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
8. 並列化する
(pmap slow-fn sequence)
並列化することで高速化を図りましょう。
(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
9. データ構造の特性を把握する
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
10. マップの代わりにレコードを使う
(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
11. 平坦化の方法を検討する
(apply concat nested-xs)
ネストしたシーケンスを平坦化するには通常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を使う必要があります。
12. Transducersを使う
(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