RFC-0116：剖析器 FIDL 資料表的有線格式支援

RFC-0116：支援剖析器 FIDL 資料表的傳輸格式
狀態	已遭拒
區域	FIDL
說明	這項 RFC 導入的 FIDL 線路格式相關異動，可將資料表最佳化來因應目前序數的稀疏分佈情形。
問題	79093 年
變更	538805
作者	bprosnitz@google.com
提交日期 (年/月)	2021-06-16
審查日期 (年/月)	2021-07-21

拒絕原因

這個 RFC 提議為資料表採用稀疏 FIDL 傳輸格式，會因下列專家 / 並行分析而遭到拒絕。

另請參閱：

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

稀疏資料表的優點

稀疏資料表的主要優點如下：

• 調整 O(n) 的效能，其中 n 是已設定的欄位數量。最大值，而不是 m。因此，與現有資料表相比，稀疏資料表使用高序數的少量欄位時，效能應該也會不錯。請特別注意，使用者通常預期資料表效能會依 O(n) 擴充，因此稀疏資料表能更符合使用者的預期。
• 更精簡的有線格式。這表示要複製的傳輸位元組數越少，保留的位元組數也較少。較精簡的傳輸格式能帶來實際好處，因為這樣或許能提升效能並降低記憶體用量，但實際上卻是未知。

稀疏資料表的缺點

稀疏資料表的主要缺點如下：

• 一般來說較為複雜，特別是與現在相當簡單的現有密集資料表實作相比。有些實作方式需要耗費大量心力來瞭解和實作。
• 輸入遭拒時，效能不佳
• 與密集的資料表實作相比，輸入密集型的資料表可能會使用額外的儲存空間
• 實際上，效率較高的資料表建構工具實作不會像 O(n) 進行擴充，其中 n 代表已設定的欄位數量。此設定會排除部分主要優點。

稀疏資料表不明

提案設計 + 建構工具

本 RFC (以及其他類似設計) 中的建議設計需要建構工具以配置線路格式配置的欄位值。其效能取決於您選擇的特定建構工具演算法，而演算法會依預期輸入內容的效能選擇。

應選擇哪種建構工具實作？

建構工具的資源調度

縮放為 O(n) 的建構工具，其中 n 是集合的欄位數量，除了最稀疏的輸入內容外，所有欄位數量通常都緩慢。包括執行插入排序或使用中介資料結構 (例如最低堆積，並轉換為已排序清單) 的建構工具。

擴充為 O(m) 的建構工具在現有密集輸入中的速度通常較快。舉例來說，如果建構工具在密集版面配置中建構資料表，然後在線上轉換成稀疏版面配置。

資料表項目分佈

視預期輸入內容的分佈而定，建構工具和稀疏資料表線型格式的設計可能有極大差異。

以下列舉幾個因素：

• 輸入項目是否密集？
• 最高序數是什麼？
• 是否只有少數項目散發？
• 這些項目是否只在單一區域中？

目前沒有任何證據顯示，目前的資料表使用情形可因稀疏資料表而受益。「稀疏資料表工作」是根據以下假設假設：日後表格使用進一步稀疏，或存在稀疏線格式，會觸發更多稀疏線材。

專業認證：編譯時間、計數等

設計表格建構工具時，如果針對輸入的分佈情形可以順利運作，替代方式是專門處理特定輸入的建構工具。例如：

• 專門用於編譯期間的已知欄位組合，並直接填入傳輸格式結構，無須支付執行階段建構費用。
• 根據實景變更建構演算法。
• 讓使用者明確決定要使用的建構工具。

這種做法的缺點是 API 變得較為複雜，在某些情況下，實際如何建立建構工具時並不明確 (例如編譯時間建構工具)。

如果效能並非考量因素

由於效能需求和標準化程序，建構工具的設計相當複雜，而且通常會導致效能不佳。如果只需要「合理快速」的效能，您可以改用鍵/值 (或序數值) 方法。這個做法更為簡單，就是使用通訊協定緩衝區的方法。

成本與延遲遷移的好處

延遲遷移的費用

日後難以遷移

有很多因素可能會增加日後遷移的費用：

• 如果現有版本有足夠的可遷移性，可能需要無限期保留這兩個版本。
• 如果是短期內，所有使用情況仍可切換，則在不結合這些變更與其他同時遷移的其他變更時，可能會產生一些負擔 (例如，您需要建立更多 GIDL 測試，且必須在每個繫結中設定版本支援)。

ABI 穩定性

我們很快就會努力達到 ABI 穩定性，尤其是依附於 FIDL 的驅動程式 SDK。延遲變更資料表傳輸格式會對這項操作產生負面影響。

延後遷移的好處

進一步瞭解用途和瓶頸

目前不需要立即使用稀疏資料表。目前也沒有大致瞭解資料表項目版面配置在線條下方的分佈情形。因此，我們必須取得一些引數，以便等待瞭解瓶頸。

避免複雜的系統

許多稀疏資料表的實作方式相當複雜。一旦系統完成這項複雜作業，我們就會永久處理。因此，我們也許會考慮將複雜的複雜情況導入系統。

結語

根據上述因素，我目前不建議實作稀疏資料表。成效優異的實作方式十分複雜，目前優勢並不明確。但是，如果日後因因素而改變，這不會排除在日後開發稀疏資料表的條件。

摘要

這個 RFC 導入的 FIDL 線路格式變更，針對使用目前序數的稀疏器分佈情形將資料表最佳化。

提振精神

目前，無論是否因保留欄位或不存在而未設定該欄位，現在都會耗用大量資源。這筆費用取自資料表目前的傳輸格式配置，以向量表示，大小等於最大序數組合。

思考具有單序的情況。向量將會與這個單一序角的值一樣大，因此若序數較大，則分配及處理向量所需的費用。

這不符合使用者的期待。在 Protobuf 等類似的傳輸格式中，設定欄位的成本與序數值無關。

如果使用 FIDL，可能不需要為所有關係嚴格設定同等費用。有些屬性會將電線格式調整為依據下弦。舉例來說，FIDL 必須保留所有非預期欄位，同時基於安全考量，我們不建議使用與 proto 擴充功能類似的做法。因此，密度輸入預期會比其他線格式存在。不過，現有的傳輸格式著重於較密度輸入，而非使用者預期的輸入。

設計

這項設計針對以特定種類的稀疏度為目標的資料表推出了一種新的線路格式：效能取決於序數，但相較於現有線路的連接方式增減情況，延遲情況會越低。

此設計假設 RFC-0032：Efficient Envelopes 已經獲得核准，並以此做為基礎使用。

電匯格式

新的線路格式版面配置將定義如下。我們在此使用虛擬 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。填入電線格式信封上的值。

解碼

逐一查看目前存在的欄位。延伸到欄位值和解碼，將信封上的 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 的機器。

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

# 個欄位	大功告成	其他集合	上次設定
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 不符合這項變更，您就必須更新這些 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 中會省略其中。

先前的圖片和參考資料

通訊協定緩衝區使用的表示法用於比較。請參閱「通訊協定緩衝區訊息表示法」一節。