增加程序branch prediction成功率的技巧

painful_dog

在"Efficiently compiling efficient query plans for modern hardware"这篇文章里看到一个东西，感觉蛮有意思的一个小点。

Entry* iter=hashTable[hash];
while (iter) {
... // inspect the entry
iter=iter->next;
}

对于上面这段代码的while(iter)，如果这个条件判断一般来讲第一次会成功，第二次会失败，那么对于branch prediction的成功率其实是很有害的。所以，我们可以改写成下面这样

Entry* iter=hashTable[hash];
if (iter) do {
... // inspect the entry
iter=iter->next;
} while (iter);

Miigon

又到了喜闻乐见的求知验证环节hhhhhh

环境：
macOS10.15.7
clang12.0.0
target: x86_64-apple-darwin19.6.0

testopt.cpp

#include <unordered_map>
#include <stdio.h>

struct Entry {
    const char *data;
    Entry *next;
};

int main() {
    std::unordered_map<int, Entry*> hashTable;
    hashTable.insert(std::make_pair(111,new Entry{"helloworld", nullptr}));
    int hash; scanf("%d", &hash);
    Entry* iter=hashTable[hash];
    while(iter) {
        printf("%s\n", iter->data);
        iter=iter->next;
    }
    // delete...
}

testopt2.cpp

#include <unordered_map>
#include <stdio.h>

struct Entry {
    const char *data;
    Entry *next;
};

int main() {
    std::unordered_map<int, Entry*> hashTable;
    hashTable.insert(std::make_pair(111,new Entry{"helloworld", nullptr}));
    int hash; scanf("%d", &hash);
    Entry* iter=hashTable[hash];
    if(iter) do {
        printf("%s\n", iter->data);
        iter=iter->next;
    } while(iter);
    // delete...
}

g++ -std=c++17 -O2 testopt.cpp -S -o testoptO2.asm

Ltmp9:
## %bb.17:
	movq	(%rax), %rbx
	testq	%rbx, %rbx
	je	LBB0_20
	.p2align	4, 0x90
LBB0_18:                                ## =>This Inner Loop Header: Depth=1
	movq	(%rbx), %rdi
	callq	_puts
	movq	8(%rbx), %rbx
	testq	%rbx, %rbx
	jne	LBB0_18

g++ -std=c++17 -O2 testopt2.cpp -S -o testopt2O2.asm

Ltmp9:
## %bb.17:
	movq	(%rax), %rbx
	testq	%rbx, %rbx
	je	LBB0_20
	.p2align	4, 0x90
LBB0_18:                                ## =>This Inner Loop Header: Depth=1
	movq	(%rbx), %rdi
	callq	_puts
	movq	8(%rbx), %rbx
	testq	%rbx, %rbx
	jne	LBB0_18

都不加O2的话，带if的版本会在je后面多出来一行jmp LBB0_7，至于这个是否有利于性能，我没有做测试。

LBB0_5:
	movq	-168(%rbp), %rax        ## 8-byte Reload
	movq	(%rax), %rcx
	movq	%rcx, -128(%rbp)
	cmpq	$0, -128(%rbp)
	je	LBB0_12
## %bb.6:
	jmp	LBB0_7
LBB0_7:                                 ## =>This Inner Loop Header: Depth=1
	movq	-128(%rbp), %rax
	movq	(%rax), %rsi