12

对于我在 Haskell 中的矢量图形库，我必须携带一个相当大的状态：线条描边参数、颜色、剪辑路径等。我知道这样做的两种方法。引用Haskell-cafe的评论：“我建议你要么使用具有可变状态的 reader monad，要么使用具有不可变状态的 state monad”。

这是我的问题：更新一个大的不可变状态会导致性能下降。使用大量 STRef 就像在 Haskell 中编写 C：它冗长且丑陋。

这是不可变状态：

data GfxState = GfxState {
  lineWidth :: Double,
  lineCap :: Int,
  color :: Color,
  clip :: Path,
  ...
}

setLineWidth :: Double -> State GfxState ()
setLineWidth x = modify (\state -> state { lineWidth = x })

据我所知，“state { lineWidth = x }”创建了一个新的 GfxState 并让旧的 GfxState 被垃圾收集。当状态很大并且经常更新时，这会降低性能。

这是可变状态：

data GfxState s = GfxState {
  lineWidth :: STRef s Double,
  lineCap   :: STRef s Int,
  color     :: STRef s Color,
  clip      :: STRef s Path,
  ...
  many more STRefs
}

setLineWidth :: GfxState s -> Double -> ST s ()
setLineWidth state x = writeSTRef (lineWidth state) x

现在我到处都得到 (GfxState s) 和 (ST s) 和 (STRef s)，这很冗长、令人困惑，并且违背了编写简短而富有表现力的代码的精神。我可以使用 C + FFI 来读取和更新大状态，但是由于我经常遇到这种模式，我希望有更好的方法。

4

3 回答 3

10

首先，我要问的是，您是否只是声称它会很慢，或者您是否分析过或至少注意到性能问题？否则猜测或做出假设并不是特别有用。无论如何，我建议对您的数据进行分组，目前看起来您只是在完全平坦地布置您的结构，而您可以将相关数据（例如与行相关的数据）分组到记录中。

您可能还想分离出真正需要处于状态 monad 中的位和其他不需要进入 reader/writer monad 的位，并使用 monad 转换器将它们组合起来。关于代码的优雅，我建议使用（一等/更高阶）记录库，如 fclabels。

我在一些小项目中大量使用了状态单子（在一堆单子变压器中），但我还没有注意到任何性能问题。

最后，您可以使用修改而不是获取/放置对。

于 2010-11-24T10:43:19.323 回答
8

即使您的记录中有很多字段，“创建一个新字段”也只是意味着复制指针。而“让旧的垃圾收集器”只是意味着以 GHC 的分代垃圾收集器处理速度非常快的方式为每个指针释放几个字节。这一切都归结为一些机器指令。因此，即使对于图形应用程序，这也可能根本不会影响您的性能。

如果您确定它确实会影响性能，请将这些字段组织成一棵树。您可以使用嵌套类型创建固定形状的树data，甚至只使用Data.IntMap. 这将为您提供平均log n / 2指针副本。如果您知道某些字段被更频繁地访问，您可以做得更好。

这将是一个非常罕见的应用程序，它的状态如此复杂，性能要求如此之高，以至于唯一的选择是STRef字段。但很高兴知道有这个选项。

于 2010-11-24T15:36:57.503 回答
6

顺便说一句，如果您担心性能，您当然应该通过拆箱来改进您的数据类型表示：

data GfxState = GfxState {
  lineWidth :: {-# UNPACK #-}!Double,
  lineCap   :: {-# UNPACK #-}!Int,
  color     :: {-# UNPACK #-}!Color,
  clip      :: Path,
  ...
}

通过解包构造函数，您可以提高数据的密度，从这样的堆结构开始：

在此处输入图像描述

到更密集、更严格的：

在此处输入图像描述

现在所有的原子类型都布置在连续的内存槽中。更新这种类型会快很多！顺便说一句，461 .. 是 pi 字段的 Word 表示形式，是我的查看器库中的一个错误

您还将减少空间泄漏的机会。

传递这种结构的成本将非常便宜，因为组件将存储在寄存器中。

于 2011-05-09T01:46:18.873 回答