在Haskell中快速更新大状态

Question

对于我在Haskell中的矢量图形库,我必须携带一个相当大的状态:线条描边参数,颜色,剪辑路径等.我知道两种方法.引用Haskell-cafe的评论:"我建议你使用具有可变状态的读取器monad,或者使用具有不可变状态的状态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来读取和更新大状态,但由于我经常遇到这种模式,我希望有更好的方法.

Answer 1

首先,我要问你是刚刚宣称它会变慢,还是你的个人资料或者至少注意到性能问题？否则猜测或做出假设并不是特别有用.无论如何,我建议您对数据进行分组,当您将相关数据(如与行相关的数据)分组到记录中时,您似乎只是将结构完全展平.

您可能还想分离出真正需要处于状态monad中的位和其他不进入读/写单元的位并使用monad变换器组合它们.关于代码的优雅,我建议使用(一流/更高阶)记录库,如fclabels.

我在一些小项目中大量使用状态monad(在monad变换器的堆栈中),我还没有注意到任何性能问题.

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

Answer 2

即使你的记录中有很多字段,"创建一个新字段"只意味着复制指针.并且"让旧的垃圾收集"只是意味着为GHC的世代垃圾收集器处理速度非常快的方式为每个指针释放几个字节.这一切都归结为一些机器指令.因此,即使是图形应用程序,也很可能根本不会破坏您的性能.

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

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

Answer 3

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

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

通过解压缩构造函数,可以提高数据的密度,从这样的堆结构:

更密集,更严格:

现在所有原子类型都布局在连续的内存插槽中.更新此类型将更快!BTW,461 ..是pi字段的Word表示,这是我的查看器库中的一个错误

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

通过这种结构的成本将非常便宜,因为组件将存储在寄存器中.