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 穩定性，尤其是 Drivers SDK，因為這項 SDK 會依附於 FIDL。延後變更資料表線路格式會對這項工作造成負面影響。

延後遷移的好處

進一步瞭解用途和瓶頸

目前不需要稀疏資料表。此外，目前也不太清楚表格項目版面配置的分配情形。因此，建議您先等待一段時間，看看瓶頸為何。

避免系統複雜化

許多稀疏資料表實作方式相當複雜。一旦系統出現這種複雜性，我們就永遠無法擺脫。因此，我們可能會猶豫是否要將這項複雜性加入系統。

結論

根據上述因素，建議您目前不要導入稀疏表格。實作成效良好的解決方案相當複雜，且目前效益不明。不過，如果因素改變，這並不排除稍後開發稀疏資料表。

摘要

這項 RFC 針對 FIDL 線路格式進行變更，可針對現有序數的稀疏分布情況，最佳化資料表。

提振精神

目前，未設定的資料表欄位會產生高昂的成本，無論欄位是因保留而未設定，還是根本不存在。這項費用來自資料表的現行線路格式配置，資料表會以向量表示，大小等於最大的序數集。

假設只有一個序數。向量的大小會與這個序數值相同，因此如果序數很大，分配及處理向量的成本也會很高。

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

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

設計

這個設計為表格導入新的線路格式，目標是特定稀疏性類型，也就是序數相關的效能，但序數增加時的降幅比現有線路格式小。

這項設計假設 RFC-0032：高效信封已獲核准，並以該 RFC 為基礎。

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 會設為 absent，且沒有表格主體。

實作

資料表作業

由於新電線格式會導致多項作業異動，因此有必要瞭解這些作業在新設計中的運作方式。

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.5 奈秒，因此可以推斷，記憶化作業每項作業可節省約 1.5 奈秒，整體約可節省 380 奈秒。不過，這次的時間是針對所有 256 個欄位都已設定的罕見情況。

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

測量結果假設欄位是預先設定，且與現有實作方式大致相同。不過，如果事先不知道要設定哪些欄位，建構時間預計會較長。不過，預期時間仍應在有效封包時間的 2 倍內。

情境中的成效結果

所測量的編碼器和解碼器是手動編寫，因此沒有現有編碼器的額外負荷。這些指標旨在指出經過高度最佳化的程式碼理想效能。如果將實際導入作業的額外負荷納入考量，前後的效能數據可能會更接近。

人體工學

主要的使用者可見異動是語言繫結中使用的特定建構函式實作項目異動。這些變更會因繫結而異。

回溯相容性

這項變更會破壞 ABI。視特定繫結中的建構工具實作方式而定，這也可能導致來源中斷。

安全性考量

沒有新的安全疑慮。表格會以不同形式呈現相同資訊。

隱私權注意事項

這不會影響隱私權。系統會保留與先前相同數量的資料，以表格線格式表示。

測試

GIDL 一致性測試套件會用於單元測試，而 FIDL 相容性測試套件則會用於整合測試。

說明文件

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

• 必須更新線路格式規格。
• 如果繫結 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。

既有技術和參考資料

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