Почему сворачивание событий и поведения использует так много памяти?

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%)
• Большую часть времени проводит сборщик мусора в Gen 1 (~ 95%)

• Data.Matrix.foldMap (т.е. fold) выделяет большую часть памяти (~45%, согласно -p)

• Когда я еще работал с реактивным бананом, Генрих Апфельмус рекомендовал, чтобы обходы на основе деревьев лучше подходили для поведения ¹. Я пробовал это для sequenceA, fold а также traverse без успеха.

• Я подозревал, что оболочка нового типа предотвращает срабатывание правил объединения векторов ². Это скорее всего не виновник.

---

На данный момент я провел большую часть недели в поисках решения этой проблемы. Интуитивно я бы сказал, что выборка должна быть намного быстрее и foldMap не должно создавать столько мусорной памяти. Есть идеи?