haskellの実行速度

Haskell

mrubyの速度測ってみたついでにHaskellって速いんだっけ？　と気になって試してみた。

http://itpro.nikkeibp.co.jp/article/COLUMN/20070403/267180/?P=2

実際、現在のGHCは、正格のプログラムを書いた場合でも、Cでループを使ったプログラムと比べてそん色のない実行速度を持つコードを生成できます

ほーそうなのか、ということで、上記のリンクに記載されているコードを参考に以下のようなコードを書いてみるも、C言語と比較して断然遅い。実行時間にして40倍くらい差があるように見える。

import Data.List

sum' :: (Num a) => [a] -> a
sum' = foldl' (+) 0

main :: IO ()
main = putStrLn $ show $ sum' [0..1000000000]

具体的にはC言語で3秒に対してHaskellで120秒もかかってしまった。
ちなみにrubyでテキトーに書くと240秒くらいでできてしまった。動的型言語の2倍しか早くないのはなんだかしょんぼり。

うーん。と思って以下を読んでいたところ、
http://togetter.com/li/122555

C/C++と同じデータ構造を用い、同じアルゴリズムを用いている限りは、同程度の速度の実行ファイルが出来上がる可能性が高いです。

まずリスト使ったら遅いですし、

という発言を見つけた。
ああ、なるほどそういうことか。と思って、とりあえず以下のようにIntを使うようにした。

import Data.List

sum' :: (Num a) => [a] -> a
sum' = foldl' (+) 0

sumi :: [Int] -> Int
sumi = sum'

main :: IO ()
main = putStrLn $ show $ sumi [0..1000000000]

これで、12秒。10倍高速になった。
（答えがIntを超えてるので正しい答えにはならない。が、速度だけ知りたいのでそこは無視。本来無視すべきではないけどなんとなくの速度感が知りたいだけなので）。

でもまだC言語とは4倍の差があるので、そこらは上記の発言を信じるならリストが遅いということになる。
ということでやっている計算はちょっと変わるけど、以下のようにしてみた。

sumii :: Int -> Int -> Int
sumii 1000000001 x = x
sumii i          x = sumii (i+1) (x+i)

main :: IO ()
main = putStrLn $ show $ sumii 1 0

これで3秒。確かにC言語と同等の速度になった。というかほんのわずかだがC言語より早かった。（といっても、そこまで見るならもうちょい厳密にいろいろ整えるべきだと思うので、ここではだいたい同等になったという結論にしておく）
ちなみにghcに-O2とかオプションつけないと末尾再帰を展開してくれないみたいなのでスタックがあふれる点に注意。

というわけでこの内容でまとめも何もないのだがまとめると、HaskellをC並の速度で使いたければ、以下の点に注意すればいいと思う。

  1. プリミティブな型を使う
  2. 不要なリストは避ける

まあ、速度を気にするシーンってそんなにないし、あってもホットスポットだけしか最適化しないと思うけど。

（追記：コードにコピペみすってるところがあったので一応修正）