Fix dlang#10798 — Reimplement FFT solver to support `@nogc nothrow pure @safe`

[Ogi-kun]

Fix dlang#10798

• FFT solver is reimplemented as a struct called FFT. It either allocates a buffer for a lookup table using malloc, or uses a preallocated buffer. In the former case, the buffer is freed upon destruction. FFT is non-copyable.
• Fft class now is just a wrapper around FFT.
• Convenience functions use FFT instead of Fft. In effect, fft(R, Ret) and inverseFft(R, Ret) can be used in @nogc, nothrow, pure and @safe code.

Though the optimization of the algorithm itself was not the goal of this change, the new version performs slightly better on the larger FFT sizes. Using LDC2 with -O -release flags, on size=64 FFT.compute works about as fast as the old Fft.fft, and on size=32768 it works 6-7 % faster. DMD shows similar results.

[dlang-bot]

Thanks for your pull request and interest in making D better, @Ogi-kun! We are looking forward to reviewing it, and you should be hearing from a maintainer soon. Please verify that your PR follows this checklist:

• My PR is fully covered with tests (you can see the coverage diff by visiting the details link of the codecov check)
• My PR is as minimal as possible (smaller, focused PRs are easier to review than big ones)
• I have provided a detailed rationale explaining my changes
• New or modified functions have Ddoc comments (with Params: and Returns:)

Please see CONTRIBUTING.md for more information.

---

If you have addressed all reviews or aren't sure how to proceed, don't hesitate to ping us with a simple comment.

Bugzilla references

Your PR doesn't reference any Bugzilla issue.

If your PR contains non-trivial changes, please reference a Bugzilla issue or create a manual changelog.

Testing this PR locally

If you don't have a local development environment setup, you can use Digger to test this PR:

dub run digger -- build "master + phobos#10799"

[Ogi-kun]

@jmdavis I kindly ask for a review.

[jmdavis]

