Re: [TriEmbed] optimized switch statements Re: Hacking a fake vintage radio (with Arduino + Pi 0)

Jon Wolfe via TriEmbed Wed, 01 Jul 2020 16:19:08 -0700

Gcc already does use jump tables without the user having to force anything. Below is a simple C program followed by the X64 assembly language. Notice the table of addresses and the jump through rax. But what the programmer has to do is craft their case values to make a "dense" range that is mostly consecutive. How smart this is, I don't recall (e.g. if case values 4, 8, 12, 16 would be recognized as easy to compute an index with, how many "gaps" in the case value range would be tolerated, etc). But also the compiler won't use the jump table until there are more than a handful of cases (the example below, with only three cases compiled into sequences of tests and conditional branches because the compiler writer judged the tradeoff of speed and space wasn't worth it).

The reason I'm familiar with this is that the gcc compiler's smarts gave the Linux version of the Java virtual machine an edge with dispatching op codes but the Sun Solaris C++ compiler didn't have the optimization (and was in a 'caretaker state' with no hope of getting the optimization by then, in the early 2000s). But the speed of dispatch was about interpretation and that was an absolute nit for code that executed frequently, as it was automagically compiled into native code by the late 90s and the quality of that native code got better and better over the years.

-Pete

// Just for fun try putting "static" in front of the two int declarations

// (first mystery _import and then also for disgusting_global_side effect) and see what comes out with gcc -S -O4

int mystery_import;int disgusting_global_side_effect;

int main(int argc, char **argv) { switch (mystery_import) { case 0: disgusting_global_side_effect = 123; break; case 1: disgusting_global_side_effect = 124; break; case 2: disgusting_global_side_effect = 125; break; case 3: disgusting_global_side_effect = 126; break; case 4: disgusting_global_side_effect = 127; break; case 5: disgusting_global_side_effect = 128; break; } return 0;} .file "dense-switch.c" .text .section .text.startup,"ax",@progbits .p2align 4 .globl main .type main, @functionmain:.LFB0: .cfi_startproc endbr64 cmpl $5, mystery_import(%rip) ja .L2 movl mystery_import(%rip), %eax leaq .L4(%rip), %rdx movslq (%rdx,%rax,4), %rax addq %rdx, %rax notrack jmp *%rax .section .rodata .align 4 .align 4.L4: .long .L9-.L4 .long .L8-.L4 .long .L7-.L4 .long .L6-.L4 .long .L5-.L4 .long .L3-.L4 .section .text.startup.L3: movl $128, disgusting_global_side_effect(%rip).L2: xorl %eax, %eax ret.L5: movl $127, disgusting_global_side_effect(%rip) jmp .L2 movl $123, disgusting_global_side_effect(%rip) jmp .L2.L8: movl $124, disgusting_global_side_effect(%rip) jmp .L2.L7: movl $125, disgusting_global_side_effect(%rip) jmp .L2.L6: movl $126, disgusting_global_side_effect(%rip) jmp .L2 .cfi_endproc.LFE0: .size main, .-main .comm disgusting_global_side_effect,4,4 .comm mystery_import,4,4 .ident "GCC: (Ubuntu 9.3.0-10ubuntu2) 9.3.0" .section .note.GNU-stack,"",@progbits .section .note.gnu.property,"a" .align 8 .long 1f - 0f .long 4f - 1f .long 50: .string "GNU"1: .align 8 .long 0xc0000002 .long 3f - 2f2: .long 0x33: .align 84:

On 7/1/20 2:12 PM, Jon Wolfe via TriEmbed wrote:

This is one of those rare circumstances, imho, where goto can reasonably be used, Dijkstra be damned 😊.

Where I have seen it used like this , it’s an optimization, and doesn’t change the semantics of code flow from a traditional switch-case, and it was wrapped in a macro I think so it could be used, if supported, by the compiler. It’s like putting inline assembly in the code: only do it if the benefit is worth the sacrifice in code portability and maintainability.

I’m not a compiler optimization expert, but the code generation optimization of using a jump table would be at the discretion of the optimizer, using a goto construct would be a way to force that. It may also be the case that the way it is implemented at the machine code level is faster using gotos.

_______________________________________________
Triangle, NC Embedded Computing mailing list


To post message: [email protected]
List info: http://mail.triembed.org/mailman/listinfo/triembed_triembed.org
TriEmbed web site: http://TriEmbed.org
To unsubscribe, click link and send a blank message: 
mailto:[email protected]?subject=unsubscribe

Re: [TriEmbed] optimized switch statements Re: Hacking a fake vintage radio (with Arduino + Pi 0)

Reply via email to