5

私が次のものを持っているとしましょう：

data FuncAndValue v res = FuncAndValue (v -> res) v

chain :: (res -> new_res) -> FuncAndValue v res -> FuncAndValue v new_res
chain new_f (FuncAndValue old_f v) = FuncAndValue (new_f . old_f) v

GHCは、インライン化によって機能を1つの機能new_fに結合できる可能性がありますか？old_f

基本的に、関数をデータ型に格納すると、とにかく最適化が妨げられますか。

GHCが関数のチェーンを1つに簡単に構成できるようにしたいと思います（つまり、構造体の「合計」には、forループのように実行されるように、サンクを表すサンクへの繰り返しの呼び出しが含まれず(+)、代わりにインライン化されます。(+)関数をデータ型に格納し、後でそれらにアクセスしてもこれが妨げられないことを望んでいます。

4

1 に答える 1

4

new_fGHC はインライン化によって関数を結合old_fし、単一の関数にすることができる可能性がありますか?

はい、介在せずに同じことができればFuncAndValue。もちろん、関数の展開を利用できるようにする必要があります。しかし、機会があれば、関数を a でラップしてFuncAndValueもほとんど違いはありません。

しかしGHC自身に聞いてみましょう。最初のタイプと非常に単純なchaining:

module FuncAndValue where

data FuncAndValue v res = FuncAndValue (v -> res) v

infixr 7 `chain`

chain :: (res -> new_res) -> FuncAndValue v res -> FuncAndValue v new_res
chain new_f (FuncAndValue old_f v) = FuncAndValue (new_f . old_f) v

apply :: FuncAndValue v res -> res
apply (FuncAndValue f x) = f x

trivia :: FuncAndValue Int (Int,Int)
trivia = FuncAndValue (\x -> (2*x - 1, 3*x + 2)) 1

composed :: FuncAndValue Int Int
composed = chain (uncurry (+)) trivia

と (の興味深い部分) と について取得したtriviaコアcomposed:

FuncAndValue.trivia1 =
  \ (x_af2 :: GHC.Types.Int) ->
    (case x_af2 of _ { GHC.Types.I# y_agp ->
     GHC.Types.I# (GHC.Prim.-# (GHC.Prim.*# 2 y_agp) 1)
     },
     case x_af2 of _ { GHC.Types.I# y_agp ->
     GHC.Types.I# (GHC.Prim.+# (GHC.Prim.*# 3 y_agp) 2)
     })

FuncAndValue.composed2 =
  \ (x_agg :: GHC.Types.Int) ->
    case x_agg of _ { GHC.Types.I# y_agp ->
    GHC.Types.I#
      (GHC.Prim.+#
         (GHC.Prim.-# (GHC.Prim.*# 2 y_agp) 1)
         (GHC.Prim.+# (GHC.Prim.*# 3 y_agp) 2))
    }

見られることはありません(.)。の 2 つcaseのtriviaは結合されているため、 には 1 つしかありませんcomposed。誰かがGHCに十分な代数を教えて単純化\x -> (2*x-1) + (3*x+2)してにしない限り\x -> 5*x + 1、それはあなたが望むことができるほど良い. 別のモジュールであっても、コンパイル時にapply composed縮小されます。6

しかし、これは非常に単純なことでした。

のインライン化可能なバージョンuntil( の現在の定義untilは再帰的であるため、GHC はインライン化しません)、

module WWUntil where

wwUntil :: (a -> Bool) -> (a -> a) -> a -> a
wwUntil p f = recur
  where
    recur x
        | p x       = x
        | otherwise = recur (f x)

別の単純な機能は独自のモジュールであり、

collatzStep :: Int -> Int
collatzStep n
    | n .&. 1 == 0  = n `unsafeShiftR` 1
    | otherwise     = 3*n + 1

そして最後にナッツ

module Hailstone (collatzLength, hailstone) where

import FuncAndValue
import CollatzStep
import WWUntil

data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !Int

fstP :: P -> Int
fstP (P x _) = x

sndP :: P -> Int
sndP (P _ y) = y

hailstone :: Int -> FuncAndValue Int Int
hailstone n = sndP `chain` wwUntil ((== 1) . fstP) (\(P n k) -> P (collatzStep n) (k+1))
                   `chain` FuncAndValue (\x -> P x 0) n

collatzLength :: Int -> Int
collatzLength = apply . hailstone

厳密なペアを使用することで、厳密性アナライザーを少し助けました。バニラ(,)では、各ステップで 1 を追加した後に 2 番目のコンポーネントが箱から出され、再度箱に入れられますが、そのような無駄には耐えられません ;) しかし、それ以外に関連する違いはありません。

そして (興味深い部分) コア GHC は以下を生成します:

Rec {
Hailstone.$wrecur [Occ=LoopBreaker]
  :: GHC.Prim.Int#
     -> GHC.Prim.Int# -> (# GHC.Prim.Int#, GHC.Prim.Int# #)
[GblId, Arity=2, Caf=NoCafRefs, Str=DmdType LL]
Hailstone.$wrecur =
  \ (ww_sqq :: GHC.Prim.Int#) (ww1_sqr :: GHC.Prim.Int#) ->
    case ww_sqq of wild_Xm {
      __DEFAULT ->
        case GHC.Prim.word2Int#
               (GHC.Prim.and# (GHC.Prim.int2Word# wild_Xm) (__word 1))
        of _ {
          __DEFAULT ->
            Hailstone.$wrecur
              (GHC.Prim.+# (GHC.Prim.*# 3 wild_Xm) 1) (GHC.Prim.+# ww1_sqr 1);
          0 ->
            Hailstone.$wrecur
              (GHC.Prim.uncheckedIShiftRA# wild_Xm 1) (GHC.Prim.+# ww1_sqr 1)
        };
      1 -> (# 1, ww1_sqr #)
    }
end Rec }

lvl_rsz :: GHC.Types.Int -> GHC.Types.Int
[GblId, Arity=1, Caf=NoCafRefs]
lvl_rsz =
  \ (x_iog :: GHC.Types.Int) ->
    case x_iog of _ { GHC.Types.I# tpl1_B4 ->
    case Hailstone.$wrecur tpl1_B4 0 of _ { (# _, ww2_sqH #) ->
    GHC.Types.I# ww2_sqH
    }
    }

それはまさにあなたがなしで得るものですFuncAndValue。すべてがきれいに並んでいて、美しいタイトなループです。

基本的に、関数をデータ型に格納すると、とにかく最適化が妨げられます。

関数を十分なレイヤーでラップする場合は、そうです。しかし、それは他の値と同じです。

于 2013-01-06T14:54:50.297 に答える