Haskell::GR-nの生成(その6)

Data.Array.Unboxedを使用し、計算量の削減を図れないか試してみる。

gr6.hs

Data.Array.Unboxedはimmutable objectであることを除けば、Cの配列に要素の型とインデックスの範囲情報が付加されたものと思えば良いらしい。リストに比べるとメモリ占有量、ランダムアクセス速度に優れる。反面、個々の要素の操作のバリエーションはリストに比べると、やや制限がかかるので計算の柔軟性には欠ける面があると言える。

今までのコードではGR-nの個々の計算結果を Int 型のリストで実装していたが、今回のコードでは要素の型が Int16 の Data.Array.Unboxed に格納するように実装した。ちなみにGR-nのマークの型をInt16にすると、計算中の桁溢れの恐れがあるが、長さの下限の推定値の式 n(n-1)/2 から

n=50 -> 1225
n=100 -> 4950
n=200 -> 19900
n=256 -> 32640
n=257 -> 32896

なので、n=100程度までの生成・探索に問題とはならないとは思われる。

これで全体としてのメモリ消費量が抑えられる事が予想される。
一方、一つ一つのGRの計算時にArray <-> リストの変換によるオーバーヘッドが伴うので計算時間の面で有利かどうかは実際に測定してみないとはっきりしない。

で、まずはプロファイルオプション無しでコンパイルしたバイナリでGR-40の一つ目を計算するのにかかる時間を測定し、その5’のコードと比較してみる。

その5′:
40:[0,1,3,8,12,22,28,46,59,82,99,114,149,175,214,244,292,333,396,453,497,561,623,732,765,817,961,990,1084,1263,1346,1481,1561,1689,1762,1884,2124,2190,2274,2379]
441.522u 0.388s 8:14.67 89.3%    496+681k 0+0io 0pf+0w

その6:
40:[0,1,3,8,12,22,28,46,59,82,99,114,149,175,214,244,292,333,396,453,497,561,623,732,765,817,961,990,1084,1263,1346,1481,1561,1689,1762,1884,2124,2190,2274,2379]
191.898u 0.381s 3:36.65 88.7%    513+665k 0+0io 0pf+0w

おお、倍ぐらいにスピードアップしてるじゃまいか。

次にプロファイルオプション付きでコンパイルしたバイナリでプロファイルを測定。

結果の抜粋。

        Thu Jan  1 01:57 2009 Time and Allocation Profiling Report  (Final)
gr6 +RTS -hd -p -RTS 40 1
total time  =      321.24 secs   (16062 ticks @ 20 ms)
total alloc = 38,033,292,852 bytes  (excludes profiling overheads)
COST CENTRE                    MODULE               %time %alloc
intersect_p                    Main                  51.3    3.2
diff_set                       Main                  30.3   85.4
l2a                            Main                  13.9    2.9
gr                             Main                   2.9    6.5
gr_p                           Main                   1.6    1.9

intersect は Array に適した実装に変更したので、時間計算量コストの割合は結構低下した。反面diff_setのコストの割合が上昇しているので合わせてのコストの割合はそれ程低下していない。さらにリストからArrayへ変換するコストもそれなりに占めているので、ループ内の時間計算量コストの割合はそれ程変化していないとも言える。
ただ、全体の計算時間は半分にまで削減できているので、時間計算量の面では Unboxed Array を実装に用いたのは正解のようだ。

次にヒープメモリの使用量をグラフにする。

gr6.png

その5’の結果に比べれば一目瞭然でヒープメモリの使用量が1/3程度まで削減できている。
ところで、一定の時間間隔で使用量がちょこっと下がっている所がある。このタイミングで、GCのgeneration scavenging が行われているのかな?

これはなかなか幸先の良い結果が得られましたね。

OGR-n の探索にも Unboxed Array の摘要が良さげな感じ。

Haskell::GR-nの生成(その5′)

去年は(O)GR-n関連のコードをいろいろ書き散らかしてはみたが、まだ真面目に性能測定をやっていないので、そろそろプロファイル測定に手を付けてみる。

そこでプロファイル測定用にその5のコードを若干修正してみた。

gr5_.hs

GHCのプロファイラではトップレベルの関数単位でしか測定できないので、gr_p、diff_set、intersect(myIntersectでラップ)の性能上のポイントになりそうな関数をトップレベルに移動してある。

GR-40の一つ目を計算する時のプロファイル測定の結果の一部を抜粋

        Thu Jan  1 00:12 2009 Time and Allocation Profiling Report  (Final)
gr5 +RTS -hd -p -RTS 40 1
total time  =      700.94 secs   (35047 ticks @ 20 ms)
total alloc = 28,245,003,008 bytes  (excludes profiling overheads)
COST CENTRE                    MODULE               %time %alloc
myIntersect                    Main                  86.1    1.0
diff_set                       Main                   9.2   89.2
gr_p                           Main                   3.6    2.9
gr                             Main                   1.1    6.9

非常に当たり前の結果だが、ループの一番内側で呼び出している関数 intersect、diff_set の実行時間が合わせて全体の95%を占めていることがわかる。

さらに、ヒープメモリの使用量をグラフ化してみた。
gr5_.png
こちらも非常にわかりやすい結果になった。

これを基準に、GR-nの計算にData.Array等を使った場合にどのように変化するか調べてみたいと思う。

明けましておめでとうございます

という訳で、記念かきこ。

お陰様でブログを始めて(3週間程度^_^;ですが)から、目出度く年を越すことができました。

これからもどうでもいいことを適当に書き綴っていけたらいいなと思ってますので、物好きな方は生温かい目で見守ってやってくださいまし。

ゆるめのつっこみも歓迎です(きつめのは本人がへこみますので、適当に手加減をしてくれると有難いです)。