如何在Haskell中进行快速数据反序列化

Question

基准测试显示，

cereal

库反序列化我的数据结构（详细信息如下）比从驱动器读取相同数据所需的时间长 100 倍：

benchmarking Read
mean: 465.7050 us, lb 460.9873 us, ub 471.0938 us, ci 0.950
std dev: 25.79706 us, lb 22.19820 us, ub 30.81870 us, ci 0.950
found 4 outliers among 100 samples (4.0%)
  4 (4.0%) high mild
variance introduced by outliers: 53.460%
variance is severely inflated by outliers

benchmarking Read + Decode
collecting 100 samples, 1 iterations each, in estimated 6.356502 s
mean: 68.85135 ms, lb 67.65992 ms, ub 70.05832 ms, ci 0.950
std dev: 6.134430 ms, lb 5.607914 ms, ub 6.755639 ms, ci 0.950
variance introduced by outliers: 74.863%
variance is severely inflated by outliers

在我的程序中分析此数据结构的典型反序列化用法也支持了这一点，其中 98% 的时间用于反序列化数据，1% 是

IO

加上核心算法：

COST CENTRE                    MODULE               %time %alloc

getWord8                       Data.Serialize.Get    30.5   40.4
unGet                          Data.Serialize.Get    29.5   17.9
getWord64be                    Data.Serialize.Get    14.0   10.7
getListOf                      Data.Serialize.Get    10.2   12.8
roll                           Data.Serialize         8.2   11.5
shiftl_w64                     Data.Serialize.Get     3.4    2.9
decode                         Data.Serialize         2.9    3.1
main                           Main                   1.3    0.6

我反序列化的数据结构是一个

IntMap [Triplet Atom]

，组件类型的定义如下：

type Triplet a = (a, a, a)

data Point = Point {
    _x :: {-# UNPACK #-} !Double ,
    _y :: {-# UNPACK #-} !Double ,
    _z :: {-# UNPACK #-} !Double }

data Atom = Atom {
    _serial :: {-# UNPACK #-} !Int    ,
    _r      :: {-# UNPACK #-} !Point  ,
    _n      :: {-# UNPACK #-} !Word64 }

我正在使用

IntMap

提供的默认

(,,)

、

[]

和

cereal

实例，以及我的自定义类型的以下类型和实例：

instance Serialize Point where
    put (Point x y z) = do
        put x
        put y
        put z
    get = Point <$> get <*> get <*> get

instance Serialize Atom where
    put (Atom s r n) = do
        put s
        put r
        put n
    get = Atom <$> get <*> get <*> get

所以我的问题是：

1. 为什么反序列化一般这么慢？
2. 有什么方法可以改变我的数据结构（即

   IntMap

   /

   []

   ）以使反序列化速度更快？
3. 有什么方法可以更改我的数据类型（即

   Atom

   /

   Point

   ）以使反序列化速度更快？
4. Haskell 中是否有比

   cereal

   更快的替代方案，或者我应该将数据结构存储在 C-land 中以进行更快速的反序列化（即使用

   mmap

   ）？

我正在反序列化的这些文件用于搜索引擎的子索引，因为完整索引无法放入目标计算机（消费级桌面）的内存中，因此我将每个子索引存储在磁盘上并读取+解码内存中初始全局索引指向的子索引。 另外，我并不关心序列化速度，因为搜索索引是最终用户的瓶颈，并且

cereal

当前的序列化性能对于生成和更新索引来说是令人满意的。

编辑：

尝试了 Don 使用节省空间的三元组的建议，这使速度提高了四倍：

benchmarking Read
mean: 468.9671 us, lb 464.2564 us, ub 473.8867 us, ci 0.950
std dev: 24.67863 us, lb 21.71392 us, ub 28.39479 us, ci 0.950
found 2 outliers among 100 samples (2.0%)
  2 (2.0%) high mild
variance introduced by outliers: 50.474%
variance is severely inflated by outliers

benchmarking Read + Decode
mean: 15.04670 ms, lb 14.99097 ms, ub 15.10520 ms, ci 0.950
std dev: 292.7815 us, lb 278.8742 us, ub 308.1960 us, ci 0.950
variance introduced by outliers: 12.303%
variance is moderately inflated by outliers

但是，它仍然是瓶颈，占用的时间是 IO 的 25 倍。 另外，有人可以解释为什么唐的建议有效吗？ 这是否意味着如果我切换到列表以外的其他内容（例如数组？），它也可能会带来改进？

编辑 #2：刚刚切换到最新的 Haskell 平台并重新运行谷物分析。 该信息相当详细，我提供了它的hpaste。

Answer 1

好的。通过建议摘要来回答这个问题。为了快速反序列化数据：

• 使用

  cereal

  （严格字节串输出）或

  binary

  （惰性字节串输出）
• 确保使用 -O2 进行编译，因为这些库依赖内联来消除开销
• 使用密集数据类型，例如用解压缩的专用形式替换多态元组。
• 避免将数据类型转换为列表来序列化它们。如果您有字节串，则会处理此问题。对于未打包的数组类型，您通常会获得非常快的 IO，但值得仔细检查实例
• 您也许可以使用 mmap'd IO
• 对于双重数据，请考虑更高效的双读取器。
• 使用针对性能进行调整的现代数组和容器类型以及更新的 GHC 版本。

Answer 2

使用向量代替 切换到使用向量列表，因为具有更好的缓存性能。

序列化使其变得智能。或欺骗数据部分[此时应该实际浏览器测试原始事件]。使用二进制或存储进行序列化可能比反序列化更快。

您可以扁平化结构：在扁平化起作用的地方，简化和扁平化您的数据结构

使用 mmap - 对于非常大的数据集，您可以考虑的更好方法是对文件进行内存映射。这将在我的文章的后面部分讨论_缓慢而有效地将数据加载到 CPU 上的稀疏张量中（第 2 部分。）。

Don 的建议ᅳ 这是如何运作的

由于 Triplet 保留了更多内存，因此仅提供较小的 Triplet 可能效果更好，因为这样可以减少驻留占用空间，最坏的情况会增加缓存局部性。转向数组支持的数据结构（例如 Vector）还可以通过减少链表引入的指针追逐开销来进一步提高性能。

如果这不能解决瓶颈，您可以分析您的反序列化步骤，以找出到底哪里花费了最多时间，并进行更多性能改进。