在Haskell中快速更新大国 [英] Updating a Big State Fast in Haskell

问题描述

对于我在Haskell中的矢量图形库，我必须携带一个相当大的状态：行行程参数，颜色，剪辑路径等。我知道这样做的两种方法。引用 Haskell-cafe 的评论：我会建议您使用具有可变状态的读卡器monad，或使用不可变状态的状态monad。

这是我的问题：更新一个很大的不可变状态是一种表演杀戮。使用大量的STRefs就像在Haskell中编写C：它是冗长和丑陋的。

这是不可变的状态：

  data GfxState = GfxState {
 lineWidth :: Double，
 lineCap :: Int，
 color :: Color，
 clip ::路径，
 ... 
} 
 
 setLineWidth :: Double  - >状态GfxState（）
 setLineWidth x = modify（\state  - > state {lineWidth = x}）
  

据我所知，state {lineWidth = x}创建一个新的GfxState，让旧的被垃圾回收。当状态很大并经常更新时，会导致性能下降。

这是可变状态：

  data GfxState s = GfxState {
 lineWidth :: STRef s Double，
 lineCap :: STRef s Int，
 color :: STRef s Color，
 clip :: STRef s Path，
 ... 
更多STRefs 
} 
 
 setLineWidth :: GfxState s  - >双 - > ST s（）
 setLineWidth state x = writeSTRef（lineWidth state）x 
  

现在我得到（GfxState s）和（ST）和（STRef s）遍布整个地方，这是冗长的，令人困惑的，并且打破了编写简短和表现力的代码的精神。我可以使用C + FFI阅读和更新大的状态，但是由于我经常遇到这种模式，我希望有一个更好的方法。

解决方案

即使在您的记录中有相当多的字段，创建新的只是意味着复制指针。 让旧的垃圾收集只是指出，GHC的代代垃圾收集器处理速度非常快，为每个指针释放几个字节。这些都归结为少量的机器说明书。所以即使是一个图形应用程序，这很可能不会杀死你的表现。

如果你确定它真的影响性能，将这些字段组织成树。您可以使用嵌套的数据类型创建一个固定形状的树，甚至只需使用 Data.IntMap 。这将使您平均获得 log n / 2 指针副本。如果您知道某些字段的访问频率更高，您可以做得更好。

这是一个非常罕见的应用程序，其状态如此复杂，其性能要求如此很重，唯一的选项是 STRef 字段。但是很高兴知道选项在那里。

For my vector graphics library in Haskell I must carry around a rather big state: line stroke parameters, colors, clip path etc. I know two ways of doing this. Quoting a comment from Haskell-cafe: "I would suggest you either use a reader monad with mutable state, or a state monad with immutable state".

Here is my problem: updating a big immutable state is a performance kill. Using lots of STRefs is like writing C in Haskell: it's verbose and ugly.

Here is the immutable state:

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

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

As far as I know, "state { lineWidth = x }" creates a new GfxState and lets the old one be garbage collected. This kills performance when the state is big and updated often.

Here is the mutable state:

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

Now I get (GfxState s) and (ST s) and (STRef s) all over the place, which is verbose, confusing, and beats the spirit of writing short and expressive code. I could use C + FFI to read and update the big state, but since I encounter this pattern quite often, I'm hoping there's a better way.

解决方案

Even with quite a few fields in your record, "creating a new one" just means copying pointers. And "letting the old one be garbage collected" just means releasing a few bytes for each pointer in a way that GHC's generational garbage collector is very fast at handling. It all boils down to a handful of machine instructions. So even for a graphics application, that very well may not kill your performance at all.

If you are sure that it really does impact on performance, organize the fields into a tree. You can create a fixed-shape tree by using nested data types, or even just use Data.IntMap. That will get you an average of log n / 2 pointer copies. You can do even better if you know that certain fields are accessed much more often.

It would be a very rare application whose state is so complex and whose performance requirements are so heavy that the only option is STRef fields. But it's nice to know that the option is there.

这篇关于在Haskell中快速更新大国的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！