呼び出しパターンの特殊化(Call-pattern specialisation)

 stream-fusionパッケージの++演算子を使ったコードに対し,前回説明した手順でGHCの最適化機能を適用すると,以下のようなコードが生成されます。

最適化前のコード:

module RewriteStream where
import Prelude hiding (map, filter, sum, (++))
import Data.List.Stream

val :: [Int] -> [Int] -> Int
val xs ys = sum $ xs ++ ys

最適化されたコード:

val xs = loop_sum 0 (L xs)
    where
      loop_sum !a !(Left s) =
        case !s of
          (L [])     -> loop_sum a (Right (L ys))
          (L (x:xs)) -> expose (L xs) $ loop_sum (a + x) (Left (L xs))
      loop_sum !a !(Right s) =
        case !s of
          (L [])     -> a
          (L (y:ys)) -> expose (L ys) $ loop_sum (a + y) (Right (L ys))

 このval関数の内部のloop_sum関数には無駄があります。loop_sum関数の実装に使われているEither型は,loop_sum関数の再帰呼び出しの際に「Lデータ構成子に格納された状態」を包むときと,loop_sum関数の最初のパターン照合にしか使われていません。それだけのためにデータ構成子を使うのは無駄です。データ構成子を利用しないよう,以下のように書き換えるべきです。

val xs = loop_sum_left 0 (L xs)
    where
      loop_sum_left !a !s =
        case !s of
          (L [])     -> loop_sum_right a (L ys)
          (L (x:xs)) -> expose (L xs) $ loop_sum_left (a + x) (L xs)
      loop_sum_right !a !s =
        case !s of
          (L [])     -> a
          (L (y:ys)) -> expose (L ys) $ loop_sum_right (a + y) (L ys)

 Either型を使わない新しいval関数の定義では,Either型のデータ構成子を利用するのに必要なメモリーを確保したり,Either型に値を格納したり,Either型から値を取り出したりする必要がありません。その結果,メモリーの消費量や処理のコストを削ることができます。

 このような「関数の再帰呼び出しの部分でデータ構成子に値を格納し,データ構成子から値を取り出して処理を行うコード」が存在する場合,データ構成子を利用しないよう書き換えることで処理を効率化できます。GHCではこのようなコードの効率化を行うための,「呼び出しパターンの特殊化」という最適化機能を提供しています。「特殊化された構成子(Specialized Constructor)」,またはそれを略したSpecConstrとも呼びます。

  GHCのSpecConstrを使ってval関数を最適化する例を見てみましょう。SpecConstrは-O2以上の最適化レベルで有効になります。レベル指定なしの-Oオプションや-O1オプションなどではSpecConstrを利用できないので注意してください(参考リンク)。

$ ghc -c -O2 RewriteStream.hs -ddump-simpl-stats
~ 略 ~
10 RuleFired
    1 ++ -> fused (1)
    3 SC:$wloop_sum0
    4 SC:$wloop_sum1
~ 略 ~

 -ddump-simpl-statsを使って出力させた統計情報には,stream-fusionパッケージにはない「SC:$wloop_sum0」と「SC:$wloop_sum1」という二つの規則が加わっています。これらの規則はSpecConstrによって追加されたものです。

 追加された二つの規則による関数の特殊化過程を-ddump-specオプションを使って出力すると,「Either型のデータ構成子を使わずに呼び出せる関数」を新たに生成し,生成したこの関数を用いて「Either型のデータ構成子を使用する式」を「Either型のデータ構成子を使用しない式」に書き換えていることがわかります(参考リンク)。

$ ghc -c -O2 RewriteStream.hs -ddump-spec
~ 略 ~
==================== SpecConstr ====================
$wval_srr :: [GHC.Types.Int] -> [GHC.Types.Int] -> GHC.Prim.Int#
LclId
[Arity 2
 Str: DmdType LL]
