在Haskell中快速更新大狀態

對於我在Haskell中的矢量圖形庫，我必須攜帶一個相當大的狀態：行筆畫參數，顏色，剪輯路徑等。我知道兩種這樣做的方法。引用來自Haskell-cafe的評論：「我建議你要麼使用具有可變狀態的讀取器monad，要麼使用具有不可變狀態的狀態monad」。在Haskell中快速更新大狀態

這是我的問題：更新一個大的不可變狀態是一個性能殺手。使用大量STRefs就像在Haskell中編寫C：它是冗長而醜陋的。

這裏是不可改變狀態：

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

setLineWidth :: Double -> State GfxState() 
setLineWidth x = modify (\state -> state { lineWidth = x })

據我所知，「狀態{=的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來讀取和更新大狀態，但由於我經常遇到這種模式，我希望有更好的方法。

來源

2010-11-24 DJS

做你正在做的事情就像在haskell中編寫C一樣，因爲我看到你暗示的庫接口是非常必要的接口。 `setLineWidth`？以更實用的方式製作界面將使實現更具功能性。 – luqui 2010-11-24 10:55:25

對於第一個版本，使用「state {lineWidth = x}」更新狀態應該與舊狀態共享，所以我不希望它創建一個全新的狀態。您可能希望至少使狀態的「原子」元素變得嚴格（例如，lineWidth變爲！Double，並且lineCap變爲！Int），我懷疑這可能會妨礙性能。 – 2010-11-24 11:59:11

@stephen，以及*值*與舊記錄共享。但是如果你有一個有100個字段的記錄，每個記錄更新將複製100個指針。 – luqui 2010-11-24 12:42:11

即使你的記錄中有很多字段，「創建一個新的」只意味着複製指針。而「讓舊垃圾收集器」就意味着爲每個指針釋放幾個字節，GHC的世代垃圾收集器處理速度非常快。這一切都歸結爲一些機器指令。所以即使對於圖形應用程序來說，這也可能不會導致您的性能下降。

如果您確定它確實會影響性能，請將字段組織到樹中。您可以使用嵌套的data類型創建固定形狀的樹，或者甚至僅使用Data.IntMap。這會讓你平均得到log n/2指針副本。如果您知道某些字段的訪問次數更多，則可以做得更好。

這將是一個非常罕見的應用程序，其狀態非常複雜，其性能要求非常高，唯一的選擇是STRef字段。但很高興知道該選項在那裏。

來源

2010-11-24 15:36:57 Yitz

首先，我不得不問你是否只是聲稱它會變慢，或者你是否在描述或至少注意到性能問題？否則猜測或做出假設並不特別有用。無論如何，我建議對數據進行分組，現在看起來您只需將相關數據（如與行相關的數據）組合到記錄中即可完全平坦化您的結構。

您可能還想分離真正需要處於狀態monad中的數據，以及其他不使用讀寫器monad的數據，並使用monad變換器將它們組合在一起。關於代碼的優雅性，我建議使用（一級/高級）記錄庫，如fclabels。

我在一些小項目中大量使用了狀態monad（在一個monad變換器中），我還沒有注意到任何性能問題。

最後，您可以使用修改而不是get/put對。

來源

2010-11-24 10:43:19

順便說一句，你當然應該通過拆箱提高你的數據類型的代表，如果你關心性能：

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

通過拆包的構造函數，可以提高數據的密度，從去堆結構是這樣的：

enter image description here

到更緻密的，更嚴格的：

enter image description here

現在所有的原子類型都被放置在連續的內存插槽中。更新這種類型會更快！ BTW，461 ..是pi字段的詞表示，我的查看器庫中存在一個錯誤

您還可以減少空間泄漏的可能性。

傳遞這樣一種結構的成本很低，因爲這些組件將存儲在寄存器中。

來源

2011-05-09 01:46:18

在Haskell中快速更新大狀態

回答

相關問題