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

拒绝理由

我们已拒绝这份 RFC，因为它提议为表格采用稀疏 FIDL 线格格式，并且存在以下利弊分析。

另请参见：

• RFC-0047：表
• RFC-0132：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 中根据需要提高此上限。存在上限还会迫使您与用户就高序数的使用情形进行对话，从而更好地了解需求。

具体如下：

• envelopes 数组必须仅包含与当前字段对应的 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。在电汇格式信封上填写这些值。

解码

迭代每个当前字段。向下进入字段值并进行解码，将封套上的 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，用于实现建议的表格布局的原型。我们针对三种不同的表输入运行了基准测试，以了解输入稀疏性的影响：设置了所有字段的表、设置了所有其他字段的表，以及仅设置了单个字段的表。

所有测量结果均来自搭载 2.60GHz Intel Core i5-7300U CPU 的机器。

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

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

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

索引编制时间要慢得多。但是，对于 64 个条目，将所有条目编入索引需要增加 103ns 的总时间，这与编码时间的节省量大致相当。请注意，这项指标是衡量访问所有字段所需的时间。如果只访问部分字段，则所需时间会更短。

由于查找包含 256 个条目的索引的平均时间比查找包含 64 个条目的索引的时间多 1.5ns，因此可以推断出，通过 Memoize 实现的性能提升大约为每项操作 1.5ns，总体而言约为 380ns。不过，这次是为了处理极少数情况下需要设置所有 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 消息表示法”部分。