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
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?
> 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
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`.
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.
It is still possible that a later pass arranges jump targets to avoid false sharing of their entries (addresses) in prediction mechanisms and such.
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
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.
>The LLVM patch was rejected a decade ago
And what was the reasoning?
Also you could try again, many things may have changed since then including who maintains the code.
No idea. Most maintainers suck
> 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
All the values are divisible by 8, so it could do it like this:
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`.
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!
Why the indirection? - why not have the jump table reference f0..fX directly rather than jumping to a jump?
[flagged]
This one was interesting, especially its name :)
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.
It is still possible that a later pass arranges jump targets to avoid false sharing of their entries (addresses) in prediction mechanisms and such.
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!)