~ 略 ~
      $s$wloop_sum_srX :: [GHC.Types.Int]
                          -> GHC.Prim.Int#
                          -> GHC.Prim.Int#
      LclId
      [Arity 2
       Str: DmdType LL]
      $s$wloop_sum_srX =
        \ (sc_srO :: [GHC.Types.Int]) (sc_srP :: GHC.Prim.Int#) ->
          case sc_srO of _ {
            [] -> sc_srP;
            : x_app [ALWAYS Just U(L)] xs_apq [ALWAYS Just L] ->
              case x_app of _ { GHC.Types.I# y_aqx [ALWAYS Just L] ->
              $wloop_sum_srz
                (GHC.Prim.+# sc_srP y_aqx)
                (Data.Stream.Right
                   @ (Data.Stream.L [GHC.Types.Int])
                   @ (Data.Stream.L [GHC.Types.Int])
                   (Data.Stream.L @ [GHC.Types.Int] xs_apq))
              }
          };
~ 略 ~
      LclId
      [Arity 2
       Str: DmdType LS
       RULES: "SC:$wloop_sum1" [0]
                  forall {sc_srO :: [GHC.Types.Int] sc_srP :: GHC.Prim.Int#}
                    $wloop_sum_srz sc_srP
                                   (Data.Stream.Right
                                      @ (Data.Stream.L [GHC.Types.Int])
                                      @ (Data.Stream.L [GHC.Types.Int])
                                      (Data.Stream.L @ [GHC.Types.Int] sc_srO))
                    = $s$wloop_sum_srX sc_srO sc_srP
              "SC:$wloop_sum0" [0]
                  forall {sc_srH :: [GHC.Types.Int] sc_srI :: GHC.Prim.Int#}
                    $wloop_sum_srz sc_srI
                                   (Data.Stream.Left
                                      @ (Data.Stream.L [GHC.Types.Int])
                                      @ (Data.Stream.L [GHC.Types.Int])
                                      (Data.Stream.L @ [GHC.Types.Int] sc_srH))
                    = $s$wloop_sum_srY sc_srH sc_srI]
~ 略 ~

 $s$wloop_sum_srX関数の定義では再帰呼び出しの際にEither型を使っていますが,最終的には"SC:$wloop_sum1"規則によってEither型を使わないよう書き換えられています。

      $s$wloop_sum_srX =
        \ (sc_srO :: [GHC.Types.Int]) (sc_srP :: GHC.Prim.Int#) ->
          case sc_srO of _ {
            [] -> sc_srP;
            : x_app [ALWAYS Just U(L)] xs_apq [ALWAYS Just L] ->
              case x_app of _ { GHC.Types.I# y_aqx [ALWAYS Just L] ->
              $wloop_sum_srz
                (GHC.Prim.+# sc_srP y_aqx)
                (Data.Stream.Right
                   @ (Data.Stream.L [GHC.Types.Int])
                   @ (Data.Stream.L [GHC.Types.Int])
                   (Data.Stream.L @ [GHC.Types.Int] xs_apq))
              }
          };
==> { "SC:$wloop_sum1"規則の適用 }
      $s$wloop_sum_srX =
        \ (sc_srO :: [GHC.Types.Int]) (sc_srP :: GHC.Prim.Int#) ->
          case sc_srO of _ {
            [] -> sc_srP;
            : x_app [ALWAYS Just U(L)] xs_apq [ALWAYS Just L] ->
              case x_app of _ { GHC.Types.I# y_aqx [ALWAYS Just L] ->
              $s$wloop_sum_srX
                xs_apq
                (GHC.Prim.+# sc_srP y_aqx)
              }
          };

 このように,SpecConstrは「無駄なデータ構成子を除去した再帰関数」と「その関数を使って『データ構成子を使用する式』を『データ構成子を使用しない式』に書き換える規則」を新たに定義します(参考リンク)。

 GHCではここで紹介した単純な例だけではなく,もっと複雑なコードでも最適化できるようにヒューリスティックな工夫が加えられています。こうした工夫について詳しく知りたい人は,SpecConstrについて書いた論文「Call-pattern specialisation for Haskell programs」やGHCのソースコードにあるSpecConstrのコメントを参照してください。

 なお,GHCではコンパイル時間とのトレードオフを考慮して,SpecConstrが対象とするコードでの変数束縛の回数をデフォルトで200回に制限しています。200回よりも多くの変数束縛を行うコードは大きすぎると見なされ,SpecConstrの対象にはなりません(参考リンク)。同様に,SpecConstrで特殊化する関数呼び出しの数をデフォルトでは3個に制限しています。より積極的な最適化を行うには,-fspec-constr-threshold=nオプションを使ってSpecConstrの対象とするコードの変数束縛の回数を変えたり,-fspec-constr-count=nオプションを使ってSpecConstrで特殊化する関数呼び出しの数を変えたりする必要があります(参考リンク1参考リンク2)。

 なお,-fno-spec-constr-thresholdオプションや-fno-spec-constr-countオプションを使うことで,これらの値を無制限に設定できます(参考リンク1参考リンク2)。


著者紹介 shelarcy

 2010年7月7日に,Haskellの新しい言語仕様である「The Haskell 2010 report」が公開されました。Haskell 2010では,階層化モジュールやbaseパッケージで提供されている関数のような,事実上の標準でありながらこれまで標準外として扱われていた機能が仕様に取り込まれました。また,実際のHaskellプログラミングに不可欠なFFIも正式に仕様に加わりました(参考リンク)。

 Haskell 2010でHaskellの言語仕様は大きく発展しましたが,残念ながらHaskell'から削られてしまった機能もあります。例えばこの連載でHaskell'に加わる機能として紹介した並行処理は,標準化のために込み入った議論が必要であることから,Haskell 2010では仕様には加えられませんでした(参考リンク1参考リンク2)。Haskell 2010に入らなかったこうした機能は,これまで通り処理系の拡張機能として扱う必要があります。これらの機能もできるだけ早くHaskell標準仕様に入って欲しいと思います。

 なお,GHCの開発版は,すでにHaskell 2010に対応しています(参考リンク1参考リンク2)。他のHaskell処理系でも,Haskell 2010への対応を意識して開発されているようです(参考リンク1参考リンク2)。