FFTs Part 5: The FFT-20XX Complex-Input Algorithm
This is part 5 of a series of posts about FFTs and the specific algorithms that FFT-20XX uses.
- The Discrete Fourier Transform
- The Basics of the FFT
- Some Optimizations to the FFT
- The Inverse FFT
- The FFT-20XX Complex-Input Algorithm (← you are here)
- The FFT-20XX Real-Input Algorithm(s)
Over the last four posts, we dug into how the FFT works, various ways to compute it (some more efficient than others), and how to invert the process (to go from frequency space back into the time domain).
Now it’s finally time to start in on the specifics of how FFT-20XX’s algorithms work, starting with the algorithm for fully-complex inputs (which, despite the name, is the simpler of the algorithms).
Will this make any sense to anyone but me? Who knows. Will it even make sense to me 6 months after I write this? Who knows.
If you’re still with me on this FFT journey, strap in, cuz here we go!
The Requirements
Before we start getting into how it works, I wanted to take a moment to spell out the properties I wanted FFT-20XX to have. For a variety of reasons, I wanted the following to be true:
- No scratch memory should be required. There are many (quite fast!) implementations out there that require writable memory in which to store temporary results. If doing multiple FFTs at once, this requires allocating scratch memory per thread, which is doable but I didn’t want to have to worry about that.
- I wanted the calculation to work completely in-place: it should be possible to write the outputs into the same memory that contained the inputs — that way without even needing a second buffer you can convert between time and frequency domains to do calculations, then convert back.
- At the API side, both the inputs and outputs should be in standard order (i.e. not bit-reversed). This requirement is true of most FFT algorithm implementations, but it’s worth calling out.
- Complex inputs (and outputs) also need to be packed complex numbers. That is, every pair of numbers in the input is a 2D real and imaginary pair (so the values are like "real0, imag0, real1, imag1, etc), and the same should be true of the outputs.
- I wanted to be able to make a single rotation table up-front for the largest-supported FFT size, where any smaller FFTs can use the same table as efficiently as if they had their own bespoke tables.
- I wanted it to be fast! It doesn’t have to be the fastest implementation out there, but it has to at least sit in the ballpark with the others.
NoteFor completeness: the functionality I sacrificed to achieve the above goals is that it only supports power-of-two FFT lengths. At the very least, handling that would make point #5 quite difficult, as the tables tend to be more bespoke for arbitrary sizes due to having a larger variety of required rotations.
But I only needed to support power-of-two lengths for my use cases, so that’s all I did.
There are many FFT implementations out there, but there are very few that support all of these. Many of the fastest ones require scratch memory or some up-front computation to figure out the best way to do the algorithm.
My initial approach was to do a radix-4 decimation-in-frequency implementation with a bit-reverse pre-pass, with heavy SIMD optimizations for not only the computations through the middle, but also for the initial bit-reverse pass (which was written such that it could work in-place). This hit the first five points, but when I started timing it against others (specifically, the chowdsp FFT by Jatin Chowdhury, who wrote up a nice post about converting PFFFT to use AVX), it was about 20% slower! So, clearly I had work to do.
After some profiling, I noticed that the bit-reverse pass (even optimized as it was!) was taking up a large percentage of the runtime of the algorithm, so I started thinking about how to remove it (without losing the standard-in/standard-out ordering of the data).
But first, we could use a better understanding of how to do an in-place bit reverse.
NoteThe following discussion is all predicated on power-of-two sizes. There are general ways to do the same tricks, but I didn’t need to implement them so I can’t speak to good ways to do them. I’ll leave that for someone else.
In-Place Bit Reversal
In our previous example code, we always did the bit reverse out-of-place (requiring separate input and output memory), but it turns out it’s possible to do it as a wholly-in-place algorithm.
Let’s arrange the indices (in both standard and bit-reversed orders) for a 16-element FFT in a grid, with labels along the top and left to show the memory indices:
There doesn’t seem to be a nice relational pattern here, but if we were to swap the middle two rows in both diagrams (note that we’re changing the view and not the memory ordering — this is the exact same data in memory as the previous set of diagrams), something becomes apparent:
Viewed this way, this is a matrix transpose! In fact, any power-of-four FFT length (as every power of 4 is also a square), can be viewed in this same way, by looking at the rows in bit-reversed order:
But what about a non-square length? This, interestingly, becomes two side-by-side matrix transposes:
NoteFor purposes of describing the FFT-20XX algorithm, we don’t need to know the above fact, I just thought it was neat.
A nice thing about matrix transposes is that they can be done in-place (since every element — except the diagonals — simply swaps with another element). Here’s a bit of pseudocode to do this in-place bit reverse:
void BitReverseInPlace(complex[] data, int len)
{
// fwiw there are fast ways to calculate this with
// a known power of 2 using clz-style instructions.
var rowCount = floor(sqrt(len))
// For power-of-4 lengths this will equal
// rowCount, otherwise it will be
// rowCount * 2
var colCount = len / rowCount
for (var row = 0; row < rowCount; row++)
{
// using rowCount here because it's the size of
// the square matrix
for (var col = row + 1; col < rowCount; col++)
{
// The only difference from a standard square
// matrix transpose, really, is that we're
// bit-reversing the row indexing.
var rc = BitRev(row * colCount, len) + col;
var cr = BitRev(col * colCount, len) + row;
Swap(data[rc], data[cr])
if (rowCount != colCount)
{
assert(colCount == rowCount * 2)
// Do the second side-by-side transpose.
Swap(
data[rowCount + rc],
data[rowCount + cr])
}
}
}
}
NoteThere are, of course, more-efficient ways to do this. It is possible to make a nice cache-coherent, SIMD implementation of this (by using the same tricks people have found for doing standard matrix transposes), but we won’t actually need any of that.
With this understanding of how an in-place bit reverse might work, we can finally get to:
Eliminating the Bit Reverse Pass
So far, we’ve predicated all of the discussion around the FFT on the fact that the algorithm either takes inputs in standard order and outputs values in bit-reversed order, or (as we formulated all of the sample code) the other way around: with the inputs in bit-reversed order and the outputs in standard order.
But this is not strictly necessary.
Naturally, as with many things in computer science, there are people who worked on this exact problem over 40 years ago. One person who definitely went down this rabbit hole is (the now, sadly, deceased) Clive Temperton, who wrote the 1982 paper “Self-sorting mixed-radix fast Fourier transforms”.
NoteIt’s always fun to find a computer science paper old enough that it was done on a typewriter!
When we first built up to the FFT algorithm way back in part 2, we noted that each step of the radix-2 FFT effectively does a deinterleave of the even and odd indices at that step, but also noted that doing an in-place deinterleave is a rough bit of work, so we’ll have to look for something else.
One thing we can note is, for a given FFT length , the index has bits, and thus there are bit reversals. For instance, a 4-bit index has 2 reversals (bits 0 ↔ 3 and 1 ↔ 2). A 5-bit index also has 2 reversals (0 ↔ 4 and 1 ↔ 3, with 2 remaining the same since it’s in the middle), 6- and 7-bit indices have 3 reversals, and so on.
Basically, with a radix-2 FFT, there are steps and half as many bit reversals (rounded down), so we could interleave single-bit reversals with the FFT steps.
There are two orders that the reversals can be done in. One way would be to start with the outer-most bits and work our way in towards the center-most bits.
Here’s the sequence of steps to do this for a 64-element FFT (note that we’re keeping the “matrix transpose” row ordering vs. natural memory ordering):
Each of these steps can be viewed as a collection of 2×2 matrix transposes:
- The first one does sixteen 2×2 transposes of individual elements (every 2×2 block of elements)
- The second does four 2×2 transposes, this time of 2×2 blocks (note the swap of the block containing “16, 48, 17, 49” and “2, 34, 3, 35”, for instance).
- The final step does a single 2×2 transpose of 4×4 blocks (swapping the upper-right and lower-left quadrants).
The other order to do these in would be, instead, starting with the inner-most bits and going out from there (which I refer to, for purely comedic purposes, as the middle-out bit reversal):
They both end up with the same final result, and there’s not (at the moment) an obvious reason to prefer one over the other. Either way, any given step can take a 2×2 grouping of values and swap the elements on the diagonals, which we’ll leverage.
We now know how to break this up into individual steps, but when should we do those steps?
When To Do The Flippy Floppy
There are many ways we can choose to group the bit reversals together. There are five somewhat obvious choices:
- Do them all at once at the beginning, before running the algorithm. This is what all the example FFT implementations in previous posts did.
- Do them all at once, at the end. This is a post-pass in-place bit-reversal.
- Because there are always half as many (rounded down) bit reversals as there are radix-2 passes, we could do them every other radix-2 pass (or, if we’re in radix-4 which has half the number of passes, once every radix-4 pass).
- We could do one per radix-2 pass for the first half of the FFT, then past the halfway point, there are no more reversals to be done and everything proceeds using the standard algorithm for bit-reversed inputs.
- We could do one per radix-2 pass for the last half of the FFT, so the first half would use the standard algorithm for standard-order inputs, before starting to swap things around.
Obviously the first two options there are what we’re trying to avoid (doing the whole thing as one big pass), so we have three (reasonable) choices. As a 16-element decimation-in-time (DIT) FFT using the middle-out bit reversal, the other three options would look something like the following (with the filled boxes denoting where we’re doing a bit reverse vs. a standard FFT algorithm step):
NoteThe goal here isn’t to be able to trace every single reversal, it’s just to demonstrate how the bit reversals “sit” in between the radix-2 passes for the different orderings.
Ultimately, the algorithm we want is going to be doing things as radix-4, so the evenly-spaced one seems tempting. After all, there’s one reversal after each pair of FFT steps, which means there would be a single reversal for every radix-4 step.
However, if we visualize it as a radix-4:
Look at that second radix-4 step. Look at it. It’s weird. The nice, even spacing between radix-4 elements is completely gone, the relative angle indices are … scattered? And it just gets worse the larger the FFT sizes get.
It’s probably possible to make this work, but it seemed like a pain, and I don’t know how well it would play with CPU caches or SIMD.
That leaves either the first-half or last-half options, neither of which has that problem (they both, conveniently, keep the radix-4 steps even at each level).
Of the two, it turns out the last-half reversal has a nice property (shared by the DIF algorithm we came up with in the previous post): similar angles are grouped together longer, which means there are a number of optimizations we can apply to that formulation that we couldn’t do with the first-half version.
NoteThe optimizations in this case include loading the angles outside of the inner-most loop and special-casing the first few sets of radix-4 passes, since we have a memory-coherent group with no rotations, then one with only 90-degree rotations, etc.
Also, it’s worth noting that it actually keeps the same sequence of butterfly strides (the spacing between subsequent inputs/outputs to the butterfly) that the standard algorithm has: each radix-2 pass has half the stride as the one before (which means each radix-4 pass has a quarter the stride of the one before). This makes the algorithm nice and regular to implement.
NoteThe first-half reversal algorithm, by comparison, has a sort of “smaller then larger” layout where they roughly halve until the midpoint where they start doubling, ending with the same stride as the start.
You can see this in the diagram of it above.
So, that’s the core of FFT-20XX’s algorithm: radix-4, decimation-in-time, and with last-half bit reversal.
Now, we just have to figure out how to do said bit reversals.
How 2 Bit Reverse
As mentioned above, because we’re radix-4 we will need to do two bit reversals per radix-4 step in the last half.
NoteThis is mostly true, with one exception: for sizes like 64, 1024, etc. where there are an odd number of bits that reverse, the first radix-4 of the back half (rounded up) only needs to do a single bit reverse since there’s an odd bit pair to swap.
Similar to how our example 1-bit-reverse-at-a-time squares above were the equivalent of doing a set of 2×2 matrix transposes, doing 2 bits ends up being the equivalent of doing a set of 4×4 matrix transposes.
The obvious way to do this would be to run the radix-4 FFT step, then do a separate pass that does the bit-reversal transposes. But we can do better — without requiring a separate pass over memory — by doing the bit reversals and the FFT step at the same time.
Here’s the beauty of the way this works: for any given radix-4 step with this method, the two bits that flip always correspond to the spacing between the radix-4 elements.
To explain what I mean by that, here’s a standard radix-4 diagram again. In last-half bit reversal world, the only two reversals in a 16-element FFT happen after the whole algorithm completes, so the diagram (without the reverses in it) is the same:
Because we start from the middle bits and get to the outer bits last, the last radix-4 step will always be flipping the bits representing 1 and 2 (swapping them with the bits representing and , respectively), which will always be the spacing of elements in the last radix-4s (by this I mean, if you look at the first radix-4 of the last step, its indices will be 0, 1, 2, 3 — which is just every on/off combination of the bits for 1 and 2).
The next-to-last radix-4 step (for FFTs sized 256 and larger) involves the bits for 4 and 8. Note that, in our 16-element diagram above (which doesn’t have this bit reverse but still illustrates the point), the first radix-4 butterfly has indices 0, 4, 8, 12 which, like the previous example, is just every on/off combination of those two bits.
The step before that (for even larger FFTs) would involve flipping the bits for 16 and 32, with butterflies where the spacing is 0, 16, 32, 48.
This pattern continues happily no matter how large the FFT ends up being.
In the last step in our 16-element example, bit 1 swaps with bit 8 and bit 2 swaps with bit 4, and there just so happens to be a butterfly that starts at 4 and one that starts at 8.
What this means is: the smallest bits in a flip correspond to the spacing within a given radix-4 computation, and the largest bits in a flip correspond to the starts of radix-4 passes.
Thus, there are exactly four evenly-spaced radix-4 butterflies involved in every 4×4 transpose.
Here’s a diagram of four butterflies (A through D) in their input order, and their post-transform order, which is exactly what the bit reversal is doing (with some color highlighting to make the butterflies clearer):
So, for each radix-4 step that does a two-bit reversal, we can instead run four radix-4 butterflies at once, and then transpose the elements within them before writing them back out to memory, doing the whole thing in one read/write pass!
NoteDoing this can just barely fit within the 16 registers that x64 SIMD (pre-AVX-512) provides, with some trickery involved around when to load from and store to memory.
Final Algorithmic Details
There are two more details that need to be handled, before the algorithm is fully described.
First is, for non-power-of-four lengths, where do we put the single radix-2 pass?
This one has an easy answer: it can go anywhere in the first half! (If it were to go somewhere in the last half, it would mess up the nice alignment of radix-4 element spacing and bit reversals we were going over in the previous section).
For FFT-20XX, I ended up putting it directly after the very first radix-4 pass (as that first pass is nicely special- cased and optimized due to having no complex rotations).
NoteIn fact, it was tempting to make the first pass a radix-8 pass, given that, in addition to the 8 complex components (16 values: reals and imaginaries), there only needs to be a single factor loaded, and it would avoid a whole pass over memory.
There wasn’t a way to get that all to fit in the 16 x64 SIMD registers (I was, annoyingly, able to get it down to needing 17 registers), and it ended up running slower — even at large FFT sizes — than just doing it as a radix-4 followed by a radix-2.
On ARM, however, where there are 32 registers to play with, this would probably work nicely!
Next, there’s the single-bit flip for FFT lengths with an odd number of bits that flip (for instance: a length of 64, which has 6-bit indices and thus 3 bits that flip, or 128 which has 7-bit indices which also has 3 bits that flip — with one that stays stationary in the middle).
It turns out this case is actually two cases: power-of-four and non-power-of-four FFT lengths.
For power-of-four lengths, we catch a nice break: the two bits that flip just so happen to be the middle two elements of each butterfly! For example, for a 64-length FFT, there are 3 radix-4 steps. The second step contains the single-bit flip, and the first radix-4 butterfly has indices 0, 4, 8, and 12. And it turns out that it’s the bits representing 4 and 8 that are flipping, so we actually only need to load a single radix-4 butterfly, then just write the inner two elements out in reverse order.
Nice!
For power-of-two lengths, we’re not that lucky. But it still only requires doing two radix-4 butterflies at a time, and the second and fourth values from one swap with the first and third values of the other (as there are two 2×2 matrix transposes within each pair of butterflies):
So here’s a rough breakdown of the whole algorithm:
- For the first half (rounded down) of the radix-4 steps in the algorithm, proceed as normal, with the inputs in standard
order.
- Unimportantly, I put the radix-2 step after the first radix-4, just because it was easy.
- If the FFT length has an odd number of bit flips:
- If it’s a power-of-four length, do a pass just like a standard one, except where the middle elements of each radix-4 are written in reversed order, to do the single bit flip.
- Otherwise, load the two relevant radix-4 butterflies, compute them both, then swap the second and fourth elements in the first with the first and third elements in the second before writing them out.
- After that, each step loads four radix-4 butterflies at a time, computes all of them, then does a 4×4 matrix transpose of their elements (while still in registers!) and writes those out.
The devil, of course, is in the details (for instance, this simple description doesn’t go into the angle indexing — but it’s actually reasonably straightforward and regular!), but this is the high level of the algorithm!
Snark!…if this many words can be described as just the “high level” overview of anything.
SIMD Considerations
This section will be light on specifics, but it’s worth going over a few of the SIMD considerations that went into the implementations.
The first thing is that, as mentioned in the requirements at the start of this post, the inputs and outputs to the complex FFT functions use packed complex numbers. For SIMD efficiency, the very first step does a deinterleave during its loads, to get a SIMD vector of all the reals and a second vector of all of the imaginary components for each.
As an example, for a 4-element SIMD type, it would load r0, i0, r1, i1, r2, i2, r3, i3
into two vectors:
vR = r0, r1, r2, r3
vI = i0, i1, i2, i3
Then, for intermediate steps, it stores those 8 neighboring values directly, without re-interleaving them (as they stay neighboring in blocks like that until the very end).
Only on the very last step does it re-interleave while writing the final results.
Next, because of the way the angles are arranged (with like angles grouped nicely together), each radix-4 SIMD butterfly only needs a single set of three angles (though, when doing two or four at a time due to the bit reversals, each butterfly has its own set of three angles, so for the double-bit-reversal case there are actually 12 angles, total).
NoteI’m saying 3 angles as that’s the canonical way, but on x64 it actually only does two angles, doing instead a “radix-” computation and taking advantage of the speed of the FMA instruction, which allows it to do technically more calculations than the canonical version, but in less cycles.
I’ve mentioned it in previous posts, but this trick is nicely described in The ryg blog.
This stops being true right around the end of the process: the very last step (for all SIMD sizes) ends up requiring a SIMD set of distinct angles, as the grouping of the angles has finally gotten down to a single element (each butterfly in the final step has a unique set of angles).
NoteFor larger SIMD sizes like AVX, the second-to-last step also needs to be special-cased, as it involves flipping bits 4 and 8. For AVX, for instance, each 8-element SIMD butterfly set contains two of the four radix-4 butterflies, in the first and last halves.
Finally, smaller FFT sizes tend to need to be special-cased. 8-element and smaller FFTs are just done in scalar (I doubt anyone is going to be perf-constrained by not having those tiny FFTs be SIMDed). And, for AVX’s 8-element vectors, 64-element and below will fall back on the SSE2 implementation.
The final pass also needs a different implementation for 2-element and 4-or-more-element SIMD vectors.
That’s Complex!
That is a hopefully-coherent rundown of how FFT-20XX’s complex-valued algorithm works! The algorithm itself isn’t that much more involved relative to a standard FFT implementation, but dropping the bit-reverse prepass (even after having heavily SIMD and CPU-cache optimized it) ended up getting FFT-20XX to be between 1.2 and 1.8x as fast as the chowdsp FFT that I was using as my baseline (tested at FFT lengths of 64 through 524,288), with the AVX implementation! (The SSE2 and NEON implementations end up 1.1 to 1.5x faster than chowdsp).
It hits all of the requirements: it works completely in place with no scratch memory needed, keeping the inputs and outputs in their natural order, and is fast (or at least, fast enough)! And it manages to do that all without an explicit bit-reverse pass!
NoteThe inverse complex FFT, which I haven’t mentioned at all in this post, uses the same algorithm with the rotations reversed (switched via C++ templates), with the scale applied during the final radix-4 before saving the final results out.
In the next (and, thankfully, final) post in this series, we’re going to tackle the final boss of the whole project: the real-input FFT (and its inverse), which ended up being way trickier than I expected.