Closed WalterSmuts closed 1 year ago
I've published a crate called constfft. A quite fundamental issue is that it requires knowledge of the size of the fft at compile time.
A less fundamental issue is that rust doesn't seem to be expressive enough right now to express a safe way of working with a RealDft
struct. At least none that I've found yet although I'm still hoping to find something.
Let me know what your thoughts are.
I’m not sure how this would be applied in practice. We obviously can’t precompile every possible FFT size ahead of time, so we’d have to make the planner take a const generic FFT size parameter. A heavy price to pay, so the benefit would need to be worth it - and I’m not sure what the benefits are here.
As for real dft, I went down that path last year and I discovered that you basically have to maintain a second copy of your entire library to support complex to real and vice versa, so it might as well just be a different library.
On Fri, Sep 2, 2022 at 1:21 PM Walter Smuts @.***> wrote:
I've published a crate called constfft https://docs.rs/constfft/latest/constfft/. A quite fundamental issue is that it requires knowledge of the size of the fft at compile time.
A less fundamental issue is that rust doesn't seem to be expressive enough right now to express a safe way of working with a RealDft struct. At least none that I've found yet although I'm still hoping to find something.
Let me know what your thoughts are.
— Reply to this email directly, view it on GitHub https://github.com/ejmahler/RustFFT/issues/93#issuecomment-1235867195, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAI2M6QEXSFSCRFJFON5W3TV4JOTFANCNFSM5634NGMA . You are receiving this because you are subscribed to this thread.Message ID: @.***>
Aha, I slightly misunderstood your second message!
I fully support your crate, and I'm glad you made it. I agree that "compile time fft size" has both benefits and drawbacks - a benefit being that it becomes impossible to express an invalid buffer size, a drawback being that users of your library must know their FFT size at compile times. Which is often, but not always, the case.
I'm curious to hear more about why a safe wrapper similar to "realfft" can't be safe. You have to transmute the array from real to complex - is that it? Or is there some other limitation?
If your concern is about the transmute, that brings me back to my comment earlier: An alternative is to implement real-only FFTs all the way down to the ground with reals instead of complexes. I started doing this last spring, but the data format (discrete hartley transform) i chose turned out to just not be good enough, and i burned myself out on it pretty hard. If I was going to start over, I'd choose FFTW's "halfcomplex" format rather than DHT or using a real input array and half-sized complex array. I absolutely despise the unwirdliness and non-intuitiveness of the halfcomplex format, but I can't deny that it's just better in every way compared to other things I've tried.
Aha, I slightly misunderstood your second message!
Suspected so :)
I fully support your crate, and I'm glad you made it. I agree that "compile time fft size" has both benefits and drawbacks - a benefit being that it becomes impossible to express an invalid buffer size, a drawback being that users of your library must know their FFT size at compile times. Which is often, but not always, the case.
Yup that's exactly it. It's even more important when considering the realfft
case. Since the returned array is of size SIZE /2 + 1
, it's much harder to reason about. Having the compiler check this for you is a nice sanity check.
I'm curious to hear more about why a safe wrapper similar to "realfft" can't be safe. You have to transmute the array from real to complex - is that it? Or is there some other limitation?
The complexity is explained in the constfft documentation. I was trying to use PhantomData
tagging with Even
and Odd
structs until someone in the internal rust forum suggested just to use the original array length const parameter.
So I've implemented it and you can have a look here.
If your concern is about the transmute, that brings me back to my comment earlier: An alternative is to implement real-only FFTs all the way down to the ground with reals instead of complexes. I started doing this last spring, but the data format (discrete hartley transform) i chose turned out to just not be good enough, and i burned myself out on it pretty hard. If I was going to start over, I'd choose FFTW's "halfcomplex" format rather than DHT or using a real input array and half-sized complex array. I absolutely despise the unwirdliness and non-intuitiveness of the halfcomplex format, but I can't deny that it's just better in every way compared to other things I've tried
Ah! Looks like you've gone the way of doing in-place manipulation if I'm understanding correctly. That does make things a whole lot more complicated. A bit out of my area of comfort. My current solution is just to have a separate buffer for input and output. Would be cool to extend it to in-place manipulation.
As it turns out there is no reason to limit constfft
's API (no planners and no panics/Results) to arrays. So I've implemented it on slices and re-branded as easyfft
. Docs are still quite lacking since I basically copied the array modules and re-organised to work on slices.
Closing this issue since I think a separate wrapping crate, i.e. easyfft is a better approach. I can achieve all of the conveniences I was suggesting using that library, although it does not get any gains from doing the checks at compile time. I suspect these gains are minimal anyway, and there are even some other additional runtime costs easyfft
incurs to do what it does. I'm specifically thinking about how rust doesn't allow for generic static items and how generic_singleton
works around it.
I may re-visit this if the generic static issue gets resolved.
Currently the
process
and related methods panics when the input or output buffers are of incorrect lengths:This can be made into compile-time failures using const-generics. Unfortunately this would require a major version bump and also increase the rustc version dependency. Depending on the complexity of the constraints required it may even require
generic_const_exprs
which is still unstable. If this is the case, I'd suggest waiting releasing until it's stabilised - but no reason not to start fiddling.Just posting this issue to see if there are any major objections before I look further into it.