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 的 Drivers SDK。延後對表格線路格式的變更，將對這項工作造成負面影響。

延後遷移的好處

進一步瞭解用途和瓶頸

目前不需要立即使用稀疏資料表。我們也不知道表格項目版面配置的分配方式會如何演變。因此，我們建議您等待情況明朗，再來判斷瓶頸為何。

避免系統複雜

許多稀疏表格實作方式都相當複雜。一旦系統出現這種複雜性，我們就必須永遠處理這個問題。因此，我們可能會猶豫是否要將這種複雜性加入系統。

結語

根據上述因素，建議您暫時不要實作稀疏資料表。實作高效的機制相當複雜，目前尚不清楚帶來的效益。不過，如果因素有所變動，這並不排除日後開發稀疏資料表的可能性。

摘要

這項 RFC 會對 FIDL 電纜格式進行異動，以便針對現有序數的稀疏分發情形，對資料表進行最佳化。

提振精神

目前，無論是因為保留而未設定資料表欄位，或是根本沒有欄位，都會造成重大成本。這項成本來自資料表的目前線路格式版面配置，資料表會以向量表示，大小等於最大序數集。

請考慮單一序數的情況。向量會與這個單一序數的值一樣大，因此如果序數很大，分配和處理向量的成本也會隨之增加。

這與使用者預期不符。在類似的傳輸格式 (例如 protobuf) 中，設定欄位的成本與序數值無關。

使用 FIDL 時，不一定需要為所有序數設定相同的費用。有些屬性會偏向將線格格式設為較低的序數。舉例來說，FIDL 要求保留所有意外的欄位，且基於安全性考量，不建議使用類似 Protobuf 擴充功能的項目。因此，輸入內容的密度會比其他線路格式高。不過，現有的線路格式會提供比使用者預期更密集的輸入內容。

設計

這項設計為針對特定稀疏度的表格引進了新的線格格式，其效能取決於序數，但隨著序數增加，其效能下降的幅度會比現有線格格式小。

此設計假設 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)。請注意，此處的 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 並未指定建構物件解碼格式表示法的具體技巧。

遷移

您必須從現有的線路格式，遷移至新格式。本 RFC 並未規定執行遷移作業的方法。我們預計將多個線路格式變更一起批次處理，以降低每項功能的遷移成本。

成效

我們編寫了 CL，實作建議表格版面配置的原型。我們針對三種不同的表格輸入內容執行基準測試，以瞭解輸入稀疏度所造成的影響：一張設定了所有欄位的表格、一張設定了所有其他欄位的表格，以及一張只設定單一欄位的表格。

所有測量結果均來自搭載 Intel Core i5-7300U CPU @ 2.60GHz 的機器。

使用稀疏資料表前後的編碼時間：

在所有情況下，編碼速度都更快。解碼會使用幾乎相同的演算法進行編碼，因此結果應會幾乎相同。

使用稀疏表格前後，查詢序號索引的平均時間 (以 ns/op 為單位)：

索引時間會變得更慢。但對於 64 個項目，總共需要 103 毫秒的時間才能為所有項目建立索引，這與節省的編碼時間相近。請注意，這項測試會評估存取所有欄位的時間。如果只存取部分欄位，時間會縮短。

由於查詢 256 個項目的索引的平均時間比查詢 64 個項目的索引的時間多 1.5ns，因此可推斷，快取記憶體的效益大約為每個作業 1.5ns，或整體約 380ns。不過，這次是針對所有 256 個欄位都已設定的情況 (這種情況不太可能發生)。

我們也記錄了以 FIDL 解碼格式建構物件的時間，但這裡省略了具體數字，因為建構時間高度依賴實作方式，且會因實作方式而有很大差異。

測量到的數字假設已知要設定的欄位，且與現有實作大致相似。不過，如果事先不知道要設定哪些欄位，建構時間可能會拉長。不過，這些時間應會在效率高的封包時間的 2 倍以內。

情境中的成效結果

測試的編碼器和解碼器是手寫編寫的，因此沒有現有編碼器的額外負擔。這些值旨在指出經過高度最佳化程式碼的理想效能。如果我們考量實際導入作業的額外負擔，前後效能數據的差距可能會縮小。

人體工學

對使用者來說，主要的異動是語言繫結中使用的特定建構工具實作方式。這些變更會依據綁定項目而有所不同。

回溯相容性

這項變更會中斷 ABI。這也可能會造成來源中斷，具體取決於特定繫結中的建構工具實作方式。

安全性考量

沒有任何新的安全疑慮。表格會傳達相同的資訊，只是格式不同而已。

隱私權注意事項

不會影響隱私權。在表格線路格式表示法中，會保留與先前相同的資料量。

測試

GIDL 相容性套件將用於單元測試，而整合測試則會使用 FIDL 相容性測試套件執行。

說明文件

這項變更主要在幕後進行，因此大部分說明文件都不需要變更。需要變更的項目如下：

• 需要更新線路格式規格。
• 您必須更新綁定 API 的任何變更，才能讓這些 API 符合這項變更。

缺點、替代方案和未知事項

缺點

複雜度

使用位元遮罩來轉換序數和線路格式索引，會增加所有階段的複雜度：依序號建構、編碼、解碼和建立索引。此外，建構工具會變得更加複雜，因為為了達到最佳效能，它可能需要計算位元遮罩，並在適當位置設定適當的欄位，尤其是在編譯時執行時。

建構工具效能

建構工具的一般實作方式會將陣列中的欄位排列，每個序號一個陣列位置，最多可達到最大序號。建構完成後，系統會將項目壓縮成稀疏表格。這需要大量工作，且在某些情況下，可能會比密集表格慢上許多。

實作建構工具的方法可能更快，特別是在能執行大量編譯時間邏輯的語言中，但這也會增加實作作業的複雜度。

遷移

需要進行完整的線路格式遷移作業。這可能會造成高昂費用。最近的線路遷移作業涉及複雜的步驟排程，需要花費許多人月才能完成。而且，在遷移作業影響的所有位置，都可能會留下清理工作。

建構工具導入方法

實作部分介紹了實作建構工具的多種方法，這些方法會以解碼格式輸出物件。本節將比較這些選項。

請注意，我們選擇以解碼格式呈現已建構的物件，而非其他中介格式，因為我們認為這麼做可讓遷移作業更輕鬆。目前，編碼和解碼是彼此的反向運算。如果需要轉換為其他中介形式進行編碼，則所有繫結都必須更新，以反映此情況。

一律以 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 無關，因為它是與本 RFC 無關的變更，且有其自身的複雜性。

既有技術與參考資料

我們使用 Protocol Buffers 使用的表示法進行比較。請參閱「Protocol Buffers 訊息表示法」一節。