3 ms·
Clang is able to convert the code to a jump table, though GCC can't. https://c.godbolt.org/z/Wq65j4rrM https://c.godbolt.org/z/Wq65j4rrM > What would it take
by xoranth 3y ago
Clang is able to convert the code to a jump table, though GCC can't.
https://c.godbolt.org/z/Wq65j4rrM https://c.godbolt.org/z/Wq65j4rrM
> What would it take to make the compiler optimize this code meaningfully?
To make GCC compile the code meaningfully, it suffices to add a bunch of else statements:
https://c.godbolt.org/z/z4KvxnbfG https://c.godbolt.org/z/z4KvxnbfG
In fact, GCC gets very clever at -O3.
(what matters is whether the compiler can turn the sequence of ifs into a switch statement, then both compilers have special logic to generate a lookup table.)
- gwern 3y agoInteresting. I only know a little assembler, so I can't tell what -03 is producing there, but I know enough to see that it's doing some sort of loop bouncing between even/odd label choice. Is that now a constant-size binary (if still linear time)?
- xoranth 3y agoWhat GCC is doing at -O3 is encoding even (resp. odd) numbers in a bitmap. 43690 = 0xAAAA = 0b1010101010101010 21845 = 0x5555 = 0b0101010101010101 Then sal rax, cl test eax, 43690 jne .L3 // .L3 mov edi, OFFSET FLAT:.LC1 // This is a pointer to the string "odd" call puts jmp .L2 is equivalent to C: if ((1 << number) & 0xAAAA) { puts("odd"); // x64 is little endian } So execution is constant time (it only needs to check against two constants), there's no loop. It should be advantageous compared to a jump table because it doesn't have to do two indirect jumps (though you now have branches that might mispredict). Edit: code formatting.