与“if/else”相比，“match”编译为次优汇编

Question

考虑以下二叉搜索树节点：

pub struct Node {
    key: i64,
    left_ptr: Option<Box<Node>>,
    right_ptr: Option<Box<Node>>,
}

以下是具有相同行为的“包含”方法的两种实现：

pub fn contains_match(root: &Option<Box<Node>>, key: i64) -> bool {
    let mut node_ptr = root;
    while let Some(node) = node_ptr {
        match node.key.cmp(&key) {
            Ordering::Equal => return true,
            Ordering::Less => node_ptr = &node.right_ptr,
            Ordering::Greater => node_ptr = &node.left_ptr,
        }
    }
    false
}

pub fn contains_if_else(root: &Option<Box<Node>>, key: i64) -> bool {
    let mut node_ptr = root;
    while let Some(node) = node_ptr {
        if node.key == key {
            return true;
        }
        if node.key < key {
            node_ptr = &node.right_ptr;
        } else {
            node_ptr = &node.left_ptr;
        }
    }
    false
}

但是，它们转换成的 ASM 代码有很大不同：

playground::contains_match:
    movq    (%rdi), %rax
    testq   %rax, %rax
    je  .LBB0_7
    movq    $-1, %rcx

.LBB0_2:
    xorl    %edx, %edx
    cmpq    %rsi, (%rax)
    setne   %dl
    cmovlq  %rcx, %rdx
    cmpq    $-1, %rdx
    je  .LBB0_5
    movb    $1, %al
    testq   %rdx, %rdx
    je  .LBB0_8
    movq    (%rdi), %rdi
    addq    $8, %rdi
    movq    (%rdi), %rax
    testq   %rax, %rax
    jne .LBB0_2
    jmp .LBB0_7

.LBB0_5:
    movq    (%rdi), %rdi
    addq    $16, %rdi
    movq    (%rdi), %rax
    testq   %rax, %rax
    jne .LBB0_2

.LBB0_7:
    xorl    %eax, %eax

.LBB0_8:
    retq

playground::contains_if_else:
    cmpq    $0, (%rdi)
    je  .LBB1_5

.LBB1_2:
    movq    (%rdi), %rdi
    movq    (%rdi), %rax
    cmpq    %rsi, %rax
    je  .LBB1_3
    leaq    16(%rdi), %rcx
    addq    $8, %rdi
    cmpq    %rsi, %rax
    cmovlq  %rcx, %rdi
    cmpq    $0, (%rdi)
    jne .LBB1_2

.LBB1_5:
    xorl    %eax, %eax
    retq

.LBB1_3:
    movb    $1, %al
    retq

操场。

根据我的基准测试，“match”版本比“if/else”版本慢 15% 到 25%：

100k_random_lookup_hits/contains_if_else                                                                            
                        time:   [14.096 ms 14.146 ms 14.212 ms]
100k_random_lookup_hits/contains_match                                                                            
                        time:   [17.938 ms 17.961 ms 17.991 ms]

100k_random_lookup_misses/contains_if_else                                                                            
                        time:   [20.451 ms 20.475 ms 20.502 ms]
100k_random_lookup_misses/contains_match                                                                            
                        time:   [23.900 ms 23.920 ms 23.943 ms]

基准。

“匹配”版本被编译成较慢的汇编是否有原因？

Answer 1

所以这将是 LLVM 的问题，而不是 Rust 特有的问题，因为似乎出于某种原因 switch 表达式没有得到正确的优化。

switch i8 %_6.0, label %bb4 [
    i8 -1, label %bb6
    i8 0, label %bb9
    i8 1, label %bb3
  ], !dbg !22

我在 Godbolt 上玩了很长时间。无法弄清楚为什么，但这似乎已经成为一个问题很长一段时间了。据我所知，在大多数情况下匹配仍然更好，但这种情况确实会发生，特别是对于像这样的少量分支。

https://llvm.org/pubs/2007-05-31-Switch-Lowering.html

https://llvm.org/devmtg/2015-10/slides/Wennborg-SwitchLowering.pdf