在Haskell中快速更新大状态

对于我在Haskell中的矢量图形库，我必须携带一个相当大的状态：行笔画参数，颜色，剪辑路径等。我知道两种这样做的方法。引用来自Haskell-cafe的评论：“我建议你要么使用具有可变状态的读取器monad，要么使用具有不可变状态的状态monad”。在Haskell中快速更新大状态

这是我的问题：更新一个大的不可变状态是一个性能杀手。使用大量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 })

据我所知，“状态{=的lineWidth X}”创建一个新的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来读取和更新大状态，但由于我经常遇到这种模式，我希望有更好的方法。

来源

2010-11-24 DJS

做你正在做的事情就像在haskell中编写C一样，因为我看到你暗示的库接口是非常必要的接口。 `setLineWidth`？以更实用的方式制作界面将使实现更具功能性。 – luqui 2010-11-24 10:55:25

对于第一个版本，使用“state {lineWidth = x}”更新状态应该与旧状态共享，所以我不希望它创建一个全新的状态。您可能希望至少使状态的“原子”元素变得严格（例如，lineWidth变为！Double，并且lineCap变为！Int），我怀疑这可能会妨碍性能。 – 2010-11-24 11:59:11

@stephen，以及*值*与旧记录共享。但是如果你有一个有100个字段的记录，每个记录更新将复制100个指针。 – luqui 2010-11-24 12:42:11

即使你的记录中有很多字段，“创建一个新的”只意味着复制指针。而“让旧垃圾收集器”就意味着为每个指针释放几个字节，GHC的世代垃圾收集器处理速度非常快。这一切都归结为一些机器指令。所以即使对于图形应用程序来说，这也可能不会导致您的性能下降。

如果您确定它确实会影响性能，请将字段组织到树中。您可以使用嵌套的data类型创建固定形状的树，或者甚至仅使用Data.IntMap。这会让你平均得到log n/2指针副本。如果您知道某些字段的访问次数更多，则可以做得更好。

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

来源

2010-11-24 15:36:57 Yitz

首先，我不得不问你是否只是声称它会变慢，或者你是否在描述或至少注意到性能问题？否则猜测或做出假设并不特别有用。无论如何，我建议对数据进行分组，现在看起来您只需将相关数据（如与行相关的数据）组合到记录中即可完全平坦化您的结构。

您可能还想分离真正需要处于状态monad中的数据，以及其他不使用读写器monad的数据，并使用monad变换器将它们组合在一起。关于代码的优雅性，我建议使用（一级/高级）记录库，如fclabels。

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

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

来源

2010-11-24 10:43:19

顺便说一句，你当然应该通过拆箱提高你的数据类型的代表，如果你关心性能：

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

通过拆包的构造函数，可以提高数据的密度，从去堆结构是这样的：

enter image description here

到更致密的，更严格的：

enter image description here

现在所有的原子类型都被放置在连续的内存插槽中。更新这种类型会更快！ BTW，461 ..是pi字段的词表示，我的查看器库中存在一个错误

您还可以减少空间泄漏的可能性。

传递这样一种结构的成本很低，因为这些组件将存储在寄存器中。

来源

2011-05-09 01:46:18

在Haskell中快速更新大状态

回答

相关问题