Switch Lowering in GCC

Posted by signa11 11 hours ago

Counter171Comment33OpenOriginal

Comments

Comment by erk__ 4 minutes 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.

Comment by LarsKrimi 9 hours ago

> 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

Comment by rep_lodsb 7 hours 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]

Comment by ack_complete 25 minutes ago

Think it could also be done with rotate, but unsure if it'd be faster:

  mov ecx, eax
  ror eax, 3
  cmp eax, 5
  ja  <return 0>
  jmp JumpTable[rcx]

Comment by LarsKrimi 6 hours 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;
        }
    }

Comment by Findecanor 7 hours ago

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`.

Comment by rurban 9 hours 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

Comment by jcranmer 3 hours 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.

Comment by bobmcnamara 2 hours ago

It comes up in emulators and VMs, and indeed those are often tool generated.

Comment by flohofwoe 1 hour 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.

Comment by 1 hour ago

Comment by nh2 6 hours 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!
https://github.com/llvm/llvm-project/issues/70687

Comment by rurban 6 hours ago

That's true. restrict is also still broken there. 30000 open issue is even worse than gcc

Comment by stefan_ 3 hours ago

#pragma omp

Ahh, there it is! This issue isn't being tended to because it will resolve itself with the imminent death of OpenMP.

Comment by jamiejquinn 58 minutes ago

Now there's a bold statement! What makes you think OpenMP is on the way out?

Comment by RossBencina 7 hours 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?

Comment by rurban 5 hours ago

See my docs. There are several cases: https://github.com/rurban/rcc/blob/main/docs/rcc.md#-o1-and-...

Comment by Sopel 3 hours ago

why is it so slow? it's around 50x slower than I would have expected for numbers https://github.com/ConstexprCore/perfect_hash

Comment by garaetjjte 4 hours ago

[flagged]

Comment by tester756 8 hours ago

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?

Comment by ahartmetz 7 hours ago

Also you could try again, many things may have changed since then including who maintains the code.

Comment by saagarjha 6 hours ago

It seems like someone did: https://github.com/llvm/llvm-project/issues/96971. However the performance implications of this was not well explored there

Comment by ahartmetz 3 hours ago

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.

Comment by rurban 7 hours ago

[flagged]

Comment by saagarjha 6 hours ago

In this case you're not doing much better.

Comment by rurban 5 hours ago

I strongly reject that.

Comment by saagarjha 3 hours ago

Then provide a link to your submission and we can see this for ourselves.

Comment by p-t 2 hours 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)

Comment by tsukikage 8 hours ago

Why the indirection? - why not have the jump table reference f0..fX directly rather than jumping to a jump?

Comment by Findecanor 7 hours 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.

Comment by andikleen2 6 hours 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.

Comment by yksalun 7 hours ago

[flagged]

Comment by Andi 8 hours 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!

Comment by sylware 9 hours 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.

Comment by ahartmetz 7 hours 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.

Comment by sylware 7 hours 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!)

Comment by arsalan17 10 hours ago

This one was interesting, especially its name :)

Comment by yarkwright 4 hours ago

[flagged]