PR

メソッド呼び出しのコストとSPECIALIZE指示文

　前回のコラム「データ構造を操作する定型コードを除去できるか？」で型クラスでのメソッド呼び出しのコストを取り上げました。説明が不足していたので，ここで補足しておきます。

　多くの場合，型クラスのメソッドは，インスタンスである型ごとに別の定義を与えられます。多重定義された関数を使って処理を行うには，メソッドの使用時に引数として与えられた値の型を見て，その型に対応するインスタンスの実際の関数定義を呼び出すディスパッチ処理を行う必要があります。

　動的型付けの言語では，使用する値の型がプログラムの実行時に決定します。したがって，多重定義された関数でどの処理を実際に呼び出すかは実行時まで決まりません。実行時に値から型を判断するには，引数の値から実際の型を判断するための情報を得る必要があります。また，実行時に処理を呼び出す際にも，多重定義された関数から型情報によって実際の処理を取り出すために，辞書や参照テーブルなどを使用する必要があります。このため，多重定義された関数の実行にはコストが伴います。

　一方，Haskellのような静的型付けの言語では，値の型がコンパイル時に静的に決定します。したがって，値に型情報を持たせる必要はありません。実際に呼び出す処理も静的に決定します。つまり，多重定義された関数を使った処理の呼び出しは，実行時での処理の決定を伴わない単なる関数呼び出しとして扱えます。

　ただし，実行時のコストが完全になくなるわけではありません。例えばライブラリなどで，関数を定義するモジュールと使用するモジュールが分かれているような場合には，モジュールのコンパイル時にすべての型情報を得ることができません。このような状況で，多重定義された関数を使って多相関数を記述すると，その多相関数の中で用いる多重定義された関数には型情報が届かなくなります。この結果，使用する値の型に応じて実際の処理を呼び出す参照を割り出すための辞書やテーブルなどが，生成されるコードにそのまま残ることになります。

　例を見てみましょう。Specializeモジュールで階乗を計算する関数factorialを定義し，SpecializeUseモジュールのmain変数でこの関数を呼び出します。

module Specialize where

factorial :: Num a => a -> a
factorial 0 = 0
factorial n = n * factorial (n-1)

module SpecializeUse where
import Specialize

main = print $ factorial (33::Int)

　GHCが型クラスのメソッドを実際にどう扱っているかは，-ddump-simplオプションでコンパイルの途中の中間形式を出力することで確認できます（参考リンク）。まず，Specializeモジュールのfactorial関数をコンパイルした結果を見てみましょう。

$ ghc -c --make -O2 -ddump-simpl SpecializeUse.hs
[1 of 2] Compiling Specialize       ( Specialize.hs, Specialize.o )

==================== Tidy Core ====================
～ 略 ～
Specialize.factorial :: forall a_afx.
                        (GHC.Num.Num a_afx) =>
                        a_afx -> a_afx
[GlobalId]
[Arity 1
 NoCafRefs
 Str: DmdType L]
Specialize.factorial =
  \ (@ a_aij) ($dNum_aiG :: GHC.Num.Num a_aij) ->
    let {
      lit_skR :: a_aij
      [Str: DmdType]
      lit_skR =
        case $dNum_aiG
        of tpl_X4
        { GHC.Num.:DNum tpl1_B2
                        tpl2_B3
                        tpl3_B4
                        tpl4_B5
                        tpl5_B6
                        tpl6_B7
                        tpl7_B8
                        tpl8_B9
                        tpl9_Ba ->
        tpl9_Ba Specialize.lvl1
        } } in
    let {
      lit1_skP [ALWAYS Just L] :: a_aij
      [Str: DmdType]
      lit1_skP =
        case $dNum_aiG
        of tpl_X4
        { GHC.Num.:DNum tpl1_B2
        ～ 略 ～
                        tpl9_Ba ->
        tpl9_Ba Specialize.lvl
        } } in
    \ (ds_djG :: a_aij) ->
      case $dNum_aiG
      of tpl_X4
      { GHC.Num.:DNum tpl1_B2
      ～ 略 ～
                      tpl9_Ba ->
      case tpl1_B2 of tpl10_Xz { GHC.Classes.:DEq tpl11_XA tpl12_XC ->
      case tpl11_XA ds_djG lit1_skP of wild_B1 {
        GHC.Bool.False ->
          tpl4_B5
            ds_djG
            (letrec {
               factorial1_skT :: a_aij -> a_aij
               [Arity 1
                Str: DmdType L]
               factorial1_skT =
                 \ (ds1_Xkf :: a_aij) ->
                   case tpl11_XA ds1_Xkf lit1_skP of wild1_X1B {
                     GHC.Bool.False ->
                       tpl4_B5 ds1_Xkf (factorial1_skT (tpl5_B6 ds1_Xkf lit_skR)
);
                     GHC.Bool.True -> lit1_skP
                   }; } in
             factorial1_skT (tpl5_B6 ds_djG lit_skR));
        GHC.Bool.True -> lit1_skP
      }
      }
      }

