When (if ever) does the Arduino compiler convert a switch to a jump table

I have poked around the forum and internet and I have yet to see a definitive answer to this question.

It is well known that switch statements are often optimized by compilers to create jump tables especially when the cases are created sequentially.

for example

Case 0:
Case 1:
Case 2:
...

I see a lot of wishful thinking or assumptions about the AVR GCC compiler doing the "right" thing. That said, Does it (and under what circumstances)?

I realize many switch statements are much better compiled as if, else chains by the compiler. It is also obvious that many larger switch statements are incredibly inefficient if they are not converted to jump tables.

In my case, I am implementing a parser. I can create an explicit jump table to be sure, but a Switch is easier to understand.

Al

It is possible to view the assembler code that the compiler produces - sorry I can't remember how to get at it.

...R

If you select File:Preferences and turn on Verbose outputs, you can see the intermediate files & path that get created on the way to the .hex file that gets uploaded. One of those I believe is the assembler.

I will try to examine the assembly code generation. Jump tables are fairly easy to recognize in assembly.

That said, has anyone investigated this question? It seems to come up without a clear answer.

I can certainly build an experiment myself, but I am am happy to learn from previous work.

Al

This code:

void setup() {
  

}

void loop() {
  int a;
  int b;

  if (a == 0)
    b = 0;
  else if (a == 1)
    b = 1;
  else if (a == 2)
    b = 2;
  else
    b = 99;
  
  switch (a){
    case 0: b = 0;break;
    case 1: b = 1;break;
    default: b = 99;break;    
  }
  Serial.println(b);
}

Attached the asm generated... No idea how to read it thou... You can do it your self finding the tmp folder that the IDE generates (activate verbose logging in Preferences) and then doing (obviously names and paths may vary):

"C:\Program Files (x86)\Arduino\hardware\tools\avr/bin/avr-objdump" -S sketch_mar03a.ino.elf

dump.txt (44.8 KB)

Missing Serial.begin(9600); in setup().
a never changes, might have even different code if a could change so that these oarts of the code could actually run
else if (a == 1)
b = 1;
else if (a == 2)
b = 2;
else
b = 99;
and
case 1: b = 1;break;
default: b = 99;break;

Otherwise they might optimized away and you wouldn't get jump tables.

Yeah, you're right about that, that's why I included the print hoping "a" wouldn't be stripped from code... I was wrong. :smiley:

Anyways the switch is in line 100 in the dump.txt

An article discussing this topic (on Intel platform) GCC generated Switch Jump Tables.

The basic gcc algorithm for switch constructs is simple: less then 5 case statements forces gcc to generate code as explained above. More then 5 case statements command gcc to use a jump table - if the labels are in some degree stick together(dense). A heuristic will calculate if the degree is sufficient. And this kicks in here, the labels are exposed and filling the gaps with defaults is to costly. So keep the labels close to each other to make this optimization possible for gcc! gcc generates a small data section where the addresses of all labels are stored and the finally switch construct leads to a simple jump

I think I have some basic results from a simple experiment.

I constructed a Switch with cases 0 thru 6 (and a default)

I measured time for each case and it appears constant for each case. This would make sense for a jump table. The resolution of the micros is too coarse (8us or 16us) which makes sense (my target runs at 8MHz)

I then changed case 6 to case 7, the program size increases by two bytes, case 6 to 8 increases by 4 bytes.

I think this makes the argument that a jump table was created since there would be one or two empty locations corresponding to missing case 6 (and later case 7).

If I randomly reorder the cases from (6,2,4,3,5,1,0), the program size is the same as (0,1,2,3,4,5,6). This would suggest that the compiler still made a jump table and was smart enough to reorder. Randomly changing any of the parameters to 7 increased the size by 2 bytes again. This includes substituting for 0.

If I replace case 6 with a much larger number, the compiler increased the program size 14 bytes. I did this with both 24 and 34. I am speculating that the compiler maybe handles that case by exception (and maybe also the default case)

I didn't work too hard to decipher the assembly code since I built my experiment into a fairly large program and disassembly is hard to read without good labels. I glanced at it and then moved on.

I have quite a bit of embedded experience, mostly with DSPs. This is my first Arduino and AVR project, so I am still learning the environment and I have not learned the assembly language.
Does a short jump take two bytes? This would help support the jump table conclusion.

If I have this wrong, please jump in and clarify.

Al

Since the case is so much simpler, just code it and see if it works well in practice. If it lacks performance, you can code it the other way.

Do not be surprised if the gcc code beats your jump table.

Cosme_Fulanito:
Attached the asm generated... No idea how to read it thou... You can do it your self finding the tp folder that the IDE generates (activate verbose logging in Preferences) and then doing (obviously names and paths may vary):

Make a and b static volatile. The generated assembler will make more sense.

This bit

  d4:	0f b6       	in	r0, 0x3f	; 63

is the b=99.

Here's code with an obvious opportunity to do a table jump:

