I once played around with having a very large switch statement (all mac address manufactors in one switch) and in LLVM it would compile fine without optimizations, but if I turned optimizations on it would just spend around half an hour compiling it. I think GCC did it faster, but its been some time ago since I did it. In the Rust crate that was the reasons for all this I just ended up doing perfect hashing which compiled much much faster.
> The switch in sparse_8 could be simplified by dividing x by eight before the jump. Interestingly, gcc doesn't find this simplification.<p>It could not because that would ensure that 7 values for each case would be handled by function calls instead of the default case - 0/8 is 0, but 3/8 is also 0
All the values are divisible by 8, so it could do it like this:<p><pre><code> cmp eax,40
ja <return 0>
test eax,7
jnz <return 0>
jmp JumpTable[rax]</code></pre>
Okay. Good point, that is quite a bit shorter than I first thought of<p>A rough benchmark of a version of that against the original shows it to be close to twice as fast for unpredictable input with GCC (4.5 ns vs 2.72 ns) on my old machine. With predictable input where x values often are the same the original version is quicker<p><pre><code> int sparse_8_jump(int x, int val) {
unsigned int idx = (unsigned int)x >> 3;
if (idx > 5)
return 0;
if (x & 7)
return 0;
switch (idx) {
case 0:
return f0(val);
case 1:
return f1(val);
case 2:
return f2(val);
case 3:
return f3(val);
case 5:
return f4(val);
default:
return 0;
}
}</code></pre>
Think it could also be done with rotate, but unsure if it'd be faster:<p><pre><code> mov ecx, eax
ror eax, 3
cmp eax, 5
ja <return 0>
jmp JumpTable[rcx]</code></pre>
Reducing the range would have been useful to reduce the size of a jump table, but when you have a decision tree then it does not matter.<p>... unless the size of immediate parameters would have affected code size. In the example code however, all constants fit in an `imm8` parameter to `cmp`.
What a shame for clang and gcc! They still don't implement perfect hashes for large sparse switch tables. I did that recently for my rcc C compiler, and it was just a single day of work. Esp. beneficial for unicode work. The LLVM patch was rejected a decade ago. Gcc has several unicode patches sitting in branches, which would also need that
Compiler optimizations are a trade-off between compile time, runtime, and code size, mediated by the availability of developer time.<p>Perfect hashing for switch tables is useful mostly for large, sparse switches, but <i>hot</i> large, sparse switches are rare, and the closest examples I can think of (e.g., parse tables) are themselves likely generated from other tools, which could itself be changed in lieu of the compiler. It really doesn't come across as a useful optimization to try implementing in a compiler.
Maybe LLVM doesn't have time for performance improvements due to still reading through 30000 open issues, which also include miscompilations leading to incorrect results at runtime?<p>For example, my bug report that `+= 2` is broken has not been acknowledged (read?) by anyone for 3 years:<p><pre><code> const size_t n = 13; // triggers the issue
#pragma omp parallel for
for (uint32_t i = 0; i < n; i += 2) { // counts PAST 13!
</code></pre>
<a href="https://github.com/llvm/llvm-project/issues/70687" rel="nofollow">https://github.com/llvm/llvm-project/issues/70687</a>
That's true. restrict is also still broken there. 30000 open issue is even worse than gcc
#pragma omp<p>Ahh, there it is! This issue isn't being tended to because it will resolve itself with the imminent death of OpenMP.
Would like to hear more about the performance characteristics. Do you perfect hash to a contiguous range and then use a jump table, or do you perfect hash directly to relative offsets to basic blocks?
I'd bet because that's probably no better, that's it.<p>>The LLVM patch was rejected a decade ago<p>And what was the reasoning?
Why the indirection? - why not have the jump table reference f0..fX directly rather than jumping to a jump?
That optimisation is simply missing.<p>Each `jmp` to f0..fX is an optimisation of a `call` and a `ret`, and probably done in a separate pass after the switch-case code has already been expanded.<p>The `mov edi, esi` at the top of the function is also an optimisation, most likely done during the register allocation pass.
This was only possible because all functions take the same value in the same register. Otherwise, there would probably have been also a `mov` before each of the calls.
gcc unfortunately cannot do this (and also not the related optimization of using word/byte offsets for the jump table, which LLVM can do) because it only has approximate estimation of code size. If it got the code size wrong it would be a mis-compilation. This is related to it not using an integrated assembler.
[flagged]
I assume 34 in the compact_7() one was supposed to be 35, and edx was supposed to be used at some point in the bittest() one (unless i'm missing something lol)
I remember having implemented similar things in JavaScript (by generating code), for immutable Maps and Sets - no significant performance gain in modern engines. For regular expressions of complex unicode ranges, the speedup was around 2x!
In order to peak into hardware speculation/BTB, having a look atswitch lowering seems a good way. Big switches will go into serious convolution to please that hardware since by definition this is a source of a lot of branch mispredicitions.
There is surprisingly little about the proper feeding of advanced hardware in that code, two or three constants in cost calculations of which one or two are hardware-dependent.<p>It is still possible that a later pass arranges jump targets to avoid false sharing of their entries (addresses) in prediction mechanisms and such.
This one was interesting, especially its name :)
[flagged]