==================== Tidy Core Rules ====================

　出力された中間形式は，Haskellから余計な構文糖衣を取り除いたコア言語（Core Language）で記述されています。コア言語はコア構文とも言います。GHCで使用されるコア言語であることを強調してGHCコアと呼ぶこともあります（参考リンク）。

　出力されたfactorialの最初の部分は，「\ (@ a_aij) ($dNum_aiG :: GHC.Num.Num a_aij) -> ...」という2引数のラムダ式になっています。第1引数であるa_aijはfactorial関数の内部で使われる型情報です。

　第2引数である$dNum_aiGが何であるかは，$dNum_aiGの型である「GHC.Num.Num a_aij」から判断できます。「GHC.Num.Num a_aij」からモジュール名を使った修飾「GHC.Num」を省き，a_aijに1番目の引数から与えられる型を代入すれば，「Num Int」のような見慣れた形になります。つまり，$dNum_aiGの型「GHC.Num.Num a_aij」は，Numクラスのインスタンスを示しているのです。

Prelude> :i Num
class (Eq a, Show a) => Num a where
～ 略 ～
instance Num Int -- Defined in GHC.Num
instance Num Integer -- Defined in GHC.Num
instance Num Double -- Defined in GHC.Float
instance Num Float -- Defined in GHC.Float

　引数$dNum_aiGに渡されるのはディスパッチすべきメソッドの情報を収めた辞書です（参考リンク1，参考リンク2）。ここではNumクラスのインスタンス対するメソッドの情報を辞書として渡しています。プログラムの実行時には，この辞書を使って，factorial関数で使用されているメソッドから実際の処理を呼び出します。

　ラムダ式の内側には「\ (ds_djG :: a_aij) -> ...」というラムダ式があります。この部分でfactorialの引数である実際の数値が渡されます。

　続いて，SpecializeUseのmain変数をコンパイルした結果を見てみましょう。

[2 of 2] Compiling SpecializeUse    ( SpecializeUse.hs, SpecializeUse.o )

==================== Tidy Core ====================
SpecializeUse.lvl :: GHC.Types.Int
[GlobalId]
[NoCafRefs]
SpecializeUse.lvl = GHC.Types.I# 33

SpecializeUse.lvl1 :: GHC.Base.String
[GlobalId]
[]
SpecializeUse.lvl1 =
  case Specialize.factorial
         @ GHC.Types.Int GHC.Num.$f6 SpecializeUse.lvl
  of w_aKx { GHC.Types.I# ww_aKz ->
  GHC.Show.$wshowSignedInt 0 ww_aKz (GHC.Types.[] @ GHC.Types.Char)
  }

