C++ switch statement for the performance profiling tutorial

preface

Almost every beginner's C language or C++ book mentions branch control statements in the first two chapters. else and switch... case, in some cases these two branch control statements can be substituted for each other, but very few people go into the if... else and switch... What are the similarities and differences behind the case statement? Which statement should I choose to make the most efficient? To answer these questions, go behind the switch statements to see how they are actually implemented.

The basic format

The basic format of the switch statement is as follows:

[

switch (expression) {
case constant expressions 1: Statement Sequence 1, break; // The content in "" can be saved
...
case constant expressions n: Statement sequence n, break; // Same as above and below
default: Statement Sequence
}

]

Among them:

Expression -- called a "conditional expression" and used as a judgment condition, takes the value of an integer, character, Boolean, or enumeration. Constant expression - Consists of constants and has the same value type as a conditional expression. Statement sequence - can be 1 statement or 1 set of statements.

if statement and switch statement

It is believed that those students who have learned C/C++ have long been familiar with the similarities and differences of these two statements. As a condition judgment, if statement satisfies the condition and enters if statement block, while else statement block does not satisfy the condition. Moreover, if and else statement block can continue to nested if statements. switch determines which case statement to enter by judging the value of one integer expression, and enters default block if all case conditions are not satisfied.

// simple if statements 
if (a == 1)
 i = 1;
else if (a == 2)
 i = 2;
else
 i = 3;

// simple switch statements 
switch (a){
 case 1: i = 1;
 case 2: i = 2;
 default: i = 3;
}

How does the compiler implement the switch statement?

Now the compiler has been smart and powerful enough, after testing, g++ switch statement of at least three ways, the compiler will be based on the actual situation of the code, weigh the time efficiency and space efficiency, to choose one of the most comprehensive efficiency for the current code.

Three ways the compiler implements switch statements:

Conditional judgment The jump table Two point search

We will test and analyze the code scenarios applicable to these three implementation methods.

1. Conditional judgment

Conditional judgment is the same as if... The compilation implementation of else statement is the same. The compiler evaluates each case condition in switch statement one by one until the correct case block is found. This approach works well in switch statements where the case conditions are few, and even a conditional-by-condition judgment does not result in a significant waste of time and space, such as this code:

#include <algorithm>
int test_switch(){
 int i ;
 int a = std::rand();
 switch(a){
  case 0: i = 0;break;
  case 1: i = 1;break;
  case 2: i = 2;break;
  default: i = 3;break;
 }
 return i;
}

The corresponding assembly code of this code is as follows:

 movl -4(%rbp), %eax
 cmpl $1, %eax
 je .L3
 cmpl $2, %eax
 je .L4
 testl %eax, %eax
 jne .L8
 movl $0, -8(%rbp)
 jmp .L6
.L3:
 movl $1, -8(%rbp)
 jmp .L6
.L4:
 movl $2, -8(%rbp)
 jmp .L6
.L8:
 movl $3, -8(%rbp)
 nop

The eax register stores the condition value (corresponding to C++ code a value). First, it determines whether a is equal to 1, if equal to 1, it jumps to.L3 to execute a==1, then it jumps to. What may be hard to understand is that line 6, testl %eax, %eax, is actually just a trick to improve the efficiency of the compiler to determine whether a register is zero or not. If eax does not equal zero, then jump to.es103EN8, and execute the code corresponding to default, if eax equals zero, execute the code corresponding to a= 0.

From the above analysis of assembly code generated by the compiler, we can see that the compiler implements switch statements in this case using conditional-by-condition judgment.

2. Method of jump table implementation

When the compiler adopts this switch statement implementation mode, a jump table will be generated in the program, and the jump table will store the address of each case statement instruction block. When the program runs, the value of switch condition will be judged first, and then the conditional value will be used as the offset of the jump table to find the instruction address of corresponding case statement, and then it will be executed. This method is suitable for case with many conditions, but the value of case is relatively continuous. Using this method can improve the time efficiency without significantly reducing the spatial efficiency. For example, the following code compiler will adopt the skip table implementation:

#include <algorithm>

