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'了自身（通过完全分解身份）？

答案是，如果您在定义通用函数的同一模块中使用专业化，那么通常您不需要{-# 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'的Identitymonad 的任何使用（如果使用优化编译，并且 monad 被识别为Identity及时触发规则）。

但是，如果 GHC 对专门化的类型不够了解，它可能看不到任何好处并且不会专门化（我不知道它是否会尝试 - 到目前为止，我已经找到了每个专业化我看的时间）。

如果你想确定，看看核心。

如果您需要在不同的模块中进行特化，GHC 在编译定义模块时没有理由特化该函数，因此在这种情况下需要一个 pragma。从 ghc-7 开始，使用 pragma 可能更好，而不是{-# SPECIALISE #-}要求对一些精心挑选的类型进行专门化的{-# INLINABLE #-}编译指示，以便在导入模块时可以访问（稍微修改的）源代码，这允许专门化对于那里的任何需要的类型。

还需要添加其他任何内容（更多编译指示）吗？

不同的用途当然可能需要不同的 pragma，但根据经验，{#- INLINABLE #-}这是您最想要的。当然{-# RULES #-}可以做编译器不能自己做的魔术。

如何验证编译map'后的显式编写代码的优化程度map？

  • 查看生成的核心、asm 或 llvm 位码，以您最了解的为准（核心相对容易）。
  • 如果您从核心不确定并且需要知道，则将生成的代码与手写的专业化进行基准测试。最终，除非您在某个阶段（core/cmm/asm/llvm）获得相同的中间结果，否则基准测试是唯一确定的方法。
于 2012-10-20T21:08:53.387 回答