为什么将数据重构为新类型可以加速我的 haskell 程序？

Question

我有一个程序，它遍历一个表达式树，该树对概率分布进行代数，采样或计算结果分布。

\n

我有两种计算分布的实现：一种 ( computeDistribution) 可以很好地与 monad 转换器重用，另一种 ( simpleDistribution) 我用手将所有内容具体化。我不想手动具体化所有内容，因为这将是采样和计算代码之间的代码重复。

\n

我还有两种数据表示形式：

\n

type Measure a = [(a, Rational)]\n-- data Distribution a = Distribution (Measure a) deriving Show\nnewtype Distribution a = Distribution (Measure a) deriving Show\n

\n

当我使用data带有可重用代码的版本时，计算 20d2 ( ) 的分布ghc -O3 program.hs; time ./program 20 > /dev/null大约需要一秒钟，这似乎太长了。选择更高的值n需要您自担风险。

\n

当我使用手工具体化代码，或者使用newtype任一实现的表示时，计算 20d2 ( time ./program 20 s > /dev/null) 只需眨眼的时间。

\n

为什么？

\n

我怎样才能找出原因？

\n

我对 Haskell 是如何执行的了解几乎为零。我发现有一张 thunk 图表，其形状与程序基本相同，但这就是我所知道的全部。

\n

我认为 的newtype表示与 的表示Distribution相同Measure，即它只是一个列表，而对于该data版本，每个都Distribution有点像单字段记录，除了指向所包含列表的指针，因此该data版本必须执行更多分配。这是真的？如果属实，这足以解释性能差异吗？

\n

我是使用 monad 变压器堆栈的新手。考虑\xe2\x80\x94 中的Let和Uniform情况，simpleDistribution它们的作用与基于 - 的实现相同吗walkTree？我怎么知道？

\n

这是我的程序。请注意，这Uniform n对应于滚动 n 面骰子（以防一元性令人惊讶）。

\n

更新：根据评论，我通过删除所有不会造成性能差距的内容来简化我的程序。我做了两个语义上的改变：概率现在是非规范化的，并且都是不稳定和错误的，并且简化步骤消失了。但我的程序的基本形状仍然存在。（请参阅非简化程序的问题编辑历史记录。）

\n

更新 2：我做了进一步的简化，Distribution通过一个小改动减少了列表 monad，删除了与概率有关的所有内容，并缩短了名称。我在使用data但不是时仍然观察到很大的性能差异newtype。

\n

import Control.Monad (liftM2)\nimport Control.Monad.Trans (lift)\nimport Control.Monad.Reader (ReaderT, runReaderT)\nimport System.Environment (getArgs)\nimport Text.Read (readMaybe)\n\nmain = do\n  args <- getArgs\n  let dieCount = case map readMaybe args of Just n : _ -> n; _ -> 10\n  let f = if ["s"] == (take 1 $ drop 1 $ args) then fast else slow\n  print $ f dieCount\n\nfast, slow :: Int -> P Integer\nfast n = walkTree n\nslow n = walkTree n `runReaderT` ()\n\nwalkTree 0 = uniform\nwalkTree n = liftM2 (+) (walkTree 0) (walkTree $ n - 1)\n\ndata P a = P [a] deriving Show\n-- newtype P a = P [a] deriving Show\n\nclass Monad m => MonadP m where uniform :: m Integer\ninstance MonadP P where uniform = P [1, 1]\ninstance MonadP p => MonadP (ReaderT env p) where uniform = lift uniform\n\ninstance Functor P where fmap f (P pxs) = P $ fmap f pxs\n\ninstance Applicative P where\n  pure x = P [x]\n  (P pfs) <*> (P pxs) = P $ pfs <*> pxs\n\ninstance Monad P where\n  (P pxs) >>= f = P $ do\n    x <- pxs\n    case f x of P fxs -> fxs\n\n

\n

Answer 1

我怎样才能找出原因？

总的来说，这很难。

最极端的方法是查看核心代码（可以通过运行 GHC 来生成-ddump-simpl）。这很快就会变得复杂，而且它基本上是一门全新的语言需要学习。你的程序已经足够大了，我很难从核心转储中学到很多东西。

找出原因的另一种方法是继续使用 GHC 并提出问题并学习 GHC 优化，直到您认识到某些模式。

为什么？

简而言之，我相信这是由于列表融合造成的。

注意：我不确定这个答案是否正确，并且需要比我现在愿意投入的时间/工作更多的时间/工作来验证。也就是说，它符合证据。

首先，我们可以通过运行来检查您所看到的这种减速是否是真正基本的结果而不是 GHC 优化触发的结果O0，也就是说，没有优化。在这种模式下，两种Distribution表示都会产生大约相同（极其长）的运行时间。这让我相信，数据表示本质上不是问题，而是版本触发的优化与newtype版本无关data。

当 GHC 运行在-O1或更高版本时，它会使用某些重写规则将列表的不同折叠和映射融合在一起，以便不需要分配中间值。（有关此概念的不错的教程，请参阅https://markkarpov.com/tutorial/ghc-optimization-and-fusion.html#fusion以及/sf/answers/2723711931/，其中另外还有一个链接到包含所有重写规则的要点base。）由于computeDistribution基本上只是一堆列表操作（本质上都是折叠），因此有可能触发这些操作。

关键在于，通过 的newtype表示Distribution，newtype 包装器在编译期间被擦除，并且允许列表操作融合。然而，通过data表示，包装器不会被删除，并且重写规则也不会触发。

因此，我将提出一个未经证实的主张：如果您希望data表示与表示一样快newtype，则需要设置类似于列表折叠的重写规则，但适用于类型Distribution。这可能涉及编写您自己的特殊折叠函数，然后重写您的 Functor/Applicative/Monad 实例以使用它们。