int test_switch(){
 int i ;
 int a = std::rand();
 switch(a){
  case 0: i = 0;break;
  case 1: i = 1;break;
  case 2: i = 2;break;
  case 3: i = 3;break;
  case 4: i = 4;break;
  case 5: i = 5;break;
  case 6: i = 6;break;
  case 7: i = 7;break;
  case 8: i = 8;break;
  case 9: i = 9;break;
  default: i = 10;break;
 }
 return i;
}

The corresponding assembly code of this code is as follows:

 movl -4(%rbp), %eax
 movq .L4(,%rax,8), %rax
 jmp *%rax
.L4:
 .quad .L3
 .quad .L5
 .quad .L6
 .quad .L7
 .quad .L8
 .quad .L9
 .quad .L10
 .quad .L11
 .quad .L12
 .quad .L13
 .text
.L3:
 movl $0, -8(%rbp)
 jmp .L14
.L5:
 movl $1, -8(%rbp)
 jmp .L14
# Leave out... 

In x64 architecture, eax registers are rax low 32-bit registers, here we can assume that the two values are equal, the code line 1 is the judgment condition (corresponding to the a C + + code value) is copied to the eax register, 2 lines of code is to put the. L4 period of migration rax register values address assigned to the size of rax registers, 3 lines of code is removed in the rax address and jump to the address. We can clearly see.L4 code segment is a jump table stored in.text segment generated by the compiler for switch statement. Each case corresponds to an address value in the jump table. We can calculate the offset of the address stored in the corresponding code segment relative to.L4 by determining the value of the condition, thus achieving an efficient jump.

3. 2 point search method

If the VALUE of case is large and the distribution is extremely discrete, the time efficiency will be low if the conditional judgment is adopted; if the jump table method is adopted, the space occupied by the jump table will be large, and the first two methods will lead to low program efficiency. In this case, the compiler will use two points, a method to realize switch statements program compiled, the compiler will be ordered all case values before they are written in 2 minutes and find order assembly code, when the program execution, on the other hand, pick two points to find methods in each case value finds the conditions, if the search is performed to the corresponding case statements, in the end if no search to execute default statement. For the following C++ code compiler will use this 2 point lookup method to achieve switch statement:

#include <algorithm>

int test_switch(){
  int i ;
  int a = std::rand();
  switch(a){
    case 4: i = 4;break;
    case 10: i = 10;break;
    case 50: i = 50;break;
    case 100: i = 100;break;
    case 200: i = 200;break;
    case 500: i = 500;break;
    default: i = 0;break;
  }
  return i;
}

Change the assembly code corresponding to the code segment to:

    movl -4(%rbp), %eax
 cmpl $50, %eax
 je .L3
 cmpl $50, %eax
 jg .L4
 cmpl $4, %eax
 je .L5
 cmpl $10, %eax
 je .L6
 jmp .L2
.L4:
 cmpl $200, %eax
 je .L7
 cmpl $500, %eax
 je .L8
 cmpl $100, %eax
 je .L9
 jmp .L2

Line 2 of the code compares the conditional value to 50 first. Why 50 instead of the first 4? This is because the 2-point lookup looks for the value in the middle first, so it is compared to 50 first, and if eax equals 50, then case is performed

50 corresponds to code. If eax is greater than 50, it jumps to.es164EN4. If eax is less than 50, it continues to compare with 4... Until the condition value is found or the condition value does not exist. It can be seen that the two-point search method not only maintains higher query efficiency but also saves space.

conclusion

When should you use if... else statement, when should you use switch... case statement?

From the above analysis, we can come to the conclusion that using if... else and switch... case corresponds to the same assembly code, so there is no difference in performance between the two, depending on your personal habits. If there are more conditions, it is obvious that switch... case is more efficient than if in both jump tables and 2-point lookups... The sequential lookup of else is more efficient, so in this case, switch statements should be chosen as far as possible to implement branch statements. Of course, if we know which condition has the highest probability of occurrence, we can put this condition in the first place of if judgment, so that the sequential search is terminated earlier, then if... The else statement can also achieve high operational efficiency.

The switch statement also has its own limitations, that is, the value of the switch statement can only be integer, for example, when we need to judge one double data, we cannot use the switch statement, then we can only use if... else statement to implement.