Branching is almost always an essential part of a C program. In C we likely choose to use if…else, switch…case, but we should still remember there is still a thing called jump table(a.k.a Array of function pointer). Try not to be too stuck on one of them and think about how to make a program look easy to understand and perform well.
if…else
If…else is the easiest to understand, it compares. Among the three ways mentioned in this story, if…else is the most versatile as the condition term has nearly no limits on comparing things, however, if...else tends to be a bit erratic if sometimes can go very fast but most likely it is the slowest, because the more complex condition is difficult to optimize sometimes.
If…else is most effective if we want to compare more complex things, like strings in the comparison term.
if(target[i]==0)function0();
else if(target[i]==1)function1();
else if(target[i]==2)function2();
else if(target[i]==3)function3();Switch…case
Switch…case is most likely what should be used most of the time as it can be very optimized, however, switch…case only takes integer-relative types as an expression, thus it is not as free as if…else. Switch—case can still do very well on non-consecutive integer inputs, for example, it can be very effective in dealing with an integer-type error code, and since we might only be interested in some of the errors, we will only perform action on some of the return values.
switch (target[j])
{
case 0:
{
function0();
break;
}
case 1:
{
function1();
break;
}
// continue down with more
}Array of function pointer(jump table)
An array is much more restrictive than a switch…case, it also can only use an integer as the input, furthermore the integer has to be consecutive. The jump table does the best when we are choosing a function with an enum, one type of
int (*functions[NUM_FUNCTION])(void) = {function0, function1, function2, function3, function4,
function5, function6, function7, function8, function9,
function10, function11, function12, function13, function14,
function15, function16, function17, function18, function19};
functions[target[j]]();The functions are the name of this array, the int in the front is the return, and the void is the function argument type(i.e. we can change it to like (int, int) if need be). The elements from function0 to function19 are the function names.
What os happening in the back?
.L70:
mov eax, DWORD PTR [rbp-28]
movsx rdx, eax
lea rax, [rbp-64]
mov rsi, rdx
mov rdi, rax
call std::vector<int, std::allocator<int> >::operator[](unsigned long)
mov eax, DWORD PTR [rax]
test eax, eax
sete al
test al, al
je .L50
call function0()
jmp .L51
.L50:
mov eax, DWORD PTR [rbp-28]
movsx rdx, eax
lea rax, [rbp-64]
mov rsi, rdx
mov rdi, rax
call std::vector<int, std::allocator<int> >::operator[](unsigned long)
mov eax, DWORD PTR [rax]
cmp eax, 1
sete al
test al, al
je .L52
call function1()
jmp .L51If…else will have to compare with each of the conditions one by one, so we should always put the most possible outcome in the first one.
Switch…case on the optimized in many ways, from similar to if…else to jump table in here I will showcase one that is optimized to a jump table.
.L72:
mov eax, DWORD PTR [rbp-20]
movsx rdx, eax
lea rax, [rbp-64]
mov rsi, rdx
mov rdi, rax
call std::vector<int, std::allocator<int> >::operator[](unsigned long)
mov eax, DWORD PTR [rax]
cmp eax, 19
ja .L50
mov eax, eax
mov rax, QWORD PTR .L52[0+rax*8]
jmp raxThe compiler is smart enough to understand the cases are in fact consecutive and uses this knowledge to jump.
Finally, a jump table.
.L50:
mov eax, DWORD PTR [rbp-20]
movsx rdx, eax
lea rax, [rbp-64]
mov rsi, rdx
mov rdi, rax
call std::vector<int, std::allocator<int> >::operator[](unsigned long)
mov eax, DWORD PTR [rax]
cdqe
mov rax, QWORD PTR [rbp-224+rax*8]
call rax
add DWORD PTR [rbp-20], 1During my test, pure jump table performed better, but it should be because I did not perform a boundary test when accessing the array, which I should.
If…else can be very fast if it gets lucky that most of the inputs are near the beginning of the if-else structure. By using switch…case, we are letting the compiler decide which is best for us, we can also use the attribute [[likely]], to give the compiler more hints on how to optimize. Use a jump table when we have a lot of consecutive things we can branch to, as it is the shortest, which makes it easier to understand than a super large if…else or switch…case. A real-world case for a jump table is for the os kernel to understand which system call is called.
Some testing codes
header.h
inline int function0(){
return 0;
}
inline int function1(){
return 1;
}
inline int function2(){
return 2;
}
inline int function3(){
return 3;
}
inline int function4(){
return 4;
}
inline int function5(){
return 5;
}
inline int function6(){
return 6;
}
inline int function7(){
return 7;
}
inline int function8(){
return 8;
}
inline int function9(){
return 9;
}
inline int function10(){
return 10;
}
inline int function11(){
return 11;
}
inline int function12(){
return 12;
}
inline int function13(){
return 13;
}
inline int function14(){
return 14;
}
inline int function15(){
return 15;
}
inline int function16(){
return 16;
}
inline int function17(){
return 17;
}
inline int function18(){
return 18;
}
inline int function19(){
return 19;
}if_else.c
#include <iostream>
#include <chrono>
#include <vector>
#include "header.h"
#define LOOP_TIME 100000
#define NUM_FUNCTION 20
int main()
{
srand(time(0));
std::vector<int> target;
int i,j;
for (int i = 0; i < LOOP_TIME; i++)
{
target.push_back(rand() % NUM_FUNCTION);
}
std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
for (j = 0; j < LOOP_TIME; j++)
{
if(target[i]==0)function0();
else if(target[i]==1)function1();
else if(target[i]==2)function2();
else if(target[i]==3)function3();
else if(target[i]==4)function4();
else if(target[i]==5)function5();
else if(target[i]==6)function6();
else if(target[i]==7)function7();
else if(target[i]==8)function8();
else if(target[i]==9)function9();
else if(target[i]==10)function10();
else if(target[i]==11)function11();
else if(target[i]==12)function12();
else if(target[i]==13)function13();
else if(target[i]==14)function14();
else if(target[i]==15)function15();
else if(target[i]==16)function16();
else if(target[i]==17)function17();
else if(target[i]==18)function18();
else if(target[i]==19)function19();
}
std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
std::cout << "Time difference = " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count()<< "[µs]" << std::endl;
}switch_case.c
#include <iostream>
#include <chrono>
#include <vector>
#include "header.h"
#define LOOP_TIME 100000
#define NUM_FUNCTION 20
int main()
{
srand(time(0));
std::vector<int> target;
int i, j;
for (int i = 0; i < LOOP_TIME; i++)
{
target.push_back(rand() % NUM_FUNCTION);
}
std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
for (j = 0; j < LOOP_TIME; j++)
{
switch (target[j])
{
case 0:
{
function0();
break;
}
case 1:
{
function1();
break;
}
case 2:
{
function2();
break;
}
case 3:
{
function3();
break;
}
case 4:
{
function4();
break;
}
case 5:
{
function5();
break;
}
case 6:
{
function6();
break;
}
case 7:
{
function7();
break;
}
case 8:
{
function8();
break;
}
case 9:
{
function9();
break;
}
case 10:
{
function10();
break;
}
case 11:
{
function11();
break;
}
case 12:
{
function12();
break;
}
case 13:
{
function13();
break;
}
case 14:
{
function14();
break;
}
case 15:
{
function15();
break;
}
case 16:
{
function16();
break;
}
case 17:
{
function17();
break;
}
case 18:
{
function18();
break;
}
case 19:
{
function19();
break;
}
}
}
std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
std::cout << "Time difference = " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << "[µs]" << std::endl;
}fpa.c (for function pointer)
#include <iostream>
#include <chrono>
#include <vector>
#include "header.h"
#define LOOP_TIME 100000
#define NUM_FUNCTION 20
int main()
{
srand(time(0));
std::vector<int> target;
int i,j;
for (int i = 0; i < LOOP_TIME; i++)
{
target.push_back(rand() % NUM_FUNCTION);
}
int (*functions[NUM_FUNCTION])(void) = {function0, function1, function2, function3, function4,
function5, function6, function7, function8, function9,
function10, function11, function12, function13, function14,
function15, function16, function17, function18, function19};
std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
for (j = 0; j < LOOP_TIME; j++)
{
functions[target[j]]();
}
std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
std::cout << "Time difference = " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << "[µs]" << std::endl;
}Time
During my testing if-else can run from 143 to 2500 microseconds, switch case from 900 to 1400 microseconds. Jump table 700 to 1000 microseconds. Although this test scheme is biased to jump table and microsecond, we can clearly see that if-else can get very lucky.
References
Stack Overflow. Easily measure elapsed time. Stack Overflow. Retrieved October 9, 2024, from https://stackoverflow.com/questions/2808398/easily-measure-elapsed-time
Compiler Explorer. Godbolt: Interactive compiler explorer. Retrieved October 9, 2024, from https://godbolt.org/
