c - 减少 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

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”。

---

新:所以在检查了所有这些编译器/和注释之后，这看起来是最[性能]最佳的 x86_64 解决方案(子程序在 edi 中获取“j”并返回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 微分之后，公式可能会变得更好(通过从太大的 LUT(查找表)中保存缓存内存) )，但此时此代码即使包含 LUT 数据也大约有 170B 长，因此即使整个循环都在使用它，它也很可能适合。

---

编辑:另一个变体，具有一半大小的 LUT，但使用 ror 在范围测试中通过单跳过滤掉奇数(我不确定性能，但与任何其他代码效率问题，分析是绝对必要的，最重要的是理论推理，如果你不能在基准测试中证实你的理论，修复你的基准测试(更有可能)，或者找出 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