图书馆ghc规则不激活

2018-06-11 13:51:48

fgl是一个用于图形操作的Haskell库。这个库附带一个基本类的实现 - Data.Graph.Inductive.PatriciaTree - 据说对性能高度优化。性能调优的一部分涉及ghc RULES编译指示，用特定版本取代某些通用函数，该版本速度更快。

但是，我的证据是，这些规则似乎根本不起作用，我不明白为什么不行。对于那些试图复制我所看到的内容的人，我已经在https://github.com/fizbin/GraphOptiTest上提供了我的测试项目，并使用ghc版本7.10.2 。

这是我的测试程序：

{-# LANGUAGE TupleSections #-}

module Main where

import Control.Exception
import Control.Monad
import Data.Graph.Inductive
import qualified Data.Graph.Inductive.PatriciaTree as Pt
import qualified MyPatriciaTree as MPt

makeGraph :: (DynGraph gr) => Int -> gr () Int
makeGraph n = mkGraph (map (,()) [1 .. n])
  (concatMap (x -> map (y -> (x, y, x*y)) [x .. n]) [1 .. n])

main1 :: IO ()
main1 =
  replicateM_ 200 $ let x = makeGraph 200 :: Pt.Gr () Int
                    in evaluate (length $ show x)

main2 :: IO ()
main2 =
  replicateM_ 200 $ let x = makeGraph 200 :: MPt.Gr () Int
                    in evaluate (length $ show x)

main :: IO ()
main = main1 >> main2

现在， Data.Graph.Inductive.PatriciaTree为类函数mkGraph定义了这个定义：

    mkGraph vs es   = insEdges es
                      . Gr
                      . IM.fromList
                      . map (second (l -> (IM.empty,l,IM.empty)))
                      $ vs

insEdges是模块Data.Graph.Inductive.Graph定义的函数，如下所示：

insEdges :: (DynGraph gr) => [LEdge b] -> gr a b -> gr a b
insEdges es g = foldl' (flip insEdge) g es

和Data.Graph.Inductive.PatriciaTree有关于insEdge ：

{-# RULES
      "insEdge/Data.Graph.Inductive.PatriciaTree"  insEdge = fastInsEdge
  #-}
fastInsEdge :: LEdge b -> Gr a b -> Gr a b
fastInsEdge (v, w, l) (Gr g) = g2 `seq` Gr g2
  where
    g1 = IM.adjust addSucc' v g
    g2 = IM.adjust addPred' w g1

    addSucc' (ps, l', ss) = (ps, l', IM.insertWith addLists w [l] ss)
    addPred' (ps, l', ss) = (IM.insertWith addLists v [l] ps, l', ss)

所以，理论上，当我在我的测试程序中运行main1 ，我应该将其编译成最终调用fastInsEdge东西。

为了测试这个，我比较了Data.Graph.Inductive.PatriciaTree的修改版本，它使用它作为mkGraph方法的定义:(这是在MyPatriciaTree使用的main2 ）

    mkGraph vs es   = doInsEdges
                      . Gr
                      . IM.fromList
                      . map (second (l -> (IM.empty,l,IM.empty)))
                      $ vs
      where
        doInsEdges g = foldl' (flip fastInsEdge) g es

当我运行我的测试程序（在cabal configure --enable-library-profiling --enable-executable-profiling和cabal build GraphOptiTest ）时， main2方法会main1方法。它甚至没有接近 - 配置文件显示该程序的时间的99.2％花费在main1 。（并且改变程序来运行main2显示是的， main2自己真的很快）

是的，我在我的cabal文件的ghc-options部分中有-O 。

尝试像-ddump-rule-firings这样的ghc选项并没有真正的帮助 - 我只能看到这些替换规则并没有被解雇，但我不知道为什么。我不知道如何让编译器告诉我为什么它没有激活替换规则。

造就什么用乱搞发现fgl响应@下面dfeuer的答案的来源：

如果我将一个专门的insEdges版本添加到Data.Graph.Inductive.PatriciaTree中：

{-# RULES
      "insEdges/Data.Graph.Inductive.PatriciaTree"  insEdges = fastInsEdges
  #-}
fastInsEdges :: [LEdge b] -> Gr a b -> Gr a b
fastInsEdges es g = foldl' (flip fastInsEdge) g es

然后main1和main2现在都快了。此替换规则触发; 为什么不是另一个呢？（不，告诉ghc NOINLINE函数insEdge不行）

结语：

所以现在有一个与fgl包一起提交的bug，用于不标记他们的函数，这些函数适当地使用insEdge和insNode以便使用快速版本。但是在我的代码中，我现在正在解决这个问题，在更多情况下，解决方法可能会有用，所以我想我会分享它。现在我的代码的顶部，我有：

import qualified Data.Graph.Inductive as G
import qualified Data.Graph.Inductive.PatriciaTree as Pt

-- Work around design and implementation performance issues
-- in the Data.Graph.Inductive package.
-- Specifically, the tuned versions of insNode, insEdge, gmap, nmap, and emap
-- for PatriciaTree graphs are exposed only through RULES pragmas, meaning
-- that you only get them when the compiler can specialize the function
-- to that specific instance of G.DynGraph. Therefore, I create my own
-- type class with the functions that have specialized versions and use that
-- type class here; the compiler then can do the specialized RULES
-- replacement on the Pt.Gr instance of my class.
class (G.DynGraph gr) => MyDynGraph gr where
  mkGraph :: [G.LNode a] -> [G.LEdge b] -> gr a b
  insNodes :: [G.LNode a] -> gr a b -> gr a b
  insEdges :: [G.LEdge b] -> gr a b -> gr a b
  insNode :: G.LNode a -> gr a b -> gr a b
  insEdge :: G.LEdge b -> gr a b -> gr a b
  gmap :: (G.Context a b -> G.Context c d) -> gr a b -> gr c d
  nmap :: (a -> c) -> gr a b -> gr c b
  emap :: (b -> c) -> gr a b -> gr a c

instance MyDynGraph Pt.Gr where
  mkGraph nodes edges = insEdges edges $ G.mkGraph nodes []
  insNodes vs g = foldl' (flip G.insNode) g vs
  insEdges es g = foldl' (flip G.insEdge) g es
  insNode = G.insNode
  insEdge = G.insEdge
  gmap = G.gmap
  nmap = G.nmap
  emap = G.emap

（如果我在代码中使用了nemap函数，我也会将它包含在该类中）然后，我以前用(G.DynGraph gr) => ...编写的任何代码现在都是用(MyDynGraph gr) => ... 编译器RULES为Pt.Gr实例激活，然后我得到每个函数的优化版本。

从本质上讲，这消除了编译器将任何这些函数内联到调用代码中的能力，并可能进行其他优化以始终获得优化版本。（以及运行时额外指针间接寻址的代价，但相比之下，这是微不足道的）因为分析表明，其他优化从来没有产生过任何重要的结果，这对我来说是一个明显的净赢。

许多人的代码可以积极使用SPECIALIZE规则来获得优化版本。然而，有时这是不可能的，而且在真正的生产代码中没有导致我的问题而没有重构大量的应用程序。我有一个具有类型的成员的数据结构（例如， (forall gr. G.DynGraph gr => tokType -> gr () (MyEdge c)) - 现在使用MyDynGraph作为类约束，但完全展开它却没有forall gr. 在签名上会是一个巨大的努力，而这样的签名会阻止专业化跨越这个边界进行工作。

我还没有做过任何实验，但这是我的猜测。 insEdge函数没有标记（分阶段） INLINE或NOINLINE ，所以只要完全应用，内联就可以自由地将其内联。在insEdges的定义中，我们看到

foldl' (flip insEdge) g es

内联foldl'给出

foldr f' id es g
  where f' x k z = k $! flip insEdge z x

flip现已完全应用，因此我们可以将其内联：

foldr f' id es g
  where f' x k z = k $! insEdge x z

现在insEdge已经被完全应用，所以GHC可能会选择将其嵌入到游戏规则之前。

尝试添加{-# NOINLINE [0] insEdge #-}向右的定义insEdge看看会发生什么。如果有效，请将提交请求提交给fgl 。

PS在我看来，这种事情应该通过使用具有默认值的类方法来完成，而不是重写规则。规则总是有点挑剔。

正如评论所揭示的那样，大问题并不是过早内联，而是没有专门化insEdge 。特别是， Data.Graph.Inductive.Graph不会为insEdges导出展开，因此无法将它专门化，并将它调用的insEdge专门insEdge适当的类型。最终的解决方案是标记insEdges INLINABLE ，但我仍然建议将insEdge NOINLINE [0]标记为非常小心。

链接地址: http://www.djcxy.com/p/33191.html

上一篇: Library ghc RULES don't activate

下一篇: Running GHC's LLVM output through the LLVM bitcode linker first