| RFC-0116：为稀疏 FIDL 表提供有线格式支持 | |
|---|---|
| 状态 | 已拒绝 |
| 领域 |
|
| 说明 | 此 RFC 引入了对 FIDL 传输格式的变更，这些变更针对当前序数的稀疏分布优化了表。 |
| 问题 | |
| Gerrit 更改 | |
| 作者 | |
| 提交日期（年-月-日） | 2021-06-16 |
| 审核日期（年-月-日） | 2021-07-21 |
拒绝原因
此 RFC 提议为表使用稀疏 FIDL 传输格式，但遭到了以下优缺点分析。
另请参见：
稀疏表的优势
稀疏表的主要优势包括：
- 可扩缩
O(n)的性能，其中n为设置的字段数。而不是m，这是最大序数。因此，与现有表相比，稀疏表在处理少量字段时应具有高序数的效果。请务必注意，用户通常希望表性能会随着O(n)而扩缩，因此稀疏表更符合用户预期。 - 更紧凑的传输格式。这意味着通过网络复制的字节数更少，持久存储的字节数也更少。较为紧凑的传输格式的实际优势尚不明确 - 它可能会提高性能并减少内存使用量，但发生这种情况的程度则未知。
稀疏表的缺点
稀疏表的主要缺点包括：
- 通常更复杂，尤其是与现有密集表实现（非常简单）相比。有些实现需要花费大量精力去理解和实现。
- 输入较为密集时，性能不佳
- 与密集表实现相比，可能会针对密集输入使用额外的存储空间
- 实际上，更高效的表构建器实现不会随着 O(n) 而扩展，其中 n 是设置的字段数。这会占用一些主要优势。
稀疏表未知
提议的设计 + 构建器
此 RFC 中提议的设计（以及其他几种类似设计）需要使用构建器以线上格式布局中的字段值进行布局。其性能取决于所选择的特定构建器算法，而该算法又根据预期输入的性能而选择。
应选择哪种构建器实现？
构建器的扩缩
扩展为 O(n) 的构建器，其中 n 是设置的字段数，在所有（最稀疏的输入除外）上，设置的字段数往往很慢。这包括执行插入排序或使用中间数据结构（例如最小堆并转换为已排序列表）的构建器。
对于现有的密集输入，扩展为 O(m) 的构建器往往速度更快。例如，构建器在密集布局中构建表，然后在线上转换为稀疏布局。
表条目分布
根据预期输入的分布，构建器和稀疏表线格式设计的性能可能截然不同。
部分因素包括：
- 条目是否密集？
- 最高序数是什么？
- 是否只有少量作品？
- 这些条目是否位于同一个区域中？
没有太多证据表明当前表的使用会从稀疏表中受益。稀疏表工作基于以下假设：将来表使用会更加稀疏，或者也许稀疏的传输格式将触发更稀疏的使用。
专精领域：编译时、计数等
设计一个针对输入分布表现良好的表构建器的另一种方法是为特定输入专门使用构建器。示例：
- 专用于在编译时处理一组已知字段，并直接填充传输格式结构，无需增加运行时构建成本。
- 根据字段数更改建筑物算法。
- 让用户明确决定要使用的构建器。
这样做的缺点是，API 会变得更复杂，并且在某些情况下，如何实际创建构建器的详细信息不明确（就编译时构建器而言）。
如果不考虑性能
由于性能要求和规范化（这通常会导致性能不佳），构建器设计很复杂。如果只需要“合理快速”的性能，可以改用键值对（或序值）方法。这要简单得多，也是 protobuf 采用的方法。
延迟迁移的成本与优势
延迟迁移的成本
难以在以后进行迁移
多种因素都可能会增加后续迁移的费用：
- 如果现有版本的不可迁移用量足够多，则可能需要无限期地维护这两个版本。
- 对于短期内（所有使用方式仍然可以切换）的迁移，如果不将这些变更与同时迁移的其他变更结合起来会带来一些开销（例如，需要创建更多的 GIDL 测试，并且需要在每个绑定中设置版本支持）。
ABI 稳定性
我们正努力尽快实现 ABI 稳定性，尤其是对于将依赖于 FIDL 的驱动程序 SDK。推迟更改表格传输格式会对这项工作产生负面影响。
延迟迁移的好处
详细了解使用场景和瓶颈
目前不需要稀疏表。关于表格条目布局的后续情况，也知之甚少。因此，有些人会犹豫不决，看看有哪些瓶颈。
避免系统复杂性
许多稀疏表实现都相当复杂。一旦这种复杂性进入系统中，我们将永远应对它。因此，我们可能需要犹豫是否要向系统添加这种复杂性。
总结
基于上述因素，我建议目前不要实现稀疏表。高性能实现是一个复杂的实现，其优势目前尚不清楚。但是，如果因素发生变化，这并不排除以后开发稀疏表的情况。
总结
此 RFC 引入了对 FIDL 传输格式的变更，这些变更优化了表，以实现当前序数的稀疏分布。
设计初衷
目前，未设置某个表字段（无论字段是由于预留而未设置，还是根本不存在）都会产生巨大的成本。此开销来自表的当前传输格式布局 - 表表示为向量，其大小等于最大序集。
考虑存在一个序数的情况。该向量将与这个单个序数的值一样大，因此，如果序数较大，则分配和处理该向量的费用也会随之增加。
这不符合用户的预期。在类似的传输格式（如 protobuf）中，设置字段的费用与序值无关。
使用 FIDL 时，可能没有必要对所有序数严格保持同等费用。有一些属性会偏向于传输格式以偏向低序数。例如，FIDL 需要保留每个意外字段，并且出于安全考虑，不建议使用与 proto 扩展类似的方法。 因此，输入的密度会比其他有线格式的输入更密集。尽管如此，现有的传输格式仍然倾向于比用户预期的更密集的输入。
设计
此设计为表格引入了一种新的有线格式，这种格式针对的是特定类型的稀疏性：性能取决于序数，但与现有有线格式相比，序数增加时的急剧下降幅度相对较小。
此设计假定 RFC-0032：高效信封已获批准，并以该信封为基础进行。
电汇格式
新的传输格式布局的定义如下所示。此处使用伪 C 结构体进行说明。传输格式的解码形式与传输格式密切相关，此图也对此进行了说明。
// Top-level inline table component.
// This is identical to the existing representation of table headers.
struct TableHeader {
// The maximum ordinal used in the table frame, or 0 if the table is empty.
uint64_t max_ordinal;
// Two possibilities, depending if this is the decoded form or wire form.
union {
// Wire form: marker value 0xffffffffffffffff indicating the presence
// of a frame. A frame is always present, but may be zero-sized.
// This field acts as a placeholder for the pointer to the table frame
// in the decoded form of the table.
uint64_t frame_present_marker;
// Decoded form: pointer to the table's frame.
TableFrame* frame;
};
};
// Body or 'frame' of the table.
struct TableFrame {
// Array of *m* 64-bit bitmasks, with each bit in a bitmask indicating the
// presence of each ordinal in the table, up to the maximum present ordinal.
// Within a bitmask, presence bits are ordered in little endian order.
uint64_t presence_bitmasks[m];
// Array of *k* envelopes, where *k* is the number of bits set in
// `presence_bitmasks`. There is one entry in the array for each of the
// table envelopes that is present. Envelopes that are not present do not
// appear in this array. Envelopes are ordered by ordinal.
FieldEnvelope envelopes[k];
};
// An envelope represents a present table field.
// This is identical to the representation in RFC-0032: Efficient envelopes.
struct FieldEnvelope {
// Two possibilities, depending if this is the decoded form or wire form.
union {
// Wire form: counts of bytes and handles.
FieldCounts counts;
// Decoded form: pointer to the data in the field.
void* data;
};
}
// Counts of bytes and handles, used for supporting unknown fields.
// This is identical to the representation in RFC-0032: Efficient envelopes.
struct FieldCounts {
// Number of bytes, recursively, used by this field.
uint32_t num_bytes;
// Number of handles, recursively, used by this field.
uint32_t num_handles
};
主要有以下三项更改：
- 表格框架中只会包含当前使用的信封。这与现有的传输格式（包括表框架中的每个元素，无论存在或不存在）形成鲜明对比。
- 表框架新增了存在位掩码部分。这些元数据用于加快编入表的速度 - 对于位掩码中的指定序数位置，在该点之前标记为存在的位数对应于信封列表中信封的索引。
- 表序的最大新限制是 256。如果消息包含大于 256 的序数，绑定必须关闭通道。 此限制是某种随机选择的，目的是平衡性能与预期序数的范围。设置限制的目的是确保性能在预期范围内，并简化绑定中的缓冲区分配。如果未来 RFC 中有足够的激励用例，可以提高此限制。限制的存在还会强制与用户就高序数的用例进行对话，并且有助于更好地了解需求。
具体要求如下：
- 信封数组必须仅包含与当前字段对应的 k 封包。
- 如果最大序数（第 k 个信封的序数）为 n，则位掩码数组 m 的长度必须为
floor((n+63)/64)。回想一下，此处的 nn 使用从 1 开始的索引。也就是说，序数 1-64 m 为 1，65-128 m 为 2，以此类推。当 n 为零时，frame_present_marker会设置为不存在，并且没有表正文。
实现
对表的操作
鉴于新的传输格式导致多项操作发生变化，了解这些操作在新设计中的工作方式非常有用。
此处描述的特定方法并非由 RFC 强制实施，但可向读者说明如何完成相关操作。
遍历现有字段
编码和解码都需要遍历和处理现有的字段。在位掩码的特定位置的 1 位表示字段位于相应的序数。要遍历当前字段，只需遍历 1 中的位。
这可以通过以下过程实现：
template<CallbackFuncType>
void iterate_through_present(
uint64_t* bitmasks, int num_bitmasks, CallbackFuncType callback) {
int index = 0;
for (int i = 0; i < num_bitmasks; i++) {
uint64_t bitmask = bitmasks[i];
uint64_t last_offset = 0;
while (true) {
if (last_offset >= 64)
break;
if ((bitmask >> last_offset) == 0)
break;
last_offset += __builtin_ctzll(bitmask >> last_offset) + 1;
if (last_offset > 64)
break;
uint64_t ordinal = 64*i + last_offset;
callback(index, ordinal);
index++;
}
}
}
编码
按照上一部分中的说明遍历每个当前字段。向下找到字段值并对其进行编码，计算 num_bytes 和 num_handles。在有线格式信封上填写这些值。
解码
遍历每个呈现字段。向下进入字段值进行解码，将信封上的 data 指针设置为适当的值。
按序数查找字段索引
位运算可用于查找表框架的 envelopes 列表中某个字段的索引（给定序数）。
这可以通过以下过程完成：
int field_index(uint64_t ordinal, uint64_t* bitmasks) {
uint64_t bitmask_index = (ordinal - 1)/64;
if ((bitmasks[bitmask_index] & (1ull << (ordinal - 1) % 64)) == 0) {
// Not found.
return -1;
}
uint64_t field_index = 0;
for (uint64_t i = 0; i < bitmask_index; i++)
field_index += __builtin_popcountll(bitmasks[i]);
uint64_t mask = (1ull << ((ordinal - 1) % 64)) - 1;
field_index += __builtin_popcountll(bitmasks[bitmask_index] & mask);
return field_index;
}
请注意，这需要线性时间，但在步骤中，每个序数都有一个包含 64 个元素的区域，其中局部时间是固定的。这样做的好处是，索引前 64 个元素需要固定的时间。
Builder
在许多绑定中，都需要执行一个构建步骤，在网域对象和已解码的线上格式之间进行转换，然后才能进行编码。
在表切换到稀疏表示法后，此步骤会更加复杂，因为信包列表必须按排序顺序排列，并且仅包含当前包。除了已设置的表字段外，您还可以修改或取消设置这些字段。
下面提供了一些方法：
- 始终维护 FIDL 解码布局中的对象。这意味着在设置字段时执行插入排序。
- 在某些数据结构中保留键值对（其中键 = 序数，值 = 指针），例如最小堆。调用
build()后，生成 FIDL 解码的布局。 - 使用存在字段和不存在字段的数组，其中数组中的索引为
ordinal - 1。完成调用build()后，构造最终的解码格式。 - 为一组特定的表字段专门使用构建器，以便直接由赋值填充解码后的格式。这可能意味着使用 C++ 中的模板或 Rust 中的宏来构建干净的接口。
如需了解对比和更多详细信息，请参阅“替代方案”部分。
此 RFC 未指定用于构建对象的解码格式表示法的具体技术。
Migration
需要从现有线上格式向新格式进行复杂的迁移。此 RFC 没有规定执行迁移的方法。我们计划一起批量处理多项传输格式更改，从而降低每个功能的迁移费用。
性能
编写了一个 CL，用于实现建议的表格布局的原型。针对三种不同的表输入运行基准，以了解输入稀疏性的影响：一个表设置了所有字段，一个表设置了所有其他字段，另一个表只设置了单个字段。
所有测量结果均来自配备 Intel Core i5-7300U CPU @ 2.60GHz 的机器。
使用稀疏表前后的时间进行编码：
| # 字段 | 设置完毕 | 所有其他集合 | 上次设置时间 |
|---|---|---|---|
| 16 | 38 -> 25 | 32 -> 20 | 28 -> 20 |
| 64 | 120 -> 74 | 103 -> 25 | 80 -> 19 |
| 256 | 366 -> 205 | 307 -> 106 | 199 -> 20 |
| 1024 | 1401 -> 656 | 1081 -> 335 | 600 -> 22 |
在所有情况下，编码速度都更快。 解码会使用几乎完全相同的算法进行编码，并且预计会产生几乎相同的结果。
在使用稀疏表前后查询某个序数的索引（以 ns/op 表示）的平均时间：
| # 字段 | 设置完毕 |
|---|---|
| 16 | 1.4 -> 2.6 |
| 64 | 0.4 -> 2.0 |
| 256 | 0.3 -> 3.5 |
| 1024 | 0.2 -> 5.7 |
索引编制速度要慢得多。但对于 64 个条目，则为所有条目编制索引时增加了 103ns 的总时间，这与编码时间的节省类似。请注意，这测量了访问所有字段所需的时间。如果仅访问部分字段，则时间会更短。
由于查找具有 256 个条目的索引的平均时间比查找具有 64 个条目的索引的时间多 1.5ns，因此可以推断出，记忆的增益约为每次操作 1.5 纳秒，或总共约 380 纳秒。但这一次适用于 256 个字段都设置完毕的极少数情况。
系统也记录了构建 FIDL 解码格式的对象所用的时间，但此处省略了具体数字，因为构建时间与实现密切相关，并且根据实现情况的不同而差异很大。
测量的数字假定所设置的字段事先已知，并且与现有的实现非常相似。但是，如果设置的字段提前不知道，那么构建时间预计会更长。尽管如此，单纯使用高效信封的时间预计仍会在时间的 2 倍以内。
上下文中的性能结果
所测量的编码器和解码器是手动编写的，没有现有编码器的开销。旨在指示高度优化的代码的理想性能。如果我们考虑实际实现的开销，则之前/之后的性能数据可能会更接近。
工效学设计
用户可见的主要更改是对语言绑定中使用的特定构建器实现的更改。这些更改因绑定而异。
向后兼容性
此变更会破坏 ABI。此外，这还可能会破坏源代码，具体取决于给定绑定中的构建器实现。
安全注意事项
没有任何新的安全问题。同样的信息也以不同形式传达在表格中。
隐私注意事项
这不会对隐私权造成任何影响。表传输格式表示中保留的数据量与之前相同。
测试
GIDL 一致性套件将用于单元测试，而集成测试将通过 FIDL 兼容性测试套件执行。
文档
此更改主要是在后台进行的，因此大多数文档不需要更改。需要更改的内容是：
- 需要更新传输格式规范。
- 此变更对绑定 API 所做的任何更改都需要进行更新。
缺点、替代方案和未知情况
缺点
复杂性
使用位掩码在序数和有线格式索引之间进行转换会增加所有阶段的复杂性：构建、编码、解码以及按序编入索引。此外，构建器变得更为复杂，因为为了获得最佳性能，它可能需要计算位掩码，并在适当的位置设置适当的字段 - 特别是在编译时完成。
构建器性能
构建器的一种常规实现是将字段布局为数组，每个序数有一个数组槽位，一直到最大序数。构建完成后，它会将条目压缩为稀疏表。这需要完成大量工作，在某些情况下，最终可能导致结果明显慢于密集表。
可能有更快的方法来实现构建器，尤其是在能够执行重要编译时逻辑的语言中，但这也会增加实现的复杂性。
Migration
需要进行完整的传输格式迁移。费用可能相当高昂。最近的电汇迁移涉及复杂的步骤，需要许多人月才能完成。它还倾向于在迁移涉及的所有位置留下清理任务的跟踪记录。
构建器实现方法
“实现”部分介绍了多种用于实现构建器的方法，这些构建器以解码形式输出对象。本部分比较了这两种选项。
请务必注意，我们选择以解码形式表示构建对象，而不是使用其他中间形式，因为我们认为这会使迁移变得更简单。目前，编码和解码是与另一种相反的。如果需要转换为其他中间形式进行编码，则需要更新所有绑定以反映这一点。
始终以 FIDL 解码格式维护对象
若要将对象构建为 FIDL 解码格式，一种简单方法是始终使其采用该格式。遗憾的是，这样做的成本很高，因为新设置的字段需要插入排序，并插入到以解码格式存在的已排序列表中。这样做的成本可能相当高。
将键值对（键 = 序数，值 = 指针）保留在最小堆中
最小堆的修改简单且相对高效。它还与已排序列表有关系，因为排序后列表是最小堆，这让您可以更轻松地执行修改解码值等操作，尽管在实践中很少会这样做。其思路是使用最小堆进行修改，然后在构建完成后，将堆中的所有条目都按照解码的格式排序。
此方法的一个优点是工作量随设置字段 k（实际为 O(k log k)）的数量而扩缩。这与可能会随最大序数扩缩的其他方法不同。这种方法的缺点是，在很多情况下，这种方法不一定是最快的，但可以考虑使用。
使用存在或不存在字段的数组，其中索引为 ordinal-1
这与现有的已解码表示形式（减去位掩码）一起使用的数组相同。设置某个字段后，系统可以直接将该字段编入索引到适当位置，从而在数组中直接赋值。为了转换为 FIDL 解码形式，必须“紧凑”数组，使其仅包含当前条目。这可以用 O(m) 次完成，其中 m 是最大序数。
这种方法的缺点是，构建时间会随着 m（而不是设置字段 k 的数量）而变化。然而，在实践中，该方法似乎通常比基于最小堆的方法更快。
附加到日志，然后压缩
另一种可能性是，设置字段后，构建器可以将键值对条目（以序数作为键）附加到日志。该日志将包含初始字段分配的条目以及所做修改。然后，构建器可以对列表进行排序，并在出现修改时应用修改，从而生成所需的输出。
为一组特定的表字段专门使用构建器
在编译时，使用模板为要设置的特定字段生成构建器。这适用于使用表进行演化，但不会动态更改所设置的字段的情况。
当字段已知时，可以直接将它们分配到有序列表的相应位置（采用 FIDL 解码格式），从而提高效率。
但其缺点是，实现起来比较困难，在很多情况下也可能无法实现。
替代选项
FIDL 操作（构建、编码、解码、查找）的性能与为传输格式选择的表示形式之间存在着紧密的相互关系。
无位掩码
另一种替代实现是从线上格式中移除位掩码。每个稀疏表条目都将是一个键值对，其中键是序数，值是信封。二进制搜索将用于查找条目。虽然这种方法可以运行，但二进制搜索的成本似乎过高。此外，为密钥添加额外的存储空间预计会降低性能。
块的层次结构
有一系列结构大致相当于一个树或一系列块，叶片是包围式。例如，页面表格样式的设计中，中间层指向底层，这些层最终在叶片上带有信封。
这类结构存在一些问题：
每一层都需要有一个需要搜索相应条目的键值对列表（如 B 树），或者有一个可以直接编入索引的列表（如页表）。这两者都需要在性能方面进行权衡。使用类似页面表格的结构，编码和解码时会遇到许多空条目，但这些条目的计数仍可能比密集表的计数少得多。但是，对于键值对列表，每个条目的字节数会增加，已知会导致速度变慢，并且将其编入索引也会变慢。
块中未使用的条目往往会占用大量空间。假设有一个 3 层树，每个层上有 8 个指针（最多 512 个元素）。第一个条目需要 388=192 字节。一个完全填充的树将占用 2624 个字节。192 字节的密集表可容纳 24 个元素，4096 字节的密集表可容纳完整的 512 个元素，因此高端占用的空间不大，而在低端使用大量额外的大小。如其他区域所示，大小会对性能产生显著影响。
规范化的开销很高。FIDL 的一项原则是，对于给定的输入，电汇消息必须具有单一的规范化表示法。但是，对于基于指针的结构，所指向的对象需要放置在特定的规范位置，这很难高效执行。所有键值对都需要进行排序，虽然 FIDL 针对指针遍历对深度优先顺序进行了标准化，但在编码和解码时间方面，处理每个指针的成本也很高。请注意，与所提议的基于位掩码的方法一样，如果预先设置的字段已知，规范化开销可能会在编译时隐藏。
它们可能需要大小限制。仍可能是出于某种原因对序数施加大小限制，但对于某些块层次结构，它们被纳入了表示形式。例如，双层树的大小限制可能为 256 个条目，具体取决于不同层的大小。更改大小限制属于破坏 ABI 合规性的更改，因为这些更改意味着更改块层的大小和配置。
协议缓冲区消息表示
协议缓冲区中的消息是一系列键值对，其键等同于 FIDL 序数。无法保证其字段会按照顺序写入。
由于 FIDL 的规范化要求，等效的 FIDL 需要按排序顺序发送字段。可以使用线性搜索或二元搜索来查找字段。这种格式与提议的位掩码格式类似，只不过使用键而非位掩码来识别序数。
对于小型表，位掩码格式预计会比通过序键列表进行二进制搜索更快。FIDL 中的序数预计低于 protobuf 中的序数，因此不需要高序支持。此外，对于这两种格式，对象构建步骤（即所提议的格式中最复杂的常见操作）是相同的。
FIDL 中的两种记录类型
可以考虑在 FIDL 中设置两种记录类型：稀疏表和密集表。不这样做的主要动机是，这会让用户加重在这两种类型之间进行选择，而这不一定是一项轻松的任务。因此，最好使 FIDL 语言保持简单，并且只使用一种类型。
不过，值得注意的是，如果引入新类型，将无需从现有类型进行迁移。
其他可能相关的传输格式变更
信封中的内嵌字段
即将发布的 RFC 预计会提出一些可变的信封，用于存放指向基元的指针，以便直接将基元（而不是指针）放到信封内。 如果获得批准，可与本 RFC 中提议的更改同时实施。它未在此 RFC 中找到，因为它是一种基本正交的更改，具有自身的复杂程度。
早期技术和参考资料
Protocol Buffers 使用的表示法用于比较。请参阅“Protocol Buffers 消息表示”部分。