所以在我的程序中有一个if-else分支,大约有30个if-else语句 . 这部分每秒运行超过100次,因此我将其视为优化的机会,并使用函数指针数组(实际上是 balancer 树映射)进行二进制搜索,而不是进行线性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
2 回答
您应该查看生成的指令以查看(
gcc -S source.c
),但通常归结为以下三个:1)N太小了 .
如果您只有8个不同的分支,则执行平均4次检查(假设同样可能的情况,否则它可能更快) .
如果你使它成为二进制搜索,那就是log(8)== 3检查,但这些检查要复杂得多,从而导致执行的代码总体上更多 .
所以,除非你的N数百,否则这样做可能没有意义 . 您可以进行一些分析以找到N的实际值 .
2)分支预测更难 .
在线性搜索的情况下,每个条件在
1/N
情况下都为真,这意味着编译器和分支预测器可以假设没有分支,然后只恢复一次 . 对于二进制搜索,您可能最终每层都刷新一次管道 . 而对于N <1024,1/log(N)
错误预测的可能性实际上会损害性能 .3)指向函数的指针很慢
当执行指向函数的指针时,你必须从内存中获取它,然后你必须将函数加载到指令缓存中,然后执行调用指令,函数设置并返回 . 您不能内联通过指针调用的函数,因此这是一些额外的指令,加上内存访问,以及移入/移出缓存 . 它很快就加起来了 .
总而言之,这只对大N有意义,并且在应用这些优化之前应始终进行概要分析 .
使用switch语句 .
编译器很聪明 . 它们将为您的特定值生成最有效的代码 . 如果认为更有效,他们甚至会进行二分搜索(使用内联代码) .
并且作为一个巨大的好处,代码是可读的,并且不需要您在六个地方进行更改以添加新案例 .
PS . 显然,您的代码是一种很好的学习体验 . 现在你已经学会了,所以不要再这样做了:-)