How does the switch work behind the scenes?

Question

Seeing those comments on the use of switch is the doubt how it really works and why it is different from the if when only buy for the equality of a single variable against a sequence of values.

How this is compiled?

He must be preferred to if?

Answer 1

How it works is implementation detail, it is not specified and you cannot use it to do something that only works if it is implemented in a specific way.

What we do know is that the compiler does the best possible to optimize its use. It does not always succeed or is viable, so there is no guarantee of what will happen. It can function similarly to if in some cases, even if not exactly in the same way.

But it will try to generate a table of deviations (branch table). With this he needs to make only a comparison and can find the address he should make a leap in execution according to a table, more or less like a array.

• Obviously needs to be a simple comparison with simple data,
• it must be dense, that is, it cannot have many gaps between the possible values. Even if he doesn’t have something to execute for a value in the middle of the sequence, he needs to create a space in the table for it. If there are too many gaps the space occupied by the table can be too large,
• need to have a minimum number of options to compensate the table,
• no deviations occur during each block of case.

It has a series of details that may vary in each case, but the idea is that a search that could take O(n) time, will take O(1). Obviously a good compiler considers the target architecture and generates the code that is most suitable for it.

Internally it works a lot like a polymorphism.

Do not call for details not important to this subject in the codes below.

If we create a switch to get names of months we can see which Assembly generated:

#include <string.h>
#include <stdlib.h>
char *mes(int i) {
  char *texto = (char *)malloc(10);
    switch (i) {
      case 0:
        strcpy(texto, "janeiro");
        break;
      case 1:
        strcpy(texto, "fevereiro");
        break;
      case 2:
        strcpy(texto, "marco");
        break;
      case 3:
        strcpy(texto, "abril");
        break;
      case 4:
        strcpy(texto, "maio");
        break;
      case 5:
        strcpy(texto, "junho");
        break;
      case 6:
        strcpy(texto, "julho");
        break;
      case 7:
        strcpy(texto, "agosto");
        break;
      case 8:
        strcpy(texto, "setembro");
        break;
      case 9:
        strcpy(texto, "outubro");
        break;
      case 10:
        strcpy(texto, "novembro");
        break;
      case 11:
        strcpy(texto, "dezembro");
        break;
    }
    return texto;
}

Behold the Assembly generated in the Compiler Explorer. I also put in the Github for future reference.

Here he makes the comparison once and finds the address in the table:

    cmp     DWORD PTR [rbp-20], 11
    ja      .L2
    mov     eax, DWORD PTR [rbp-20]
    mov     rax, QWORD PTR .L4[0+rax*8]
    jmp     rax

Just below is the table and then the code blocks that must be executed.

If you make a if there will be a comparison for each value:

#include <string.h>
#include <stdlib.h>

char *mes(int i) {
  char *texto = (char *)malloc(10);
    if (i == 0) {
      strcpy(texto, "janeiro");
    } else if (i == 1) {
      strcpy(texto, "fevereiro");
    } else if (i == 2) {
      strcpy(texto, "marco");
    } else if (i == 3) {
      strcpy(texto, "abril");
    } else if (i == 4) {
      strcpy(texto, "maio");
    } else if (i == 5) {
      strcpy(texto, "junho");
    } else if (i == 6) {
      strcpy(texto, "julho");
    } else if (i == 7) {
      strcpy(texto, "agosto");
    } else if (i == 8) {
      strcpy(texto, "setembro");
    } else if (i == 9) {
      strcpy(texto, "outubro");
    } else if (i == 10) {
      strcpy(texto, "novembro");
    } else if (i == 11) {
      strcpy(texto, "dezembro");
    }
    return texto;
}

Behold the Assembly generated in the Compiler Explorer. Also in the Github.

Can see the code if you have few options (Github). Does not optimize so much.

Group cases is not a problem and optimizes, as can be seen in the code (Github). When there is the cascade it puts an item in the table for each case, but optimization occurs the same way. The break is used to determine when to quit and not continue walking on the table.

Already having many gaps is a problem and practically turns into the code of if. See how it looks (Github).

But that code is better if it’s a array even. See how it’s simpler (Github).

You might think you can only use one array if it’s to take a simple value and store it somewhere. In fact it is possible to do the same with code blocks in function and call each function according to the search value, the table would be the addresses of the functions.

The GCC even has a more explicit way to do this, but does not work on other compilers.

Completion

So that’s it, the performance is usually better. More than the performance should prefer it whenever it makes sense, whenever it is a sequence to be analyzed. This value for numbers, characters, enumerations, or other forms that boil down to simple numbers.

The same goes for many languages that value performance. There is language that has this more for embellishment, or more to give a more appropriate syntax and does not bring much internal advantage. But overall it is not just because it is more "cute", it has a function of its own and if it is used correctly it has no drawbacks.

Don’t use where you don’t need it, don’t be afraid where it’s suitable.