ANN: InplaceRealFFT.jl : inplace real-to-complex and complex-to-real FFT


#1

Hello everyone!

I’ve created the InplaceRealFFT.jl module to expose FFTW’s inplace real-to-complex (rfft!) and complex-to-real (irfft!) transformations. Currently, Julia only provides inplace version of the transform for complex-to-complex transformations (fft! and ifft!). I’ve been using this module for a while but it was only now that I’ve polished it to be used by others.

It is not yet registered, so in order to install it one must Pkg.clone("https://github.com/favba/InplaceRealFFT.jl").
It is still not well documented, but it works almost the same as the out-of-place transform rfft.

I believe this package can be useful to anyone performing FFTs of real data.


I’d love to have some feedback from the community, If people find this useful I could register it. Also, if people think this package is worth living in FFTW.jl as a submodule, I’d happily make a PR.


#2

+1 for making a pull request in to FFTW.jl


#3

Definitely a PR to FFTW.jl!

Nice work.


#4

I opened an issue for FFTW.jl to see what folks think of providing this natively.


#5

I’d also like to ask something to someone more knowledgeable on the matter.

In order to make the module work on Julia v0.7 I had to stop using reinterpret and started using this trick.

Could that lead to problems? I though that maybe, because both views of the data are living in the same struct, that could make it safer to use.


#6

I think you should not run into any gc problems with this, and this looks like the most possible safe usecase.

If a user decides to keep the real view and let the PaddedArray die, then he can corrupt memory; this is ok (just don’t do this!).

If a user works on both the real and complex views at the same time there might be aliasing issues, but your code does not do such things (and these hypothetical aliasing issues are probably only my paranoia).

Caveat: My understanding of the internals is limited. Maybe others know better.

Option: Make the real array the owner of the memory. Then it is safe to take out the real part and run away with it, and unsafe to take out the complex view and run away.


#7

No you must not do it. There’s absolutely no guarantee that the data will be valid


#8

Would you mind elaborating what the problem is?

From you answer, I’d guess you think that a use-after-free might happen in some cases; in what kind of cases?


#9

Compiler can do this, easily.

In general, just don’t do this kind of analysis. All what you can ever do is to assume certain compiler limitation and rely on implementation details that can easily change.


Unsafe_wrap with array of arrays
#10

That’s a reasonable standard for security-relevant code and for base / quasi-stdlib code.

I have a feeling that performance now is more important than possible breakage in future updates for much numerics code (especially since I would expect reinterpreted arrays to become fast soon), but it’s not my call to make.

Nevertheless, thanks!


#11

No it’s not breakage in future, it’s breakage when the code is used in a way that the compiler can already optimize.


#12

So the proper guard would be to @noinline all scary functions, and then just read the @code_llvm or test to see whether everything is fine?

I mean, the overhead of a couple function calls is negligible compared to fft computation.


#13

No, the propery way is to use @gc_preserve in this function and every single users.


#14

Thanks a lot!

Now I feel stupid. Since @favba has a quite small lib, this is actually feasible (there are only 3-4 dangerous functions to annotate).


#15

Thank you guys, for the help.

It does make a lot more sense to use the real view as the “parent” of the others. I believe most of the use for rfft! starts with real data, perform some calculation in Fourier space, then ends again in real space.

Since we are trying to push this functionality to FFTW.jl , I’ll try to stick to the supported ReinterpretedArray, which will hopefully became faster in the future. For some reason it wasn’t working but I really didn’t dove deep to find the problem as I found the trick to get the same past behavior.


#16

I’m changing my mind again. In order to use the new ReinterpretArray I’d have to change FFTW.jl internals, which I got away with so far and might be out of my league. Also, right now I’m getting a 200x slowdown on a sum with the ReinterpretArray.

Sorry to bother again, my understanding of this subject is very limited. Do you mean here that every time the unsafe_wraped array is used, not only in the module itself, but also in any code used by a prospective user, there must be a @gc_preserve? In other words, it would be impossible to make usage of the module by third parties inherently safe?


#17

Correct.

If that array is to be used directly by user code, then yes, that is the case. It’s ok if the user will never access that array directly.


#18

Finally, to see if I really understand it: Then, this risky behavior of the trick was already present in the reinterpret method provided in Julia v0.6 and this is the reason (or at least one of them) for the new ReinterpretArray type, right?


#19

No.


#20

I think the reason for the new type is so that Julia can assume that arrays with different element types never alias.