Обновление Big State Fast в Хаскеле - PullRequest
Новая
       47

Обновление Big State Fast в Хаскеле

12 голосов
/ 24 ноября 2010

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

Вот моя проблема: обновлениебольшое неизменное состояние - это убийство производительности.Использование множества STRefs похоже на написание 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}msgstr "создает новый 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 для чтения и обновления большого состояния, но, поскольку я довольно часто сталкиваюсь с этим шаблоном, я надеюсь, что есть лучший способ.

Ответы [ 3 ]

10 голосов
/ 24 ноября 2010

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

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

В некоторых из них я интенсивно использовал монады состояний (в стеке преобразователя монад)небольшие проекты, и я еще не заметил каких-либо проблем с производительностью.

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

8 голосов
/ 24 ноября 2010

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

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

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

6 голосов
/ 09 мая 2011

Кроме того, вам, безусловно, следует улучшить представление типов данных с помощью распаковки, если вы беспокоитесь о производительности: 

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

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

enter image description here

плотнее, строже:

enter image description here

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

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

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

...