Re:Haskellで書いてみたらC++の10倍遅かった 5倍程度になりました

10倍は遅すぎませんか?

本の虫: Haskellで書いてみたらC++の10倍遅かった

を読みました.

10倍は差が出過ぎなのではないかと思いました.

C++ソースコード

まずC++のソースコードが完全なものではないので補完しました.

2018-02-06T12:05:17 ncaq@strawberry/pts/4(1) ~/Documents/archive/2018-02
% g++ -O2 -std=c++17 coin.cpp
2018-02-06T12:05:30 ncaq@strawberry/pts/4(0) ~/Documents/archive/2018-02
% time ./a.out
100      : 14%
1000     : 8.3%
10000    : 8.8%
100000   : 8.557%
./a.out  0.21s user 0.00s system 99% cpu 0.217 total

Haskellソースコードにhlintをかけたもの

Haskellソースコードを写して,元のソースコードが読みにくいのでhlintに従って整形しました.

2018-02-06T13:43:57 ncaq@strawberry/pts/4(130) ~/Documents/archive/2018-02
% stack ghc -- -O2 oldCoin.hs
2018-02-06T13:43:59 ncaq@strawberry/pts/4(0) ~/Documents/archive/2018-02
% time ./oldCoin
100      : 10.0%
1000     : 8.1%
10000    : 8.780000000000001%
100000   : 8.559999999999999%
./oldCoin  3.23s user 0.03s system 99% cpu 3.268 total

なるほど確かに10倍程度遅いようですね.

プロファイリング

ところでghcにはプロファイリングオプションがあります.

計測せよって偉い人も言ってました.

2018-02-06T12:11:55 ncaq@strawberry/pts/6(0) ~/Documents/archive/2018-02
% stack ghc -- -prof -fprof-auto -rtsopts coin.hs
[1 of 1] Compiling Main             ( coin.hs, coin.o )
Linking coin ...
2018-02-06T12:13:11 ncaq@strawberry/pts/6(0) ~/Documents/archive/2018-02
% time ./coin +RTS -p
100      : 91.0%
1000     : 91.2%
10000    : 91.43%
100000   : 91.259%
./coin +RTS -p  10.76s user 0.11s system 99% cpu 10.882 total
        Tue Feb  6 12:13 2018 Time and Allocation Profiling Report  (Final)

           coin +RTS -p -RTS

        total time  =       10.15 secs   (10151 ticks @ 1000 us, 1 processor)
        total alloc = 11,164,362,552 bytes  (excludes profiling overheads)

COST CENTRE               MODULE        SRC                                %time %alloc

hasContiguousElems        Main          coin.hs:11:1-68                     21.2   25.6
randomIvalInteger         System.Random System/Random.hs:(468,1)-(489,76)   21.0   26.5
stdNext                   System.Random System/Random.hs:(518,1)-(528,64)   13.8   15.8
randomIvalInteger.f       System.Random System/Random.hs:(486,8)-(489,76)    9.3    2.1
randomIvalInteger.f.v'    System.Random System/Random.hs:489:25-76           5.3    4.3
randomIvalInteger.b       System.Random System/Random.hs:473:8-54            4.0    5.7
randomIvalInteger.(...)   System.Random System/Random.hs:472:8-36            3.8    0.0
randomIvalInteger.magtgt  System.Random System/Random.hs:483:8-21            3.7    1.4
randomR                   System.Random System/Random.hs:(387,3)-(397,30)    2.9    0.0
next                      System.Random System/Random.hs:218:3-17            2.8    2.1
splitN                    Main          coin.hs:8:1-43                       2.7    5.4
randoms.\                 System.Random System/Random.hs:316:42-67           2.4    5.0
randomIvalInteger.f.(...) System.Random System/Random.hs:488:25-39           2.3    0.0
randomIvalInteger.k       System.Random System/Random.hs:482:8-20            1.8    1.4
random                    System.Random System/Random.hs:399:3-49            1.1    0.0
stdNext.z                 System.Random System/Random.hs:520:17-34           0.6    1.4
stdNext.s1''              System.Random System/Random.hs:524:17-64           0.3    1.4
stdNext.s2''              System.Random System/Random.hs:528:17-64           0.2    1.4

やっぱり乱数生成が遅い

あーやっぱりRandomが遅い.そんな気はしていました.

Haskellの乱数事情 - Qiitaで触れられてるとおり,System.Randomは遅いのです.

乱数を速度を重視して真面目に考えたことがないので何を選択すれば良いのか全くわからない.先程の記事で推奨されていたmwc-randomを使ってみます.

一番速いものを選ぼうかと思ったのですが,純Haskellで実装されたものでないと「Haskellの速度」を測るレギュレーションに違反しているのではないかと思ったので純Haskellで実装されたものを選びました.

System.Random.MWCでの再実装

2018-02-06T13:08:09 ncaq@strawberry/pts/6(0) ~/Documents/archive/2018-02
% stack ghc -- -O2 coin.hs
2018-02-06T13:08:13 ncaq@strawberry/pts/6(0) ~/Documents/archive/2018-02
% time ./coin
100      : 9.0%
1000     : 9.2%
10000    : 0.9199999999999999%
100000   : 9.2e-2%
./coin  0.03s user 0.00s system 98% cpu 0.038 total

これでC++の2倍程度の遅さに収まりましたね.良かったですね.

と言いたいところですが,乱数が偏りすぎていてまともな答えが帰ってきていない.これではコードがちゃんと動いたとは言い難いです.

まともな偏りを持った純Haskell製乱数生成ライブラリは少しだけ調べた結果見つかりませんでした.実用的には他言語へのバインディングライブラリ使えば良いんでしょうけど,今回のケースを解決するものは見つかりませんでした.残念です.

答えとしては片手落ちですね.誰か知ってる人が居たら教えてください.

そもそも無限リストなんかじゃなくてRandomIOとか使って必要なところに乱数を使えばそこそこ早くなるんじゃないのと思ったのですがとても眠いので大幅な書き換えをやる気が起きません.

指摘してもらいました

なるほど.

元のアルゴリズムを全く読まずに適当な書き換えをしたツケですね.

乱数に偏りがあったという私の理解は誤りでした.

修正版

2018-02-06T16:54:40 ncaq@strawberry/pts/9(0) ~/Documents/archive/2018-02
% time ./coin
100      : 8.0%
1000     : 7.7%
10000    : 8.959999999999999%
100000   : 8.698%
./coin  1.09s user 0.04s system 99% cpu 1.133 total

これで1.133 / 0.217 = 5.221198156682028というわけで,5倍程度の速さ(遅さ)になりました.

リストじゃなくてVectorのまま取り扱ったらもっと早くなるだろうって?それは読者の宿題としようと思います(めんどくさい).

このエントリーをはてなブックマークに追加 fb-like g-plusone pocket