Honestly, this is not code or an algorithm that I'm particularly familiar with. So, I'm not necessarily well-suited to review it (and I don't know who would be out of those contributors who are currently active).

However, at a glance, I can say that this design is somewhat questionable:

1. Having a struct on the stack means that it can be copied, and the member variables include both pseudo-reference types and reference types. So, a copy would not be fully independent, and it wouldn't be fully dependent either. I haven't studied it enough to know what's likely to happen if a copy is made, but I expect that there's a high chance that it won't work properly. Presumably, that's why the type was a class in the first place. That could be fixed by making the type non-copyable, but it's a concern. It might also be a concern with regards to moving, so the type might have to be made immovable (which I hope is possible with move constructors by using @disable, but they're quite new, and I don't know what the current state of things is there). Similarly, opAssign might need to be @disabled. Either way, these are issues that would need to be tested in the unit tests, and I don't see any tests along those lines.

2. It's almost never a good idea to have struct members be const or immutable (assignment in particular gets broken by it). They'll obviously become const or immutable if a variable of the struct's type is, but marking the member variables themselves with those attributes causes problems. Now, in this case, if the type isn't copyable, movable, or assignable, then it shouldn't cause issues, but as a general rule, the members of a struct should be mutable.

3. You're renaming at least one function in the struct vs the class, creating an unnecessary inconsistency between the two.

4. You're making it so that we'd have two types which do almost the same thing and have almost identical names, which is likely to increase confusion. Obviously, the goal behind that is to be able to use @nogc, but it does make the API worse otherwise.

Also, as a general rule, I don't think that it's a great idea to be altering existing Phobos code to work with @nogc, though that's a somewhat controversial topic. And this appears to be a situation where using the GC does avoid issues (like copyability). So, I'm inclined to argue that a solution like this should be left to user code where someone actually needs @nogc rather than being included in Phobos.

Regardless, this will need to be approved by @atilaneves, because it adds a new symbol.

[LightBender]

We have run into endless trouble every time we add attribute restrictions to Phobos. And this implementation seems brittle at best.

This is a no vote for me.

It's the kind of thing that would best be handled in a library with specific @nogc intentions.

[Ogi-kun]

Honestly, this is not code or an algorithm that I'm particularly familiar with. So, I'm not necessarily well-suited to review it (and I don't know who would be out of those contributors who are currently active).

Thank you for your time! The algorithm was left untouched (almost), so the reviewer doesn’t need to know anything about signal processing. The only thing that changed about the algorithm is the way the lookup table is stored (2D array vs that dense triangular array thingy). This was done to avoid extra allocation.

1. Having a struct on the stack means that it can be copied, and the member variables include both pseudo-reference types and reference types.

FFT struct is non-copyable. I was absolutely sure that I wrote a Ddoc comment about this… It can be moved with the current core.lifetime.move, but I don’t know how the new move semantics is supposed to work, At this point it’s very underdocumented to say the least.

Not being able to copy the object is a valid concern. Actually, I intended to use SafeRefCounted but the performance penalty was severe. But there are workarounds around non-copyability, and they are not painful.

If you don’t care about @nogc, you can just slap new there and call it a day:

auto fft = new FFT(1024); // `fft` is a copyable pointer

Or, you can use recently introduced ref variables:

auto _fft = FFT(1024);
ref fft = _fft; // `fft` is a copyable reference

2. It's almost never a good idea to have struct members be const or immutable (assignment in particular gets broken by it).

I have no idea what immutable members you’re talking about.

struct FFT
{
    immutable(lookup_t)* pStorage;
    immutable(lookup_t)[] table;
}

Mind the parentheses! The members themselves are mutable, so the struct mutable as well. No issues with assignment.

3. You're renaming at least one function in the struct vs the class, creating an unnecessary inconsistency between the two.

4. You're making it so that we'd have two types which do almost the same thing and have almost identical names, which is likely to increase confusion.

I see some issues the existing names:

1. It’s confusing for a class called Fft to have a member called fft.
2. Fft and inverseFft don’t follow D naming conventions for acronyms.
3. Functions that are not properties should be verbs.

The struct is not an alternative to the class, it’s a replacement. The class remains just for compatibility with existing code. Introduction of the new API presents an opportunity to fix naming. Or maybe it should be called SafeNoGCPureFFT for the time being and renamed to FFT in Phobos v3?

[pbackus]

Functions that are not properties should be verbs.

This is absolutely not true. "Square root" and "absolute value" are not verbs, for example, but it would be ridiculous to name the functions that return them computeSquareRoot and computeAbsoluteValue.

[Ogi-kun]

We have run into endless trouble every time we add attribute restrictions to Phobos.

My design doesn’t impose any restrictions on the user. You’re want to use GC? By all means:

unittest
{
    enum size = 1024;
    auto fft = new FFT(size);
    auto data = new float[](size);
    auto result = fft.compute(data);
}

I can see where your concern is coming from but this is not the case where attributes are problematic.

And this implementation seems brittle at best.

Please elaborate.

It's the kind of thing that would best be handled in a library with specific @nogc intentions.

The only downside of this implementation is that the solver is not copyable, and this is trivially solved. The upsides are better support for language features and a (slightly) better performance. This is not a different design with its own set of strengths and weaknesses, it’s an improvement over the original design.

[Ogi-kun]

Functions that are not properties should be verbs.

This is absolutely not true. "Square root" and "absolute value" are not verbs, for example, but it would be ridiculous to name the functions that return them computeSquareRoot and computeAbsoluteValue.

This is not a hard rule for functions in general but its more important for member functions. Noun makes it look like a property function, because that’s what the D Style guide recommends for properties.

[pbackus]

Noun makes it look like a property function, because that’s what the D Style guide recommends for properties.

Does existing code in Phobos actually follow this rule? My impression is that @property is rarely used in practice, and that non-@property functions are often named with nouns when doing so makes sense.

[atilaneves]

Having both FFT and Fft is going to be incredibly confusing. Can't we instead make it so the existing code can be used with these properties but doesn't have to?

[Ogi-kun]

Does existing code in Phobos actually follow this rule? My impression is that @property is rarely used in practice, and that non-@property functions are often named with nouns when doing so makes sense.

Property is any function that is intended to be used as if it was a variable or a field. It doesn’t have to be marked as @property.

Property Functions

Properties are functions that can be syntactically treated as if they were fields or variables. <…> Simple getter and setter properties can be written using UFCS. These can be enhanced with the additon of the @property attribute to the function, which adds the following behaviors…

Farther documentation refers to functions with this attribute as “@property functions” as apposed to “property functions”.

[Ogi-kun]

Having both FFT and Fft is going to be incredibly confusing.

FFT is to Fft what SafeRefCounted is to RefCounted. Fft only stays so that the existing code could keep working.

Can't we instead make it so the existing code can be used with these properties but doesn't have to?

I can mark its constructor as @nogc nothrow pure @safe. But as far as I know, there’s no way to instantiate a class that is both @nogc and @safe.

[atilaneves]

FFT is to Fft what SafeRefCounted is to RefCounted. Fft only stays so that the existing code could keep working.

The fact that SafeRefCounted exists as well as RefCounted tells me that the former is safe and the latter is not. FFT vs Fft is anyone's guess.

I can mark its constructor as @nogc nothrow pure @safe. But as far as I know, there’s no way to instantiate a class that is both @nogc and @safe.

Sure there is:

class Class { }

void main() @safe @nogc {
    scope c = new Class;
}

[Ogi-kun]

The fact that SafeRefCounted exists as well as RefCounted tells me that the former is safe and the latter is not.

I believe that at some point in the feature (maybe in Phobos v3?) we will remove the old version and rename SafeRefCounted to just RefCounted. Having “safe” as part of a name is silly. “This goes to ‘11’!” — “Why not just make ‘10’ louder?” — “… This goes to ‘11’.”

If the class was actually called FFT (to be consistent with the current naming rules in D), we would be forced to give the new type some awkward name like SafeNoGCPureFFT. Since this is not the case, we have an opportunity to add new features and improve the name in one move.

scope c = new Class;

This requires DIP1000 to not be a potential disaster. Without -dip1000, this happily compiles:

class Class {
    void fun() @safe @nogc {}
}
void main() @safe @nogc {
    Class c;
    {    
        scope scoped = new Class;
        c = scoped; 
    }
    c.fun(); // Segfault
}

The same thing but with a struct will not compile, with or without -dip1000:

struct Struct {
    void fun() @safe @nogc {}
}
void main() @safe @nogc {
    Struct* p;
    {    
        auto s = Struct();
        p = &s; // Error: taking the address of stack-allocated 
                // local variable `s` is not allowed in a `@safe` function
    }
    p.fun();
}

[atilaneves]

I believe that at some point in the feature (maybe in Phobos v3?) we will remove the old version and rename SafeRefCounted to just RefCounted.

Yes.

we would be forced to give the new type some awkward name like SafeNoGCPureFFT.

Is that good name? No. Is it better than Fft? Yes.

[Ogi-kun]

Is that good name? No. Is it better than Fft? Yes.

How about ScopedFFT?

[atilaneves]

Why Scoped?