库 ghc 规则未激活

Question

fgl 是一个用于图形操作的 Haskell 库。该库附带了其基础 classes - Data.Graph.Inductive.PatriciaTree 的实现 - 据称已针对性能进行了高度调整。性能调整的一部分涉及 ghc RULES pragmas，用更快的专用版本替换某些通用函数。

但是，我的证据是这些规则似乎根本不起作用，我不明白为什么不起作用。对于那些试图完全复制我所看到的内容的人，我将我的测试项目放在 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 具有 class 函数的定义 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 方法的定义：（这是 class 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 包中存在一个错误，因为没有正确标记使用 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 函数，我也会将其包含在 class 中）然后，我以前根据 [=53= 编写的任何代码] 现在写成 (MyDynGraph gr) => ...。编译器规则为 Pt.Gr 实例激活，然后我得到每个函数的优化版本。

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

许多人的代码可以积极使用 SPECIALIZE 规则来获得优化版本；然而，有时这是不可能的，而且在没有重构大量应用程序的情况下，并不是在真正的生产代码中引起了我的问题。我有一个数据结构，其成员的类型为 (forall gr. G.DynGraph gr => tokType -> gr () (MyEdge c)) - 现在使用 MyDynGraph 作为 class 约束，但完全展开它以在签名中没有 forall gr.本来需要付出巨大的努力，而这样的签名会阻止专业化跨越该边界。

Answer 1

我没有做过任何实验，但这是我的猜测。 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 可能会选择在规则有机会触发之前立即内联它。

尝试根据 insEdge 的定义添加 {-# NOINLINE [0] insEdge #-}，看看会发生什么。如果可行，请向 fgl.

提交拉取请求

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

正如评论所揭示的那样，最大的问题不是过早的内联，而是未能专门化 insEdge。特别是，Data.Graph.Inductive.Graph 不会导出 insEdges 的展开，因此不可能将它及其调用的 insEdge 专门化为适当的类型。最终的解决方法是标记 insEdges INLINABLE，但出于谨慎起见，我仍然建议标记 insEdge NOINLINE [0]。

库 ghc 规则未激活

Library ghc RULES don't activate

haskell

ghc