PR

ボトルネックを特定する

 HashTable.profに出力された結果には,まだ疑問が残っています。MAINとCAFはそれぞれmain変数内のinsertを呼び出しており,insertが大部分の処理を行っています。しかし,これら二つのinsertが行っている処理はおそらく異なるものです。もし二つの処理が全く同じならば,実行時間とメモリー消費量は同じになるはずです。しかし,実際にはこれらの実行時間とメモリー消費量は異なっています。また,CAFからのコールグラフにあるinsertのentriesは0であることから,CAFからはinsertの処理そのものを呼び出しているのではなく,insertの処理の一部だけを行っていると推測できます。

 では,CAFが呼び出している処理は何なのでしょうか? それを調べるために,CAFについての詳しい情報を表示してみましょう。-profオプションに-caf-allオプションを追加することで,CAFに束縛された変数名が表示されます。

ghc -O2  -prof -auto-all -caf-all HashTable.hs -rtsopts
[1 of 1] Compiling Main             ( HashTable.hs, HashTable.o )
Linking HashTable ...

$ ./HashTable +RTS -p
Just 100

~ 略 ~
                                                                                               individual    inherited
COST CENTRE              MODULE                                               no.    entries  %time %alloc   %time %alloc

MAIN                     MAIN                                                   1           0   0.0    0.0   100.0  100.0
 main                    Main                                                 232           1   0.0    0.0    72.1   66.2
  lookup                 Main                                                 241           1   0.0    0.0     0.0    0.0
  insert                 Main                                                 234           1  72.1   66.2    72.1   66.2
  new                    Main                                                 233           1   0.0    0.0     0.0    0.0
 CAF:lvl4_r172           Main                                                 226           1   0.0    0.0    27.9   33.8
  main                   Main                                                 235           0   0.0    0.0    27.9   33.8
   insert                Main                                                 236           0  27.9   33.8    27.9   33.8
 CAF:lvl3_r170           Main                                                 225           1   0.0    0.0     0.0    0.0
~ 略 ~

 CAFに「lvl4_r172」「lvl3_r170」といった変数名が追加されています。これらの変数は,プログラムのコンパイル過程でGHCが生成したものです。生成された変数の定義は,-ddump-simplオプションを利用することで参照できます。

ghc -O2 -c HashTable.hs -ddump-simpl -prof -auto-all -caf-all

==================== Tidy Core ====================
~ 略 ~
lvl2_r16Y :: GHC.Types.Int
[GblId, Str=DmdType m]
lvl2_r16Y =
  __scc {main main:Main !}
  __scc {insert main:Main !} GHC.Types.I# 10000000

lvl3_r170 :: GHC.Types.Int
[GblId, Str=DmdType m]
lvl3_r170 =
  __scc {main main:Main !} __scc {insert main:Main !} GHC.Types.I# 1

lvl4_r172 :: [GHC.Types.Int]
[GblId, Str=DmdType]
lvl4_r172 =
  __scc {main main:Main !}
  __scc {insert main:Main !}
  case lvl3_r170 of _ { GHC.Types.I# x_aAq ->
  case lvl2_r16Y of _ { GHC.Types.I# y_aAA ->
  GHC.Enum.eftInt x_aAq y_aAA
  }
  }
~ 略 ~

 なお,-profや-caf-allを付けるかどうかで,異なった変数が生成されるので注意してください。

ghc -O2 -c HashTable.hs -ddump-simpl -prof
~ 略 ~
lvl3_r173 :: [GHC.Types.Int]
[GblId, Str=DmdType]
lvl3_r173 =
  __scc {insert main:Main !}
  case lvl2_r171 of _ { GHC.Types.I# x_aAq ->
  case lvl1_r16Z of _ { GHC.Types.I# y_aAA ->
  GHC.Enum.eftInt x_aAq y_aAA
  }
  }
~ 略 ~

 変数の定義を出力する際には,プロファイルを取ったときと同じオプションを指定する必要があります。

 それでは,lvl4_r172変数の定義を見てみましょう。lvl4_r172ではSCC指示文に対応する「__scc {...}」という式の後ろで,GHC.EnumモジュールのeftInt関数を呼び出しています。eftIntは,EnumクラスのenumFromメソッドやenumFromToメソッドの定義に使われている関数です(参考リンク)。

