Real to complex and complex to real transforms

[calebzulawski]

In these special cases, the imaginary reads could be replaced with zeros, and the writes elided.

[smu160]

Hi @calebzulawski,

I think I utilized real to complex in an example, here. I'm going to assume a specialized version for real to complex would offer better performance since we'd avoid doing anything with the zeros.

If that's the case, we can have two separate PR's for closing out this issue -- I'll start a new PR now to implement real-to-complex. I think we can call it rfft_64 and rfft_32.

A future PR can address the complex-to-real version. Thanks!

Best,
Saveliy

[calebzulawski]

I wonder if it might make sense possibly to use a trait? I could see the various supported types ballooning, so you could have something like Fft<In, Out> for Planner?

[smu160]

@calebzulawski

I'm not well-versed in using traits in Rust. I'm happy to try out any of your suggestions. If you don't mind, please feel free to expand on this idea, and I will try it out

[astral4]

I wonder if it's possible for this library to do what realfft does. Packing real-valued data into shorter complex-valued sequences seems to be significantly faster than just setting all imaginary parts to 0. Does the power-of-two input length requirement make this unviable?

[smu160]

@astral4

I may be way off base here, so please correct me if I'm wrong. From what I gather, we can create a rfft_64 (and rfft_32) that simply takes a single input slice of &mut [f64] or &mut [f32]. This would be the real components we care about. The advantage I see here is we'd spend, potentially, significantly less CPU cycles. Now, I'm not sure if this would be as good as what realfft does.

For example, take a look at the implementation of fft_butterfly_n_simd (which can be found here)

@calebzulawski I'm curious to here your thoughts here as well.

Thank you!

Best,
Saveliy

Edit: @astral4 with respect to the viability of what realfft does and the power of 2 requirement, I am not sure. I need to look into what realfft does.

Edit 2: A lot of what I wrote above was nonsensical 😅. Please disregard.

[smu160]

@astral4

I wonder if it's possible for this library to do what realfft does. Packing real-valued data into shorter complex-valued sequences seems to be significantly faster than just setting all imaginary parts to 0. Does the power-of-two input length requirement make this unviable?

I finally read up on the approached you described, here. I don't see why the power-of-two requirement would make this nonviable. It's definitely the best way forward given that it allows us to reduce memory usage and run-time by 2x (in comparison to using a c2c fft and just setting the imags vec to all 0s). From what I gather, the steps would be as follows:

0. accepts a reference to the real-valued signal
1. converts the real-valued signal into a complex-valued signal
   note that in our case, that means we basically split into evens/odds by putting all even-indexed elements into a reals vec and all odd-indexed elements into the imaginaries vec
2. run fft_64 or fft_32 on the complex-valued signal
3. "untangle" -- this is the step I'm reading up on now

Work on this implementation will continue in #26. Thank you!

Best,
Saveliy

[mfreeborn]

I wonder what's left on PR #26 ? Looks like it got pretty close to being covered before activity stopped? I'm interested in an rfft implementation for processing audio signals.

[Shnatsel]

Right now we're looking into getting the basics right before we add more features.

I'd like to know more about your use case to know what to optimize for. Specifically, are you calling PhastFT from Rust or from Python? What is the size of the data you're going to process - is it always fixed or is it variable, and what is the ballpark?

[mfreeborn]

I'd be calling the library from Rust and the length is fixed at 192k. Rounding up to the next power of 2 isn't a big issue, though, depending on what works out the fastest.

I'm using the aforementioned realFFT at the moment, and happily so, but I like to compare different libraries where possible.

In particular, I've been looking at fearless simd, because I'd like users of my application to get optimal performance on their CPUs even when I compile the binary with no particular target features enabled.

[Shnatsel]

There are massive gains to be had with newer instruction sets at size 256k. I can see RustFFT exploit AVX for a 3x speedup.

We've been using std::simd but switched to wide so that PhastFT would work on stable. This broke multiversioning and our code now always lowers into SSE without -C target-cpu=native. Worse, even with -C target-cpu=native it seems that our current implementation via wide fails to exploit AVX-512 - performance barely changes compared to the SSE version.

So now I'm also looking into fearless_simd. I think that's our best bet for multiversioning on stable Rust. But fearless_simd itself is somewhat immature, so I can't promise any specific timeline for porting PhastFT to it.