haskell - 型クラス関数呼び出しのための GHC コード生成

Question

Haskell で型クラスのインスタンスを定義するには、型クラスが必要とする関数の辞書を提供する必要があります。つまり、のインスタンスを定義するにはBounded、との定義を提供する必要がありminBoundますmaxBound。

この質問の目的のために、このディクショナリvtblを型クラスインスタンスのと呼びましょう。これが貧弱な類推であるかどうか教えてください。

私の質問は、型クラス関数を呼び出すときに、GHC からどのようなコード生成を期待できるかについてです。そのような場合、3 つの可能性が考えられます。

実行時に実装関数がダウンしていることを確認するための vtbl ルックアップ
vtbl ルックアップはコンパイル時に行われ、実装関数への直接呼び出しが生成されたコードで発行されます。
vtbl ルックアップはコンパイル時に行われ、実装関数は呼び出しサイトでインライン化されます。

これらのそれぞれがいつ発生するか、または他の可能性があるかどうかを理解したいと思います。

また、型クラスが「メイン」コンパイルユニットの一部ではなく、個別にコンパイルされたモジュールで定義されているかどうかは重要ですか?

実行可能なプログラムでは、Haskell はプログラム内のすべての関数と式の型を認識しているようです。したがって、型クラス関数を呼び出すとき、コンパイラは vtbl が何であるか、および呼び出すべき実装関数を正確に認識している必要があります。コンパイラが少なくとも実装関数への直接呼び出しを生成することを期待しています。これは本当ですか？

(ここでは、実行しないモジュールをコンパイルすることと区別するために、「実行可能なプログラム」と呼んでいます。)

score 20 · Accepted Answer