void loop() {
  int c;

  c = Serial.read();
  if (c > 0) {
    switch (c) {
      case 1:
        Serial.println("ctrl-A");
        break;
      case 2:
        Serial.println("ctrl-B");
        break;
      case 3:
        Serial.println("ctrl-C");
        break;
      case 4:
        Serial.println("ctrl-D");
        break;
      case 5:
        Serial.println("ctrl-E");
        break;
      case 6:
        Serial.println("ctrl-F");
        break;
      case 7:
        Serial.println("Bell");
        break;
      default:
        Serial.println(c);
        break;
    }
  }
}

And it does, as you can tell from the assembly output. Even if you don't understand the AVR assembly language, the use of the tablejump2 symbol sort-of gives it away...

 65e:   0e 94 b9 00     call    0x172   ; 0x172 <HardwareSerial::read()>
 662:   18 16           cp      r1, r24
 664:   19 06           cpc     r1, r25
 666:   0c f0           brlt    .+2             ; 0x66a <main+0x1d8>
 668:   41 c0           rjmp    .+130           ; 0x6ec <main+0x25a>
 66a:   ac 01           movw    r20, r24
 66c:   09 2e           mov     r0, r25
 66e:   00 0c           add     r0, r0
 670:   66 0b           sbc     r22, r22
 672:   77 0b           sbc     r23, r23
 674:   fc 01           movw    r30, r24
 676:   31 97           sbiw    r30, 0x01       ; 1
 678:   e7 30           cpi     r30, 0x07       ; 7
 67a:   f1 05           cpc     r31, r1
 67c:   d8 f4           brcc    .+54            ; 0x6b4 <main+0x222>
 67e:   ec 5c           subi    r30, 0xCC       ; 204
 680:   ff 4f           sbci    r31, 0xFF       ; 255
 682:   0c 94 c8 03     jmp     0x790   ; 0x790 <__tablejump2__>
 686:   83 e1           ldi     r24, 0x13       ; 19
 688:   91 e0           ldi     r25, 0x01       ; 1
 68a:   11 c0           rjmp    .+34            ; 0x6ae <main+0x21c>
 68c:   8a e1           ldi     r24, 0x1A       ; 26
 68e:   91 e0           ldi     r25, 0x01       ; 1
 690:   0e c0           rjmp    .+28            ; 0x6ae <main+0x21c>
 692:   81 e2           ldi     r24, 0x21       ; 33
 694:   91 e0           ldi     r25, 0x01       ; 1
 696:   0b c0           rjmp    .+22            ; 0x6ae <main+0x21c>
 698:   88 e2           ldi     r24, 0x28       ; 40
 69a:   91 e0           ldi     r25, 0x01       ; 1
 69c:   08 c0           rjmp    .+16            ; 0x6ae <main+0x21c>
 69e:   8f e2           ldi     r24, 0x2F       ; 47
 6a0:   91 e0           ldi     r25, 0x01       ; 1
 6a2:   05 c0           rjmp    .+10            ; 0x6ae <main+0x21c>
 6a4:   86 e3           ldi     r24, 0x36       ; 54
 6a6:   91 e0           ldi     r25, 0x01       ; 1
 6a8:   02 c0           rjmp    .+4             ; 0x6ae <main+0x21c>
 6aa:   8d e3           ldi     r24, 0x3D       ; 61
 6ac:   91 e0           ldi     r25, 0x01       ; 1
 6ae:   0e 94 97 01     call    0x32e   ; 0x32e <Print::println(char const*) [clone .constprop.3]>
 6b2:   1c c0           rjmp    .+56            ; 0x6ec <main+0x25a>

Why do you care? A compare and conditional jump is about two instructions; can't you just trust that compiler makes a "good enough" decision about which to use? If it guesses wrong, then SOME cases of your switch might take a couple of extra instructions (and some will be slightly faster...)

Thank you for your analysis

I know that if you have a simple set of choices, there is not going to be a huge benefit to a jump table.
I was testing with a relatively small set. What I really care about is a command parser that creates substantially larger table. An if/else chain would be horrible in this situation.

My query started because I couldn't find any actual information on how the compiler addressed switch statements. C code is convenient, but I find that all too often, programmers assume that compilers always do a good job. This can be a very bad assumption when memory and speed are limited.

With the DSP processors I use, I can look at each line of C and the resulting assembly. This is really informative. It would be helpful if the Arduino environment made it easier to do something similar.
When you can see the assembly, you also get an appreciation on how efficient (or inefficient) a simple C function can be. This might suggest coding something a little different even if you never write anything in assembly.

Al

With the DSP processors I use, I can look at each line of C and the resulting assembly. This is really informative. It would be helpful if the Arduino environment made it easier to do something similar.
When you can see the assembly, you also get an appreciation on how efficient (or inefficient) a simple C function can be. This might suggest coding something a little different even if you never write anything in assembly.

This is fine for low to no levels of optimization, but once you start really squeezing out the performance, the instructions might not have a clear one-tone correspondence (cf, loop unrolling, expression hoisting) to the C code.

