RFC-0116：对解析器 FIDL 表的有线格式支持

拒绝理由

此 RFC 提议为表使用稀疏 FIDL 线格式，但因以下优缺点分析而被拒绝。

另请参见：

• RFC-0047：表格
• RFC-0132：FIDL 表大小限制

稀疏表的优势

稀疏表的主要优势包括：

• 性能会随着设置的字段数量 n 而按 O(n) 的比例缩放。而不是 m，即最大序数。因此，与现有表相比，稀疏表在少量高序数字段的情况下应具有良好的性能。请务必注意，用户通常希望表格性能随 O(n) 而扩展，因此稀疏表格更符合用户预期。
• 更紧凑的线上传输格式。这意味着需要通过网络复制的字节数和需要持久保存的字节数更少。更紧凑的序列化格式的实际好处尚不清楚 - 它可能会提高性能并减少内存用量，但具体效果尚不清楚。

稀疏表的缺点

稀疏表的主要缺点是：

• 通常更复杂 - 尤其是与现有的密集表实现（非常简单）相比。有些实现需要花费大量精力才能理解和实现。
• 在输入较密集时效果不佳
• 与密集表格实现相比，使用密集输入时可能会使用额外的存储空间
• 实际上，更高效的表格构建器实现不会按 O(n) 进行扩缩，其中 n 是设置的字段数。这会抵消一些关键优势。

稀疏表的未知数

建议的设计 + 建造者

此 RFC 中提出的设计（以及其他几种类似的设计）要求构建器以有线格式布局来布局字段值。此方法的性能取决于所选的具体构建器算法，而构建器算法的选择又取决于预期输入的性能。

应选择哪种构建器实现？

扩大制作工具的规模

以 O(n) 缩放的 build（其中 n 是设置的字段数）在除最稀疏的输入之外的所有输入上往往都很慢。这包括执行插入排序或使用中间数据结构（例如最小堆）并转换为已排序列表的构建器。

以 O(m) 比例扩缩的构建器往往在处理现有密集输入时速度更快。一个示例是，构建器以密集布局构建表格，然后在网络上转换为稀疏布局。

表格条目的分布

根据预期输入的分布情况，构建器和稀疏表有线格式设计可能会有截然不同的性能。

一些因素：

• 条目是否密集？
• 最高序数是什么？
• 只有少量分散的条目？
• 条目是否仅位于单个区域中？

没有太多证据表明当前表格使用情况会受益于稀疏表格。稀疏表方案基于以下假设：未来，稀疏表的使用将更加普遍，或者稀疏线格式的存在将促使更多稀疏使用。

专业化：编译时、计数等

除了设计一个能够针对输入分布实现出色性能的表格构建器之外，另一种方法是针对特定输入专门设计构建器。示例：

• 在编译时专门针对一组已知字段，并直接填充线格式结构，而无需运行时构建成本。
• 根据字段数量更改了构建算法。
• 让用户明确决定使用哪个构建器。

但这样做的缺点是 API 会变得更加复杂，并且在某些情况下，如何实际创建 build 器的细节并不明确（对于编译时 build 器而言）。

如果效果不是影响因素

由于性能要求和规范化，构建器设计非常复杂，这通常会导致性能不佳。如果只需“相当快”的性能，则可以改用键值（或序数值）方法。这种方法要简单得多，也是 protobuf 所采用的方法。

延迟迁移的成本与收益

延迟迁移的成本

日后迁移的难度

有许多因素可能会增加后续迁移的成本：

• 如果现有版本有足够多的无法迁移的用法，可能需要无限期地维护这两个版本。
• 对于短期内可以完全切换的迁移，如果不将这些变更与其他同时迁移的变更相结合，则会产生一些开销（例如，需要创建更多 GIDL 测试，并在每个绑定中设置版本支持）。

ABI 稳定性

我们正在努力尽快实现 ABI 稳定性，尤其是对于将依赖于 FIDL 的驱动程序 SDK。延迟更改表格线框格式会对这项工作产生负面影响。

延迟迁移的好处

详细了解使用情形和瓶颈

目前，我们并不急需稀疏表。此外，我们对未来表格条目布局的分布情况也知之甚少。因此，有人认为应该先等待一段时间，看看瓶颈是什么。

避免系统过于复杂

许多稀疏表实现都相当复杂。一旦这种复杂性进入系统，我们将永远需要处理它。因此，我们可能需要谨慎地向系统添加这种复杂性。

总结

根据上述因素，我建议目前不要实现稀疏表格。高性能实现比较复杂，目前尚不清楚其优势。不过，如果情况发生变化，我们不排除日后开发稀疏表的可能性。

摘要

此 RFC 对 FIDL 有线格式进行了更改，以优化具有更稀疏的当前序号分布的表。

设计初衷

目前，如果表字段未设置（无论是因预留而未设置，还是根本不存在），都会产生相当大的费用。此开销来自表的当前有线格式布局 - 表表示为大小等于最大序数的向量。

考虑存在单个序数的情况。向量的大小将与此单个序数值一样大，因此如果序数较大，分配和处理向量的成本也会很高。

这与用户的预期不符。在类似 protobuf 的线格式中，设置字段的成本与序号值无关。

使用 FIDL 时，可能不必严格要求所有序数的费用都相等。有些属性会使传输格式偏向较低的序数。例如，FIDL 要求预留每个意外字段，并且出于安全原因，不建议使用类似于 proto 扩展的内容。因此，与现有其他线材格式相比，预计输入会更密集。不过，现有的有线格式面向的是比用户预期更密集的输入。

