So there is an if-else branch in my program with about 30 if-else statements. This part runs more than 100 times per second, so I saw it as an opportunity to optimize, and made it do binary search with a function pointer array (practically a balanced tree map) instead of doing linear if-else condition checks. But it ran slower about 70% of the previous speed.
I made a simple benchmark program to test the issue and it also gave similar result that the if-else part runs faster, both with and without compiler optimizations.
I also counted the number of comparisons done, and as expected the one doing binary search did about half number of comparisons than the simple if-else branch. But still it ran 20~30% slower.
I want to know where all my computing time is being wasted, and why the linear if-else runs faster than the logarithmic binary search?
#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;
}
possible output:
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