减少 C 中的 if 语句以提高效率

Question

我正在尝试通过减少条件语句的数量来提高我的代码的效率，因为我以后将在汇编中编写代码。你们有什么方法可以减少语句以提高效率吗？

if (j==18)
{
    store=12;
}
else if(j==30)
{
    store=10;
}
else if(j==42)
{
    store=8;
}
else if(j==54)
{
    store=6;
}
else if(j==66)
{
    store=4;
}
else if(j==78)
{
    store=2;
}
else if(j==92)
{
    store=2;
}
else if(j==106)
{
    store=4;
}
else if(j==120)
{
    store=6;
}
else if(j==134)
{
    store=8;
}
else if(j==148)
{
    store=10;
}
else if(j==162)
{
    store=12;
}
else store=1;

Answer 1

嗯，使用 switch 语句而不是一系列 if 语句肯定会更快（也更紧凑）。大多数语言可以比一系列 if 更好地优化 switch 语句。您的代码在 switch 语句形式中看起来像这样：

switch(j) {
    case 18:
        store = 12;
        break;
    case 30:
        store = 10;
        break;
    // and so on
    default:
        store = 1;
}

当然，这不会像没有条件的代码版本那样快（可能）。如果你能想出一个数学公式来根据 j 计算 store 的值，那（可能）会快很多。

Answer 2

我会尝试使用 162 字符或更少的数组，如果这些都是您必须处理的。这听起来像是一种内存浪费，但考虑到所有这些指令都被保存了，它们也占用了内存。 M2c

Answer 3

if (j < 18 || 162 < j) {
    store = 1;
} else if (j < 90) {
    int mod12 = (j-6) % 12;
    // ((j-6)/12) -> 18=>1, .. 78=>6  (/6 used to get *2)
    store = (mod12) ? 1 : 14 - ((j-6) / 6);
} else {
    int mod14 = (j-8) % 14;
    // ((j-8)/14) -> 92=>6, ... 162=>11 (/7 used to get *2)
    store = (mod14) ? 1 : ((j-8) / 7) - 10;
}

这可以通过手动汇编器直接实现，尽管现代 C++ 编译器会比普通人做得更好，for example gcc 7.3 produces something a bit better 比我最初想的要好（而且我不想手工编写的东西).

其实 gcc 可以是 hand-holded a bit to understand that formula better.

修改来源：

if (j < 18 || 162 < j) {
    store = 1;
} else if (j < 90) {
    int mod12 = (j-6) % 12;
    // ((j-6)/12) -> 18=>1, .. 78=>6
    store = (mod12) ? 1 : 14 - 2*((j-6) / 12);
} else {
    int mod14 = (j-8) % 14;
    // ((j-8)/14) -> 92=>6, ... 162=>11
    store = (mod14) ? 1 : 2*((j-8) / 14) - 10;
}

为了完整起见，这里是 switch 版本（没有对其进行基准测试，但应该比上面的代码慢得多）：https://godbolt.org/g/ELNCYD

看起来 gcc 无法解决这个问题，并且确实使用了很多 "ifs"。

NEW：所以在检查了所有这些 compilers/and 评论之后，这看起来是最 [性能] 最优的 x86_64 解决方案（采用 "j" 在 edi 中返回 "store" 在 rax 中）（NASM 语法）：

; input: edi = j, output: rax = store
storeByJ:
    sub     edi, 18
    cmp     edi, (162-18)
    ja      .JoutOfRange    ; j < 18 || 162 < j -> return 1
    ; rdi = 0 .. 162-18 = 144
    movzx   eax, byte [rel .JtoStoreLUT + rdi]
    ret
.JoutOfRange:
    mov     eax,1
    ret

.JtoStoreLUT:
    ;        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
    db      12, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1         ; 18->12
    db      10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1         ; 30->10
    db       8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1         ; 42->8
    db       6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1         ; 54->6
    db       4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1         ; 66->4
    db       2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1   ; 78->2
    db       2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1   ; 92->2
    db       4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1   ;106->4
    db       6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1   ;120->6
    db       8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1   ;134->8
    db      10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1   ;148->10
    db      12                                          ;162->12

如果你有更大的范围（更多的值）仍然是 +12 并且在某个点 +14 微分之后，公式可能会变得更好（通过从 too-big LUT 中保存缓存内存（Look-Up-Table))，但此时此代码即使有 LUT 数据也有大约 170B 长，因此即使整个循环都在使用它，它也很可能适合。

编辑：另一种变体，使用half-sized LUT，但使用ror通过范围测试中的单跳过滤掉奇数（我不确定性能，但与任何其他 code-efficient 问题，分析是绝对必要的，最重要的是理论推理，如果你不能在基准测试中证实你的理论，修复你的基准（更有可能），或者发现 CPU 内部结构以及您是如何误解某些事情的……（但这仍然很可能经常发生））.. 并且使用 cmovCC（总计 97B）消除了范围分支：

; input: edi = j, output: eax = store
storeByJ:
    mov     eax, 1
    sub     edi, 18
    ror     edi, 1          ; /2 but keeps "odd" bit in the edi
                            ; to make it fail range check on next line
    cmp     edi, (162-18)/2
    cmova   edi, eax        ; j < 18 || 162 < j || j&1 -> return 1 (from LUT[1])
    ; rdi = 0 .. (162-18)/2 = 72  # rdi = (j-18)/2
    movzx   eax, byte [rel .JtoStoreLUT + rdi]
    ret

.JtoStoreLUT:
    ;        0, 1, 2, 3, 4, 5, 6
    db      12, 1, 1, 1, 1, 1       ;  18->12
    db      10, 1, 1, 1, 1, 1       ;  30->10
    db       8, 1, 1, 1, 1, 1       ;  42->8
    db       6, 1, 1, 1, 1, 1       ;  54->6
    db       4, 1, 1, 1, 1, 1       ;  66->4
    db       2, 1, 1, 1, 1, 1, 1    ;  78->2
    db       2, 1, 1, 1, 1, 1, 1    ;  92->2
    db       4, 1, 1, 1, 1, 1, 1    ; 106->2
    db       6, 1, 1, 1, 1, 1, 1    ; 120->2
    db       8, 1, 1, 1, 1, 1, 1    ; 134->2
    db      10, 1, 1, 1, 1, 1, 1    ; 148->2
    db      12                      ; 162->2

减少 C 中的 if 语句以提高效率

reducing if statements in C for efficiency

c

reduce

assembly

conditional

if-statement