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

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

12 голосов | спросил DJS 24 32010vEurope/Moscow11bEurope/MoscowWed, 24 Nov 2010 13:18:03 +0300 2010, 13:18:03

3 ответа


0

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

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

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

ответил Yitz 24 32010vEurope/Moscow11bEurope/MoscowWed, 24 Nov 2010 18:36:57 +0300 2010, 18:36:57
0

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

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

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

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

ответил snk_kid 24 32010vEurope/Moscow11bEurope/MoscowWed, 24 Nov 2010 13:43:19 +0300 2010, 13:43:19
0

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

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

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

введите описание изображения здесь

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

введите описание изображения здесь

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

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

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

ответил Don Stewart 9 Mayam11 2011, 05:46:18

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132