大佬们为什么编译器不能把这段代码的分支提升到循环外

re0312 发表于 2024-08-23 08:50

理论上循环内的分支都是没有必要的,而且应该也不是black_box阻止优化,我进行简单的求和加减也是一样的结果,看起来是hashmap的问题,但是我没看出来hashbrown的实现中哪块阻止了优化.

use std::hint::black_box;

use hashbrown::HashMap;

pub fn main() {
    let mut map: HashMap<u32, u32> = hashbrown::HashMap::default();
    map.insert(0, 0);
    
    for i in 0..10000 {
        if let Some(_) = map.get(&0) {
            continue;
        } else {
            black_box(i);
        }
    }
}

godbolt汇编 https://rust.godbolt.org/z/vr3WGsfhP

评论区

写评论

wangbyby 2024-08-24 23:08

还有cpp的std::unordered_map在gcc下似乎也没有优化掉循环内find。

https://rust.godbolt.org/z/3s3jvaEbj

wangbyby 2024-08-24 22:28

我在本地查看了下llvm-ir。 rust版本的hashbrown::get函数是一个向量化查询，内联到main之后还是循环内进行条件判断。猜测是get函数过于复杂导致没优化

TinusgragLin 2024-08-23 22:46

循环里面计算好像压根没有执行,在前面已经直接走编译器计算好的值的分支了

这不一定，可以循以下路径走到 .LBB0_19：

main -> .LBB0_9 -> .LBB0_13 -> .LBB0_17 -> .LBB0_19

（此时可以再沿 -> .LBB0_20 -> .LBB0_23 -> .LBB0_34 走到 .LBB0_34）

指令在前面也不一定先被执行，你可以本地用 gdb 单步一下。

作者 re0312 2024-08-23 21:29

循环里面计算好像压根没有执行,在前面已经直接走编译器计算好的值的分支了

        setne   cl
        xor     al, 1
        test    cl, al
        jne     .LBB0_43
        test    rbx, rbx
        mov     eax, 3691155   // 这个已经是直接在编译期算出的值了  299 * 12345
        mov     esi, 2456655   // 另一个分支的值  199*12345
        cmove   esi, eax   // 
        jmp     .LBB0_35  // 跳转到最后cout输出了

--  
👇  
TinusgragLin: > 感觉那个分支还是在循环内，你说的优化是指其他方面吗，还是我有什么地方搞错了？

TinusgragLin 2024-08-23 21:01

clang就完全可以优化了

我（把循环次数换为 12345 以容易辨认）看了一下，

.LBB0_34:
        add     esi, ebx
        inc     edx
        cmp     edx, 12345
        je      .LBB0_35  ; 循环结束
.LBB0_19:                 ; 下一次循环
        prefetcht2      byte ptr [rdi] ; 不懂
        mov     r10, rax
        xor     r11d, r11d
        jmp     .LBB0_20  ; 跳到 ...

; 这里！
.LBB0_20:
        and     r10, rcx
        movdqu  xmm2, xmmword ptr [rdi + r10]
        movdqa  xmm3, xmm0
        pcmpeqb xmm3, xmm2
        pmovmskb        ebx, xmm3
        test    ebx, ebx
        je      .LBB0_23
.LBB0_21:
        rep       bsf r14d, ebx
        add     r14, r10
        and     r14, rcx
        cmp     dword ptr [r8 + 8*r14], 8208820
        je      .LBB0_31
        lea     ebp, [rbx - 1]
        and     bp, bx
        mov     ebx, ebp
        jne     .LBB0_21
.LBB0_23:
        pcmpeqb xmm2, xmm1
        pmovmskb        ebp, xmm2
        mov     ebx, 299
        test    ebp, ebp
        jne     .LBB0_34
        add     r10, r11
        add     r10, 16
        add     r11, 16
        cmp     r11, rcx
        jbe     .LBB0_20
        jmp     .LBB0_25
