doallで遅くなる(Clojure)

 mapなどリスト処理の間に, doallを間に挟むと, その分遅くなっているような気がしたので, 調べてみると, 確かにdoallを挟むことで実行時間が伸びています.

 副作用を考えない場合, 意味的にはidentityと同じなので, 忘れがちですが, しっかり計算コストとメモリ確保のためのコストがかかっているようです.

 以下がその証拠. (Linux Mint 17 Cinnamon 64-bit, Intel Core i7-4790, メモリ : 31.4GB)

user> (defn dub [n] (* n 2))
#'user/dub
user> (time (reduce + (map inc (map dub (range 10000000)))))
"Elapsed time: 1661.92639 msecs"
100000000000000
user> (time (reduce + (map (comp inc dub) (range 10000000))))
"Elapsed time: 1388.861015 msecs"
100000000000000
user> (time (reduce + (map inc (doall (map dub (range 10000000))))))
"Elapsed time: 1892.659523 msecs"
100000000000000
user> (time (reduce + (map inc (map dub (range 1000000000)))))
user> (time (reduce + (map inc (map dub (range 100000000)))))
"Elapsed time: 15394.220163 msecs"
10000000000000000
user> (time (reduce + (map (comp inc dub) (range 100000000))))
"Elapsed time: 13912.628054 msecs"
10000000000000000
user> (time (reduce + (map inc (doall (map dub (range 100000000))))))
"Elapsed time: 54838.803745 msecs"
10000000000000000

 一回目のトライは, 普通にmapを２回リストに適用した場合で1.6秒程度.

 次にmap分配則を用いて2回分のmapを1回に縮めてみた場合. 若干, 早くなりました. Haskellだとこの最適化は, 効果的なのですが, Clojureではおそらくリストの実装上の違いによりあまり効果がないようです.

 三行目が, 問題のdoallを挟んだリスト処理です. 通常のリスト操作と比べて0.2秒ほど, 遅くなっています. 遅くはなっていますが, 1.1倍程度です.

 下三行の入力は, リストのサイズを大きくした(1ケタ上げた)場合. map分配則による変換の効果の割合はリストサイズが10分の1以下の時と変わらないようです.

 一方で, doallを挟んだ場合は, 3倍以上の時間がかかっています. 与えられたリストのサイズに対して実行時間が線形に増加していないのは, メモリ確保に時間がかかっていることが原因だと思われます.

 ちなみに, 上記のreplのプロセスが終了すると約5.5GiBのメモリ領域が開放されました. というわけで, メモリサイズがシビアなノートPCとかだと, (GCなどに)よりその影響が顕著に出てくるかもしれません.