Clojure高速化テクニック

Clojureプログラムを高速化するためのテクニック集です。

本稿に書いてある手法が全てではありません。個々の手法について細かく書いてはいないため、詳しい情報は他の文献を参照してください。また、Clojureプログラムの外側（JVMなど）については記述していません。

> Premature optimization is the root of all evil.
> &nbsp;&nbsp;-- 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.
> &nbsp;&nbsp;-- [Rob Pike](http://www.lysator.liu.se/c/pikestyle.html)

ボトルネックをきちんと調査した上で、適切なパフォーマンスチューニングを行いましょう。

# 測定方法について

Clojureのバージョンはv1.8、測定ツールとして[criterium](https://github.com/hugoduncan/criterium) v0.4.4を使用しています。コード中に現れる`bench`関数はcriteriumのものです。`bench`は様々な情報を出力してくれますが、ここでは簡略化のため、平均実行時間と標準偏差のみを記します。

測定コードは[totakke/clj-perf-tips](https://github.com/totakke/clj-perf-tips)で公開しています。自分の環境で測定してみたい場合はご利用ください。

# 1. 型ヒント

```clj
(defn str-len [^String s]
  (.length s))
```

型ヒントを付けることでリフレクションを避け、高速化できます。

```clj
;; 型ヒントあり
(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](https://leiningen.org/)を使っている場合、`project.clj`に、

```clj
:profiles {:dev {:global-vars {*warn-on-reflection* true}}}
```

を設定しておくと良いかもしれません。

# 2. プリミティブヒント

```clj
(defn calc [^long x]
  (* (+ x 5) 2))
```

関数の引数に対してプリミティブヒントを付けることでBoxingを避け、高速化できます。

ただし、プリミティブヒントは関数の引数に対してのみ付けられ、最大4つまで、型は`^long`, `^double`の2種類のみとなっています。

```clj
;; プリミティブヒントあり
(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

```clj
(loop [i n, v (transient [])]
  (if (pos? i)
    (recur (dec i) (conj! v i))
    (persistent! v))))
```

`transient`を使うことで一時的にミュータブルなデータ構造を作成し、高速化できます。

```clj
;; 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`を用いたほうが速くなることがあります。

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

```clj
(def ^:const pi 3.14)
```

`:const`タグを使用することでvarをインライン化できます。

```clj
;; :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 プロトコル

多重ディスパッチを行う場合、マルチメソッドよりプロトコルを使用したほうが速いようです。

```clj
;; マルチメソッド
(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](http://insideclojure.org/2015/04/27/poly-perf/)

# 7. キャッシュする

```clj
(def f (memoize f))
```

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

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

```clj
(pmap slow-fn sequence)
```

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

```clj
(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`は遅いです。

```clj
(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`のほうが高速です。

```clj
;; ベクタに対する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. マップの代わりにレコードを使う

```clj
(defrecord Point [x y z])
```

キーがほとんど固定のマップを使用している場合、レコードを使うことで高速化できる場合があります。レコードのほうが要素へのアクセスが速いためです。

```clj
;; マップ
(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のフィールドアクセスを用いるとさらに速くなります。

```clj
user> (bench
       (dotimes [_ 10000000] (.y ^Point p2)))
;; mean: 15.905680 ms, sd: 1.293925 ms
```

# 11. 平坦化の方法を検討する

```clj
(apply concat nested-xs)
```

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

```clj
(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を使う

```clj
(let [xf (comp (filter even?)
               (map inc))]
  (transduce xf + (range 100)))
```

複数のシーケンス操作を行う場合、Clojure 1.7で導入された[Transducers](https://clojure.org/reference/transducers)を用いることで高速化できます。Transducersは中間データを生成しないためです。

```clj
;; 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
```