.LBB0_31:
        add     r14, rdi
        cmp     r14, r9
        je      .LBB0_45
        cmp     byte ptr [r14], 0
        js      .LBB0_44
        mov     ebx, 199
        cmp     r14, r9
        je      .LBB0_45

感觉那个分支还是在循环内，你说的优化是指其他方面吗，还是我有什么地方搞错了？

作者 re0312 2024-08-23 18:09

这感觉不一定是llvm的问题,大佬下面两个cpp的例子我感觉是llvm和gcc自动内联的阈值问题,比如下面这个例子,clang在循环内还有函数调用(所以不被视为纯函数被优化是可以理解的),我调高llvm自动内联的参数,clang就完全可以优化了,而rust版本的hashbrown已经是全内联了,但是编译器仍然毫无作为.

clang iline-more: https://rust.godbolt.org/z/jsxnxG3z4

--
👇
TinusgragLin: > 我试了下cpp标准库的哈希表是完全可以优化这种情况的

我简单测试了一下，有了一些发现：

鉴于 hashbrown 借鉴的是 SwissTable 的实现，公平起见，我用 absl::flat_hash_map 试了一下：

#include <iostream>
#include <absl/container/flat_hash_map.h>
//#include <unordered_map>
int main() {
    // std::unordered_map<int, int> map;
    absl::flat_hash_map<int, int> map;
    map.insert({8208820, 0});
    std::cout << "Let's go baby!" << std::endl;
    for (int i = 0; i < 10000; i++) {
        auto it = map.find(8208820);
        if (it != map.end()) {
            continue;
        } else {
            std::cout << "NYPD, freeze!" << std::endl;
        }
    }
    return 0;
}

用 x86-64-gcc 14.2 编译，见 Let's go baby!，不见 NPYD, freeze!。

用 x86-64-clang 18.1 编译，见 Let's go baby!，也见 NPYD, freeze!。

我感觉可能是 LLVM 的问题。

TinusgragLin 2024-08-23 13:32

我试了下cpp标准库的哈希表是完全可以优化这种情况的

我简单测试了一下，有了一些发现：

鉴于 hashbrown 借鉴的是 SwissTable 的实现，公平起见，我用 absl::flat_hash_map 试了一下：

#include <iostream>
#include <absl/container/flat_hash_map.h>
//#include <unordered_map>
int main() {
    // std::unordered_map<int, int> map;
    absl::flat_hash_map<int, int> map;
    map.insert({8208820, 0});
    std::cout << "Let's go baby!" << std::endl;
    for (int i = 0; i < 10000; i++) {
        auto it = map.find(8208820);
        if (it != map.end()) {
            continue;
        } else {
            std::cout << "NYPD, freeze!" << std::endl;
        }
    }
    return 0;
}

用 x86-64-gcc 14.2 编译，见 Let's go baby!，不见 NPYD, freeze!。

用 x86-64-clang 18.1 编译，见 Let's go baby!，也见 NPYD, freeze!。

我感觉可能是 LLVM 的问题。

asuper 2024-08-23 11:45

pub fn main() {
    let mut map: HashMap<u32, u32> = hashbrown::HashMap::default();
    map.insert(0, 0);

    if let None = map.get(&0) {
        for i in 0..10000 {
            black_box(i);
        }
    }
}

没有问题啊，你代码写错了吧

作者 re0312 2024-08-23 10:09

是的,我的好奇是hashbrown实现哪块阻止了优化,我看了一下理论上应该能被优化的,我试了下cpp标准库的哈希表是完全可以优化这种情况的

--
👇
Foreverhighness: 可能是 get 实现太复杂被视作了 black_box 吧。 https://rust.godbolt.org/z/sqnPPTEoc

Foreverhighness 2024-08-23 10:01

可能是 get 实现太复杂被视作了 black_box 吧。 https://rust.godbolt.org/z/sqnPPTEoc

1 共 10 条评论, 1 页