Clojure高速化テクニック

コンテンツ

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のインライン化

: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

7. キャッシュする

メモ化などにより過去の計算結果をキャッシュしておくことで、空間効率と引き換えに時間効率を高めることができます。

;; メモ化あり
(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. 並列化する

並列化することで高速化を図りましょう。

(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

また、同じ機能を持つ関数でも計算量が異なることがあります。たとえば、ベクタに対するlastpeekはどちらも最後の要素を返しますが、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. 平坦化の方法を検討する

ネストしたシーケンスを平坦化するには通常flattenを使用しますが、ネストが1段階の場合はapply concatmapcatを使うことで高速化できます。

(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
要約する
Clojureプログラムの高速化テクニックを紹介。型ヒントやプリミティブヒント、transientデータ構造、loop/recurの使用、varのインライン化、マルチメソッドとプロトコルの比較などが効果的。過度な最適化は避け、ボトルネックを測定してから適切にチューニングすることが重要。詳細は他文献を参照。