一個很酷的 Rust 優化故事

語言: CN / TW / HK

關注「 Rust程式設計指北 」,一起學習 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 迭代器都已排序。

倒排索引將提供兩個迭代器,每個迭代器分別動態解碼與 helloworld 關聯的釋出列表。

Tantivy 的工作包括有效地組合這兩個迭代器以在它們的交集上建立迭代器。由於所有涉及的迭代器都可以方便地排序,tantivy 可以在有限的記憶體量和線性的時間內完成此操作。

在實踐中,tantivy 不依賴於 rust 的 Iterator trait,而是依賴於如下所示的 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
ret

cmove 是個神奇的指令。

現在讓我們看看它在標準庫二分查詢中的作用。

在 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
ret

LLVM 確實超越了自己。想象一下那裡發生了什麼:LLVM 設法

  • 展開 while 迴圈

  • 證明 start + len - 1 總是小於 128 並刪除所有邊界檢查
  • 在不那麼瑣碎的地方發出 CMOV。

  • 為第一個和最後一個迭代案例找到了一個非平凡的優化。

讓我們一起分解這個彙編程式碼:

在這個函式中,

  • rax
    start
    eax
    al
    rax
    eax
    al
    
  • 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 ,其終值只能是 064

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(⌖)
// 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%。

Query simd linear search binary search
AVERAGE 794 μs 713 μs
+bowel +obstruction 143 μs+2.9 %195 docs 139 μs195 docs
+vicenza +italy 184 μs+57.3 %856 docs 117 μs856 docs
+digital +scanning 173 μs+22.7 %664 docs 141 μs664 docs
+plus +size +clothing 685 μs+12.3 %266 docs 610 μs266 docs
+borders +books 987 μs+8.9 %2,173 docs 906 μs2,173 docs
+american +funds 1,541 μs+8.4 %14,165 docs 1,421 μs14,165 docs

由於 block-WAND 演算法,使用 top-K 收集器的 OR 查詢也受益於這種優化。

Query simd linear search binary search
AVERAGE 1,546 μs 1,424 μs
bowel obstruction 194 μs+7.8 % 180 μs
vicenza italy 326 μs+24.0 % 263 μs
digital scanning 384 μs+17.1 % 328 μs
plus size clothing 2,408 μs+9.6 % 2,198 μs
borders books 1,452 μs+8.6 % 1,337 μs
american funds 3,487 μs+19.4 % 2,920 μs

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

推薦閱讀

覺得不錯,點個贊吧

掃碼關注「 Rust程式設計指北