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
cmp eax,40
ja <return 0>
test eax,7
jnz <return 0>
jmp JumpTable[rax]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
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;
}
} mov ecx, eax
ror eax, 3
cmp eax, 5
ja <return 0>
jmp JumpTable[rcx]... 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`.
It is still possible that a later pass arranges jump targets to avoid false sharing of their entries (addresses) in prediction mechanisms and such.
Obvsiously engaging in pleasing as much as it can speculative/BTB hardware (to the cost of memory tables!)
>The LLVM patch was rejected a decade ago
And what was the reasoning?
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.
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.
Sometimes a decision tree is definitely faster. When developing System.HashCode, I used a switch (which I think always compiles to a jump table in .Net - at least my case did back then). This was for the trailing non-block sized bytes, I think. It was either suggested, or I decided to try, a decision tree and it was significantly faster. This was _many_ years back, so I don't have the figures, but they can be better in some scenarios.
For example, my bug report that `+= 2` is broken has not been acknowledged (read?) by anyone for 3 years:
const size_t n = 13; // triggers the issue
#pragma omp parallel for
for (uint32_t i = 0; i < n; i += 2) { // counts PAST 13!
That's a bit surprising to me given how heavily Rust uses the underlying mechanisms. Do you mean specifically how restrict is used in Clang or is there still something in LLVM that is broken?
For what it's worth, according to Godbolt the test program in your probe seems to work correctly for Clang 12.0.0 and later, which IIRC corresponds to when Rust (re-(re-?))enabled emitting noalias.
Comparing open issues in the llvm-project repository is basically equivalent to comparing the open issues in GCC, binutils-gdb, glibc, and various utilities. Moreover, the LLVM project is intended as a compiler infrastructure/library framework, so it naturally has a larger surface area for bugs/issues relative to GCC. I mean, it’s not like GCC offers a generic API to interact with GIMPLE, or any other of its numerous internal representations.
gcc: 244 fails
clang: 826 fails
Ahh, there it is! This issue isn't being tended to because it will resolve itself with the imminent death of OpenMP.
Sure, OpenMP is not a pretty API, nor is it likely to yield best-in-class performance. But OpenMP is highly portable, it enjoys first-class support GCC and LLVM/clang, and it’s very straightforward to get “good enough” performance with minimal code changes. Personally, I think it’s wonderful.
Perfect hashing for switch tables is useful mostly for large, sparse switches, but hot 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.
arsalan17•1d ago