Быстрое обновление большого состояния в Haskell

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


data-structures haskell state-monad
person DJS    schedule 24.11.2010    source источник
comment
Делать то, что вы делаете, будет похоже на написание C на Haskell, потому что интерфейс библиотеки, на который вы намекаете, очень императивен. setLineWidth? Создание интерфейса в более функциональном стиле сделает реализацию более функциональной.   -  person luqui    schedule 24.11.2010
comment
В первой версии обновление состояния с помощью состояния {lineWidth = x} должно иметь совместное использование со старым состоянием, поэтому я не ожидал, что оно создаст совершенно новое состояние. Возможно, вы захотите сделать по крайней мере атомарные элементы состояния строгими (например, lineWidth становится !Double, а lineCap становится !Int), я подозреваю, что это может немного снизить производительность.   -  person stephen tetley    schedule 24.11.2010
comment
@stephen, ну, значения используются совместно со старой записью. Но если у вас есть запись со 100 полями, каждое обновление записи будет копировать 100 указателей.   -  person luqui    schedule 24.11.2010
comment
@luqui - Действительно, но это настоятельно рекомендует не делать запись со 100 полями тогда ... и добавлять некоторую вложенность для группировки связанных элементов вместе. В любом случае, это было бы более модульно и лучше с точки зрения понятности.   -  person stephen tetley    schedule 24.11.2010
comment
@luqui, setLineWidth не принадлежит интерфейсу. В интерфейсе есть функция, которая берет список команд (moveTo, lineTo, setColor, setLineWidth, штрих и т. д.) и создает список графических объектов (Штрих {path::Path, color::Color и т. д.}).   -  person DJS    schedule 24.11.2010
comment
@DJS, вы только что сказали, что setLineWidth — это одна из команд, которые он может выполнять. Это то, что я имел в виду. Если это проблема, которую вы решаете — скажем, взять список команд на стандартный ввод и нарисовать их, тогда круто. Но если вы пишете больше haskell, который будет использовать это, то список команд — это не то, что я бы рекомендовал в качестве интерфейса. С комбинаторной библиотекой будет приятнее работать. См. hackage.haskell.org/packages. /архив/ для вдохновения   -  person luqui    schedule 24.11.2010

Ответы (3)


arrow_upward
8
arrow_downward

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

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

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

person Yitz    schedule 24.11.2010
comment
Спасибо, думаю, так и сделаю. Придерживайтесь неизменного состояния (т. е. без монады ST) и переместите поля в древовидную форму позже, во время оптимизации производительности. Я немного разочарован, потому что впервые после перехода на Haskell я действительно скучаю по C. - person DJS; 24.11.2010

arrow_upward
10
arrow_downward

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

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

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

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

person snk_kid    schedule 24.11.2010
comment
Спасибо. Библиотека fclabels выглядит интересно. - person DJS; 24.11.2010
comment
Я изменил пример кода, чтобы использовать модификацию вместо получения и установки. Спасибо. - person DJS; 24.11.2010

arrow_upward
6
arrow_downward

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

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

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

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

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

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

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

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

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

person Don Stewart    schedule 09.05.2011