Reducers は並列化のためだけのライブラリではない

Reducers を並列化のためのライブラリだと思っていませんか？ 私も最初はそう思っていたのですが，Reducers がもたらす性能向上は並列化によるものだけではありませんでした．

Reducers の 2 つの効果

Clojure プログラムでは map/filter/reduce による遅延シーケンス計算が頻出します． これらの関数組み合わせにより何らかの計算をするプログラムを， 本記事では map-reduce プログラムと呼ぶことにします． 典型的な map-reduce プログラムはスレッドマクロで次のように表現できます．

(->> s
     (map mf)
     (filter ff)
     (reduce rf))

Reducers は，次の 2 つの改善により， map-reudce プログラムの性能を向上させます:

• オブジェクト生成を抑制
• （可能であれば）並列化

この記事では，簡単な map-reduce プログラムを例に， Reducers による性能向上を紹介します．

map-reduce プログラミングの例題

例として，次のような問題を解くことを考えます:

1 以上 1000000 未満の整数について七角数を計算し，そのうち三角数であるものの和を求めよ．

この解答を Clojure で求めてみます． 七角数と三角数の一般式は Wikipedia に載っているもの を利用します．次のような map-reduce プログラムで書けます:

(def s (range 1 1000000))

(defn ->heptagonal
  [^long x]
  (-> (* 5 x x)
      (- (* 3 x))
      (quot 2)))

(defn triangular?
  [^long x]
  (let [n (-> (* 8 x)
              inc
              Math/sqrt
              dec
              (/ 2.0))]
    (= n (Math/floor n))))

(def solver #(->> s
                  (map ->heptagonal)
                  (filter triangular?)
                  (reduce +)))

この solver の実行時間を計ってみます．

user> (use 'criterium.core)
nil

user> (dorun s)
nil

user> (bench (solver))
Evaluation count : 720 in 60 samples of 12 calls.
             Execution time mean : 88.173601 ms
    Execution time std-deviation : 2.287743 ms
   Execution time lower quantile : 86.886580 ms ( 2.5%)
   Execution time upper quantile : 95.758184 ms (97.5%)
                   Overhead used : 3.316905 ns

Found 9 outliers in 60 samples (15.0000 %)
    low-severe   3 (5.0000 %)
    low-mild     6 (10.0000 %)
 Variance from outliers : 12.6456 % Variance is moderately inflated by outliers
nil

手元で計ってみたところ 88ms でした．

Reducers の性能向上その 1

名前空間 clojure.core.reducers には clojure.core と同じく map, filter という名前の関数が用意されています． 先ほどの例の map, filter 関数を clojure.core.reducers のものに置き換えて実行時間を計ってみましょう．

(require '[clojure.core.reducers :as r])

(def rsolver #(->> s
                  (r/map ->heptagonal)
                  (r/filter triangular?)
                  (reduce +)))


user> (bench (rsolver))
Evaluation count : 840 in 60 samples of 14 calls.
             Execution time mean : 75.952144 ms
    Execution time std-deviation : 3.717203 ms
   Execution time lower quantile : 72.984782 ms ( 2.5%)
   Execution time upper quantile : 86.263413 ms (97.5%)
                   Overhead used : 3.316905 ns

Found 4 outliers in 60 samples (6.6667 %)
    low-severe   4 (6.6667 %)
 Variance from outliers : 35.2050 % Variance is moderately inflated by outliers
nil

今度は 76ms になりました．非 Reducers 版が約 88ms だったので， Reducers のライブラリを使うだけで性能が向上したことになります． この時点では並列化されていないのですが， それでも性能向上するのはどうしてでしょうか．

それは，Reducers 版のライブラリが途中で遅延シーケンスを生成しないためです． 非 Reducers 版と Reducers 版との途中の動作の違いを確認してみましょう． まずは，非 Reducers 版から，

(def solver #(->> s
                  (map ->heptagonal)
                  (filter triangular?)
                  (reduce +)))

この solver の動作を順に追っていきます．まず， (map ->heptagonal s) が遅延シーケンスを返します．

user> (map ->heptagonal s)
(1 7 18 34 55 81 112 148 189 235 286 342 403 469 540 616 697 783 874 970 ...)

この遅延シーケンスを受け取った (filter triangular?) も遅延シーケンスを返します．

user> (filter triangular? (map ->heptagonal s))
(1 55 121771 5720653 12625478965 593128762435)

そして，最後に (reduce +) が和を計算します．

(->> s
     (map ->heptagonal)
     ； この時点で 999999 要素の遅延シーケンスが生成される
     (filter triangular?)
     ;  この時点で 6 要素の遅延シーケンスが生成される
     (reduce +))

このように 1000k 要素の長大遅延シーケンスが生成されます．

今度は Reducers 版をみてみましょう． コードの全景は非 Reducers 版と大差ありません．

(def rsolver #(->> s
                   (r/map ->heptagonal)
                   (r/filter triangular?)
                   (reduce +)))

