一個很酷的 Rust 優化故事
大家好，我是螃蟹哥。
這是一篇關於 Rust 優化的文章，文章有點長，很硬核，但讀完，相信會有收穫。
在 Quickwit，我們正在爲大數據構建最具成本效益的搜索引擎。我們的整個搜索引擎 [1] 是用 rust 開發的，搜索的核心是由一個名爲 tantivy[2] 的庫提供的。
人們經常問我爲什麼 tantivy[3] 在基準測試中的 [4] 表現優於 Lucene[5]。這是一個複雜的問題。許多人認爲其中之一是 rust 比 Java 更快。但真相要複雜得多。
Rust 的真正好處是它爲程序員提供了更多的特性，供你玩耍。相比之下，JVM 是工程的寶藏，但優化是一種令人沮喪的體驗。雖然 JIT 做了一項出色的一刀切的工作，但它使程序員很難理解和控制生成的代碼。
在這篇博文中，我們將介紹一段特定的性能關鍵代碼，這些代碼多年來經歷了一些引人入勝的變化。
這段代碼是我最喜歡的展示 rustc/LLVM 功能的片段之一。
今天我將成爲你的兔子嚮導。請跟我進我的兔子洞。
##01 問題設置
tantivy 的基本原理在於接受用戶查詢並返回一個迭代器，遍歷與該查詢匹配的文檔 ID（無符號 32 位整數）。
你可能知道，整個過程依賴於倒排索引 [6]。讓我們考慮一個用戶搜索hello world默認情況下，tantivy 會將其解釋爲布爾查詢hello AND world。倒排索引方便地爲每個術語存儲包含該術語的文檔 ID 列表。我們稱之爲 posting list（發佈列表）。發佈列表以及 tantivy 生成的所有文檔 ID 迭代器都已排序。
倒排索引將提供兩個迭代器，每個迭代器分別動態解碼與 hello 和 world 關聯的發佈列表。
Tantivy 的工作包括有效地組合這兩個迭代器以在它們的交集上創建迭代器。由於所有涉及的迭代器都可以方便地排序，tantivy 可以在有限的內存量和線性的時間內完成此操作。
在實踐中，tantivy 不依賴於 rust 的Iteratortrait，而是依賴於如下所示的 trait DocSet[7]：
/// Represents an iterable set of sorted doc ids.
pub trait DocSet: Send {
/// Goes to the next element.
///
/// The DocId of the next element is returned.
/// In other words we should always have :
/// ```ignore
/// let doc = docset.advance();
/// assert_eq!(doc, docset.doc());
/// ```
///
/// If we reached the end of the DocSet, TERMINATED
/// should be returned.
///
/// Calling `.advance()` on a terminated DocSet
/// should be supported, and TERMINATED should
/// be returned.
fn advance(&mut self) -> DocId;
/// Returns the current document
/// Right after creating a new DocSet, the docset
/// points to the first document.
///
/// If the DocSet is empty, .doc() should return
///`TERMINATED`.
fn doc(&self) -> DocId;
/// Advances the DocSet forward until reaching the
/// target, or going to the lowest DocId greater than
/// the target.
///
/// If the `DocSet` is already at a `doc == target`,
/// then it is not advanced, and `self.doc()` is
/// simply returned.
///
/// Calling seek with a target lower than the current
/// `document` is illegal and may panic.
///
/// If the end of the DocSet is reached, TERMINATED
/// is returned.
///
/// Calling `.seek(target)` on a terminated DocSet is
/// legal. Implementation of DocSet should support it.
///
/// Calling `seek(TERMINATED)` is also legal and is
/// the normal way to consume a DocSet.
fn seek(&mut self, target: DocId) -> DocId {
// This is just a default implementation
// that `DocSet` implementation should override.
let mut doc = self.doc();
debug_assert!(doc <= target);
while doc < target {
doc = self.advance();
}
doc
}
}這裏的 seek 操作大大簡化了我們 DocSet 交集的實現。
impl<Lhs, Rhs> DocSet for IntersectionDocSet<Lhs, Rhs>
where
Lhs: DocSet,
Rhs: DocSet {
fn advance(&mut self) -> DocId {
let mut candidate = self.left.advance();
loop {
let right_doc = self.right.seek(candidate);
candidate = self.left.seek(right_doc);
if candidate == right_doc {
return candidate;
}
}
}
/* ... */
}很明顯，使得 seek(...) 儘可能快地獲得最佳交集性能至關重要。
事實上，profiling 告訴我們調用 seek(...) 運行交集查詢時佔 73.6% 的時間。
Intersection profiler
如果交集中的兩個詞具有非常不同的頻率（例如， The Mandalorian），則查找可能一次跳過數百萬個文檔。這一事實暗示了一個重要的優化機會。我們能否無痛地掃描這數百萬份文件的情況下找到我們的目標？
Tantivy 的發佈列表被壓縮成 128 個文檔塊。我們通過內存映射訪問所有這些數據。在搜索時，我們使用非常有效的 SIMD 位打包方案動態解壓縮這些塊。
爲了避免在不需要時訪問和解壓縮這些塊，tantivy 單獨保留每個塊的最後一個 doc id 的列表。我們稱這個列表爲 skip 列表。
在 seek 期間，tantivy 首先使用此列表來識別可能包含目標文檔的單個塊。它只是最後一個文檔超過目標的第一個塊。然後 Tantivy 對其進行解壓縮並在解壓縮的塊中搜索目標。
在這最後一步中，我們必須將目標文檔搜索到一個由 128 個排序的 DocId 組成的塊中。我們知道這個塊中的最後一個文檔大於或等於我們的目標，我們想要找到大於或等於我們的目標的第一個元素的索引。
我們的問題歸結爲實現以下功能，即今天要優化的功能。
/// Returns the position of the first document that is
/// greater or equal to the target in the sorted array
/// `arr`.
fn search_first_greater_or_equal(
arr: &[u32],
needle: u32) -> usize;這就是我今天要討論的這個功能的實現。
01 第一個實現：標準二分查找
當術語的頻率有些平衡並且傾向於出現在同一文檔中時，在同一塊中 seek 和 find 多個文檔的情況並不少見。
有了這個設置，每次都從塊的開頭繼續尋找（seeking）是很愚蠢的。如果在第 62 位找到最後一個文檔，我們可以將搜索限制爲&block[63..128]。
對於頻率較低的，候選者很可能會在我們最後一個位置後不久出現。這種情況相當頻繁。一個項是小步，而另一個是大步。
出於這個原因，該算法首先運行指數搜索以限制我們的搜索範圍。然後我們將對數組的剩餘部分執行簡單的二分搜索。
總體而言，該功能 [8] 如下所示：
/// Search the first index containing an element greater or equal to the needle.
///
/// # Assumption
///
/// The array is assumed non empty.
/// The target is assumed greater or equal to the first element.
/// The target is assumed smaller or equal to the last element.
fn search_within_block(arr: &[u32], needle: u32) -> usize {
let (start, end) =
exponential_search(needle, arr);
start + arr[start..end]
.binary_search(&needle)
.unwrap_or_else(|e| e),
}
fn exponential_search(arr: &[u32], needle: u32) -> Range<usize> {
let end = arr.len();
let mut begin = 0;
for &pivot in &[1, 3, 7, 15, 31, 63] {
if pivot >= end {
break;
}
if arr[pivot] > needle {
return begin..pivot;
}
begin = pivot;
}
begin..end
}02 Rust 1.25 中的性能迴歸
請注意，儘管聽起來很普通，但 tantivy 只是依賴於 rust 標準庫 binary_search 實現。
那時，它剛剛被 Alkis Evlogimenos 改進 [9] 爲無分支。這個新實現非常適合我的用例，在這個用例中，我的針（needle）的分佈本質上是均勻的。
如果您不熟悉無分支算法背後的思想，這裏有一個簡而言之的關鍵思想。現代 CPU 在長管道中處理指令。爲了避免花費愚蠢的時間等待分支條件的結果，CPU 對分支的結果下注，並圍繞這個假設組織他們的工作。
分支預測器負責根據歷史數據預測這個結果。當一個分支被錯誤預測時，CPU 需要處理它的所有工作並重新組織它的管道。這是我們想避免的非常昂貴的事件。
雖然現代分支預測器因其預測準確性而受到稱讚，但在我們的陣列中的任何地方搜索一根針是 50/50 的賭注。
出於這個原因，扭曲我們的算法以刪除其所有分支是有用的。最常用的工具之一是用條件移動替換我們的分支。條件移動是相當於此代碼段的 CPU 指令。
fn conditional_mov(
cond: bool,
val_if_true: usize,
val_if_false: usize) -> usize {
if cond {
val_if_true
} else {
val_if_false
}
}如果你在 Godbolt[10] 上檢查這個函數，它會生成以下代碼：
mov rax, rsi
test edi, edi
cmove rax, rdx
retcmove 是個神奇的指令。
現在讓我們看看它在標準庫二分查找中的作用。
在 rustc 1.24 中，以下代碼段：
pub fn binary_search(sorted_arr: &[u32], needle: u32) -> usize {
sorted_arr
.binary_search(&needle)
.unwrap_or_else(|e| e)
}編譯成：
push rbp
mov rbp, rsp
xor eax, eax
test rsi, rsi
je .LBB0_5
cmp rsi, 1
je .LBB0_4
xor r8d, r8d
.LBB0_3:
mov rcx, rsi
shr rcx
lea rax, [rcx + r8]
cmp dword ptr [rdi + 4*rax], edx
cmova rax, r8
sub rsi, rcx
mov r8, rax
cmp rsi, 1
ja .LBB0_3
.LBB0_4:
cmp dword ptr [rdi + 4*rax], edx
adc rax, 0
.LBB0_5:
pop rbp
ret循環體發生在 .LBB0_3 並且它包含的唯一分支是在這裏檢查我們是否已經完成了足夠的迭代。這個唯一的分支是可以預測的，所以一切都很好。
不幸的是，rustc 1.55 生成的代碼非常不同。
xor eax, eax
test rsi, rsi
je .LBB0_8
mov rcx, rsi
jmp .LBB0_2
.LBB0_5:
inc rsi
mov rax, rsi
mov rsi, rcx
.LBB0_6:
sub rsi, rax
jbe .LBB0_8
.LBB0_2:
shr rsi
add rsi, rax
cmp dword ptr [rdi + 4*rsi], edx
jb .LBB0_5
je .LBB0_7
mov rcx, rsi
jmp .LBB0_6
.LBB0_7:
mov rax, rsi
.LBB0_8:
ret從 rustc 1.25 開始，二分查找不再是無分支的！
我觀察了 tantivy 基準的迴歸並在此處報告了該 issue #57935[11]，但它與 #53823[12] 重複。直到今天，這個問題仍然沒有解決。
03 CMOV 或者 not CMOV
這是一個簡短的旁白。我不知道爲什麼 LLVM 在這種情況下不發出 CMOV 指令。
發出 CMOV 是否是一個好主意是一個非常棘手的難題，通常取決於提供給程序的數據。
即使對於二分查找，如果已知指針幾乎總是在 0 位置，則分支實現在任何 CPU 上都將優於無分支實現。
從歷史上看，CMOV 名聲不佳，部分原因是 Pentium 4 在這條指令上的表現非常糟糕。讓我們看看 Linus Torvald[13] 在 2007 年對 CMOV 的評價：
CMOV（以及更一般地說，任何 “謂詞指令”）在嚴重無序的 CPU 上通常是一個壞主意。它並不總是很糟糕，但實際上它很少很好，而且（像往常一樣）在 P4 上它可能真的很糟糕。
在 P4 上，我認爲 cmov 基本上需要 10 個週期。
但是即使忽略通常的 P4 “我討厭不完全正常的事情”，cmov 實際上也不是一個好主意。你可以隨時替換它：
j<negated condition> forward mov ..., %reg forward:並且假設分支完全是可預測的（並且所有分支的 95+% 是可預測的），對於 CPU 來說，分支實際上會好很多。
爲什麼？因爲分支是可以預測的，當它們被預測時，它們基本上就會消失。它們也在許多層面消失了。不僅僅是分支本身，而且就代碼的關鍵路徑而言，分支的_條件_消失了：CPU 仍然需要計算並檢查它，但從性能角度來看它 “不再存在” ，因爲它不持有任何東西了。
Pentium 4 在 CMOV 上確實很爛，但現代編譯器通常不再針對它進行優化。
事實上，現在 LLVM 往往更喜歡 CMOV 而不是分支。
例如，這是一個令人驚訝的編譯結果：
pub fn work_twice_or_take_a_bet(cond: bool, val: usize) -> usize {
if cond {
val * 73 + 9
} else {
val * 17 + 3
}
}編譯成：
lea rax, [rsi + 8*rsi]
lea rcx, [rsi + 8*rax]
add rcx, 9
mov rax, rsi
shl rax, 4
add rax, rsi
add rax, 3
test edi, edi
cmovne rax, rcx
ret在這裏，LLVM 更喜歡計算兩個分支和 CMOV 結果，而不是發出一個分支！
當然，這只是因爲 LLVM 觀察到兩個分支內的工作量足夠輕，可以證明這種權衡是合理的…… 但這仍然很令人驚訝，不是嗎？
線性 SIMD 搜索
這種性能迴歸非常煩人，而且 rustc 編譯器似乎不太可能很快修復它。
我決定用一個始終快速執行並且對編譯器的變遷不那麼敏感的實現來交換我的指數 + 二進制搜索。
鑑於數組很小，我決定實現一個簡單的 SIMD 無分支線性搜索。
使線性搜索無分支的技巧是將搜索問題重新表述爲計算有多少元素小於針的問題。
這個想法轉化爲以下標量代碼：
fn branchless_linear_search(arr: &[u32; 128], needle: u32) -> usize {
arr
.iter()
.cloned()
.map(|el| {
if el < needle { 1 } else { 0 }
})
.sum()
}不幸的是，SSE 的實現又長又臭：
use std::arch::x86_64::__m128i as DataType;
use std::arch::x86_64::_mm_add_epi32 as op_add;
use std::arch::x86_64::_mm_cmplt_epi32 as op_lt;
use std::arch::x86_64::_mm_load_si128 as op_load;
use std::arch::x86_64::_mm_set1_epi32 as set1;
use std::arch::x86_64::_mm_setzero_si128 as set0;
use std::arch::x86_64::_mm_sub_epi32 as op_sub;
use std::arch::x86_64::{_mm_cvtsi128_si32, _mm_shuffle_epi32};
const MASK1: i32 = 78;
const MASK2: i32 = 177;
/// Performs an exhaustive linear search over the
///
/// There is no early exit here. We simply count the
/// number of elements that are `< needle`.
unsafe fn linear_search_sse2_128(
arr: &[u32; 128],
needle: u32) -> usize {
let ptr = arr as *const DataType;
let vkey = set1(needle as i32);
let mut cnt = set0();
// We work over 4 `__m128i` at a time.
// A single `__m128i` actual contains 4 `u32`.
for i in 0..8 {
let cmp1 = op_lt(op_load(ptr.offset(i * 4)), vkey);
let cmp2 = op_lt(op_load(ptr.offset(i * 4 + 1)), vkey);
let cmp3 = op_lt(op_load(ptr.offset(i * 4 + 2)), vkey);
let cmp4 = op_lt(op_load(ptr.offset(i * 4 + 3)), vkey);
let sum = op_add(op_add(cmp1, cmp2), op_add(cmp3, cmp4));
cnt = op_sub(cnt, sum);
}
cnt = op_add(cnt, _mm_shuffle_epi32(cnt, MASK1));
cnt = op_add(cnt, _mm_shuffle_epi32(cnt, MASK2));
_mm_cvtsi128_si32(cnt) as usize
}該實現爲我帶來了在 1.25 之前享受的性能。
04 二分查找的反擊
在閱讀了 dirtyhandscoding 的博客文章後 [14]，我決定再試一次二分查找。
這裏的要點是簡化代碼庫。不僅 SIMD 的使用難以閱讀和維護，而且 SIMD 指令集也是特定於體系結構的，這意味着我還必須維護算法的標量版本。我獲得的性能提升只是蛋糕上的一顆櫻桃。
這次我會一直搜索整個 block。該塊的長度爲 128 個元素，這意味着我們應該能夠在 7 次比較中確定結果。這樣，我們就可以不惜一切代價進行這 7 個比較。
當然，我們也希望我們生成的代碼儘可能高效且完全無分支。
這是我能想出的最慣用的代碼來實現我們的目標。
pub fn branchless_binary_search(arr: &[u32; 128], needle: u32) -> usize {
let mut start = 0;
let mut len = arr.len();
while len > 1 {
len /= 2;
if arr[start + len - 1] < needle {
start += len;
}
}
start
}我沒想到用這麼簡單的一段代碼就能達到我想要的效果。
這裏的關鍵部分是我們沒有傳遞切片 ( &[u32]) 作爲參數，而是傳遞了一個數組 ( &[u32; 128])。這樣，LLVM 在編譯時就知道我們的塊正好有 128 個文檔 ID。
生成的程序彙編代碼如下所示：
; Idiom to set eax to 0.
xor eax, eax
; Iteration 1 (len=64)
cmp dword ptr [rdi + 252], esi
setb al
shl rax, 6
; Iteration 2 (len=32)
lea rcx, [rax + 32]
cmp dword ptr [rdi + 4*rax + 124], esi
cmovae rcx, rax
; Iteration 3 (len=16)
lea rax, [rcx + 16]
cmp dword ptr [rdi + 4*rcx + 60], esi
cmovae rax, rcx
; Iteration 4 (len=8)
lea rcx, [rax + 8]
cmp dword ptr [rdi + 4*rax + 28], esi
cmovae rcx, rax
; Iteration 5 (len=4)
lea rdx, [rcx + 4]
cmp dword ptr [rdi + 4*rcx + 12], esi
cmovae rdx, rcx
; Iteration 6 (len=2)
lea rax, [rdx + 2]
cmp dword ptr [rdi + 4*rdx + 4], esi
cmovae rax, rdx
; Iteration 7
cmp dword ptr [rdi + 4*rax], esi
adc rax, 0
retLLVM 確實超越了自己。想象一下那裏發生了什麼：LLVM 設法
-
展開 while 循環
-
證明
start + len - 1總是小於 128 並刪除所有邊界檢查 -
在不那麼瑣碎的地方發出 CMOV。
-
爲第一個和最後一個迭代案例找到了一個非平凡的優化。
讓我們一起分解這個彙編代碼：
在這個函數中，
-
rax: 是我們的返回值，start在 Rust 代碼中。使所有這些有點混亂的一件事是我們還通過eax和al寫入和讀取它。它佔 64 位。雖然rax是一個 64 位寄存器，eax和al分別是指其最低 32 位和它的最低 8 位。 -
esi是我們的針參數。 -
rdi是我們數組中第一個元素的地址。
讓我們一步一步地完成彙編。
EAX 歸零
xor eax, eax這可能看起來很奇怪，但這只是設置 eax 爲 0 的最常見方式。爲什麼？機器碼只需要 2 個字節。此外，現代 CPU 實際上不會在這裏計算 XOR。它們只是將這條指令視爲 “wink”，告訴它們我們想要一個值爲 0 的寄存器。
第一次迭代
// Iteration 1 (len=64)
cmp dword ptr [rdi + 252], esi
setb al
shl rax, 6第一次迭代有點奇怪。顯然，LLVM 發現了一些特定於第一次迭代的優化。但是第一次迭代有什麼特別之處呢？此時，start 等於 0，其終值只能是 0 或 64。
rdi + 252 只是訪問數組第 63 個元素的指針運算。( 252 = 63 * size_of::<u32>())
如果之前比較較低，setb al 指令設置 al 爲 1。
shl 是位移指令。
Rust 代碼如下所示：
let cmp = arr[63].cmp(&needle);
start = //< well actually we only set the lowest 8 bits.
if cmp == Ordering::Lower {
1
} else {
0
}
start <<= 6;因爲64 = 2 ^ 6，我們確實以預期的 start = 64 或 start = 0 結束。。。
迭代 2-6
迭代 2-6 是類似的，不包含任何詭祕。例如，讓我們看一下迭代 2：
lea rcx, [rax + 32]
cmp dword ptr [rdi + 4*rax + 124], esi
cmovae rcx, rax如果比較將我們帶到右半部分，我們使用 rcx 存儲我們想要的 start 值。因此等效的 Rust 代碼是：
// lea rcx, [rax + 32]
let start_if_right_of_pivot: usize = start + 32;
// cmp dword ptr [rdi + 4*rdx + 124], esi
let pivot = arr[start + 31];
let pivot_needle_cmp: std::cmp::Ordering = pivot.cmp(target);
// cmovb rax, rcx
let start =
if pivot_needle_cmp_order == Ordering::Lower {
start_if_right_of_pivot
} else {
start
};哦，等一下！我只是撒了謊。 我們擁有的代碼不是 cmovb rax, rcx，它是 cmovae rcx, rax。
出於某種原因，LLVM 最終輪換了寄存器的角色。注意 rax 和的角色 rcx 是如何一次又一次地交換的。它在性能方面沒有任何好處，所以我們忽略它。
最後一次迭代
最後一次迭代似乎也很特別。這裏有趣的是 shift 值只是1，所以我們可以直接添加我們比較的輸出到 start。
等效的 rust 代碼如下所示：
// cmp dword ptr [rdi + 4*rax], esi
let cmp = arr[start].cmp(&target)
// adc rax, 0
if cmp == std::cmp::Lower {
start += 1;
}05 基準測試
CPU 模擬器和微基準測試
CPU 模擬器估計此代碼需要 9.55 個週期 [15]。很優秀！請記住，我們正在搜索 128 個整數塊中的值。
相比之下，我們的 SIMD 線性搜索實現估計爲 26.29 個週期。
我能想到的最好的 C++ 實現是在 Clang 上超過 12 個週期，在 GCC 上超過 40 個週期。
讓我們看看模擬器告訴我們的內容是否真的轉化爲現實世界。
Tantivy 有幾個微基準測試來測量在發佈列表上調用 seek 的速度。這些基準測試將大致對應於每次調用 Advance 時跳過的平均文檔數的倒數作爲參數。跳躍越短，值越高。
Before (無分支 SSE2 線性查找)
bench_skip_next_p01 58,585 ns/iter (+/- 796)
bench_skip_next_p1 160,872 ns/iter (+/- 5,164)
bench_skip_next_p10 615,229 ns/iter (+/- 25,108)
bench_skip_next_p90 1,120,509 ns/iter (+/- 22,271)After (無分支內聯二分查找)
bench_skip_next_p01 44,785 ns/iter (+/- 1,054)
bench_skip_next_p1 178,507 ns/iter (+/- 1,588)
bench_skip_next_p10 512,942 ns/iter (+/- 11,090)
bench_skip_next_p90 733,268 ns/iter (+/- 12,529)這一點也不差！在這個基準測試中，Seek 現在大約快 11%。
真實場景的基準測試
Tantivy 帶有一個搜索引擎基準測試 [16]，可以比較不同的搜索引擎實現。它嘗試將不同類型的現實世界查詢與不同的數據集進行比較。
以下是 AND 查詢的輸出示例。Tantivy 在交集查詢上平均快 10%。
由於 block-WAND 算法，使用 top-K 收集器的 OR 查詢也受益於這種優化。
06 Conclusion
所以 LLVM 是完美的，看彙編代碼是徒勞的？在這一點上，你們中的一些人可能認爲這裏的教訓是 LLVM 在編譯慣用代碼方面做得如此出色，以至於查看彙編、手動展開內容等只是浪費時間。
我被告知過無數次，但我不同意。
爲了得到這個版本的 rust 代碼，我不得不反覆琢磨並確切地知道我想要什麼。例如，這是我的第一個實現。
pub fn branchless_binary_search(arr: &[u32; 128], target: u32) -> usize {
let mut range = 0..arr.len();
while range.len() > 1 {
let mid = range.start + range.len() / 2;
range = if arr[mid - 1] < target {
mid..range.end
} else {
range.start..mid
};
}
range.start
}它使用範圍而不是(start, len)獨立操作。LLVM 無法應用我們在此代碼中討論的優化的任何優化。
我會進一步優化。本博客中的實現實際上不是 tantivy 中提供的代碼版本。雖然 rustc 今天在編譯這個函數方面做得很好，但我不相信未來的rustc版本也會這樣做。
例如，一年前，Rustc 1.41 未能刪除邊界檢查。爲了獲得一致的編譯結果，tantivy 實際上調用了不安全的 get_unchecked。我有信心它是安全的嗎？我會在晚上睡覺嗎…… 我會的。rustc 1.55 生成的代碼提供了它安全的正式證明。
原文鏈接：https://quickwit.io/blog/search-a-sorted-block/
參考資料
[1] 整個搜索引擎: https://github.com/quickwit-inc/quickwit
[2] tantivy: https://github.com/quickwit-inc/tantivy
[3] tantivy: https://github.com/quickwit-inc/tantivy
[4] 基準測試中的: https://tantivy-search.github.io/bench/
[5] Lucene: https://lucene.apache.org/
[6] 倒排索引: https://evanxg852000.github.io/tutorial/rust/data/structure/2020/04/09/inverted-index-simple-yet-powerful-ds.html
[7] DocSet: https://github.com/quickwit-inc/tantivy/blob/main/src/docset.rs
[8] 該功能: https://github.com/tantivy-search/tantivy/blob/0.8.2/src/postings/segment_postings.rs#L144-L158
[9] 剛剛被 Alkis Evlogimenos 改進: https://github.com/rust-lang/rust/commit/2ca111b6b91c578c8a2b8e610471e582b6cf2c6b
[10] Godbolt: https://godbolt.org/
[11] #57935: https://github.com/rust-lang/rust/issues/57935
[12] #53823: https://github.com/rust-lang/rust/issues/53823
[13] Linus Torvald: https://yarchive.net/comp/linux/cmov.html
[14] dirtyhandscoding 的博客文章後: https://dirtyhandscoding.wordpress.com/2017/08/25/performance-comparison-linear-search-vs-binary-search/
[15] CPU 模擬器估計此代碼需要 9.55 個週期: https://bit.ly/3mZTWYZ
[16] 搜索引擎基準測試: https://github.com/tantivy-search/search-benchmark-game
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/UiOx8GFmP32fDNtpLSJ01Q