SpecializeUse.a :: GHC.Prim.State# GHC.Prim.RealWorld
                   -> (# GHC.Prim.State# GHC.Prim.RealWorld, () #)
[GlobalId]
[Arity 1
 Str: DmdType L]
SpecializeUse.a =
  \ (eta_iEh :: GHC.Prim.State# GHC.Prim.RealWorld) ->
    case GHC.IO.a29 GHC.Handle.stdout SpecializeUse.lvl1 eta_iEh
    of wild_iKl { (# new_s_iKn, a89_iKo #) ->
    GHC.IO.$wa10 GHC.Handle.stdout '\n' new_s_iKn
    }

SpecializeUse.main :: GHC.IOBase.IO ()
[GlobalId]
[Arity 1
 Str: DmdType L]
SpecializeUse.main =
  SpecializeUse.a
  `cast` (sym ((GHC.IOBase.:CoIO) ())
          :: GHC.Prim.State# GHC.Prim.RealWorld
             -> (# GHC.Prim.State# GHC.Prim.RealWorld, () #)
               ~
             GHC.IOBase.IO ())

==================== Tidy Core Rules ====================

　main変数はコンパイル時に作成された変数aを呼び出し，変数aはコンパイル時に作成された変数lvl1を呼び出します。lvl1ではfactorial関数を使って値を計算し，次いでGHC.Show.$wshowSignedIntを使って計算した値を文字列に変換する処理です。lvl1でのfactorialの呼び出しには，Int型の型情報，辞書であるGHC.Num.$f6，factorialの計算の対象になるlvl，の三つの引数が使われます。

　では，main変数をfactorialと同じモジュールに記述するとどうなるでしょうか？ この場合には，main変数の定義式「main = print $ factorial (33::Int)」に記述されている「factorial関数がInt型の値に対して適用される」という事実を利用し，実行時のディスパッチ処理がない特別なfactorialが別途生成されます。そしてこの特別版のfactorialがmain変数内で実際に利用されます。

$ ghc -c -O2 -ddump-simpl Specialize.hs

==================== Tidy Core ====================
～ 略 ～
Rec {
Specialize.$wfactorial :: GHC.Prim.Int# -> GHC.Prim.Int#
[GlobalId]
[Arity 1
 NoCafRefs
 Str: DmdType L]
Specialize.$wfactorial =
  \ (ww_sFA :: GHC.Prim.Int#) ->
    case ww_sFA of wild_B1 {
      __DEFAULT ->
        case Specialize.$wfactorial (GHC.Prim.-# wild_B1 1)
        of ww1_sFE { __DEFAULT ->
        GHC.Prim.*# wild_B1 ww1_sFE
        };
      0 -> 0
    }
end Rec }

Specialize.factorial1 :: GHC.Types.Int -> GHC.Types.Int
[GlobalId]
[Arity 1
 Worker Specialize.$wfactorial
 NoCafRefs
 Str: DmdType U(L)m]
Specialize.factorial1 =
  __inline_me (\ (w_sFy :: GHC.Types.Int) ->
                 case w_sFy of w1_XFL { GHC.Types.I# ww_sFA ->
                 case Specialize.$wfactorial ww_sFA of ww1_sFE { __DEFAULT -
                 GHC.Types.I# ww1_sFE
                 }
                 })

Specialize.lvl2 :: GHC.Base.String
[GlobalId]
[]
Specialize.lvl2 =
  case Specialize.$wfactorial 33 of ww_sFE { __DEFAULT ->
  GHC.Show.$wshowSignedInt 0 ww_sFE (GHC.Types.[] @ GHC.Types.Char)
  }

～ 略 ～

Specialize.a =
  \ (eta_ayA :: GHC.Prim.State# GHC.Prim.RealWorld) ->
    case GHC.IO.a29 GHC.Handle.stdout Specialize.lvl2 eta_ayA

～ 略 ～

Specialize.main =
  Specialize.a
～ 略 ～

==================== Tidy Core Rules ====================
"SPEC Specialize.factorial [GHC.Types.Int]" ALWAYS
    forall {$dNum_swV :: GHC.Num.Num GHC.Types.Int}
      Specialize.factorial @ GHC.Types.Int $dNum_swV
      = Specialize.factorial1

　この特別なfactorial1は，実行時ディスパッチが不要であるため，計算の対象になる数値だけを渡すように定義されています。

　このように，多重定義された関数を利用して多相関数を定義する場合，同一モジュールで多相関数の型が確定するかどうかで処理の効率が異なります。同一モジュールで型が確定すれば，実行時のコストがない効率的な処理が行われます。一方，同一モジュール内で型が確定しない場合には，引数として型情報を受け取り，そこから実際に使用する関数を決めるためのコストが生じます。

　Haskellは，こうした実行時コストの問題に対処するためにSPECIALIZE指示文という機能を提供しています。GHCなどのSPECIALIZEに対応した処理系で，SPECIALIZE指示文に多相関数と型を指定することで，特定の型に特化（specialize）したバージョンの関数を生成するよう指示できます（参考リンク1，参考リンク2）。

module Specialize where

factorial :: Num a => a -> a
factorial 0 = 0
factorial n = n * factorial (n-1)
{-# SPECIALIZE factorial :: Int -> Int #-}
{-# SPECIALIZE factorial :: Integer -> Integer #-}

　この場合も，多重定義された関数に対する実行時ディスパッチは行われなくなります。

$ ghc -c -O2 -ddump-simpl Specialize.hs

==================== Tidy Core ====================
～ 略 ～
Rec {
Specialize.factorial1 :: GHC.Integer.Internals.Integer
                         -> GHC.Integer.Internals.Integer
[GlobalId]
[Arity 1
 NoCafRefs
 Str: DmdType S]
Specialize.factorial1 =
  \ (ds_djM :: GHC.Integer.Internals.Integer) ->
    case GHC.Integer.eqInteger ds_djM Specialize.lvl of wild_B1 {
      GHC.Bool.False ->
        GHC.Integer.timesInteger
          ds_djM
          (Specialize.factorial1
             (GHC.Integer.minusInteger ds_djM Specialize.lvl1));
      GHC.Bool.True -> Specialize.lvl
    }
end Rec }

Rec {
Specialize.$wfactorial :: GHC.Prim.Int# -> GHC.Prim.Int#
[GlobalId]
[Arity 1
 NoCafRefs
 Str: DmdType L]
Specialize.$wfactorial =
  \ (ww_sok :: GHC.Prim.Int#) ->
    case ww_sok of wild_B1 {
      __DEFAULT ->
        case Specialize.$wfactorial (GHC.Prim.-# wild_B1 1)
        of ww1_soo { __DEFAULT ->
        GHC.Prim.*# wild_B1 ww1_soo
        };
      0 -> 0
    }
end Rec }

Specialize.factorial2 :: GHC.Types.Int -> GHC.Types.Int
[GlobalId]
[Arity 1
 Worker Specialize.$wfactorial
 NoCafRefs
 Str: DmdType U(L)m]
Specialize.factorial2 =
～ 略 ～

　SPECIALIZEを利用した結果，Int型とInteger型に対して実行時ディスパッチがない特別なfactorialが生成されているのがわかります。

　SPECIALIZEを使えば実行時のディスパッチ処理を消去できます。その反面，余分な処理が必要になる分，生成されるバイナリが大きくなります。そのプログラムで扱うすべての型にSPECIALIZEを使用すると，コード肥大化（code bloat）の問題が生じます。あくまで，頻繁に使う型だけにSPECIALIZEを使用するようにしなければなりません。

　結局のところ，SPECIALIZEも究極の解決策ではありません。メソッドに対する実行時ディスパッチのコストは何らかの形で残ります。このことは忘れないでください。


著者紹介 shelarcy

　Data.Foldableモジュールでは，今回紹介したFoldableクラスのメソッドやその派生系であるfold*，toListのほかに，Foldableクラスのメソッドを使って定義できる関数もいくつか提供されています。

　リストに対するような処理を別のデータ構造に対して行いたい場合，まずはそのデータ構造が定義されているモジュールの関数を参照するべきです。そこに関数が存在しない場合には，Data.Foldableモジュールを参照するという選択肢もある，ということです。使用したいデータ構造がFoldableクラスのインスタンスとして定義されているなら，Data.Foldableの関数を使ってリストに対するような処理を行えます。このことは魅力的な選択肢になるでしょう。