| RFC-0116：支援剖析器 FIDL 資料表的傳輸格式 | |
|---|---|
| 狀態 | 已遭拒 |
| 領域 |
|
| 說明 | 這個 RFC 導入了 FIDL 線格式的變更，用於最佳化資料表的剖析器分佈。 |
| 問題 | |
| 毛皮變化 | |
| 作者 | |
| 提交日期 (年-月-日) | 2021-06-16 |
| 審查日期 (年-月-日) | 2021-07-21 |
拒絕原因
此 RFC 提出資料表的稀疏 FIDL 線格式建議， 下列專家 / 缺點分析。
另請參閱：
稀疏資料表的優點
稀疏資料表的主要優點如下：
- 擴充
O(n)的效能，其中n是欄位集數量。 最高序數，而不是m。因此稀疏資料表 相較之下，如果欄位數量較高 與現有資料表結合請特別注意 以便擴充為O(n)的資料表效能，讓稀疏資料表更接近 使用者的期望 - 較精簡的電線格式。這樣可以減少透過線路複製的位元組數 減少的位元組數更精簡的電線格式實際優點 因為這種模式可能會改善效能並降低記憶體用量， 無法得知這個情況的發生時間
稀疏資料表的缺點
稀疏資料表的主要缺點如下：
- 通常較為複雜，特別是與現有稠密型相比 方法很簡單有些實作程序 值得學習和導入的工作
- 輸入時密度較弱，效能不佳
- 與密集資料表相比，可能會使用額外的儲存空間搭配密集輸入 實作
- 實際上，更有效率的表格建構工具實作方式不會像 O(n)，其中 n 是欄位組合數量。這樣會使部分金鑰 好處
稀疏資料表的不明資訊
設計提案 + 建構工具
這個 RFC 中提議的設計 (以及其他一些類似設計) 需要 建構工具，轉換為有線格式版面配置中的版面配置欄位值。 這取決於選取的特定建構工具演算法 所選指標的依據為預期輸入的成效
這時應選擇哪種建構工具實作？
建構工具的資源調度
擴充為 O(n) 的建構工具，其中 n 是欄位組合數量通常會是
在稀疏輸入以外的所有輸入速度過慢這包括執行
插入排序或使用中介資料結構，例如最小堆積和
轉換為排序清單
擴充為 O(m) 的建構工具，對於現有密集輸入來說，速度通常較快。
例如以密集版面配置建構資料表的建構工具。
然後轉換成電線的稀疏版面配置
資料表項目分佈情形
取決於預期輸入的分佈情形、建構工具和稀疏資料表 電線格式設計可能會有極大差異。
部分因素：
- 項目是否密集？
- 最高序數是多少？
- 有幾個項目散落？
- 這些項目是否位於單一區域中？
目前沒有太多證據能指出目前使用資料表會因稀疏型而受益 表格。稀疏資料表工作是以未來的假設為基礎 資料表用量稀疏程度較不高，甚至存在 稀疏的線格式會觸發更稀疏的使用方式。
專業認證：編譯時間、計數等
用來設計資料表建構工具的替代方案。 輸入內容分佈情形，是將建構工具用於特定輸入。例如：
- 專門在編譯期間處理已知欄位，並直接填入 無需處理執行階段建構成本
- 根據欄位數變更建築物演算法。
- 讓使用者明確決定要使用的建構工具。
缺點就是 API 變得更複雜，在某些情況下 詳細建立該建構工具的詳細步驟 編譯時間建構工具)。
如果效能不是因素
基於效能需求，且起因於 標準化，這通常會導致效能不佳。僅適用於成效 這並非最佳做法 取代 YAML 檔案這簡單許多，也就是由 protobuf 採取的方法。
費用與延後遷移作業的好處
延後遷移的費用
日後遷移困難
有幾項因素可能會使 遷移：
- 可能必須無限期維護兩個版本， 或累積足夠的現有版本使用。
- 適用於短期遷移，所有用量仍可切換 不能將這些變更 變更也要同時遷移 (例如，需進行更多 GIDL 測試) 您必須在每個繫結中設定建立與版本支援)。
ABI 穩定性
我們努力盡快提高 ABI 的穩定性，特別是駕駛人 與 FIDL 相依的 SDK。延後變更桌線格式 否則可能會受到負面影響
延後遷移的好處
進一步瞭解用途和瓶頸
目前您應該不需要立即使用稀疏資料表。此外， 表格項目版面配置的分佈圖 垂直線段。因此 並瞭解有哪些瓶頸。
避免系統的複雜性
許多稀疏資料表的實作方式相當複雜，將此 變得複雜，我們會一直處理這個過程因為 我們可能會想將這類複雜性納入考量 猶豫不決
結語
根據上述因素，我建議您不要實作稀疏型實作 。高效率的導入作業十分複雜，而且優點 目前不清楚。但不會排除 但要是因素有所變動
摘要
此 RFC 導入了將表格最佳化的 FIDL 線格式變更 產生現在序數的稀疏器分佈情形
提振精神
目前，不設定資料表欄位需要很高的成本。 欄位並非保留，因為系統已保留或不存在。 這筆費用是表格目前使用的電匯格式配置，資料表為 大小等於最大序數組合的向量
請考慮出現單一序數的情況。向量則是 大等單一序數的值，如果序數較大 則是配置和處理向量的費用
這不符合使用者期望。採用相似的傳輸格式，例如 通訊協定緩衝區，設定欄位的成本與序數無關 值。
使用 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 若有， 或是充分激勵使用者的用途限制的存在也會 與使用者進行對話，瞭解高用量方面的用途，並協助觸及 以便更加瞭解自己的需求
具體細節：
- 信封陣列「必須」只包含與 輸入欄位的值
- 如果最高序數 (k 信封的序數) 為 n，則
位元遮罩陣列 m 的長度必須為
floor((n+63)/64)。回想一下，n 這裡使用的索引從 1 開始也就是說，通常 1-64 m 的值為 1，而 65 到 128 m 為 2，以此類推。如果 n 為 0，則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 個項目總計會 為所有項目建立索引，這與編碼時間節省類似。請注意， 就能測量存取所有欄位的時間如果只有部分欄位 時間越少
因為查詢含有 256 個項目的索引平均耗時超過 1.5 秒 查詢含有 64 個項目的索引時，可以推論其中輸入的 也就是每台運算約 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 中提供兩種記錄類型：sparse 資料表和稠密型資料表如果不這麼做，主要的動機是 會造成使用者不便選擇這兩種類型 這並不是件簡單的工作因此，有些偏好保留 FIDL 而且只有一個類型
但值得注意的是，一旦導入新型別，就不會 不必從現有類型遷移
其他相關可能線格式變更
信封中的內嵌欄位
即將到來的 RFC 預計會提議變更信封，將指標指向 直接保留信封裡的基元，而不是 指標。 如果核准，系統可能會同時導入變更和變更項目 的提議。這個 RFC 中也不會提到 本身的複雜性和邏輯變動
既有藝術品和參考資料
通訊協定緩衝區的表示法用於比較。 請參閱「通訊協定緩衝區訊息表示法」專區。