> The switch in sparse_8 could be simplified by dividing x by eight before the jump. Interestingly, gcc doesn't find this simplification.
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
rep_lodsb 2 days ago [-]
All the values are divisible by 8, so it could do it like this:
cmp eax,40
ja <return 0>
test eax,7
jnz <return 0>
jmp JumpTable[rax]
LarsKrimi 2 days ago [-]
Okay. Good point, that is quite a bit shorter than I first thought of
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;
}
}
ack_complete 2 days ago [-]
Think it could also be done with rotate, but unsure if it'd be faster:
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.
... 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`.
rurban 2 days ago [-]
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
jcranmer 2 days ago [-]
Compiler optimizations are a trade-off between compile time, runtime, and code size, mediated by the availability of developer time.
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.
bobmcnamara 2 days ago [-]
It comes up in emulators and VMs, and indeed those are often tool generated.
flohofwoe 2 days ago [-]
Hmm, IME at least in emulators the switch tables usually have enough 'structure' that GCC or Clang have no trouble turning them into jump tables.
bobmcnamara 22 hours ago [-]
That usually works well enough for risc code.
As a massage, I wish there was a flag to set a minimum branch target size. If all the branch targets for a switch are the same size then you can often turn the jump table into a multiply-accumulate, or sometimes even a shift and add.
2 days ago [-]
nh2 2 days ago [-]
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?
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!
Ahh, there it is! This issue isn't being tended to because it will resolve itself with the imminent death of OpenMP.
SubjectToChange 2 days ago [-]
OpenMP is arguably in a better place today than it was ten years ago. For instance, MSVC added support for newer OpenMP standards and implementations now support genuine device offloading. Indeed, OpenMP is probably the most popular parallel programming interface for C/C++/Fortran in use today.
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.
jamiejquinn 2 days ago [-]
Now there's a bold statement! What makes you think OpenMP is on the way out?
rurban 2 days ago [-]
That's true. restrict is also still broken there. 30000 open issue is even worse than gcc
SubjectToChange 2 days ago [-]
Comparing all of the open issues of the llvm-project to GCC is obviously unfair. For instance over 500 issues are related to MLIR, 1700 issues are related to BOLT/lld/lldb, almost 3000 issues are related to the various clang tools that GCC does not offer (clang-tidy, clang-format, clang-doc, etc), another 442 issues are related to HLSL support, 281 issues belong to LLVM libc, various sanitizers have another 200 open issues, etc. Not to mention the extra compatibility clang offers, e.g. clang-cl, nor the fact that clang tries to be compatible with (undocumented) GCC idiosyncrasies.
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.
Both should be zero. In all my compilers I'm thriving for zero.
aw1621107 2 days ago [-]
> restrict is also still broken there.
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?
Hrm, interesting. First time I've heard of such a thing. Would have expected the Rust devs to have rolled back emitting noalias if it were still causing miscompiles. A quick glance through the bug tracker didn't turn up anything obvious, though I wouldn't be surprised if I just missed it.
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.
RossBencina 2 days ago [-]
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?
If the problem with the previous attempt was the same as with the more recent one, well duh. Just because this approach is new and clever doesn't mean it should always be used. It should be a last resort if cost estimates for other approaches are higher than some threshold where perfect hashing is likely to be cheaper.
rurban 2 days ago [-]
[flagged]
saagarjha 2 days ago [-]
In this case you're not doing much better.
rurban 2 days ago [-]
[flagged]
saagarjha 2 days ago [-]
Then provide a link to your submission and we can see this for ourselves.
rurban 1 days ago [-]
Why should I submit a patch for project when I know it will be rejected? Someone else did about a decade ago.
saagarjha 1 days ago [-]
I mean, it seems like you are probably not submitting patches to anything at all with that attitude
rurban 1 days ago [-]
Do have the FSF CLA? I do
saagarjha 1 days ago [-]
No most of the projects I've contributed to don't require it anymore
erk__ 2 days ago [-]
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.
zamalek 2 days ago [-]
> The compiler is able to implement them as a decision tree (even though maybe it shouldn't)
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.
tsukikage 2 days ago [-]
Why the indirection? - why not have the jump table reference f0..fX directly rather than jumping to a jump?
Findecanor 2 days ago [-]
That optimisation is simply missing.
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.
andikleen2 2 days ago [-]
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.
cowlevel 1 days ago [-]
Why does it need to know code size to put function addresses in the jump table?
jacquesm 20 hours ago [-]
Not necessarily function addresses but jump table targets. Those can be in the middle of a subroutine. If you don't know the addresses then you need to keep them symbolic and if they're symbolic they are subject to change, for instance they could end up 'on the bubble' of fitting in a small offset or they might just spill over into a larger one. And that would change the data type of the jump table. If you have a built in binary code generator then will know the addresses exactly at compile time.
yksalun 2 days ago [-]
[flagged]
sylware 2 days ago [-]
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.
ahartmetz 2 days ago [-]
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.
It is still possible that a later pass arranges jump targets to avoid false sharing of their entries (addresses) in prediction mechanisms and such.
sylware 2 days ago [-]
Just look at the assembly output of significantly sized switch statements (with good random values): it's scary :)
Obvsiously engaging in pleasing as much as it can speculative/BTB hardware (to the cost of memory tables!)
ahartmetz 2 days ago [-]
I've seen it and it's not pretty, but hopefully fast. You kinda need to single-step it in assembly to be (somewhat) able to see what it does.
sylware 1 days ago [-]
Yep, this is a big issue with compilers: you cannot snoop in and skim the code even to have rough understanding of what it does because you need to embrace and be proficient, nearly all the time, with their 'hardcore abstracted' model.
I did dive in LLVM a long time ago, and OMG... we have to get rid of it.
On the long term, gcc and clang are cooked, better move to binary specifications with various ISA implementations. Ofc here, we would need a bit of optimization knowledge in order to write assembly code not too much under-performant (because the goal here would not be speed, but independence from compilers!)
But it is not that much horrible: most performant micro-architectures use the same speculative concepts, then it is a matter to find the sweet spot between all of them: a good generic conditional branch machine instruction layout of a cache line with some additional care for non-conditional branch, and use branchless logic as much as you can. It is a matter to know such patterns: hopefully all those "coding AIs" can help (never tested them, cannot access them).
Andi 2 days ago [-]
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!
p-t 2 days ago [-]
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)
arsalan17 2 days ago [-]
This one was interesting, especially its name :)
yarkwright 2 days ago [-]
[flagged]
Rendered at 16:15:32 GMT+0000 (UTC) with Wasmer Edge.
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
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
... 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`.
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.
As a massage, I wish there was a flag to set a minimum branch target size. If all the branch targets for a switch are the same size then you can often turn the jump table into a multiply-accumulate, or sometimes even a shift and add.
For example, my bug report that `+= 2` is broken has not been acknowledged (read?) by anyone for 3 years:
https://github.com/llvm/llvm-project/issues/70687Ahh, 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.
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.
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.
>The LLVM patch was rejected a decade ago
And what was the reasoning?
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.
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.
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!)
I did dive in LLVM a long time ago, and OMG... we have to get rid of it.
On the long term, gcc and clang are cooked, better move to binary specifications with various ISA implementations. Ofc here, we would need a bit of optimization knowledge in order to write assembly code not too much under-performant (because the goal here would not be speed, but independence from compilers!)
But it is not that much horrible: most performant micro-architectures use the same speculative concepts, then it is a matter to find the sweet spot between all of them: a good generic conditional branch machine instruction layout of a cache line with some additional care for non-conditional branch, and use branchless logic as much as you can. It is a matter to know such patterns: hopefully all those "coding AIs" can help (never tested them, cannot access them).