それでは rsolver の動作を順に追っていきましょう．まず， (r/map ->heptagonal s) は計算せずに folder を返します． 遅延シーケンスを作りません．

user> (r/map ->heptagonal s)
#<reducers$folder$reify__3198 clojure.core.reducers$folder$reify__3198@1ba2d9ca>

この folder を受け取った (r/filter triangular?) も計算せずに folder を返します． これも遅延シーケンスを作りません．

user> (r/filter triangular? (r/map ->heptagonal s))
#<reducers$folder$reify__3198 clojure.core.reducers$folder$reify__3198@6397a286>

そして最後に (reduce +) が folder を計算して結果を返します．

(->> s
     (r/map ->heptagonal)
     ; folder を返す．遅延シーケンス作らない．
     (r/filter triangular?)
     ; folder を返す．遅延シーケンス作らない
     (reduce +) ; folder を計算する．
     )

のようになります．長大遅延シーケンスを作られません． このように，Reducers はなるべくオブジェクトを作らないことで， map-reduce プログラムの性能向上を図ります．CPU だけでなく メモリにも優しいプログラムになります．

Reducers の関数はカリー化されている

ここで一休み，性能の話からは逸れますが， Reducers の特徴を一つ紹介しておきます．

clojure.core の map, filter はカリー化されていませんが， clojure.core.reducers の map, filter はカリー化されています． ですので，先ほどの rsolver は，(r/map ->heptagonal) と (r/filter triangular?) との合成関数 tf を利用して， 次のように書けます:

(def tf (comp (r/filter triangular?)
              (r/map ->heptagonal)))

(def rsolver #(reduce + (tf s)))

スレッドマクロで書くよりもすっきりするので，今後はこの書き方で話を進めます．

Reducers の性能向上その 2

いよいよ，Reducers を使って rsolver を並列化します． Reducers による並列化は， 他の言語のように並列化コレクションを用意するわけでも， pmap のように並列化バージョンの関数を用意するわけでもありません． fold 関数による並列 reduce+combine により実現されます． すなわち，fold という関数の中で並列処理が行なわれます．

fold の使い方は簡単，reduce と置き換えるだけです．

(def rsolver #(reduce + (tf s)))   ; 並列化前

(def rsolver' #(r/fold + (tf s)))  ; 並列化後

ほとんど変わりませんね．それでは早速ベンチマークしてみましょう．

user> (bench (rsolver'))
Evaluation count : 840 in 60 samples of 14 calls.
             Execution time mean : 76.454941 ms
    Execution time std-deviation : 3.966713 ms
   Execution time lower quantile : 73.057997 ms ( 2.5%)
   Execution time upper quantile : 87.052600 ms (97.5%)
                   Overhead used : 3.316905 ns

Found 5 outliers in 60 samples (8.3333 %)
    low-severe   3 (5.0000 %)
    low-mild     2 (3.3333 %)
 Variance from outliers : 38.4521 % Variance is moderately inflated by outliers
nil

あれ，並列化前が 76ms で並列化後も 76ms．全然で速くなっていません．

Reducers による並列化の現時点での制限

現時点での Reducers の実装では，fold 関数が並列化するコレクションはベクタとマップのみです． ほかのコレクション，たとえば，配列も並列化できそうなのなのですが，現時点では並列化に対応していません． さきほどの例にも示したように，シーケンスも並列化しません．

仕方がないので，Reducers が提供する並列化を体感するために， 予めシーケンスをベクタに変換しておきます．

(def v (into [] s))

(def rsolver' #(r/fold + (tf v)))

今度こそ，うまくいくでしょう:

user> (bench (rsolver'))
Evaluation count : 1620 in 60 samples of 27 calls.
             Execution time mean : 38.875048 ms
    Execution time std-deviation : 1.821926 ms
   Execution time lower quantile : 37.116478 ms ( 2.5%)
   Execution time upper quantile : 45.414021 ms (97.5%)
                   Overhead used : 3.316905 ns

Found 4 outliers in 60 samples (6.6667 %)
    low-severe   1 (1.6667 %)
    low-mild     3 (5.0000 %)
 Variance from outliers : 33.5476 % Variance is moderately inflated by outliers
nil

並列化後は 76ms => 39ms と半分の時間で計算できました．

おわりに

この記事では，Reducers による map-reduce プログラムの性能向上効果を紹介しました． clojure.core の関数を clojure.core.reducers の関数に置き換えることで， map-reduce プログラムの中間遅延シーケンスの生成を抑制できます． これにより，メモリを節約でき，実行時間も少し短くなります． また，reduce の代わりに fold を使うことで map-reduce プログラムを簡単に並列化できます． 遅延シーケンス生成抑制と並列化とを組み合わせることで， 例題のプログラムは， 88ms => 76ms => 39ms と高速化できました．

Reducers は既存の関数の置き換えだけで手軽に map-reduce プログラムの性能を向上させられる魔法のようなライブラリです． また，並列化の恩恵が受けられない場合でも性能向上効果が得られるという， 非常に使い勝手の良いライブラリです． これから積極的に使っていきたいですね．