ETA:
And if you diddle when the optimization level is low to get good assembler generation, you might hamstring the compiler at larger levels of optimization. One reason why the "register" directive has always been just a suggestion.

aclark:
With the DSP processors I use, I can look at each line of C and the resulting assembly. This is really informative. It would be helpful if the Arduino environment made it easier to do something similar.

I'm fairly sure there is a compiler option to interleave the source code as comments in the assembler listing. To change compiler options I think you have to run the commands manually. Use the verbose build output option in Preferences and copy the command lines from the verbose output.

I know you used to be able to get that. IIRC, with lto enabled, you can't get the interleaved source and assembler anymore (but your sketches compile 10-20% smaller)

johnwasser:
I'm fairly sure there is a compiler option to interleave the source code as comments in the assembler listing. To change compiler options I think you have to run the commands manually. Use the verbose build output option in Preferences and copy the command lines from the verbose output.

You don't have to do this manually. The standard Arduino IDE (tested on 1.8.0) creates an .elf file. For Windows this is in your AppData\Local\Temp\arduino_build_xxxxx directory.
You can then use avr-objdump -S -l -C  [file.elf] to get an interleaved source/assembly output. Many other options as well. In Windows the avr-objdump.exe file is installed at C:\Program Files (x86)\Arduino\hardware\tools\avr\bin

avr-objdump -S -l -C  [file.elf]

Heh. That MIGHT work. I used it to generate the listing I posted...

  1. lto obfuscates things a lot. It might be better in a real program; the example inlined Serial.read()...
  2. there's been a bug, off and on, where the .elf files don't get annotated properly with the parent directory of the source. Looks like 1.8.1 doesn't like "unsaved" files, for instance.
  3. Optimization obfuscates things some more.

Here's the objdump output after I save the file:

 6c2:   ec 5c           subi    r30, 0xCC       ; 204
 6c4:   ff 4f           sbci    r31, 0xFF       ; 255
 6c6:   0c 94 38 04     jmp     0x870   ; 0x870 <__tablejump2__>
/Applications/arduino/Arduino-1.8.1.app/Contents/Java/portable/sketchbook/casejumptable/casejumptable.ino:15
      case 1:
        Serial.println("ctrl-A");
 6ca:   83 e1           ldi     r24, 0x13       ; 19
 6cc:   91 e0           ldi     r25, 0x01       ; 1
 6ce:   02 c0           rjmp    .+4             ; 0x6d4 <main+0x184>
/Applications/arduino/Arduino-1.8.1.app/Contents/Java/portable/sketchbook/casejumptable/casejumptable.ino:18
        break;
      case 2:
        Serial.println("ctrl-B");
 6d0:   8a e1           ldi     r24, 0x1A       ; 26
 6d2:   91 e0           ldi     r25, 0x01       ; 1
 6d4:   0e 94 f6 01     call    0x3ec   ; 0x3ec <Print::println(char const*) [clone .constprop.3]>
 6d8:   79 c0           rjmp    .+242           ; 0x7cc <main+0x27c>
/Applications/arduino/Arduino-1.8.1.app/Contents/Java/portable/sketchbook/casejumptable/casejumptable.ino:21
        break;
      case 3:
        Serial.println("ctrl-C");
 6da:   81 e2           ldi     r24, 0x21       ; 33
 6dc:   91 e0           ldi     r25, 0x01       ; 1
 6de:   fa cf           rjmp    .-12            ; 0x6d4 <main+0x184>
/Applications/arduino/Arduino-1.8.1.app/Contents/Java/portable/sketchbook/casejumptable/casejumptable.ino:24
        break;
      case 4:
        Serial.println("ctrl-D");
 6e0:   88 e2           ldi     r24, 0x28       ; 40
 6e2:   91 e0           ldi     r25, 0x01       ; 1
 6e4:   f7 cf           rjmp    .-18            ; 0x6d4 <main+0x184>
/Applications/arduino/Arduino-1.8.1.app/Contents/Java/portable/sketchbook/casejumptable/casejumptable.ino:27
        break;
      case 5:
        Serial.println("ctrl-E");
 6e6:   8f e2           ldi     r24, 0x2F       ; 47
 6e8:   91 e0           ldi     r25, 0x01       ; 1
 6ea:   f4 cf           rjmp    .-24            ; 0x6d4 <main+0x184>
/Applications/arduino/Arduino-1.8.1.app/Contents/Java/portable/sketchbook/casejumptable/casejumptable.ino:30
        break;
      case 6:
        Serial.println("ctrl-F");
 6ec:   86 e3           ldi     r24, 0x36       ; 54
 6ee:   91 e0           ldi     r25, 0x01       ; 1
 6f0:   0e 94 f6 01     call    0x3ec   ; 0x3ec <Print::println(char const*) [clone .constprop.3]>
 6f4:   52 e4           ldi     r21, 0x42       ; 66
 6f6:   a5 2e           mov     r10, r21
 6f8:   51 e0           ldi     r21, 0x01       ; 1
 6fa:   b5 2e           mov     r11, r21