Haskell 中的 Packed Data 支持
Arthi-chaud 计算机科学博士生和音乐狂热者
主页 Haskell 中的 Packed Data 支持
Haskell 中的 Packed Data 支持
Packed Data x Haskell = Portable(类型安全 + 性能) 发布于 2025 年 4 月 27 日，更新于 2025 年 4 月 28 日 作者：Arthur J. 阅读时长 12 分钟 Haskell 中的 Packed Data 支持 目录 Packed Data support in Haskell
这篇博文旨在对一篇将在 ECOOP 2025 上发表的论文《Type-safe and portable support for packed data》进行简短而易懂的总结。
简介：Packed Data
当程序想要持久化数据或通过网络发送数据时，它们需要对数据进行序列化（例如，序列化为 JSON 或 XML）。另一方面，当程序从网络接收数据或从文件读取数据时，数据需要被反序列化。
flowchart LR
Server(["Server"])
Server --> SD["Serialise"]
SD -- Network --- RD["Deserialise"]
RD --> Client(["Client"])
这些序列化/反序列化步骤是必要的，因为我们不能在文件或通过网络发送数据时使用数据的内存表示/布局，这主要是因为数据可能包含指针。
因此，序列化/反序列化数据是有成本的：它需要时间，并且数据的序列化版本通常比其内存表示形式更大。在通过网络交互的系统中，这会导致要发送的有效载荷更大，从而导致传输时间更慢。
现在，如果我们在将数据发送给客户端之前不必序列化数据呢？如果客户端可以直接使用来自网络的数据，而无需任何编组步骤呢？我们可以节省服务器和客户端的时间。
介绍 “packed”数据格式，这是一种二进制格式，允许按原样使用数据，而无需反序列化步骤。这种格式的一个显着优点是，已被证实在 packed 树上的遍历比在 'unpacked' 树上更快：由于数据结构的字段是内联的，因此没有指针跳转，从而最大限度地利用 L1 缓存。
为了更好地理解它的外观，这里有一个使用指针的内存中树的表示。 N 代表节点，L 代表叶子。数字是树的数据，点和箭头是指针。
内存中基于指针的树布局
这是 packed 树在内存中的样子。
内存中 packed 树的布局
一些项目使用或利用了这种“packed”方法。例如，Cap’n Proto1 是一个流行的库，它允许 packing 数据（即构建包含数据的二进制缓冲区），并按原样使用该缓冲区（例如，遍历它并“unpack”结构的字段）。但是，没有语言原生支持 packed 数据。Haskell 支持紧凑范式 (CNF)，但 Compact 数据类型不允许使用（例如，解构）packed 值。我们应该注意到 Gibbon 的存在，这是一个研究编译器，它接受函数式程序并生成原生使用 packed 数据的程序。
不幸的是，packed 数据的使用仅限于研究项目，可能是因为很难支持它。
在这篇文章中，我将介绍 packed-data Haskell 库。借助类型的力量，它允许 packing 和 unpacking 数据，以及按原样遍历 packed 数据（使用自定义的 case 函数），而无需编组步骤或编译器修改。据我们所知，这是仅使用宿主语言的类型系统、元编程 (Template Haskell) 且无需修改编译器来支持 packed 数据的首次尝试之一。
库、其特性和 API
使用 Template Haskell，packed-data 生成所有必要的代码，以便人们可以对 任何 类型2 执行以下操作：
- pack 数据（即将数据序列化为二进制格式）
- unpack 数据（即从该二进制格式反序列化数据）
- traverse 数据，这要归功于生成的
case函数，该函数允许对数据类型的构造函数进行模式匹配。
让我们考虑一个二叉树的例子：
1
```
| ```
data Tree a = Leaf a | Node (Tree a) (Tree a)
```
---|---
`
我们可以使用以下 Template Haskell 入口点（来自 `Data.Packed`[](https://arthi-chaud.github.io/posts/packed/<https:/hackage-content.haskell.org/package/packed-data-0.1.0.3/docs/Data-Packed.html#g:5>)):
1
| ```
$(mkPacked ''Tree [])
---|---
这将生成以下类的实例（也在Data.Packed` 中定义）：
1
2
3
4
5
```
| ```
class Packable a where
write :: a -> NeedsBuilder a r t
class Unpackable a where
read :: PackedReader '[a] r a
```
---|---
`
以及函数：
1 2 3
| ```
caseTree :: (PackedReader '[a] r b) ->
(PackedReader '[Tree a, Tree a] r b) ->
(PackedReader '[Tree a] r b)
---|---
`
喔，所有这些类型都很吓人。别担心，我们现在就来看看它们。
NeedsBuilder
为了 构建 packed 数据，我们使用中间缓冲区，通过其幻像类型参数，可以限制它将哪些数据作为输入。
我们并没有想出这个主意，它很大程度上受到了 Linear Haskell 论文1 中示例的启发。该论文的作者定义了 Needs 类型，带有两个幻像类型参数 p 和 t，其中
p告诉缓冲区在被认为是 准备好 或 完整 之前需要的数据类型t给出缓冲区中 packing 的所有数据的类型，一旦准备就绪（即当p是一个空列表时）
1
2
3
```
| ```
import Data.ByteString.Builder (Builder)
newtype Needs (p :: [Type]) (t :: [Type]) = Needs Builder
```
---|---
`
例如，`Needs '[Int] '[Tree Int]` 是一个不完整的缓冲区，在我们可以将其具体化为适当的 packed `(Tree Int)` 之前，它需要一个 `Int`。另一方面，`Needs '[] '[Char, Char]` 已经准备好被具体化，并且生成的缓冲区将包含两个 `Char`。
我们扩展了该论文的想法，使缓冲区的构建成为单子的。例如，使用 Template Haskell，我们生成以下代码（或类似的代码）以将 `Tree` `write` 到 `Needs` 中
1 2 3 4 5 6 7 8
| ```
instance Packable Tree where
write (Leaf n) = do
writeTag 0
write n -- The library provides an instance of Packable Int
write (Node t1 t2) = do
writeTag 1
write t1 -- We call the function recursively
write t2
---|---
`
Needs 类型只是 Data.ByteString.Builder 的一个包装器。当我们使用 write 函数3 时，不会创建缓冲区。finish 就是用于此目的的：
1
```
| ```
finish :: Needs '[] t -> Packed t
```
---|---
`
请注意输入 `Needs` 的第一个类型参数如何为空。它确保缓冲区是 _满_ 和 _准备好_ 的。
该库还提供了一个简写 `pack` 函数：
1 2
| ```
pack :: (Packable a) => Packed '[a]
pack = finish . withEmptyNeeds . write
---|---
`
PackedReader
PackedReader 表示对 packed 数据的读取操作。它是一个 monad。更具体地说，它是一个索引的 monad。这意味着计算的“状态”反映在其类型中。
例如，PackedReader '[Int] '[Int, Int] Char 在缓冲区中读取一个 Int，其中缓冲区的 其余部分 包含另外两个 Int。这意味着我们可以将该读取器与 Packed '[Int, Int, Int] 一起使用，但不能与 Packed '[Char, Int, Int] 一起使用。该操作产生一个 Char。
为什么存在这个 monad？在底层，PackedReader 传递一个 Ptr 并使用 peek 在 IO monad 中读取数据。PackedReader 抽象了指针操作，同时还确保了 packed 缓冲区上类型正确的读取操作。
如果没有 PackedReader 会是什么样子？
下面是一个在 packed Tree（在下一小节中定义）上的遍历的例子，如果没有 PackedReader 抽象：
getRightMostNodePacked :: Packed (Tree1 Int ': r) -> IO Int
getRightMostNodePacked packed = fst <$> go (unsafeForeignPtrToPtr fptr)
where
(BS fptr _) = fromPacked packed
go :: Ptr Word8 -> IO (Int, Ptr Word8)
go ptr = do
tag <- peek ptr :: IO Word8
case tag of
0 -> do
!n <- peek (plusPtr ptr 1)
return (n, plusPtr ptr 9)
1 -> do
(!_, !r) <- go (plusPtr ptr 1)
(!right, !r1) <- go r
return (right, r1)
_ -> undefined
很丑，不是吗？
case 函数
对于每个对 mkPacked 的调用，都会为给定的类型生成一个 case 函数。
例如，对于 Tree ADT，它生成 caseTree 函数。它采用与 Tree 中构造函数的数量一样多的 PackedReader 作为参数。每个 PackedReader 都有一个与每个构造函数的类型匹配的类型：
1
2
3
4
5
6
7
8
9
10
11
```
| ```
data Tree a = Leaf a | Node (Tree a) (Tree a)
caseTree ::
-- The first PackedReader will only read an 'a',
-- as the first constructor has an 'a'
(PackedReader '[a] r b) ->
-- The second reads two trees
(PackedReader '[Tree a, Tree a] r b) ->
-- The resulting PackedReader reads a 'Tree'
(PackedReader '[Tree a] r b)
```
---|---
`
我们可以使用生成的 `caseTree` 函数来定义 `Tree` 的 `Unpackable` 实例：
1 2 3 4 5 6 7 8 9 10 11 12
| ```
-- This function is generated by `mkPacked`
instance (Unpackable a) => Unpackable (Tree a) where
read = caseTree
(do
n <- read -- 'n' has type Int
return n
)
(do
left <- read -- 'left' is a 'Tree a'
right <- read -- 'right' is also a 'Tree a'
return $ Node left right
)
---|---
`
第二个 lambda 乍一看可能有点奇怪。你可以将 PackedReader 视为在缓冲区内移动光标的操作。在这里，read unpack 当前光标位置的值，并将其移动到下一个 packed 值。
Indirections
packed 数据的一个常见挑战是访问 packed 数据结构中的字段。由于所有字段都是内联的，因此我们无法预测给定字段在缓冲区中的位置，因为前面的字段可能没有固定的大小（在递归数据结构（如树）的情况下）。
因此，有两种方法可以访问字段：
- 遍历前面的字段。如果这些前面的字段很大，可能会导致严重的性能问题。
- 在每个字段前面加上一个 indirection：一个给出它前面字段大小的数字。它们允许我们通过简单的指针移位跳过字段。在
packed-data中，我们称它们为FieldSize。
在构建 packed 数据时，该库会自动插入这些 indirections，并修改 case 函数的签名，以便它的 PackedReader 知道缓冲区中散布着 FieldSize。
要跳过前面带有 FieldSize 的值，我们提供 skipwithFieldSize 函数，其类型为 PackedReader '[FieldSize, a] r ()。
示例
下面是在 packed 树中获取最右侧值的样子：
1
2
3
4
5
6
```
| ```
getRightMostNodePacked :: PackedReader '[Tree1 Int] r Int
getRightMostNodePacked =
caseTree1
read
skip R.>> getRightMostNodePacked
```
---|---
`
对 packed 树中的值求和类似：
1 2 3 4 5 6 7 8 9 10
| ```
sumPacked :: PackedReader '[Tree1 Int] r Int
sumPacked =
caseTree1
read
( R.do
!left <- sumPacked
!right <- sumPacked
let !res = left + right
R.return res
)
---|---
`
你可以在 package’s repository 中找到更多树遍历的例子。
Benchmarks
所有这些东西有多快？为了回答这个问题，我们对简单的树遍历进行了 benchmarks：对树中的值求和，获取树中最右侧的值，评估算术表达式的 AST，以及递增树中叶子的值。
我们将这些操作的执行时间与 C、“Unpacked”/原生 Haskell 和 Gibbon 进行了比较，树的大小在 1 到 20 之间（例如，大小为 5 的树有 2^5 = 32 个叶子，对称地分配）。我们注意到以下几点：
- 对于对值求和，我们注意到与“unpacked”Haskell 相比，速度略有提高（20%）。
- 另一方面，获取树中最右侧的值比原生 Haskell 慢 5 倍。
- 令人惊讶的是，评估 AST 比 Haskell 和 C 都快 (2.5x)。
- 最后，递增 packed 树的值与在 Haskell 中递增原生、unpacked 树一样快。我们认为这是因为
ByteString.Builder只进行一次大的内存分配，而原生操作对每个节点都进行一次分配。
完整的 benchmark 结果表
我们应该注意到，这些 benchmark 结果因机器 CPU 的架构而异。与 Intel CPU 相比，ARM CPU 没有获得这样的速度提升。
（你可以在你的机器上运行这些 benchmarks，源代码可以在 GitHub 上找到）
结果分析
嗯，我们确实获得了一些速度提升，但在我们所有的 benchmark 案例中并不一致。
使用 packed 布局应该始终提供更快的遍历，因为我们避免了使用指针跳转，并最大限度地利用了 L1 缓存。
我们怀疑 PackedReader 的单子方法由于 IO 操作（如 peek）的密集使用而导致一些计算开销。
为了好玩，我们实现了一个非单子的遍历版本来获取 packed 树中最右边的值。此版本不使用 PackedReader，并且在没有任何抽象的情况下使用 peek。（代码可在此处找到）。它确实加快了遍历速度（比 PackedReader 快 30%），但仍然比原生 Haskell 慢 (4x)。
这证实了 我们的指针操作的单子抽象导致了计算开销。
未来工作和结论
好的，所以仅使用一个库，而无需修改编译器，我们在某种程度上设法利用了 packed 数据所允许的速度提升。但是，由于其浅层嵌入（即它_只是_一个库），我们遭受了计算开销，如果没有更改编译器，这几乎无法绕过。
一个解决方案是重写该库，以便 PackedReader 生成一个 AST，该 AST 将用于生成 C 代码。然后，使用 Template Haskell，我们可以将 FFI 调用注入到 Haskell 代码中，以代替 PackedReader 的执行。这将使我们能够避免由我们的单子方法引起的计算开销。
我只依赖类型来确保 packed 数据读取操作的正确性。我实际上很好奇这种基于库的方法是否适用于其他强类型语言，如 Rust、Scala 甚至 TypeScript。
我在引言中谈到了服务器和客户端。对于 Web 服务，通常使用 JSON。如果可以使用 JSON bytestring 作为客户端的按原样数据，而无需反序列化步骤，并使用像 packed-data 中那样的强类型接口，那将很有趣。
- Linear Haskell paper ↩︎ ↩︎2
- 只要它不是 unboxed type ↩︎
- 我们建议查看
Data.ByteString.Builder模块。 ↩︎
Haskell 本文已获得作者的 CC BY 4.0 许可。 分享
最近更新
热门标签
目录
进一步阅读
Mar 4, 2025Data.Reify for GADTs'Reimplementing' data-reify for GADTs Data.Reify for GADTs
© 2025 Arthur J.. 保留一些权利。 使用 Jekyll 的 Chirpy 主题。