c - 使用二进制搜索优化大型 if-else 分支

Question

所以我的程序中有一个 if-else 分支，大约有 30 个 if-else 语句。这部分每秒运行超过 100 次，因此我将其视为优化的机会，并使其使用函数指针数组(实际上是平衡 TreeMap )进行二进制搜索，而不是进行线性 if-else 条件检查。但是它比之前的速度慢了大约 70%。

我做了一个简单的基准程序来测试这个问题，它也给出了类似的结果，即 if-else 部分运行得更快，无论是否有编译器优化。

我还计算了完成的比较次数，正如预期的那样，进行二分查找的比较次数大约是简单的 if-else 分支的一半。但它的运行速度仍然慢了 20~30%。

我想知道我所有的计算时间都浪费在哪里，以及为什么线性 if-else 比对数二分查找运行得更快？

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long long ifElseCount = 0;
long long binaryCount = 0;

int ifElseSearch(int i) {
    ++ifElseCount;
    if (i == 0) {
        return 0;
    }
    ++ifElseCount;
    if (i == 1) {
        return 1;
    }
    ++ifElseCount;
    if (i == 2) {
        return 2;
    }
    ++ifElseCount;
    if (i == 3) {
        return 3;
    }
    ++ifElseCount;
    if (i == 4) {
        return 4;
    }
    ++ifElseCount;
    if (i == 5) {
        return 5;
    }
    ++ifElseCount;
    if (i == 6) {
        return 6;
    }
    ++ifElseCount;
    if (i == 7) {
        return 7;
    }
    ++ifElseCount;
    if (i == 8) {
        return 8;
    }
    ++ifElseCount;
    if (i == 9) {
        return 9;
    }
}

int getZero(void) {
    return 0;
}

int getOne(void) {
    return 1;
}

int getTwo(void) {
    return 2;
}

int getThree(void) {
    return 3;
}

int getFour(void) {
    return 4;
}

int getFive(void) {
    return 5;
}

int getSix(void) {
    return 6;
}

int getSeven(void) {
    return 7;
}

int getEight(void) {
    return 8;
}

int getNine(void) {
    return 9;
}

struct pair {
    int n;
    int (*getN)(void);
};

struct pair zeroToNine[10] = {
    {0, getZero},
    {2, getTwo},
    {4, getFour},
    {6, getSix},
    {8, getEight},
    {9, getNine},
    {7, getSeven},
    {5, getFive},
    {3, getThree},
    {1, getOne},
};

int sortCompare(const void *p, const void *p2) {
    if (((struct pair *)p)->n < ((struct pair *)p2)->n) {
        return -1;
    }
    if (((struct pair *)p)->n > ((struct pair *)p2)->n) {
        return 1;
    }
    return 0;
}

int searchCompare(const void *pKey, const void *pElem) {
    ++binaryCount;
    if (*(int *)pKey < ((struct pair *)pElem)->n) {
        return -1;
    }
    if (*(int *)pKey > ((struct pair *)pElem)->n) {
        return 1;
    }
    return 0;
}

int binarySearch(int key) {
    return ((struct pair *)bsearch(&key, zeroToNine, 10, sizeof(struct pair), searchCompare))->getN();
}

struct timer {
    clock_t start;
    clock_t end;
};

void startTimer(struct timer *timer) {
    timer->start = clock();
}

void endTimer(struct timer *timer) {
    timer->end = clock();
}

double getSecondsPassed(struct timer *timer) {
    return (timer->end - timer->start) / (double)CLOCKS_PER_SEC;
}

int main(void) {
    #define nTests 500000000
    struct timer timer;
    int i;

    srand((unsigned)time(NULL));
    printf("%d\n\n", rand());
    for (i = 0; i < 10; ++i) {
        printf("%d ", zeroToNine[i].n);
    }
    printf("\n");
    qsort(zeroToNine, 10, sizeof(struct pair), sortCompare);
    for (i = 0; i < 10; ++i) {
        printf("%d ", zeroToNine[i].n);
    }
    printf("\n\n");

    startTimer(&timer);
    for (i = 0; i < nTests; ++i) {
        ifElseSearch(rand() % 10);
    }
    endTimer(&timer);
    printf("%f\n", getSecondsPassed(&timer));

    startTimer(&timer);
    for (i = 0; i < nTests; ++i) {
        binarySearch(rand() % 10);
    }
    endTimer(&timer);
    printf("%f\n", getSecondsPassed(&timer));
    printf("\n%lli %lli\n", ifElseCount, binaryCount);
    return EXIT_SUCCESS;
}

可能的输出:

78985494

0 2 4 6 8 9 7 5 3 1 
0 1 2 3 4 5 6 7 8 9 

12.218656
16.496393

2750030239 1449975849

Answer 1

您应该查看生成的指令以查看 (gcc -S source.c)，但通常归结为以下三个:

1) N太小

如果您只有 8 个不同的分支，则平均执行 4 次检查(假设情况概率相同，否则可能会更快)。

如果你让它成为二分查找，那就是 log(8) == 3 检查，但这些检查要复杂得多，导致整体执行的代码更多。

因此，除非您的 N 为数百，否则执行此操作可能没有意义。您可以进行一些分析以找到 N 的实际值。

2) 分支预测更难。

在线性搜索的情况下，每个条件在 1/N 情况下都为真，这意味着编译器和分支预测器可以假设没有分支，然后只恢复一次。对于二进制搜索，您可能最终会每层刷新一次管道。对于 N < 1024，1/log(N) 错误预测的机会实际上会损害性能。

3) 指向函数的指针很慢

当执行指向一个函数的指针时，你必须从内存中获取它，然后你必须将你的函数加载到指令缓存中，然后执行调用指令，函数设置并返回。你不能内联通过指针调用的函数，所以这是一些额外的指令，加上内存访问，加上将东西移入/移出缓存。它加起来很快。

---

总而言之，这只对较大的 N 有意义，您应该始终在应用这些优化之前进行概要分析。