| RFC-0116：稀疏 FIDL 表的有线格式支持 | |
|---|---|
| 状态 | 已拒绝 |
| 领域 |
|
| 说明 | 此 RFC 引入了对 FIDL 线路格式的更改，以优化现有序数的稀疏分布表。 |
| 问题 | |
| Gerrit 更改 | |
| 作者 | |
| 提交日期（年-月-日） | 2021-06-16 |
| 审核日期（年-月-日） | 2021-07-21 |
拒绝理由
此 RFC 提议的表采用稀疏 FIDL 传输格式，并被拒绝， 以下优缺点分析。
另请参见：
稀疏表的优势
稀疏表的主要优势如下：
- 可扩缩
O(n)的性能，其中n是设置的字段数量。 最大序数，而不是m。因此，稀疏表应该 相较于 现有的表。请务必注意，用户通常希望 将表性能扩展为O(n)，使稀疏表更贴近 用户期望。 - 更紧凑的传输格式。这意味着要复制的字节更少， 减少的字节数更紧凑的线缆格式的实际优势 不清楚 - 这可能会提高性能并减少内存使用量，但 这种情况的发生程度未知。
稀疏表的缺点
稀疏表的主要缺点如下：
- 通常更为复杂，尤其是与现有密集的 表格的实现，非常简单有些实现需要 理解和实施的重要工作。
- 使用更密集的输入时性能不佳
- 与密集表相比，可能需要使用额外的存储空间来处理密集输入 实现
- 事实上，更高效的表格构建器实现并不会像之前一样进行扩展 O(n)，其中 n 是设置的字段数。这会排除一些关键的 优势。
未知的稀疏表
提议的设计 + 建造者
本 RFC 中建议的设计（以及一些其他类似的设计）要求使用 Builder 将字段值布局为线上格式布局。通过 这取决于所选的具体构建器算法，反过来 是基于预期输入值的效果选择的。
应选择哪种构建器实现？
构建器的扩缩
扩展为 O(n) 的构建器（其中 n 是设置的字段数）往往
在除最稀疏输入之外的所有输入上都很慢。这包括
插入排序或使用中间数据结构（例如最小堆和
转换为有序列表。
对于现有的密集输入，以 O(m) 形式扩缩的构建器往往速度更快。
例如，构建器以密集布局构建表，
然后转换为线路上的稀疏布局。
表条目的分布
根据预期输入、构建器和稀疏表的分布 线上格式设计可能会有截然不同的性能。
部分因素：
- 条目是否密集？
- 最高序数是多少？
- 是不是只有几个条目分散了？
- 这些条目是否仅在单个区域中？
没有太多证据表明当前的表使用会受益于稀疏 表格。稀疏表工作基于未来 更常见的情况是表的用法稀疏，或者可能存在 将会触发更多稀疏的使用行为。
专精领域认证：编译时、计数等
另一种方法是设计能够很好地适应当前环境的 输入分布是为特定输入专用构建器。示例：
- 在编译时专门处理一组已知字段，并直接填充 传输格式结构，无需运行时构建成本。
- 根据字段数更改构建算法。
- 让用户明确决定要使用的构建器。
这种方法的缺点在于，API 会变得更加复杂，在某些情况下， 有关如何实际创建构建器的详情并不清楚（在这种情况下， 编译时构建器）。
如果性能不是影响因素
由于性能要求和 这通常会导致性能不佳。如果只关注效果 需要“相当快”，而键值对（或序数值）方法可以 。这要简单得多，也是 protobuf 采用的方法。
延迟迁移的成本与优势
延迟迁移的费用
以后迁移时遇到困难
有很多因素可能会增加 迁移：
- 如果存在以下情况，则可能需要无限期地维护这两个版本： 使用现有版本时，必须充分且不可迁移。
- 用于短期迁移（所有使用方式仍可切换） 因此，如果不将这些变化与其他应用结合使用，会产生一些开销。 同时迁移多项更改（例如，需要 和版本支持）。
ABI 稳定性
我们正致力于尽快实现 ABI 稳定性，尤其是对于驱动程序 SDK，具体取决于 FIDL。推迟对表格传输格式的更改 会对这项工作产生负面影响。
延迟迁移的好处
详细了解用例和瓶颈
目前没有立即需要稀疏表。此外， 表格条目布局的分布情况 更进一步。因此，等待 并找出瓶颈所在
避免系统复杂性
许多稀疏表实现都相当复杂。完成上述 系统复杂性，我们将永远处理该问题。由于 我们可能需要设法增加系统 犹豫不决的。
总结
根据上述因素，我建议不要实现稀疏 目前有个表高效实现十分复杂， 目前还不清楚。这并不排除在 但稍后，如果因素发生变化。
摘要
此 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 个信封的序数）是 n，则
位掩码数组 m 的长度必须为
floor((n+63)/64)。回想一下，n 此处使用从 1 开始的索引。也就是说，对于序数 1-64 m 而言，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()，构造最终 解码格式。 - 为一组特定的表字段提供专用构建器， 格式由分配直接填充。这可能意味着使用模板 或 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 个条目， 将所有条目编入索引，类似于节省编码时间。请注意， 这衡量的是访问所有字段所需的时间如果只有部分字段 就能越短越好
由于使用 256 个条目查找索引的平均时间比 查询包含 64 个条目的索引时，可以推断出 大约为每次操作 1.5ns，总时间约为 380ns。这次 但极少会出现这种情况，即设置了全部 256 个字段的情况。
以 FIDL 解码格式构建对象的时间也会记录下来，但 因为构建时间非常长 取决于具体实现，具体差异很大。
所测得的数字假定所设置的字段事先已知， 与现有的实施方式大体相似。但是，如果 但构建时间预计是 。尽管如此，该时间预计在时间的 2 倍以内
在具体情境下取得成效
被测的编码器和解码器都是手动编写， 可能会降低现有编码器的开销它们旨在指明 高度优化的代码的性能。如果我们考虑 实际实现时，前后的性能数据可能是
工效学设计
用户可见的主要更改是对特定构建器的更改 语言绑定中使用的实现。这些更改因绑定而异 以体现其约束力
向后兼容性
此变更破坏 ABI 合规性。这也有可能破坏源代码 指定绑定中的构建器实现。
安全注意事项
没有新的安全问题。同样的信息则通过表格传达 只是形式不同而已
隐私注意事项
这不会对隐私权造成任何影响。Google Analytics 像之前那样。
测试
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 的规范化要求，此 则需要按排序顺序发送字段。线性搜索或二元搜索 查找字段。此格式与建议的位掩码格式类似， 只不过使用键（而不是位掩码）来识别序数。
对于小型表，位掩码格式预计比二进制格式更快 来搜索序数键列表。普及率预计会降低 与 protobuf 相比，它具有 FIDL，因此对高序数支持的需求不如 protobuf。 此外，对象构建步骤是最常见的 操作 - 对于这两种格式是相同的。
FIDL 中的两种记录类型
可以考虑的一种方案是在 FIDL 中使用两种记录类型：稀疏 表和密集表。我们不这样做的主要动机是 给用户带来一些负担 一项简单的任务。因此，最好保留 FIDL 并且只有一种类型。
但值得注意的是，如果引入新类型， 不需要从现有类型进行迁移
其他相关的潜在电线格式变更
信封中的内嵌字段
即将到来的 RFC 预计会建议更改信封中存放指向 基元可直接在信封内保存基元，而不是 指针。 如果获得批准，此更改可能会与更改同时生效。 建议的参数。本 RFC 中将其省略，因为它主要用于 具有自身的复杂性。
先验技术和参考资料
比较的是 Protocol Buffers 所用的表示法。 请参阅“Protocol Buffers 消息表示法”部分。