Обновление Большого государства в Хаскелле

Для моей векторной графической библиотеки в Haskell я должен нести вокруг довольно большого состояния: параметры штриховки линии, цвета, путь клипа и т.д. Я знаю два способа сделать это. Цитируя комментарий Haskell-cafe: "Я бы предложил вам использовать монаду-читатель с изменчивым состоянием или государственную монаду с неизменяемым состоянием".

Вот моя проблема: обновление большого неизменяемого состояния - это убийство производительности. Использование большого количества STRef похоже на запись C в Haskell: она многословная и уродливая.

Вот неизменное состояние:

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 и позволяет старому собрать мусор. Это убивает производительность, когда государство велико и часто обновляется.

Вот измененное состояние:

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) по всему месту, что является многословным, запутанным и превосходит дух написания короткого и выразительного кода. Я мог бы использовать C + FFI для чтения и обновления большого состояния, но поскольку я часто встречаюсь с этим шаблоном, я надеюсь, что там будет лучший способ.

Ответ 1

Даже при наличии нескольких полей в вашей записи "создание нового" просто означает копирование указателей. И "позволить старому собрать мусор" означает только высвобождение нескольких байтов для каждого указателя таким образом, что сборщик мусора GHC поколения очень быстро обрабатывает. Все это сводится к горстке машинных инструкций. Поэтому даже для графического приложения это очень хорошо не может вообще убить вашу производительность.

Если вы уверены, что это действительно влияет на производительность, организуйте поля в дерево. Вы можете создать дерево фиксированной формы, используя вложенные типы data или даже просто использовать Data.IntMap. Это даст вам в среднем log n / 2 копии указателя. Вы можете сделать еще лучше, если знаете, что некоторые поля доступны гораздо чаще.

Это было бы очень редкое приложение, состояние которого настолько сложное и чьи требования к производительности настолько тяжелы, что единственным вариантом является STRef. Но приятно знать, что опция есть.

Ответ 2

Прежде всего, я должен спросить, утверждаете ли вы, что это будет медленным, или вы профилируете или, по крайней мере, замечаете проблему с производительностью? в противном случае предположение или предположение не особенно полезно. В любом случае, я рекомендую группировать ваши данные, на данный момент похоже, что вы просто полностью структурируете свою структуру, когда можете группировать связанные данные, такие как данные, относящиеся к строкам, в записи.

Вы также можете выделить отдельные биты, которые действительно должны быть в государственной монаде и других, которые не входят в монаду-читатель/писатель и объединяют их с помощью монадных трансформаторов. Что касается элегантности кода, я бы рекомендовал использовать библиотеки записей первого и более высокого порядка, такие как fclabels.

Я много использовал государственные монады (в стеке монадного трансформатора) в нескольких небольших проектах, и я еще не заметил никаких проблем с производительностью.

Наконец, вы можете использовать модификацию вместо пар get/put.

Ответ 3

В стороне, конечно, вы должны улучшить свое представление типа данных через unboxing, если вас беспокоит производительность:

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

При распаковке конструкторов вы улучшаете плотность своих данных, переходя из структуры кучи, как это:

до более плотного, строже:

Теперь все атомные типы выложены в последовательных слотах памяти. Обновление этого типа будет намного быстрее! BTW, 461.. является представлением Word поля pi, ошибкой в моей библиотеке зрителей

Вы также уменьшите вероятность утечки пространства.

Стоимость прохода такой структуры вокруг будет очень дешевой, так как компоненты будут храниться в регистрах.