在Haskell中快速更新大状态

Question

为了我的Haskell矢量图库，我必须携带一个相当大的状态：线条描边参数、颜色、剪辑路径等。我知道两种做法。引用自 Haskell-cafe 的一条评论：“我建议你使用具有可变状态的读取器单子或不可变状态的状态单子。”

这是我的问题：更新一个大的不可变状态会严重影响性能。大量使用STRefs就像在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来读取和更新大状态，但由于我经常遇到这种模式，所以我希望有更好的方法。

- DJS

---

你现在所做的就像是在Haskell中编写C代码，因为我看到你暗示的库接口是非常命令式的。setLineWidth？使用更多函数式风格的接口将使实现更具有函数式特性。 - luqui

对于第一个版本，使用“state {lineWidth = x}”更新状态时，应该与旧状态共享，因此我不希望它创建一个全新的状态。您可能希望将状态的至少“原子”元素设为严格（例如，lineWidth变为！Double和lineCap变为！Int），我怀疑这可能会严重影响性能。 - stephen tetley

@Stephen，好的，“values”与旧记录共享。但如果有一个拥有100个字段的记录，每次更新记录都会复制100个指针。 - luqui

@luqui - 的确如此，但这强烈暗示“不要使用100个字段创建记录”，应该添加一些嵌套来将相关元素分组。从可理解性的角度来看，这将更加模块化且更好。 - stephen tetley

@luqui，setLineWidth不属于接口。该接口有一个函数，它接受一系列命令（moveTo、lineTo、setColor、setLineWidth、stroke等），并生成一系列图形对象（Stroke {path::Path, color::Color等）。 - DJS

@DJS，你刚才说“setLineWidth”是其中一个命令。这就是我想要的。如果你正在解决的问题是从标准输入中获取一系列命令并绘制它们，那很好。但是，如果你要编写更多使用此功能的Haskell代码，则不建议使用命令列表作为接口。组合器库将更易于使用。请参见http://hackage.haskell.org/packages/archive/graphics-drawingcombinators/0.3/doc/html/Graphics-DrawingCombinators.html以获得灵感。 - luqui

Answer 1

首先我必须询问您是否只是声称它会变慢，还是已经进行了性能分析或至少注意到了性能问题？否则猜测或做出假设并不是特别有用的。无论如何，我建议分组数据，目前看起来您只是完全展平了结构，而实际上您可以将相关数据（例如与行相关的数据）分组成记录。

您可能还需要将确实需要在状态单子中的位和不需要的位分开，使用阅读器/编写器单子将其组合，并使用monad变换器。关于代码的优雅性，我建议使用（一级/高阶）记录库，例如fclabels。

我在几个小项目中大量使用状态单子（在单子变换器的堆栈中），但尚未注意到任何性能问题。

最后，您可以使用modify而不是get / put对。

- snk_kid

---

谢谢。fclabels 库看起来很有趣。 - DJS

我已经修改了示例代码，使用“修改”代替“获取”和“放置”。谢谢。 - DJS

Answer 2

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

如果您确信它确实会影响性能，请将字段组织成树形结构。您可以使用嵌套的 data 类型创建固定形状的树，甚至只需使用 Data.IntMap。这将使您平均需要进行 log n / 2 次指针复制。如果您知道某些字段经常被访问，则可以做得更好。

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

- Yitz

---

谢谢，我想这就是我要做的。坚持使用不可变状态（即没有ST monad），并在性能优化时将字段移动到树形式。我有点失望，因为这是自从切换到Haskell以来我第一次真正想念C。 - DJS

Answer 3

作为旁注，如果您关心性能，您应该通过取消装箱来改善数据类型表示：

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

通过拆解构造器，可以提高数据密度。从像这样的堆结构：

到更加紧凑、严格的结构：

现在所有原子类型都放置在连续的内存位置上。更新此类型将会快得多！顺便说一下，“461..”是pi字段的Word表示，在我的查看器库中有一个错误。

您还将减少空间泄漏的可能性。传递这样的结构的成本将非常便宜，因为组件将存储在寄存器中。

- Don Stewart