`dispatch!` is expensive

[Shnatsel]

In PhastFT for smaller sizes I'm calling dispatch! three times when running an FFT operation on 512 bytes of data (64-long batch of f64) and it is degrading performance by 25% (-20% throughput) measured as of commit https://github.com/QuState/PhastFT/tree/e5fcd61f3d540fcef9f8d60173dbfbe777c02e40

Meanwhile RustFFT with its handwritten dispatch does not suffer any penalty at all, and in fact is slightly slower under -C target-cpu=native than it is under its regular dynamic dispatch.

This overhead needs to be removed for code based on fearless_simd to be competitive with handwritten dynamic dispatch.

perf diff and profiling with samply both point to these dispatch! calls as a major source of slowdown: https://github.com/QuState/PhastFT/blob/c7ea3d7aef474e53233834354364fa50bbb0ba6e/src/algorithms/dit.rs#L259-L260
Profile with -C target-cpu=x86-64-v3: https://share.firefox.dev/3LMqjuI
Profile with dynamic dispatch: https://share.firefox.dev/3NTwJZw

I'm not sure what the cause is. I wouldn't expect a handful of perfectly predictable branches to tank performance. Perhaps dispatch! results in subotimal codegen, or perhaps I'm just pushing the boundaries of dynamic dispatch and need a facility to get a function pointer and store it in a struct for reuse instead of just reusing a cached Level.

[Ralith]

The API intent is that you call dispatch! once at the very top level. That said, it's confusing that handwritten dispatch wouldn't be identical -- how does it compare to the macroexpansion of dispatch!?

[Shnatsel]

The README instructs to determine the Level once at the top level, which makes sense.

Doing only a single dispatch! per program is not currently advised by the README and is less practical - every single function then needs to be wrapped in monomorphised, causing a lot of binary bloat and also ergonomics issues with the functions being generic over SIMD, requiring #[inline(always)], requiring vectorize(...) to call each other.

In this case I could probably cut down the overhead to a single dispatch! instead of three, but it the call is still more expensive than I would expect.

[Shnatsel]

I've refactored the code to only call dispatch! once per operation: QuState/PhastFT#72

That still causes a 10% overhead for FFT on input length 64.

I don't know how to reduce the overhead further without having a facility that gives me a function pointer to cache for later instead of going through dispatch! every time.

And it still feels like a few perfectly predictable branches in dispatch! should not create as much overhead as they do.

[Shnatsel]

I've prototyped storing a function pointer instead of branching in https://github.com/Shnatsel/fearless_simd/tree/dispatch-for-later but it didn't close the gap, the change is slight if present at all.

So it doesn't look like branching is to blame. There must be some other overheads that are the cause for this gap.

[Ralith]

Yeah, usually branching is faster if anything.

[Ralith]

perhaps I'm just pushing the boundaries of dynamic dispatch and need a facility to get a function pointer and store it in a struct for reuse

Would this work?

let my_fn: Box<dyn Fn()> = dispatch!(level, simd => Box::new(move || ...));