Reduce dynamic dispatching

[dannys4]

There's a bit of dynamic dispatching going on every time that fft! is called recursively. This is reasonably expensive. What should happen is that either a lambda expression is used or there's a central fft! function that does the dispatch itself (which should be cheaper than the compiler doing the dispatching since I know more about the functions and can specialize it better).

[andreasnoack]

I've linked two competing PRs that addresses the issue here

current version

julia> @btime fft(x) setup=(x=complex.(randn(5*7*11*13)));
  363.959 μs (6380 allocations: 307.50 KiB)

Function barrier approach #57

julia> @btime fft(x) setup=(x=complex.(randn(5*7*11*13)));
  300.417 μs (709 allocations: 181.42 KiB)

Enum approach #56

julia> @btime fft(x) setup=(x=complex.(randn(5*7*11*13)));
  292.959 μs (68 allocations: 166.48 KiB)

Both based on this and the implementation, I think that the enum solution is better.

[dannys4]

I'm going to link the related #59 because I have a feeling that it might be worth considering a few common use-cases that people tend to like. While it's unlikely that the sizes will be powers of four, if this goes into data kernel density estimation or whatever for example, you're "probably" going to have something divisible by four or sixteen. I'm not sure what they do to benchmark, e.g., FFTW; I'm more familiar with HeFFTe, which really they only benchmarked on tensorized powers of four (not really the use-case for this package I think).

[dannys4]

On a slightly different note, you're the expert here, but it looks to me like the difference is really being made up in the memory allocations. If that's the truth, then benchmarking fft (instead of the inplace variant) may give misleading results since the savings might just be in the plan/callgraph generation, particularly for such quick benchmarks.

[andreasnoack]

Indeed it would be useful with a more complete benchmark suite. Here is a larger example that only measures the evaluation part. I've made some ad hoc benchmarks and, generally, most of allocation overhead is in the evaluation of the CompositeFFT and not in the Callgraph generation.

current version

julia> @btime p*x setup=(x = randn(5^8); p = plan_fft(x));
  54.024 ms (1780258 allocations: 49.60 MiB)

Function barrier approach #57

julia> @btime p*x setup=(x = randn(5^8); p = plan_fft(x));
  38.444 ms (370673 allocations: 19.52 MiB)

Enum approach #56

julia> @btime p*x setup=(x = randn(5^8); p = plan_fft(x));
  35.592 ms (6 allocations: 11.92 MiB)

[dannys4]

Would it be okay with you then if I merged #56 but kept #57 open for the time being? I think there's some ability to hybridize the approaches in the future, and this would prove helpful when looking at what a benchmark suite should provide.

[andreasnoack]

Yes. That sounds good to me.

[andreasnoack]

While there is more performance work to do,I think #56 got rid of the dynamic dispatch overhead so should we close this issue?

[dannys4]

Yeah sounds good. For reference, I just ran a simple workload through SnoopCompile and got this:

julia> using SnoopCompile, SnoopCompileCore, ProfileView, FFTA

julia> x = randn(3*4*5*7*11*13)

julia> @snoop_inference fft(x);

julia> tinf = @snoop_inference [fft(x)*0. for _ in 1:100];

julia> fg = flamegraph(tinf)

All the red at the base of the plot which represents runtime dispatches just comes from the array reduction (used to make sure the tracing doesn't run too fast) and not the FFT itself. Thought I'd run this to make sure the assumption that runtime dispatch is virtually "fixed" is reasonable.

[dannys4]

Probably reasonable to check that things work with JET and all that though.