设计

此设计为表格引入了一种新的线格式，该格式针对的是一种特定的稀疏性 - 性能与序数相关，但随着序数的增加，性能下降的幅度不如现有线格式那么陡峭。

此设计假设 RFC-0032：高效信封已获批准，并以此为基础。

Wire 格式

新的有线格式布局将定义如下。此处使用伪 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)。请注意，此处的 n 使用从 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。在有线格式信封中填写这些值。

Decode

遍历每个存在的字段。进入字段值并进行解码，将信封上的 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 的机器。

使用稀疏表对之前和之后的时间进行编码：

在所有情况下，编码速度都更快。 解码使用与编码几乎相同的算法，预计会产生几乎相同的结果。

使用稀疏表之前和之后，查找序号索引的平均时间（以纳秒/操作为单位）：

编入索引的时间要长得多。但对于 64 个条目，为所有条目编制索引的总时间增加了 103 纳秒，这与编码时间的节省类似。请注意，这是衡量访问所有字段所需的时间。如果仅访问部分字段，时间会更短。

由于查找包含 256 个条目的索引的平均时间比查找包含 64 个条目的索引的时间多 1.5 纳秒，因此可以推断出记忆化带来的增益约为每次操作 1.5 纳秒，总共约为 380 纳秒。不过，此时间是针对所有 256 个字段都已设置的极小概率情况。

我们还记录了以 FIDL 解码格式构建对象的时间，但此处省略了具体数字，因为构建时间高度依赖于实现，并且会因实现而异。

所测得的数字假设预先已知要设置的字段，并且与现有实现大致相似。不过，如果设置的字段事先未知，则 build 时间预计会更长。不过，这些时间预计在仅使用高效信封的时间的 2 倍以内。

上下文中的效果数据

被测量的编码器和解码器是手动编写的，没有现有编码器的开销。旨在表示高度优化的代码的理想性能。如果考虑实际实现的开销，前后性能数字可能会更接近。

工效学设计

面向用户的主要变化是语言绑定中使用的特定构建器实现发生了变化。这些更改将因绑定而异。

向后兼容性

此项变更会破坏 ABI。它也可能会破坏源代码，具体取决于给定绑定中的构建器实现。

安全注意事项

没有新的安全问题。表格中也传达了相同的信息，只是形式不同。

隐私注意事项

不会对隐私权造成影响。与之前一样，以表格线格式表示的数据量保持不变。

测试

GIDL 一致性套件将用于单元测试，而集成测试将使用 FIDL 兼容性测试套件执行。

文档

此变更主要在底层进行，因此大多数文档无需更改。需要更改的内容包括：

• 需要更新线上传输格式规范。
• 由此变更导致的所有绑定 API 变更都需要更新。

缺点、替代方案和未知因素

缺点

复杂性

使用位掩码在序号和有线格式索引之间进行转换会增加所有阶段的复杂性：构建、编码、解码和按序号编制索引。此外，构建器变得更加复杂，因为为了获得最佳性能，它可能需要计算位掩码，在适当的位置设置适当的字段，尤其是在编译时完成这些操作时。

构建器性能

一种通用的构建器实现方式是将字段布局在一个数组中，每个序号对应一个数组槽，直到达到最大序号。构建完成后，它会将条目压缩为稀疏表。这需要做大量工作，在某些情况下，最终可能会比密集表慢得多。

可能存在更快的构建器实现方式，尤其是在能够执行大量编译时逻辑的语言中，但这也会增加实现的复杂性。

Migration

需要进行完整的线框格式迁移。这可能相当昂贵。最近一次电汇迁移涉及复杂的步骤安排，耗费了许多人月才完成。它还会在迁移所涉及的所有位置留下清理任务的痕迹。

构建器实现方法

实现部分介绍了多种用于实现以解码形式输出对象的 build 器的方案。本部分将对这些选项进行比较。

请务必注意，我们之所以选择以解码形式（而非其他中间形式）表示构建的对象，是因为我们认为这样可以简化迁移。目前，编码和解码是彼此的逆运算。如果需要转换为其他中间形式才能进行编码，则需要更新所有绑定以反映这一点。

始终以 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 等效项需要按排序顺序发送字段。系统会使用线性搜索或二分搜索来查找字段。此格式与提议的位掩码格式类似，只是使用键而不是位掩码来标识序数。

对于小型表，位掩码格式的速度预计会快于通过序号键列表进行二进制搜索。与 protobuf 相比，FIDL 中的序号预计会更低，因此不需要提供高序号支持。此外，对象构建步骤（建议格式中最复杂的常见操作）对于这两种格式是相同的。

FIDL 中的两种记录类型

可以考虑的一种方案是在 FIDL 中使用两种记录类型：稀疏表和密集表。不这样做的主要原因是，这会给用户带来在两种类型之间进行选择的负担，而这不一定是一项简单的任务。因此，我们倾向于保持 FIDL 语言的简单性，并仅使用一种类型。

不过，值得注意的是，如果引入新类型，则无需从现有类型迁移。

其他相关的潜在线格式变更

信封中的内嵌字段

即将发布的 RFC 预计会提议更改包含指向基元的指针的信封，以直接在信封内保存基元，而不是指针。如果获得批准，该更改可能会与此 RFC 中提出的更改同时实施。之所以未将此功能纳入本 RFC，是因为它是一项基本正交的更改，具有自己的一组复杂性。

在先技术和参考资料

用于比较的是 Protocol Buffers 使用的表示形式。 请参阅“Protocol Buffers 消息表示法”部分。