How does the switch work under the rags?

10

Viewing these comments about using switch is in doubt as to how it works even and why it is different from if when only buying by equality of a single variable against a sequence of values. p>

How is this compiled?

Should it be preferred to if ?

    
asked by anonymous 11.01.2017 / 12:20

1 answer

9

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

What we do know is that the compiler does its best to optimize its usage.Not always it achieves or is feasible, so there is no guarantee of what will happen. It can work in an analogous way to if in some cases, even if not exactly the same way.

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

  • Obviously it needs to be a simple comparison with simple data,
  • must be dense, that is, there can not be many gaps between possible values. Even though it does not have something to perform for a value in the middle of the stream, it needs to create a table space for it. If you have too many gaps the space occupied by the table may be too large,
  • needs to have a minimum number of options to compensate for the table,
  • No detours occur during each block of case .

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

Internally it works much like a polymorphism.

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

If we create a switch to get names of months we can see which Assembly is 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;
}

See the Assembly generated in GodBolt . I also put it on Github for future reference .

Here he does 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

Below is the table and then the code blocks that should be executed.

If you do 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;
}

See the Assembly generated in GodBolt . Also on Github .

You can see the code if you have few options (Github ). It does not optimize as much.

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

Having too many gaps is a problem and pretty much transforms into if code. See how it is (Github ).

But this code looks better if it is an array itself. See how simple it is (Github ).

You may be thinking that you can only use an array if it is to take a simple value and save somewhere. In fact it is possible to do the same with function blocks and call each function according to the search value, the table would be the address of the functions.

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

Conclusion

So that's it, performance tends to be better. But more than 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 are limited to simple numbers.

The same goes for many languages that cherish performance. It has language that has this more to embellish itself, or more to give a more appropriate syntax and does not bring much internal advantage. But in general it is not only because it is more "cute", it has a function of its own and if used properly it has no disadvantages.

Do not use where you do not need it, do not be afraid where it is suitable.

    
11.01.2017 / 12:20