16

例として、リスト上にモナディックマップと非モナディックマップを記述したいとします。私はモナディックのものから始めましょう：

import Control.Monad
import Control.Monad.Identity

mapM' :: (Monad m) => (a -> m b) -> ([a] -> m [b])
mapM' _ [] = return []
mapM' f (x:xs) = liftM2 (:) (f x) (mapM f xs)

mapここで、コードを再利用して、 （コードを繰り返すのではなく）純粋なものを記述したいと思います。

map' :: (a -> b) -> ([a] -> [b])
map' f = runIdentity . mapM' (Identity . f)

明示的に書かれmap'ているかのように最適化するには何が必要ですか？map特に：

  1. 書く必要がありますか

    {-# SPECIALIZE mapM' :: (a -> Identity b) -> ([a] -> Identity [b]) #-}

    またはGHCは（完全map'に除外することによって）それ自体を最適化しますか？Identity

  2. 他に何か（より多くのプラグマ）を追加する必要がありますか？

  3. map'明示的に記述されたコードに対して、コンパイルがどの程度最適化されているかを確認するにはどうすればよいmapですか？
4

1 に答える 1

20

さて、コンパイラ自体に聞いてみましょう。

モジュールのコンパイル

module PMap where

import Control.Monad
import Control.Monad.Identity

mapM' :: (Monad m) => (a -> m b) -> ([a] -> m [b])
mapM' _ [] = return []
mapM' f (x:xs) = liftM2 (:) (f x) (mapM f xs)

map' :: (a -> b) -> ([a] -> [b])
map' f = runIdentity . mapM' (Identity . f)

with ghc -O2 -ddump-simpl -ddump-to-file PMap.hs（ghc-7.6.1、7.4.2は、一意の名前を除いて同じものを生成します）は、次のコアを生成します。map'

PMap.map'
  :: forall a_afB b_afC. (a_afB -> b_afC) -> [a_afB] -> [b_afC]
[GblId,
 Arity=2,
 Caf=NoCafRefs,
 Str=DmdType LS,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=2, Value=True,
         ConLike=True, WorkFree=True, Expandable=True,
         Guidance=IF_ARGS [60 30] 160 40}]
PMap.map' =
  \ (@ a_c) (@ b_d) (f_afK :: a_c -> b_d) (eta_B1 :: [a_c]) ->
    case eta_B1 of _ {
      [] -> GHC.Types.[] @ b_d;
      : x_afH xs_afI ->
        GHC.Types.:
          @ b_d
          (f_afK x_afH)
          (letrec {
             go_ahZ [Occ=LoopBreaker]
               :: [a_c] -> Data.Functor.Identity.Identity [b_d]
             [LclId, Arity=1, Str=DmdType S]
             go_ahZ =
               \ (ds_ai0 :: [a_c]) ->
                 case ds_ai0 of _ {
                   [] ->
                     (GHC.Types.[] @ b_d)
                     `cast` (Sym <(Data.Functor.Identity.NTCo:Identity <[b_d]>)>
                             :: [b_d] ~# Data.Functor.Identity.Identity [b_d]);
                   : y_ai5 ys_ai6 ->
                     (GHC.Types.:
                        @ b_d
                        (f_afK y_ai5)
                        ((go_ahZ ys_ai6)
                         `cast` (<Data.Functor.Identity.NTCo:Identity <[b_d]>>
                                 :: Data.Functor.Identity.Identity [b_d] ~# [b_d])))
                     `cast` (Sym <(Data.Functor.Identity.NTCo:Identity <[b_d]>)>
                             :: [b_d] ~# Data.Functor.Identity.Identity [b_d])
                 }; } in
           (go_ahZ xs_afI)
           `cast` (<Data.Functor.Identity.NTCo:Identity <[b_d]>>
                   :: Data.Functor.Identity.Identity [b_d] ~# [b_d]))
    }

うん、castsだけ、本当のオーバーヘッドはありません。goあなたは、まったく同じように行動する地元の労働者を手に入れますmap。

まとめ：必要なのは、だけです-O2。コア（-ddump-simpl）を確認するか、コードを読み取ることができる場合は、生成されたアセンブリ（-ddump-asm）またはLLVMビットコードを確認することで、コードがどの程度最適化されているかを確認できます-ddump-llvm。

少し詳しく説明するのはおそらく良いことです。について

書く必要がありますか

{-# SPECIALIZE mapM' :: (a -> Identity b) -> ([a] -> Identity [b]) #-}

または、GHCはmap'（IDを完全に除外することによって）それ自体を最適化しますか？

答えは、一般的な関数が定義されているのと同じモジュールで特殊化を使用する場合、一般に{-# SPECIALISE #-}プラグマは必要ないということです。GHCは、その利点があれば、独自に特殊化を作成します。上記のモジュールで、GHCは特殊化ルールを作成しました

"SPEC PMap.mapM' [Data.Functor.Identity.Identity]" [ALWAYS]
    forall (@ a_abG)
           (@ b_abH)
           ($dMonad_sdL :: GHC.Base.Monad Data.Functor.Identity.Identity).
      PMap.mapM' @ Data.Functor.Identity.Identity
                 @ a_abG
                 @ b_abH
                 $dMonad_sdL
      = PMap.mapM'_$smapM' @ a_abG @ b_abH

mapM'これは、定義モジュールの外部でのIdentityモナドでの使用にも役立ちます（最適化を使用してコンパイルされ、モナドがIdentityルールの実行に間に合うように認識される場合）。

ただし、GHCが専門化するタイプを十分に理解していない場合、メリットが見られず、専門化されない可能性があります（とにかく試行するかどうかを判断するのに十分な知識がありません-これまでのところ、それぞれの専門分野を見つけました私が見た時間）。

確認したい場合は、コアを見てください。

別のモジュールに特化する必要がある場合、GHCは定義モジュールをコンパイルするときに関数を特殊化する理由がないため、その場合はプラグマが必要です。いくつかの厳選されたタイプの特殊化を要求するプラグマの代わりに、{-# SPECIALISE #-}プラグマを使用する方がおそらく良いでしょう- {-# INLINABLE #-}（わずかに変更された）ソースコードがモジュールのインポートでアクセス可能になり、特殊化が可能になりますそこに必要なタイプの場合。

他に何か（より多くのプラグマ）を追加する必要がありますか？

もちろん、用途が異なれば、必要なプラグマも異なりますが、経験則として、{#- INLINABLE #-}最も必要なものです。そしてもちろん{-# RULES #-}、コンパイラが単独では実行できない魔法を実行できます。

map'明示的に記述されたコードに対して、コンパイルがどの程度最適化されているかを確認するにはどうすればよいmapですか？

  • 生成されたコア、asm、またはllvmビットコードのどちらか最もよく理解しているものを見てください（コアは比較的簡単です）。
  • コアから確信が持てず、知る必要がある場合は、作成されたコードを手書きの特殊化に対してベンチマークします。最終的に、ある段階（core / cmm / asm / llvm）で同一の中間結果が得られない限り、ベンチマークは確実に知る唯一の方法です。
于 2012-10-20T21:08:53.387 に答える