为什么折叠事件和行为会占用如此多的内存？

Question

我目前正在探索使用基本容器为FRP网络提供更多结构的可能性,从而更容易创建更复杂的事件网络.

注意:我使用ordrea但反应性香蕉也有同样的问题,所以我想这个问题不是特定于所选的frp实现.

---

在这个特殊情况下,我使用一个简单Matrix的存储Events:

newtype Matrix (w :: Nat) (h :: Nat) v a where
   Matrix :: Vector a -> Matrix w h v a

-- deriving instances: Functor, Foldable, Traversable, Applicative

Matrix基本上只是一个薄的包装器Data.Vector,我将使用的大多数功能基本上与相应Vector的功能相同.值得注意的例外是索引,但这应该是自我解释的.

---

有了这个,我可以定义事件的矩阵,Matrix 10 10 (Event Double)并且能够定义基本的卷积算法:

applyStencil :: (KnownNat w, KnownNat h, KnownNat w', KnownNat h')
             => M.Matrix w' h' (a -> c)
             -> M.Matrix w h (Event a)
             -> M.Matrix w h (Event c)
applyStencil s m = M.generate stencil
  where stencil x y = fold $ M.imap (sub x y) s
        sub x0 y0 x y g = g <$> M.clampedIndex m (x0 - halfW + x) (y0 - halfH + y)
        halfW = M.width s `div` 2
        halfH = M.height s `div` 2

笔记:

• M.generate :: (Int -> Int -> a) -> M.Matrix w h a 和

  M.imap :: (Int -> Int -> a -> b) -> M.Matrix w h a -> M.Matrix w h b

  只是包装Vector.generate和Vector.imap分别.

• M.clampedIndex 将指数钳制到矩阵的边界.
• Event是一个实例的Monoid这就是为什么它可能只是fold在Matrix w' h' (Event c)通过返回M.imap (sub x y) s.

---

我的设置大致如下:

let network = do
  -- inputs triggered from external events 
  let inputs :: M.Matrix 128 128 (Event Double)

  -- stencil used:
  let stencil :: M.Matrix 3 3 (Double -> Double)
      stencil = fmap ((*) . (/16)) $ M.fromList [1,2,1,2,4,2,1,2,1]

  -- convolute matrix by applying stencil
  let convoluted = applyStencil stencil inputs

  -- collect events in order to display them later
  -- type: M.Matrix 128 128 (Behavior [Double])
  let behaviors = fmap eventToBehavior convoluted

  -- now there is a neat trick you can play because Matrix
  -- is Traversable and Behaviors are Applicative:
  -- type: Behavior (Matrix 128 128 [Double])
  return $ Data.Traversable.sequenceA behaviors

---

使用这样的东西我触发~15kEvents/s没有问题,并且在这方面有很多空间.

问题是,一旦我对网络进行采样,我每秒只能得到大约两个样本:

main :: IO ()
main = do

  -- initialize the network
  sample <- start network

  forever $ do

    -- not all of the 128*128 inputs are triggered each "frame"
    triggerInputs

    -- sample the network
    mat <- sample

    -- display the matrix somehow (actually with gloss)
    displayMatrix mat

---

到目前为止,我已经做了以下观察:

• 分析告诉我生产率非常低(4%-8%)
• 大部分时间是第1代垃圾收集器的花费(~95%)

• Data.Matrix.foldMap(即fold)分配最多的内存(~45%,按照-p)

• 当我还在使用反应性香蕉时, Heinrich Apfelmus建议基于树的遍历更适合行为¹.我试过了sequenceA,fold并traverse没有成功.

• 我怀疑newtype包装器阻止了矢量融合规则来解雇².这很可能不是罪魁祸首.

---

在这一点上,我花了一周的时间来寻找这个问题的解决方案.直观地说,我会说采样应该更快,并且foldMap不应该创建如此多的垃圾内存.有任何想法吗？