为什么 C 编译器优化 switch 和 if 不同

Question

我最近在做个人项目时遇到了一个奇怪的问题。

在一个非常紧凑的循环中，我有一个整数，其值介于 0 和 15 之间。我需要为值 0、1、8 和 9 获取 -1，为值 4、5、12 和 13 获取 1 .

我求助于 godbolt 检查了几个选项，令我惊讶的是编译器似乎无法像 if 链一样优化 switch 语句。

密码是：

const int lookup[16] = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};

int a(int num) {
    return lookup[num & 0xF];
}

int b(int num) {
    num &= 0xF;

    if (num == 0 || num == 1 || num == 8 || num == 9) 
        return -1;

    if (num == 4 || num == 5 || num == 12 || num == 13)
        return 1;

    return 0;
}

int c(int num) {
    num &= 0xF;
    switch (num) {
        case 0: case 1: case 8: case 9: 
            return -1;
        case 4: case 5: case 12: case 13:
            return 1;
        default:
            return 0;
    }
}

我原以为 b 和 c 会产生相同的结果，并且我希望我可以阅读 bit-hacks 以自己提出一个有效的实现，因为我的解决方案（switch 语句 - 另一种形式） ) 相当慢。

奇怪的是，b 编译为 bit-hacks 而 c 要么几乎没有优化，要么根据目标硬件减少为 a 的不同情况。

谁能解释为什么会出现这种差异？ 'correct' 优化此查询的方法是什么？

编辑：

澄清

我希望 switch 解决方案是最快的，或者类似的"clean" 解决方案。然而，当在我的机器上进行优化编译时，if 解决方案明显更快。

我写了一个快速程序来演示，TIO 与我在本地找到的结果相同：Try it online!

使用 static inline 查找 table 会加快一点：Try it online!

Answer 1

C 编译器对 switch 有特殊情况，因为它们希望程序员理解 switch 的习语并利用它。

代码如下：

if (num == 0 || num == 1 || num == 8 || num == 9) 
    return -1;

if (num == 4 || num == 5 || num == 12 || num == 13)
    return 1;

不会通过合格的 C 编码员的审查；三四个审稿人会同时惊呼"this should be a switch!"

C 编译器分析 if 语句的结构以转换为跳转 table 是不值得的。其条件必须恰到好处，一堆 if 语句中可能的变化量是天文数字。分析既复杂又可能会得出负面结果（如："no, we can't convert these ifs to a switch"）。

Answer 2

以下代码将在约 3 个时钟周期、约 4 个有用的指令和约 13 个字节的高度 inline 可用的 x86 机器代码中计算您的无分支查找 LUT-free。

这取决于 2 的补码整数表示。

但是，您必须确保 u32 和 s32 typedef 确实指向 32 位无符号和有符号整数类型。 stdint.h 类型 uint32_t 和 int32_t 会比较合适，但我不知道 header 是否适合您。

const int lookup[16] = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};

int a(int num) {
    return lookup[num & 0xF];
}


int d(int num){
    typedef unsigned int u32;
    typedef signed   int s32;

    // const int lookup[16]     = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};
    // 2-bit signed 2's complement: 11 11 00 00 01 01 00 00 11 11 00 00 01 01 00 00
    // Hexadecimal:                   F     0     5     0     F     0     5     0
    const u32 K = 0xF050F050U;

    return (s32)(K<<(num+num)) >> 30;
}

int main(void){
    for(int i=0;i<16;i++){
        if(a(i) != d(i)){
            return !0;
        }
    }
    return 0;
}

在这里亲眼看看：https://godbolt.org/z/AcJWWf

关于常量的选择

您查找的是 -1 到 +1 之间的 16 个非常小的常数。每个都在2位之内，共有16位，我们可以这样布局：

// const int lookup[16]     = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};
// 2-bit signed 2's complement: 11 11 00 00 01 01 00 00 11 11 00 00 01 01 00 00
// Hexadecimal:                   F     0     5     0     F     0     5     0
u32 K = 0xF050F050U;

通过将它们的索引 0 放置在最靠近 most-significant 位的位置，2*num 的一次移位会将您的 2 位数的符号位放入寄存器的符号位。将 2 位数字右移 32-2=30 位 sign-extends 到完整的 int，完成技巧。

Answer 3

如果您明确枚举所有情况，gcc 会非常高效：

int c(int num) {
    num &= 0xF;
    switch (num) {
        case 0: case 1: case 8: case 9: 
            return -1;
        case 4: case 5: case 12: case 13:
            return 1;
            case 2: case 3: case 6: case 7: case 10: case 11: case 14: case 15: 
        //default:
            return 0;
    }
}

只是在一个简单的索引分支中编译：

c:
        and     edi, 15
        jmp     [QWORD PTR .L10[0+rdi*8]]
.L10:
        .quad   .L12
        .quad   .L12
        .quad   .L9
        .quad   .L9
        .quad   .L11
        .quad   .L11
        .quad   .L9
        .quad   .L9
        .quad   .L12
etc...

请注意，如果 default: 未被注释，gcc 将返回其嵌套分支版本。

Answer 4

您可以仅使用算术来创建相同的效果：

// produces : -1 -1 0 0 1 1 0 0 -1 -1 0 0 1 1 0 0 ...
int foo ( int x )
{
    return 1 - ( 3 & ( 0x46 >> ( x & 6 ) ) );
}

尽管从技术上讲，这仍然是（按位）查找。

如果以上觉得太玄乎，你也可以这样做：

int foo ( int x )
{
    int const y = x & 6;
    return (y == 4) - !y;
}

为什么 C 编译器优化 switch 和 if 不同

Why C compilers optimize switch and if differently

c

gcc

optimization

bit-manipulation

disassembly

澄清

关于常量的选择