instance  Enum Int  where
~ 略 ~
    {-# INLINE enumFrom #-}
    enumFrom (I# x) = eftInt x maxInt#
        where !(I# maxInt#) = maxInt
        -- Blarg: technically I guess enumFrom isn't strict!

    {-# INLINE enumFromTo #-}
    enumFromTo (I# x) (I# y) = eftInt x y
~ 略 ~

 [x..y]は「enumFromTo x y」の構文糖衣です。つまり,lvl4_r172変数は[1..10000000]というリストを作成するものです(参考リンク)。

 CAFで行っているのがリストの作成であることを確認してみましょう。リストの作成を"makeList"という名前のコスト集約点にするよう,main変数の定義を変更します。

main = do
    m <- {-# SCC "new" #-} new (==) hashInt
    let list = {-# SCC "makeList" #-} [1..10000000]
    {-# SCC "insert" #-} forM_ list $ \n -> insert m n n
    v <- {-# SCC "lookup" #-} lookup m 100
    print v

 変更したプログラムをビルドして実行した結果を以下に示します。

ghc -O2  -prof -auto-all -caf-all HashTable.hs -rtsopts
[1 of 1] Compiling Main             ( HashTable.hs, HashTable.o )
Linking HashTable ...

$ ./HashTable +RTS -p
Just 100

~ 略 ~
                                                                                               individual    inherited
COST CENTRE              MODULE                                               no.    entries  %time %alloc   %time %alloc

MAIN                     MAIN                                                   1           0   0.0    0.0   100.0  100.0
 main                    Main                                                 232           1   0.0    0.0    78.9   66.2
  lookup                 Main                                                 241           1   0.0    0.0     0.0    0.0
  insert                 Main                                                 234           1  78.9   66.2    78.9   66.2
  new                    Main                                                 233           1   0.0    0.0     0.0    0.0
 CAF:list_r179           Main                                                 226           1   0.0    0.0    21.1   33.8
  main                   Main                                                 235           0   0.0    0.0    21.1   33.8
   makeList              Main                                                 236           1  21.1   33.8    21.1   33.8
~ 略 ~

 list_r179という名前のCAFからは,main変数内の処理であるmakeListが呼ばれているのがわかります。list_r179でのinherited列の値は,makeListでのindividual列の値と同じです。makeListはリストを作成する式をコスト集約点にしたものなので,この結果からCAFで行われていた処理がリストの作成であることが確認できました。

 リストの作成がボトルネックになっているということは,利用するデータ構造をリスト以外のものに変えるとよいかもしれません。リストの代わりにVectorを利用してみましょう。

import Prelude hiding (lookup)
import Data.HashTable (new, newHint, hashInt, insert, lookup)
import Data.Vector (forM_, enumFromN)

main = do
    m <- {-# SCC "new" #-} new (==) hashInt
    let vector = {-# SCC "makeVector" #-} enumFromN 1 10000000
    {-# SCC "insert" #-} forM_ vector $ \n -> insert m n n
    v <- {-# SCC "lookup" #-} lookup m 100
    print v

 結果は以下の通りです。

~ 略 ~
COST CENTRE              MODULE                                               no.    entries  %time %alloc   %time %alloc

MAIN                     MAIN                                                   1           0   0.0    0.0   100.0  100.0
 main                    Main                                                 276           1   0.0    0.0    90.4   92.0
  lookup                 Main                                                 285           1   0.0    0.0     0.0    0.0
  insert                 Main                                                 278           2  90.4   92.0    90.4   92.0
  new                    Main                                                 277           1   0.0    0.0     0.0    0.0
 CAF:vector_r1tE         Main                                                 270           1   0.0    0.0     9.6    8.0
  main                   Main                                                 279           0   0.0    0.0     9.6    8.0
   makeVector            Main                                                 280           1   9.6    8.0     9.6    8.0
~ 略 ~

 データ構造をリストからVectorに変更したことで,CAFで行われる処理の占める割合が大幅に減少しています。

 このように,-caf-allオプションを使うことで,CAF内で行われている処理からボトルネックを見つけ出すヒントが得られます。