すべての良い質問と同様に、答えは「場合による」です。経験則では、型クラスのポリモーフィックコードには実行時のコストがかかります。ただし、ライブラリの作成者には、GHC の書き換え規則を使用してこのコストを排除する柔軟性があり、特に、多相関数の単相バージョンを自動的に作成し、多相関数が単相で使用されると推論できる場合はいつでもそれらを使用できる{-# SPECIALIZE #-}プラグマがあります。タイプ。（これを行うための価格は、ライブラリと実行可能サイズだと思います。）

-ddump-simplghc のフラグを使用して、特定のコードセグメントに関する質問に答えることができます。たとえば、短い Haskell ファイルは次のとおりです。

vDouble :: Double
vDouble = 3
vInt = length [2..5]
main = print (vDouble + realToFrac vInt)

最適化を行わないと、GHC が実行時に辞書検索を行うことがわかります。

Main.main :: GHC.Types.IO ()
[GblId]
Main.main =
  System.IO.print
    @ GHC.Types.Double
    GHC.Float.$fShowDouble
    (GHC.Num.+
       @ GHC.Types.Double
       GHC.Float.$fNumDouble
       (GHC.Types.D# 3.0)
       (GHC.Real.realToFrac
          @ GHC.Types.Int
          @ GHC.Types.Double
          GHC.Real.$fRealInt
          GHC.Float.$fFractionalDouble
          (GHC.List.length
             @ GHC.Integer.Type.Integer
             (GHC.Enum.enumFromTo
                @ GHC.Integer.Type.Integer
                GHC.Enum.$fEnumInteger
                (__integer 2)
                (__integer 5)))))

...関連するビットはrealToFrac @Int @Double. 一方、では-O2、辞書検索が静的に実行され、実装がインライン化されていることがわかります。結果はへの 1 回の呼び出しint2Double#です。

Main.main2 =
  case GHC.List.$wlen @ GHC.Integer.Type.Integer Main.main3 0
  of ww_a1Oq { __DEFAULT ->
  GHC.Float.$w$sshowSignedFloat
    GHC.Float.$fShowDouble_$sshowFloat
    GHC.Show.shows26
    (GHC.Prim.+## 3.0 (GHC.Prim.int2Double# ww_a1Oq))
    (GHC.Types.[] @ GHC.Types.Char)
  }

また、ライブラリ作成者は、多相関数を単相関数の呼び出しに書き換えることを選択できますが、単相関数の実装をインライン化することはできません。これは、あなたが提案したすべての可能性 (およびそれ以上) が可能であることを意味します。

score 11 · Accepted Answer

コンパイラがコンパイル時に、使用している実際の型を「伝える」ことができる場合、コンパイル時にメソッドの検索が行われます。それ以外の場合は、実行時に発生します。ルックアップがコンパイル時に発生する場合、メソッドのサイズによっては、メソッドコードがインライン化される場合があります。（これは通常の関数にも当てはまります。コンパイラが呼び出している関数を認識している場合、その関数が「十分に小さい」場合はインライン化します。）

たとえば、を考えてみましょう(sum [1 .. 10]) :: Integer。ここで、コンパイラはリストがテイクのリストであることを静的に認識しているため、関数 forIntegerをインライン化できます。一方、次のようなことをすると+Integer

foo :: Num x => [x] -> x
foo xs = sum xs - head x

次に、を呼び出すsumと、コンパイラは使用している型を認識しません。( に与えられた型によって異なりますfoo)、コンパイル時のルックアップを行うことはできません。

一方、{-# SPECIALIZE #-}プラグマを使用すると、次のようなことができます

{-# SPECIALIZE foo:: [Int] -> Int #-}

fooこれが行うことは、入力が値のリストである特別なバージョンをコンパイルするようにコンパイラに指示することIntです。これは明らかに、そのバージョンの場合、コンパイラがコンパイル時にすべてのメソッド検索を実行できることを意味します (そして、ほぼ確実にすべてをインライン化します)。現在、には 2 つのバージョンがあります。1 つfooは任意の型で機能し、実行時の型検索を行います。もう 1 つはのみで機能しますIntが、[おそらく] はるかに高速です。

関数を呼び出すときfoo、コンパイラは呼び出すバージョンを決定する必要があります。コンパイラがコンパイル時に、Intバージョンが必要であることを「伝える」ことができる場合、コンパイラはそれを行います。どのタイプを使用するかを「判断」できない場合は、低速の any-type バージョンが使用されます。

1 つの関数に対して複数の特殊化を行うことができることに注意してください。たとえば、次のことができます

{-# SPECIALIZE foo :: [Int] -> Int #-}
{-# SPECIALIZE foo :: [Double] -> Double #-}
{-# SPECIALIZE foo :: [Complex Double] -> Complex Double #-}

これで、コンパイラは、これらの型のいずれかを使用していると判断できる場合はいつでも、その型にハードコードされたバージョンを使用します。ただし、使用している型をコンパイラが認識できない場合、特殊化されたバージョンは使用されず、常にポリモーフィックバージョンが使用されます。(これはfoo、たとえば、を呼び出す関数を特殊化する必要があることを意味する場合があります。)

コンパイラのコア出力を調べれば、特定の状況でコンパイラが何をしたかを正確に把握できるでしょう。あなたはおそらく狂ったように狂ってしまうでしょう...

score 9 · Accepted Answer

他の回答が説明しているように、これらはいずれもさまざまな状況で発生する可能性があります。特定の関数呼び出しを確認する唯一の方法は、生成されたコアを確認することです。とはいえ、何が起こるかをよく知ることができる場合もあります。

モノモーフィック型で型クラスメソッドを使用する。

コンパイル時に型が完全にわかっている状況で型クラスのメソッドが呼び出されると、GHC はコンパイル時にルックアップを実行します。例えば

isFive :: Int -> Bool
isFive i = i == 5

ここで、コンパイラは s Eq 辞書が必要であることを認識しているIntため、関数を静的に呼び出すコードを発行します。その呼び出しがインライン化されるかどうかは、GHC の通常のインライン化規則と、INLINEプラグマがクラスメソッド定義に適用されるかどうかに依存します。

ポリモーフィック関数の公開

コンパイルされたモジュールからポリモーフィック関数が公開されている場合、基本的なケースは、実行時にルックアップを実行する必要があるということです。

module Foo (isFiveP) where

isFiveP :: (Eq a, Num a) => a -> Bool
isFiveP i = i == 5

GHC が実際に行うことは、これを (多かれ少なかれ) 形式の関数に変換することです。

isFiveP_ eqDict numDict i = (eq_op eqDict) i (fromIntegral_fn numDict 5)

そのため、実行時に関数ルックアップを実行する必要があります。

とにかく、それがベースケースです。実際に起こっていることは、GHC がクロスモジュールのインライン化に対して非常に積極的であるということです。 isFiveP呼び出しサイトにインライン化されるほど小さいです。呼び出しサイトで型を判別できる場合、辞書検索はすべてコンパイル時に実行されます。ポリモーフィック関数が呼び出しサイトで直接インライン化されていなくても、コードが関数 (クラスディクショナリパラメーターを含む) が可能な形式に到達した場合、GHC の通常の関数変換により、コンパイル時にディクショナリルックアップが引き続き実行される可能性があります。静的に知られている辞書に適用されます。

haskell - 型クラス関数呼び出しのための GHC コード生成

3 に答える 3

Related

Reference