我们正在开发一个程序,它接收和转发"消息",同时保留这些消息的临时历史记录,以便它可以告诉您消息历史记录(如果请求).消息以数字方式标识,通常大小约为1千字节,我们需要保留数十万条这些消息.
我们希望优化此程序的延迟:发送和接收消息之间的时间必须低于10毫秒.
该程序是用Haskell编写的,并用GHC编译.但是,我们发现垃圾收集暂停对于我们的延迟要求来说太长了:在我们的实际程序中超过100毫秒.
以下程序是我们的应用程序的简化版本.它使用a Data.Map.Strict来存储消息.消息ByteString由a标识Int.以递增的数字顺序插入1,000,000条消息,并且不断删除最旧的消息以使历史记录最多保留200,000条消息.
module Main (main) where
import qualified Control.Exception as Exception
import qualified Control.Monad as Monad
import qualified Data.ByteString as ByteString
import qualified Data.Map.Strict as Map
data Msg = Msg !Int !ByteString.ByteString
type Chan = Map.Map Int ByteString.ByteString
message :: Int -> Msg
message n = Msg n (ByteString.replicate 1024 (fromIntegral n))
pushMsg :: Chan -> Msg -> IO Chan
pushMsg chan (Msg msgId msgContent) =
Exception.evaluate $
let
inserted = Map.insert …这种结构对于实时应用是必需的 - 例如用户界面.(如果点击一个按钮需要0.1秒或0.2秒,用户不在乎,但是如果第100次点击强制执行一个非常懒的计算并且需要10秒才能继续,他们会关心.)
我正在阅读Okasaki的论文Purely functional data structures,他描述了一种有趣的通用方法,用于将具有分摊边界的惰性数据结构转换为具有每个操作的相同最坏情况边界的结构.这个想法是分配计算,以便在每次更新时强制部分未评估的thunk.
我想知道,是否有任何这样的实施标准集合(的Map,Set等等)在Haskell？
该容器包装说
每项操作的申报成本是最坏情况或摊销,但即使共享结构也仍然有效.
因此无法保证单个操作的最坏情况限制.有严格的变体Data.Map.Strict,但它们的键和值严格:
键和值参数被评估为WHNF; 在将值和值存储在地图中之前,它们将被评估为WHNF.
没有关于(可能)严格的结构.