ITK 5.4.8: Concurrent IO, Correct DICOM Geometry, and Sturdier Python WrappingWe are pleased to announce the release of ITK 5.4.8! ITK 5.4.8 is a maintenance release for this cross-platform, open-source toolkit for N-dimensional scientific image analysis with spatially-aware algorithms. This release focuses on correctness, concurrency, and compatibility. It removes a MetaIO deadlock that could stall heavily multithreaded reads, fixes DICOM series geometry when slice spacing […]📝Kitware IncWelcome to SwedenCpp
Latest blogs, videos, podcasts and releases in one stream
Friday, November 20, 2026
ITK 5.4.8: Concurrent IO, Correct DICOM Geometry, and Sturdier Python WrappingWe are pleased to announce the release of ITK 5.4.8! ITK 5.4.8 is a maintenance release for this cross-platform, open-source toolkit for N-dimensional scientific image analysis with spatially-aware algorithms. This release focuses on correctness, concurrency, and compatibility. It removes a MetaIO deadlock that could stall heavily multithreaded reads, fixes DICOM series geometry when slice spacing […]📝Kitware Inc
Lightning Talk: The Unanticipated Allocator - Jeff Trull - C++Now 2026🎥CppNow
Why do I get inconsistent results when I ask for the icon for the .. parent folder?It depends on what the parent folder is. The post Why do I get inconsistent results when I ask for the icon for the .. parent folder? appeared first on The Old New Thing .📝The Old New Thing
Same Bits Without Losing MIPS: Reproducible Numerics at Full Hardware Speed - Andrew Drakeford🎥CppCon
Decoding base64 email attachments: a speed ranking of programming languagesEmail attachments are base64. So are cryptographic PEM certificates. In both cases the text is broken into lines, 76 characters for email and 64 for PEM. Skipping line endings sounds trivial. Yet many fast decoders only work on uninterrupted base64. As soon as they meet a line break, they fall back to a slow path. … Continue reading Decoding base64 email attachments: a speed ranking of programming languages📝Daniel Lemire's blog
Real-Time AI Audio Processing at Scale - Building Cloud-Native Audio Applications - Vishal Alhat🎥audiodevcon
chrono_literals, units, and comparison | Modern Cpp Series Ep. 253🎥Mike ShahIf this page is useful, please consider donating a coffee
Thursday, November 19, 2026
FFTs Part 4: The Inverse FFTThis is part 4 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 (← you are here) The FFT-20XX Complex-Input Algorithm The FFT-20XX Real-Input Algorithm(s) In the last post we looked at ways to make the core FFT algorithm more efficient. Before we (finally!) get to the actual FFT-20XX algorithm, it’s worth going over how the inverse FFT works. But to do that, we need to first take a detour into the decimation-in-frequency (DIF) FFT . I hope you’re ready for some more diagrams because we’re about to dive in. Note In this post we’ll be focusing on radix-2 because it’s the simplest form to reason about, but all of this applies to other radixes as well. Flipping Our Focus Last time we started graphing the data flow of the FFT algorithm (using semi-standard butterfly diagrams ). The radix-2 decimation-in-time algorithm ultimately ends up looking like this: The diagram of a radix-2 FFT from the previous part, showing the four stages of the algorithm and how they interleave, with the input indices in bit-reversed order and the output indices in sorted order. " 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 0 0 0 0 0 0 0 4 0 4 0 4 0 4 0 2 4 6 0 2 4 6 0 1 2 3 4 5 6 7 If you remember back in part 2 , we visualized the rotations for a length-8 FFT, and split things into even/odd inputs and first/last halves of the output. We can, instead, visualize the same rotations, but switch to looking at even/odd outputs and first/last havles of the inputs (effectively transposing the breakdown we did before): in[0] [0] in[1] [1] in[2] [2] in[3] [3] in[4] [4] in[5] [5] in[6] [6] in[7] [7] out O [0] = + + + + + + + out O [1] = + + + + + + + out O [2] = + + + + + + + out O [3] = + + + + + + + out O [4] = + + + + + + + out O [5] = + + + + + + + out O [6] = + + + + + + + out O [7] = + + + + + + + Note I’m going to go through this faster than I did the first time, in the hopes that having already done a similar set of steps once, it’s clearer what’s going on this time. Similar to part 2, we’ll group the evens and odds (this time, outputs instead of inputs), and make the rotations in the second half of the odd outputs be a negation of the first half’s rotations: in[0] [0] in[1] [1] in[2] [2] in[3] [3] in[4] [4] in[5] [5] in[6] [6] in[7] [7] out O [0] = + + + + + + + out O [2] = + + + + + + + out O [4] = + + + + + + + out O [6] = + + + + + + + out O [1] = + + + - - - - out O [3] = + + + - - - - out O [5] = + + + - - - - out O [7] = + + + - - - - Now, we can note that for a given output, the first and last half inputs have the same rotations (i.e. inputs 0 and 4 have matching rotations, 1 and 5, etc), with the evens being summed and the odds being subtracted. We can pre-add (for the evens) and pre-subtract (for the odds) these to get two 4x4 blocks, first the evens, which is just a standard 4-element FFT: [0]+[4] [1]+[5] [2]+[6] [3]+[7] out[0] = + + + out[2] = + + + out[4] = + + + out[6] = + + + Then the odds which, like in part 2, are a little bit different: [0]−[4] [1]−[5] [2]−[6] [3]−[7] out[1] = + + + out[3] = + + + out[5] = + + + out[7] = + + + In this case, before doing the sub-FFT, we can rotate the inputs to the sub-FFT to get it in standard N 2 \frac{N}{2} -length FFT form: × × × × ([0]−[4]) ([1]−[5]) ([2]−[6]) ([3]−[7]) out[1] = + + + out[3] = + + + out[5] = + + + out[7] = + + + This effectively puts the add/sub step first at each “level”, then the rotation afterwards (to feed into the next sub-FFT). Because of the way that the divisions into sub-FFTs happen based on outputs rather than inputs, this results in a graph that looks like the DIT diagram, but flipped horizontally: A diagram of a 16-element decimation-in-frequency FFT, showing the four "stages" of processing and how they interleave. The flow of the diagram and the angles are the same as the decimation-in-time version, but in reverse. 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 0 0 0 0 0 0 0 4 0 4 0 4 0 4 0 2 4 6 0 2 4 6 0 1 2 3 4 5 6 7 Where decimation-in-time started with smaller sub-FFTs and then built up to the full one, each step of decimation-in-frequency instead does a computation pass on its inputs and then splits them up into sub-FFTs after, such that the last step of the radix-2 DIF is just a set of standard length-2 FFTs. The computation pass is also different: rather than rotate the odd input before the addition and subtraction, DIF instead does the add/sub first then rotates odd output . This is why the rotation (twiddle) factors in the above diagram are on the right-hand side of the butterflies instead of the left. Despite looking almost like its reversal, this actually computes the exact same outputs as the DIT FFT given the same inputs (ignoring floating-point error, for the pendantic. Yeah, I see you). Note that, as formulated here, the diagram starts with the inputs in-order and ends with the outputs bit-reversed ; this is a consequence of the alternate way we broke down the algorithm. It’s still possible to do the bit-reverse on the inputs so the outputs come out in-order, however. If we rearrange the inputs and outputs in the diagram accordingly, we get the folowing: Diagram of a radix-2 decimation-in-frequency FFT, with the inputs in bit-reversed order and the outputs in natural (sorted) order, just like the original decimation-in-time diagrams. The angle indices in each stage are in bit-reversed order as a consequence of this reordering. 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 4 2 6 1 5 3 7 0 0 4 4 2 2 6 6 0 0 0 0 4 4 4 4 0 0 0 0 0 0 0 0 Just to reiterate: the above two diagrams are functionally identical , it is simply a matter of visualizing them with different input/output orderings. We now have enough information to turn this into a routine that — like the DIT version — does the bit reversal on the inputs before computing the result in-place. Here is some pseudocode: void CalculateDFT ( complex [ ] inputs , complex [ ] outputs , int len ) { if ( len == 1 ) { outputs [ 0 ] = inputs [ 0 ] return } BitReverseCopy ( inputs , outputs , len ) for ( int span = 2 ; span len ; span *= 2 ) { for ( int groupI = 0 ; groupI len / span ; groupI ++ ) { var * data = & outputs [ groupI * span ] // We can pull the twiddle lookup/calculation // out of the innermost loop. Note the bit // reversal in the index lookup. var twiddle = Twiddle ( BitRev ( groupI , len ) , len ) for ( int k = 0 ; k span / 2 ; k ++ ) { int kOdd = k + span / 2 complex even = data [ k ] complex odd = data [ kOdd ] // Note the post-rotation here vs. the pre- // rotation that DIT does. data [ k ] = even + odd data [ kOdd ] = ( even - odd ) * twiddle ; } } } } This code is very similar to the DIT version; the main differences are the bit-reversed angle lookup and the rotation of the output of the computation pass instead of rotating the inputs (again, a consequence of doing the even/odd split on the outputs instead of the inputs). Note On systems without a fast fused multiply-add (FMA) instruction, this DIF formulation ends up being a really nice choice! However, there’s a trick using FMA mentioned in a note in part 3 (which is broken down nicely on The ryg blog ) which, sadly, does not work with the DIF’s post-rotation. A nice thing about the DIF formulated this way (with the bit reverse first) is that it lets the angle lookup move outside of the innermost loop (as you can see above). This is especially nice for radix-4 implementations where the table doesn’t store the 3 k 3k angles and they’re built via a multiplication, as the multiplication itself can move out of the inner loop. The other interesting thing is that, with the angle lookups in bit-reversed order, you can store your table of rotations in bit-reversed order as well and, when stored this way, you automatically get nice cache-coherence for the smaller FFT types. If you look at the above butterfly diagram, the first angle is always 0, the second is always a quarter turn (it’s 4 16 \frac{4}{16} in the above diagram, and for a length-8 FFT it would be 2 8 \frac{2}{8} , which is equivalent), and so on. So with an arbitrarily-large FFT table, any given (power-of-2) sized FFT of length N N would just use the first N 2 \frac{N}{2} elements of the table. Note These properties are also true for DIT implementations where the bit reverse is done at the end instead of on the input. That’s decimation-in-frequency! It ends up being a near-reversal of the way that decimation-in-time works, yet still computes the same result. Now that we’re through that, we can finally get to: The Inverse FFT Breaking a (time domain) signal down into its frequency components is pretty handy (you can use it to write cool visualizers, for instance!), but it’s even more useful if you can go from frequencies back into time-domain samples , letting you convert your audio into frequencies, manipulate them in some way (like an EQ ) and then turn it back into samples that can be played back or encoded as normal. The FFT (and the DFT in general) is really a linear system, which means it can be inverted , so we can make a transform that takes the output of an FFT and gives us the original inputs. This is the inverse FFT (IFFT) . To figure out how to do this, let’s start with the simplest useful case: a single DIT radix-2 pass (with an arbitrary angle k k ): Diagram of a 2-length FFT, showing the two inputs going into a single processing node, then back out to the two outputs. The second input node has a "k" representing the fact that it is rotated by an unspecified angle. 0 1 0 1 k There are effectively two steps here: Rotate input 1 by k k . Add/subtract input 0 with the rotated input 1 to get the two outputs. To invert this, we need to undo these two steps (in the opposite order as we did them). Undoing the addition/subtraction is first, and this one is easiest to do algebraically. If we have these two equations: y 0 = x 0 + x 1 y_0 = x_0 + x_1 y 1 = x 0 − x 1 y_1 = x_0 - x_1 We can solve them for x 0 x_0 and x 1 x_1 to get: x 0 = ( y 0 + y 1 ) / 2 x_0=(y_0 + y_1)/2 x 1 = ( y 0 − y 1 ) / 2 x_1=(y_0 - y_1)/2 After that, we need to undo our initial step 1, which is the rotation by k k . Undoing a rotation is just rotating the same amount the other way, so that becomes a rotation by − k {-}k . Note Because a complex rotation value for a given angle looks like cos θ + i sin θ \cos\,\theta + i\,\sin\,\theta , the opposite rotation would be: cos ( − θ ) + i sin ( − θ ) \cos({-}\theta) + i\,\sin({-}\theta) By the negative angle trig identites , this becomes: cos θ − i sin θ \cos\,\theta - i\,\sin\,\theta So reversing the angle just means negating the imaginary component of the twiddle factor. For a moment, we’re actually going to ignore that 1 2 \frac{1}{2} scale on our result (just for now — we’ll get back to it), which ends up making the resulting 2-element inverse FFT steps look like: Add/subtract inputs 0 and 1 (the outputs from our forward FFT) to get two output values. Rotate the second output of the first step by − k {-}k . This ends up looking like: Diagram of a 2-length inverse FFT, showing the two inputs going into a single processing node, then back out to the two outputs. The second output node has a "-k" representing the fact that it is rotated by the opposite of the angle from the forward FFT. 0 1 0 1 -k Which looks just like the DIF from earlier, except with the angle negated ! This continues to work as we scale the FFT up to larger sizes. Here it is as a 16-element inverse FFT: A diagram of a 16-element inverted decimation-in-time FFT, which looks exactly like the earlier decimation-in-frequency diagram (with bit-reversed outputs), except all of the rotations are negated. 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 -0 -0 -0 -0 -0 -0 -0 -0 -0 -4 -0 -4 -0 -4 -0 -4 -0 -2 -4 -6 -0 -2 -4 -6 -0 -1 -2 -3 -4 -5 -6 -7 That’s right, by inverting the decimation in time FFT we end up with what looks like a decimation in frequency FFT with negated angles! A Grumpy Aside Honestly, I don’t actually like the “decimation-in-time/frequency” terminology, specifically because when using the same code for the inverse, it ends up being wrong: the DIT algorithm is decimating the inputs which are in time domain for a forward FFT, but they’re actually in frequency domain for an inverse FFT (since we’re going from frequency space back to time). I would have preferred “decimation-in-input” and “decimation-in-output” but I don’t think I’m going to win a fight that I’m 60 years late to. This relationship plays out the other way, as well: inverting the DIF gets a DIT -like FFT with negated angles: A diagram of a 16-element inverted decimation-in-frequency FFT, which looks exactly like the earlier decimation-in-time diagram (with bit-reversed inputs), except all of the rotations are negated. 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 -0 -0 -0 -0 -0 -0 -0 -0 -0 -4 -0 -4 -0 -4 -0 -4 -0 -2 -4 -6 -0 -2 -4 -6 -0 -1 -2 -3 -4 -5 -6 -7 This is great, because it means the same routine (whether DIT or DIF) can be used for forward and inverse complex FFTs! But, what about that 1 2 \frac{1}{2} scale that we ignored earlier? Every (radix-2) step in the IFFT has that 1 2 \frac{1}{2} scale on all of its outputs, so we can factor them all out of the inner steps and combine them into a single 1 N \frac{1}{N} scale per output for the whole process! Tiny Math! The scale becomes 1 N \frac{1}{N} because there are log N \log\,N passes, each with a 1 2 \frac{1}{2} scale, and ( 1 2 ) log N = 1 N (\frac{1}{2})^{\log\,N} = \frac{1}{N} . Thus, to use our (forward) FFT routine as an inverse FFT, there only need to be two changes: The twiddles need to have their sin \sin components negated (to rotate by the opposite angle ). Scale each resulting value by 1 N \frac{1}{N} (where N is the FFT length). This scale can be applied at the start or at the end, it doesn’t matter; it’s a constant scale to the whole result. You could even do it in the middle somewhere if you’re an absolute monster . Here’s some pseudocode for this, which uses the same overall algorithm to compute either the forward or inverse FFT: void CalculateFFT ( complex [ ] inputs , complex [ ] outputs , int len , bool inverse ) { if ( len == 1 ) { outputs [ 0 ] = inputs [ 0 ] return } BitReverseCopy ( inputs , outputs , len ) for ( int subLen = 2 ; subLen len ; subLen *= 2 ) { for ( int subStart = 0 ; subStart len ; subStart += subLen ) { var * data = & outputs [ subStart ] for ( int k = 0 ; k subLen / 2 ; k ++ ) { int kOdd = k + subLen / 2 complex evenSum = data [ k ] complex oddSum = data [ kOdd ] // Get the twiddle factor and invert the imaginary // component for an inverse FFT to negate the rotation. var tw = Twiddle ( k , subLen ) ; if ( inverse ) tw . imag = - tw . imag oddSum *= tw data [ k ] = evenSum + oddSum data [ kOdd ] = evenSum - oddSum } } } if ( inverse ) { // The inverse FFT needs to scale everything down // by the FFT length. float scale = 1 / len ; for ( int i = 0 ; i len ; i ++ ) { outputs [ i ] *= scale ; } } } We Made It! This brings us (finally!) to the end of the “standard” breakdown of various FFT techniques. In this post, we looked at: The decimation-in-frequency FFT, which is effectively a reversal of the flow of a decimation-in-time FFT. The inverse FFT, which can be calculated the same as a forward FFT with the angles negated and with a constant scale. In the next two posts, I’m going to go way off into the weeds and discuss the algorithmic variants that I used in FFT-20XX, starting with the algorithm for complex inputs.📝JoshJers' Ramblings
How we turned a C++ idea into a funded reality 💻 #coding #entrepreneur #event🎥C++ Alliance
How to Properly Implement Code Quality Gates in your Development Process - Paul Jansen - ACCU 2026🎥ACCUConf
Why C++11 changed everything about your code #cpp #cplusplus #programming🎥CppCon
Interview with Kate Gregory about her Meeting C++ 2026 keynote brains and belonging🎥MeetingCpp
Stop Rebuilding the World: Faster C++ CI with vcpkg Binary Caching🎥Utah Cpp Programmers
Examples of Lossy SystemsLossy Systems There’s a pattern in software engineering which I call the ’lossy system’. A ’lossy’ system is any system designed to return only incomplete answers, either to make a problem at all tractable, or just to keep costs down. Data compression is the easiest example. If you’re fine with storing “imperfect” images, you use JPEG. JPEG will throw away some of the data inside of your image, in return for making the image smaller. The lines are blurry: Is reaching for the most common image format a “lossy system pattern”? No, not really. Yes, lossiness is built into JPEGs, but reaching for them is just the industry standard. It becomes a pattern when you make a deliberate decision to drop data that you were previously processing, to approximate data, to compress, or to serve stale data, etc. Big fucking whoop, who cares, etc., why is any of this interesting? Sufficiently large systems inevitably become lossy. It’s what lets them scale, it’s also what makes big tech so complex , and explains why YouTube or Twitter’s algorithm only serves you hot garbage (maybe). Additionally, your system is already lossy . Any distributed system has to account for data being dropped, components breaking, etc. Some systems are designed around this and resilient, other systems just break entirely. In the following, let’s go over a short list of examples, each of which illustrates a different instance of what lossy systems look like. This post is not going to be deeply technical, and it’s not a complete list. It’s just examples. Concepts. To get the basic shape. I may come back to it if I ever figure out a clean taxonomy. Examples Sampling Simple. Instead of gathering “all” data, you just sample say, 1% of it. This is such a fundamental idea that it’s used everywhere, across all industries. Instead of putting every single widget through quality control, only send 0.1%. Boom. You cut 99.9% of the cost required to process items. Better yet, if you realize that this is where your costs are, you can easily just cut the sampling rate even further. The tradeoff, of course, is that if your data is highly varied, you might care about single specific data points which did not get sampled . You lose certainty (this will be a common thread, for obvious reasons). Approximate Data Structures Your server handles 10,000 queries per second. You want to track how many distinct 1 active 2 users are using your service at any given moment in time. The problem: You need to store each user’s identifier, so you can check if you’ve seen them before. This scales linearly in the number of active users you have, i.e. it may cost a lot of memory for just a single observability metric you want to track. Expensive! Question: What if you could store the approximate user count, in a way that doesn’t cost a lot of memory? Enter HyperLogLog . It works by noticing that if I give you a random number from 0 to 999,999 then the odds of seeing a number that ends in 0 are 10%. The odds of seeing a multiple of a hundred (0, 100, 200, … 900) are 1%. Etc. Therefore, by mapping our users uniformly onto a slice of integers and keeping track of the most rare numbers we see, we get an approximate user count. “The HyperLogLog algorithm is able to estimate cardinalities of > 10^9 with a typical accuracy (standard error) of 2%, using 1.5 kB of memory.” ( Wikipedia ) There’s a whole bunch of fancy probabilistic data structures out there, see e.g. this post for a list of examples. Dropping the Tail You open up Google, enter a query. The Google search backend fans out, meaning that it sends your request to say, 100 different servers, each of which handles a “chunk” of the work required to answer your query. If Google waits for all of the servers to complete their work before returning an answer, then you have to wait for the slowest server . This is bad even under ideal circumstances: Imagine we have one hundred worker servers, each of which has a 1% chance of being slow. We are going to hit a slow server 63% of the time! Instead, you follow cancellation policies which allow dropping the slowest or least important work: Deadlines: Drop everything that takes longer than one second. After enough of the servers returned, cancel the remaining ones. (Could be 90%, could be “enough to fill the first page of Google Search”). Deadlines with partial results: Each server is responsible for returning the ‘best currently known’ result after a deadline is up. Evaluate returned results by quality, then cancel everything once you have enough high-quality results. The obvious tradeoff: The user has no guarantee you actually returned the data they were looking for. Trimming with Cheaper Substitutes Open any feedscroller app. Xitter, YouTube, TikTok, etc. Personalization is the name of the game, whatever you see at the top of the page has gone through some sort of ranking process that tries to maximize your engagement. Imagine for a second, how long it would take to rank every single post on Twitter according to your preferences. Now imagine having to do this every single time someone refreshes the page, and having to do it for all users across the platform. Expensive. Instead, you put a cheap selection tool in front of the neural net. This tool grabs a pool of potential candidates (say, ~1,500 tweets, according to Twitter ), which are then handed off to the (more expensive) neural network ranking them according to what it knows about your behavior. If you think about this, this is aesthetically unsatisfying: You spent a long time building an amazing neural network to get down preferences. Woo! And then, the final algorithm is still a Frankensteinian abomination, a complex multi-stage pipeline where every piece of content has to pass multiple stages, half of which may be ineffective or pure cost optimizations. Is this an example of a lossy system? Yes, of course. Running the algorithm on all available data is expensive, so you use heuristics to drop some of it, and then only process what’s left. Caching / Staleness Arguably the most fundamental pattern. Why re-compute everything from scratch every time you need the data? Just store it somewhere, lmao. Rollouts? Data consistency? Cache invalidation? Sharding and load-balancing? Consistent hashing ? How hard can it be? This is everywhere. Recomputing everything on request is expensive, and takes a long time. If you believe that users are not going to care if say, their search results are 30 minutes out of date, then it’s fine for search data to be outdated by 30 minutes. This is a pattern of a lossy system, in the sense that there is a deliberate decision to not gather data that you could have gathered. It sounds laughably simple, but requires you to think about difficult questions, e.g.: Where does the stored data live? Is it on disk or in RAM? Who is responsible for managing the stored data? Who updates it to ensure it doesn’t get too stale? What happens if it does get stale? How are we going to notice? Is the system going to serve stale data, or will it just go back to recomputing everything on demand? Does it get updated on-demand, or is there a regularly running (say, daily) job that refreshes the data? Can it be updated on a chunk-by-chunk or item-by-item basis, or do you need to update the whole thing at once? Does the stored data have a specific layout or schema associated with it? If yes, what happens if the schema changes? Does the data need to be refreshed immediately? Is there a risk that loading data with the old schema may break something? Depending on your situation, these questions will have vastly different answers. Critically, it’s important to understand that “serving stale data” often involves adding a new node to your distributed system. It’s another link, another component that can (and will) break, and this will cause exciting new (and hard to detect) failure modes you never even thought possible. No, really, why does it matter? You live in a society governed by technology. A small script on your computer behaves fundamentally differently from the mess that’s a big tech corporate technology microservice stack. Understanding a few principles of how large-scale systems work may help you understand the technology that surrounds you. We can couple our examples to obtain a worst possible outcome: You urgently need to go somewhere. You reach for Google maps and enter the information you received. Now, imagine that: For whatever reason, the worker process that would’ve found the place you are looking for never returned. Therefore, you cannot find the place on Maps. When you try to repeat the search, the previous result was cached. So instead of finding it on the second search, it keeps telling you that the place doesn’t exist. Due to sampling reasons, your complaint / bad experience never even makes it anywhere, it just silently gets dropped. This is (almost certainly) not how Google Maps actually works, but you can see the issue. Each piece of lossy friction within the system can increase the risk of errors or data loss, and multiple errors can combine into something worse than the sum of their parts. i.e. you cannot just count the number of queries you receive. ↩︎ i.e. you cannot just check how many users are signed up, some of them are not using your service right now. ↩︎📝MOND←TECH MAGAZINEWednesday, November 18, 2026
C++ Programming with No AI, LSP, or Debugger: Ep24 -- Back to NDC Coordinates🎥Zed A. Shaw
Java4Shell: when base64 decoding leads to remote code execution?Let us start with an example that triggers the issue. byte[] src = ("A".repeat(128) + "=").getBytes(StandardCharsets.US_ASCII); Base64.getDecoder().decode(src); One hundred and twenty-eight letters A and one =. The string is not valid base64, and a correct decoder rejects it. OpenJDK writes past the end of the array anyway. The bug is CVE-2026-114938. It has been in … Continue reading Java4Shell: when base64 decoding leads to remote code execution?📝Daniel Lemire's blog
C++ Insights - Episode 80: A facet of C++s narrowing conversions🎥Andreas Fertig
std::recursive_timed_mutex in C++ | Recursive + Timed Locking #shorts🎥CppNuts
How to Host an ISO C++ Standards Meeting🎥C++ Alliance
If the Windows documentation doesn’t list a particular technology as supporting an operation, does that mean that it doesn’t support it?Windows documents what it knows, but it doesn't know what third party network protocols support. The post If the Windows documentation doesn’t list a particular technology as supporting an operation, does that mean that it doesn’t support it? appeared first on The Old New Thing .📝The Old New Thing
Math on MeshesIn my very first numpy blog back in 2014, I closed with a teaser: the gradient of a field on an unstructured grid, “a concept that does not exist in numpy”. A few blogs ago, I also said there was a lot more to say about vtkmodules.util.functions. Let’s say it.📝Kitware Inc
LidarView 5.3: now connected to ROS2In this blog, we will focus on this last point: what possibilities this brings to ROS2 users, but also for non ROS2 users, and go into the implementation details as well as the limitations of the approach.📝Kitware Inc
Back to Basics: Move Semantics - Ruslan Arutyunyan - CppCon 2026🎥CppCon
C++を1行も書かずに - RustとWeb GUIで商用オーディオプラグインを構築する - Sota Ichikawa & hotwatermorning (Kohsuke Yuasa)🎥audiodevcon
⬢ Distrobox: An In-depth Guide for Developers - Part 2Distrobox gives developers a fast, practical way to work across Linux distributions without the setup time and resource overhead of full virtual machines. This the second part of an in-depth guide. It is recommended to read the first part, if you haven't read it, yet.📝KDAB
C++ Insights Episode 80: A facet of C++s narrowing conversionsI published a new C++ insights episode: A facet of C++s narrowing conversions. In this episode, you'll learn about a fact of C++'s narrowing conversions and how I tripped and almost felt :-) Andreas📝AndreasFertig.com
"Breathe"“Breathe.” The city is brimming as heat rises from the asphalt. An artificial enclave, chock-full of cars, stumbling addicts, skittering rats, and there’s a hostile glare in the air. “But I cannot just”. Stop? Correct. It’s not who you are. You strive. You keep climbing higher, and higher, until you find yourself at a level where everyone is as smart as you, everyone has the same level of ambition, and you realize that you don’t know why you are here and finally start to crack and break down. The universe has allocated you just enough time to drag yourself out of the hole it put you in, just in time to watch the world be cut into atomized slices and get addicted to feedscroller ai-generated fruit cuckolding pornography appslop. This is the IQ shredder. Go on. Throw yourself into the blender for literally no reason, and remember that your flaws are deeply innate and fundamentally lower your worth as an individual. Or go shit yourself in the gym while deadlifting after dry-scooping five types of preworkout. it’s at least going to be a story You pass half-open laptops, men bragging about their incoherently circulating agent swarms with the same retardation with which managers re-allocate SWEs to poorly-drafted “Enterprise-ready” B2B SaaS projects, waiting to be made obsolete by raw, equalizing intelligence and anyone with a plan. Yeah, look at that guy over there adding another line to his claude.md . When you moved here, you thought the billboards stopped being ugly and started being generic, and you hate what this says about your sense of aesthetics. Have you heard of that new start-up? they’re running ads on Tubu. they have Heebee sponsorship. it’s on Poodoo with ads. it’s on Poob— right, you haven’t watched a show in ages Is this it? Look, you know why you are here. You made the decision to come here. You have no one to blame but yourself, and that inkling of fear in your heart that you will not be there when it happens. You know that your presence here doesn’t matter, right? Of course you do. This machine is in motion, has been for ages. You couldn’t steer it off course even if you knew what to do. Didn’t stop you from coming here. it’s the call to adventure bro it’s lit it’s the grand cosmic dance, enjoy the social atomization while it lasts, you know that you feel more at home with the insane people you met online, look if you just believe strongly enough it’s all going to work out, it’s like gurren lagan bro Breathe. Take a step back. Drop five placebos before bed. Unwind. You are still tense. Today it feels different. Less sharp. Your teeth are gritting again. You should be tense. But the other tense. Something that wells up from within, encompasses you, and opens you up to be shaped by the world into the you that needs to exist. ugh. you are not even tired. crawl out of bed, slam down another huel, feel better about yourself than you should, and head back to doing whatever you pretend to care about Do you still remember what you did yesterday? Do any of these days fit into a coherent narrative arc, or are you just retroactively inventing one? Every non-decision in your life led to this very moment, please cherish it.📝MOND←TECH MAGAZINETuesday, November 17, 2026
C++ Optimizations in MSVC Build Tools 14.52C++ Optimizations in MSVC Build Tools 14.52 The Microsoft C++ team implemented new optimizations in MSVC Build Tools 14.52. Let’s walk through examples of some of these optimizations. We will focus on reassociation, loop optimizations, SIMD code generation, inlining, and patterns. Where noted, we’ll also include a few optimizations that appeared in MSVC 14.51 but […] The post C++ Optimizations in MSVC Build Tools 14.52 appeared first on C++ Team Blog .📝C++ Team Blog
Lightning Talk: Organic Evolution of Reflection in Apache Thrift - Shai Szulanski - C++Now 2026🎥CppNow
In the Microsoft employee price list, why did the BASIC compiler cost less than the BASIC interpreter?Understanding the pricing scheme. The post In the Microsoft employee price list, why did the BASIC compiler cost less than the BASIC interpreter? appeared first on The Old New Thing .📝The Old New Thing
How I built a simulation with C++23 and Unreal #tutorial #coding🎥CppCon
C++ Programming with No AI, LSP, or Debugger: Ep23 -- Rect and Meters🎥Zed A. Shaw
How can I ask a second program to show a dialog box as if it were shown by my first program?You have to explicitly coordinate the window management. The post How can I ask a second program to show a dialog box as if it were shown by my first program? appeared first on The Old New Thing .📝The Old New Thing
ceo mindsetNever type in full sentences. Abbreviate. Single word answers. Typos. Make everyone stress out for hours over the e-mail or pitch deck they want to send you, then gut-punch them with a two word “luv it” or a “no”, and refuse to address any questions they asked. Ignore their follow-ups. They get five minutes of your attention per week. Make them wait. You are a node, a data nexus, a machine that exists to loosely associate and make decisions, your attention is split across hundreds of pitch decks a week. If they want something from you, it’s on them. If you’ve ever used full grammar talking to someone beneath you in the corporate hierarchy, you are not going to make it. – Sent from my iPhone fit off The employim need a shepherd to guide them. I am that shepherd. They must be guided like sheep to the pasture, so that they may graze in the fields of free microkitchen drink benefits, and provide shareholder value even through bearish downturns. It is I who take responsibility. I am the one who lays off. 45 minute meditation on why all of my enemies are ontologically evil. CEO mindset affirmations. Sigma style. I am the wolf that howls. I am the door that opens. I am the one who peels the infinitely-layered onion. Unstructured data. Business insights. 6'2" at my standing desk. Polished black leather Santoni shoes. Just coffee, black. Macbook Air. Custom-tailored slim-fit suit. Hair gelled-back. Stack of cards on the table. Eggshell. Romalian type. Subtle watermark. No e-mail, phone, or LinkedIn. Make them work for it. Words are hanging in the air. If someone called out my name, it didn’t register. Airpods are in. Liquid Drum n Bass Cheetah Mix - Peak Focus For Complex Tasks [2022] . I am locked in. I multi-task, Oura’ed finger rapidly jackhammering a worn-out Tab key to jump across nineteen open charts back to the one specific email draft I need. There it is. “Hey, sorry for the hold-up, it looks like there’s been a procurement issue on the side of one of our suppliers, we’re currently—” My eyes glaze over as I type a response. “no ask jeff” Sent. I get up. I enter the fortnightly business report pre-alignment, claim a seat. We start, watch a pretty, dolled-up thing with slightly-off-burgundy lipstick present flowcharts of actionable business insights. Susan, I think. Flowcharts AI generated, of course. She has not looked at them before. That’s how we roll. Synergy. Low-hanging fruits. Take it to the next level. Move the needle. Outside the box. The words flow like honey, caressing my ears. Three minutes later, the door opens. A man steps in, still fiddling with his iPhone Pro Max. No case. Casual turtleneck. Jeans. Sneakers. No laptop, no suitcase, no notebook. Every molecule of moisture is sucked out of the air, and my throat is dryer than parchment paper. My suit feels tight. I feel tense. He smiles at the crowd that he just interrupted. Don’t clear your throat. Look at him. Raise your left eyebrow by half an inch, then look back to Senior Programming Manager Michael. Bare hint of a smirk. CEO Mindset. CEO Mindset. ceo mindset mindset mindset My brow doesn’t move. Whatever spell this guy has cast, his power level exceeds my own, and there is nothing I could’ve done to protect my people from his influence. He is brimming with aura. His chakras are aligned. i am the redditor, and he’s the 4chan shitposter whose posts are funnier than mine. oh god his net worth must be so much higher than mine mogged no fit-off ever felt so humiliating. he is snoopy, i am charlie brown he is Mt. Everest, i am the stupid chudded out mount godwin-austen K2 that literally no one gives a shit about i am the original poster, he is the reply-chad ratio-mogging my X dot com join the conversation post by depicting me as the soyjak and himself as the chad he deadlifts three plates, and i shat myself in the gym after dryscooping two ounces of creatine The guy reaches for a chair, pulls it back and sits down. For a brief moment everyone is silent. “Uh, hey guys, sorry, I uh… I’m the new guy, I couldn’t find the room, hahah…” A beat. We are back. Warmth rushes into my limbs. I feel air rushing out of my mouth, then sharply bite my tongue to stifle the breath of relief before it has any chance to escalate. “Uhm, you can continue, sorry, it won’t happen again.” My eyebrows are back under my control. They waggle. Briefly. They skeptically dart back and forth across the crowd, before finally joining my chin to communicate ‘continue’ to Susan on the other side of the table. Susan fidgets with her cheap laptop, reaching for whatever app she uses to present her slides. New guy. I stare at him from across the table. I smile.📝MOND←TECH MAGAZINEMonday, November 16, 2026
C++ Programming with No AI, LSP, or Debugger: Ep22 - Rectangles🎥Zed A. Shaw
MSVC Build Tools version 14.52 now generally availableMicrosoft C++ (MSVC) Build Tools version 14.52 is now generally available as a long-term support (LTS) release. It is available with Visual Studio 2026 version 18.12 on the Stable Channel and Visual Studio 2026 LTSC version 18.11, both released on November 10. With this release, C++23 is ready for production use through /std:c++23, and the […] The post MSVC Build Tools version 14.52 now generally available appeared first on C++ Team Blog .📝C++ Team Blog
Classic C and errors of GmSSL projectWhile AI is discovering new ways to make mistakes, human developers stay true to the classics: typos and memory errors. Let's take a look at them.📝from pvs-studio.com
Cognitive radiusThe most interesting change AI brings to software work is not faster coding. It is the expansion of context or range… what I call radius. For decades the job was defined by the limits of what one person could hold in their head. You tended to specialize. You got good at one or two systems, … Continue reading Cognitive radius📝Daniel Lemire's blog
C++ Weekly - Ep 559 - Computing Template Parameters🎥Jason Turner
C++26 Uncovered: Everything You Need to Know About the New Standard :: Inbal Levi🎥CoreCpp
Real-Time Control, Simulation, and Visualization in C++23 With CUDA and Unreal Engine - Kevin Gomez🎥CppCon
std::recursive_mutex Explained | C++ Multithreading #shorts🎥CppNuts
Constraining Templates Before and After C++20 - The What, the How, and the Why - Johannes Kalmbach🎥ACCUConf
Introducing Focusrite Group Japan - Takeshi Nishimoto & Kengo Shimizu - ADC Japan 2026🎥audiodevcon
::🎥CoreCpp
FFTs Part 3: Some Optimizations to the FFTThis is part 3 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 (← you are here) The Inverse FFT The FFT-20XX Complex-Input Algorithm The FFT-20XX Real-Input Algorithm(s) In the last post we got to a basic implementation of the radix 2 decimation-in-time Cooley-Tukey algorithm . But there are still other additions and optimizations we can make before getting into the way FFT-20XX works. We’ll start by diving into the “radix 2” part of the algorithm: we can make improvements there. Butterflies Before we go into the specifics, I’m finally going to bring in a classic FFT diagram: the butterfly , an FFT data flow diagram. The most basic one is for a FFT of length 2, which has only a single step over two inputs. Here’s a diagram for the radix-2 decimation-in-time length-2 FFT (a 2-element version of the algorithm we derived in the previous post): Diagram of a 2-length FFT, showing the two inputs going into a single processing node, then back out to the two outputs. The second input node has a "0" representing the fact that it is unrotated. " 0 1 0 1 0 In this diagram, the inputs are on the left, each computation (just one, in this example) is represented as a small circle, and the outputs are on the right. The computation (for a decimation-in-time FFT) rotates its second input (the odd input, which is the bottom one in the diagram) by the given rotation value; in this diagram the rotation is just a 0 0 , but in general the value there will be some t t where the actual rotation angle is t / N t/N clockwise turns ( − 2 π t / N {-}2\pi t/N radians), where N N is the length of the FFT. Note The formatting of these butterfly diagrams is a little different than a standard butterfly diagram, which tend to look more like the following: A classic-style diagram of a 2-element FFT, with a "w" component on the second input showing it rotates 0/2 times, then gets added to the first input for the first output and subtracted from the the first input for the second output. w 0 2 -1 0 1 0 1 These diagrams are more comprehensive (the w N k w^k_N value makes the fraction of k / N k/N clockwise turns clear, where in my diagrams the “ / N / N ” is implied), it has a − 1 -1 multiplier on the lower input going into the sum circle (to signify that the bottom “sum” is a difference), and the sums are each on their own line as opposed to a central circle that represents the add/subtract pair, but in practice — especially on lower-resolution displays — my variant is, imo, less visually noisy. Plus, once you get into the higher radixes, even the standard diagrams start to be drawn more simply. Now here’s one for the decimation-in-time length-4 FFT (where the bit reverse is performed on the input): Diagram of a 4-element FFT, showing how the even inputs and odd inputs combine with each other in the same way the 2-element FFT's do, then how the results of those interleave to create the final outputs. 0 2 1 3 0 1 2 3 0 0 0 1 There are two “stages” in this radix-4 FFT (two runs of the outer loop of the code), which are separated via the vertical dotted lines. Really, though, this is four of the previous (length 2 FFT) butterflies bolted together, first with two separate 2-element computations (the first pass) followed by a single 4-element computation loop (the second pass, itself just two 2-element computations stacked on top of each other wearing a trench coat). Finally, here’s a butterfly diagram for a full 16-element FFT: A more complicated diagram of a 16-element FFT, showing the four "stages" of processing and how they interleave. 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 0 0 0 0 0 0 0 4 0 4 0 4 0 4 0 2 4 6 0 2 4 6 0 1 2 3 4 5 6 7 There are four stages in this one (since log 2 16 = 4 \log_2\,16 = 4 ), and note that you can still see the structure (discussed in the previous post) of eight 2-element computations in the first stage, then four 4-element computations in the next, then two 8-element computations, then a single 16-element computation. Also note the rotation angles in each stage: the last stage has rotations 0-7 (corresponding to 0 / 16 0/16 to 7 / 16 7/16 turns), the previous one has just the even numbers, the one before that just 0 and 4 (every other even value), down to no rotations in the first stage. This is true in general (and if you look at the code we derived in the previous post, you can see the same relationship) where the last iteration has the most rotations, the next-to-last has half as many, and so on. Now, here’s a diagram that we made in the previous post, showing a 16-element FFT in a sort of “index flow” way: A diagram from the previous post showing the way the indices interleave at each step as they flow through the FFT. 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 0 4 8 12 2 6 10 14 1 5 9 13 3 7 11 15 0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Hopefully, the similarity between this diagram and the previous one is apparent: they’re diagramming the same process, but with different goals (the latter showing the indices flowing through the system, and the former showing the flow of values and the angles used to compute them). So, now that we (hopefully) have an understanding of these diagrams and what they represent, it’s time to move on to the first optimization: a higher radix. Doubling the Radix We went with a radix-2 breakdown in the last post because it’s the most straightforward, but there are others. The one we’re going to focus on here is radix-4 , which, in contrast to the above 16-element butterfly diagram, would instead look like the following (don’t worry about the specifics of the rotation values or what this four-in/four-out computation node is doing yet — we’ll get to that shortly): A diagram of the same 16-element FFT as before, except this time as a radix-4 transform, with every 4 inputs combining together, then those combining in a second pass to generate the final outputs. 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 0 0 0 0 0 0 0 0 0 0 0 2 4 6 0 1 2 3 0 3 6 9 The first things worth noticing here are that there are now half as many passes over the data, and each computation handles four values at a time instead of two. This will end up being more efficient in a couple different ways. The main efficiency gain is that doing half as many passes means it halves the number of reads from and writes to memory , which as the FFT lengths get larger can make a big difference in how often there are cache misses. Second, it is possible to reduce the number of rotations needed by 1 4 \frac{1}{4} , which can also make a difference on some CPUs (but not all, which we’ll get to). To derive a radix 4 solution, you could go back to the original equation, split the inputs into four interleaved sections (where k m o d 4 k\mod 4 is 0 0 , 1 1 , 2 2 , and 3 3 respectively), then split the outputs into quarters, and redo all of the rotation shenanigans that we did when deriving radix-2. Nah . I’m not doing all that. Instead, we’re going to start with the radix-2 diagram and build up to what that four-in/four-out computation looks like. Every pair of radix-2 passes can be turned into a single radix-4 pass, so let’s start by highlighting a couple such groupings in our radix-2 diagram: The diagram of the 16-element radix-2 FFT again, but this time with the first two stages for the first 4 inputs highlighted in blue, then last two stages corresponding to outputs 2, 6, 10, and 14 highlighted in red, showing them both as being topographically the same, despite the spacing difference. 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 0 0 0 0 0 0 0 4 0 4 0 4 0 4 0 2 4 6 0 2 4 6 0 1 2 3 4 5 6 7 Each of the groupings of “two pairs of radix-2 passes that all use the same 4 values” can be represented generically as: A diagram similar to the earlier 4-element radix-2 FFT one, showing that inputs 2 and 3 get rotated by 2t, then the outputs of the inputs 1 and 3 computation get rotated by t and t + N/4 respectively before going into their final passes. '0' '2' '1' '3' '0' '1' '2' '3' 2t 2t t t+ N ― 4 Note the similarity between this and the 4-element butterfly diagram we made earlier: this is essentially just a generalized version of that. The input/output indices are relative to the position in the FFT, but note that the middle two indices are in the opposite order as the output indices: this will always be true when we’ve done the bit reverse at the outset, and remains true no matter which intermediate step we’re on (i.e. it just automatically happens that way). Also note that the angles themselves are relative, too: there will be some base angle t t that the other angles are relative to, and we’ll set it as the first angle in the second radix-2 pass (the t t just to the right of the middle line). As examples, in the first highlighed group at input indices 0, 8, 4, and 12, t t is 0 0 , and in the second at output indices 2, 6, 10, and 14, t t is 2 2 . Both angles in the first radix-2 pass are double this t t value (both labeled 2 t 2t ), and the second angle in the last pass is always a quarter turn more than t t (labeled t + N 4 t + \frac{N}{4} ). To get from here to a full radix-4 computation, we can rearrange the angles a bit to get something equivalent: Diagram of the same transform as the previous one, but with the angles rearranged. This time inputs 1, 2, and 3 get rotated by t, 2t, and 3t respectively, then the second output of the 1 and 3 transform gets rotated a quarter turn. '0' '2' '1' '3' '0' '1' '2' '3' 2t t 3t N/4 The Math We do this by splitting the t + N 4 t + \frac{N}{4} apart at the addition, making it a rotate by t t then a separate rotation of N / 4 N/4 . We can then distribute the common rotation by t t back to the first stage and do them on inputs ‘1’ and ‘3’: input ‘1’ had no rotation so it ends up with a rotation of t t , and for input ‘3’ the t t combines with the 2 t 2t it already had to make a single rotation of 3 t 3t . The N / 4 N/4 turn (a 90-degree clockwise rotation) can be done without any sine/cosine multiplications at all (it transforms a + i b a + ib into b − i a b - ia ), so this is mathematically more efficient: it does 3 rotations on three inputs at the start of the process instead of 4 rotations split between the first and second inner radix-2 stages. The number of adds/subtractions remains the same, but that’s okay: there’s no way to reduce it any further. This, then, is what becomes the computation node of the radix-4 butterfly diagram we made above! Here is the equivalent radix-4 diagram to the previous diagram (which hides the internal complexities, including the effectively-free quarter turn): A 4-element radix-4 diagram showing the same t, 2t, and 3t rotations as the previous diagram, but instead as a single radix-4 process instead of 2 separate radix-2 passes. '0' '2' '1' '3' '0' '1' '2' '3' 2t t 3t Note An implementation detail worth mentioning here: on some systems using the first 4-element breakdown from above (the radix-2 one with the t + N 4 t + \frac{N}{4} term) can be more efficient! There are systems that have FMA instructions (the fused multiply-add ) which have a cost close to doing either a multiply or an add by itself (x64 CPUs with the FMA extension — like most with AVX2 instructions — have this property). Doing it that way (which is sometimes referred to as radix- 2 2 2^2 ), even with what seems like an extra complex multiply, can end up being cheaper due to less overall operations and one less required angle (the 3 t 3t angle isn’t required, using t t and 2 t 2t is sufficient). There’s a breakdown of this trick on The ryg blog: Notes on FFTs: for implementers . Here’s the 16-element radix-4 diagram we used earlier, with our same two radix-4 sections highlighted: Diagram of a 16-element radix-4 FFT with the same corresponding "blue" and "red" highlighted paths as in the earlier radix-2 diagram. 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 0 0 0 0 0 0 0 0 0 0 0 2 4 6 0 1 2 3 0 3 6 9 Note This formulation of radix-4 is slightly different than the canonical one, which has a different “scrambled” input or output order from the bit reverse that we’re using. In that case, the reordered indices are reversed pairs of bits: for instance, an 8-bit binary value with bits 01234567 would becomes 67452301 instead of 76543210 . Instead, we’ve kept the radix-2 style bit reverse, the consequence of which is the reversal of the middle 2 inputs in the above diagrams (with reversed bit pairs , those would be in proper order, and the angles would instead be t t , 2 t 2t , and 3 t 3t , respectively). Now, hopefully, it’s clear why the angle values are the way they are in this diagram. The first stage has no rotations (except for the effectively-free 90-degree rotation), and the second stage has four computations with increasing rotation values of the form 2 t 2t , t t , 3 t 3t . The only issue with using the radix-4 algorithm is that it only fully works on FFTs with power-of-four lengths (because it splits in fours each time, so it works for length 4 but not 8, 16 but not 32, etc). The good news is that the way we’ve formulated it (by effectively smooshing together two radix-2 passes into a single radix-4 pass), you can just put a single radix-2 pass in there to make up the difference … and it doesn’t even matter where! Here is a length-8 FFT where the first pass is still radix-2 but the second is radix-4: Diagram of an 8-element FFT where the first pass is done as radix-2 and the last is done as radix-4. 0 4 2 6 1 5 3 7 0 1 2 3 4 5 6 7 0 0 0 0 0 2 0 1 0 3 And here’s the same length-8 FFT the other way around: radix-4 then radix-2: Diagram of an 8-element FFT where the first pass is done as radix-4 and the last is done as radix-2 (the opposite ordering as the previous diagram). 0 4 2 6 1 5 3 7 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 1 2 3 For longer FFTs, the radix-2 pass can be anywhere in the middle, as well - whatever is most efficient for your implementation! I found it easiest to place it right after the very first radix-4 pass (i.e. like that last diagram), mostly for simplicity. Other Radix Flavors So if radix 4 is more efficient than radix 2, that raises the question: are there other, even more efficient radixes? radix-8? radix-16? How far is too far? Well, radix-4 is the largest power-of-two radix that has “free” rotations in the middle (that quarter turn). Radix-8 has some 45-degree-multiple rotations in the middle, which still require some multiplication. However, because both cosine and sine of 45 degrees (and related friends) are both 2 2 \frac{\sqrt{2}}{2} , the multiply can be done as a common factor so it still is somewhat more efficient. The problems with radix-8 tend to have to do with CPU register limits: you need to load 8 complex values (so 16 scalars), then (similar to how radix-2 needs 1 rotation and radix-4 needs 3) it tends to need 7 complex twiddles plus the 2 2 \frac{\sqrt{2}}{2} internal value (so another 15 scalars) and you tend to also need some scratch registers as well to do computations. AVX and AVX2 only have 16 SIMD registers so even before you get to the angles you’ve already run out of register space. AARCH64 has 32, so you could maybe squeeze in there, but it would be tight. Plus you’re going to be up against CPU cache associativity for systems with eight-way associative caches, because you’re loading from 8 locations but also need to be loading the angles from somewhere. Past radix-8, you’re out of register space, hitting CPU cache limits, and also have more internal rotations, so it’s going to perform way worse under most circumstances. Note One place where it’s really tempting to use radix-8, however, is on the very first decimation-in-time step, which has no twiddles (all seven of the twiddle angles are 0), and thus only has those nice-to-compute internal 45-degree rotations. However, the register limits are still an issue and, depending on how you have to load your values (i.e. for SIMD purposes you may want to do a deinterleave to separate the real and imaginary components), you may still not have enough register space. But it’s worth considering, if you can. There is another radix option worth mentioning: the split-radix FFT algorithm , which I’m not going to detail here (because it’s complex and weird). In terms of required math operations, the split-radix algorithm gets you to some of the lowest-known possible operation counts. Unfortunately, in practice, I found that it breaks up the nice regularity of using just a standard radix-4 algorithm and ultimately — at least in my attempts at implementing it — had worse performance overall. Okay, we’re through all of the radix shenanigans! Lookup Tables The last thing to touch on in this post is doing lookup tables for the angles . These tend to be exactly what they sound like: you precompute a table for your required FFT length that contains all of the sin/cos values needed for that length. The simplest lookup table is one where you have N 2 \frac{N}{2} cos/sin values ( 0 0 turns through N 2 − 1 \frac{N}{2} - 1 turns), in order. However, there are some potential ways to make the table a little more efficient (with size, cache-friendliness, or both): In many implementations, you don’t need both N 2 \frac{N}{2} cos \cos and N 2 \frac{N}{2} sin \sin values: because cos ( t ) = sin ( π 2 + t ) \cos(t) = \sin(\frac{\pi}{2} + t) , you can store 3 N 4 \frac{3N}{4} scalar values and start the cosine lookup partway into the table, and use 1 4 \frac{1}{4} less memory. If you’re doing radix-4, you can avoid storing the 3 t 3t angles and instead compute them using the t t and 2 t 2t rotations, which saves a bunch of table space. This may sound like you’re adding a complex multiply back in after eliminating it, but you can likely move that computation into an outer loop so it isn’t an issue. It can also be convenient — for SIMD loads and CPU cache-friendliness — to store not only the angles in order for size N N , but to store all of the table sizes from some minimum length (like 4 or 8) up to your max length. Doing this is nice because it means you can build a single table for your maximum required FFT length and it will perform just as well for any smaller FFT lengths as well. Also, the earlier passes of the algorithm can take advantage of these smaller tables (the second radix-2 pass only needs the angles for a length-4 FFT, and the next only needs the angles for a length-8 FFT, etc). Loading from them can help with CPU cache coherence (as all of the required angles at that level are contiguous), plus SIMD loading if you need multiple angles within a single pass. For FFT-20XX I found all of the above bullet points to be useful. What Now? No code this time, but using the above tricks (namely: using radix-4 instead of radix-2 where possible and switching to lookup tables for the rotations) gets you to a somewhat decent baseline FFT implementation! There are many more places to optimize: figuring out SIMD support and optimizing the bit reversal pass (or — spoiler alert — eliminating it altogether). We’ll get to those once we finally get into FFT-20XX’s algorithms. Before that, next time , we’ll touch on the decimation-in-frequency version of the algorithm on our way to finally talking about the inverse FFT and how to compute it!📝JoshJers' Ramblings
I'm joining Google!I have some exciting career news to share: I'm joining Google's AI Edge Performance team as a Staff Software Engineer, working on YNNPACK and Slinky ! If you haven't heard of them before, YNNPACK is Google's next-generation neural network inference engine (succeeding XNNPACK ), and Slinky is the Halide -inspired loop scheduling and dataflow runtime at its core. Where XNNPACK traditionally optimized whole operators one by one (across a large combinatorial space), YNNPACK schedules low-level microkernels with Slinky to automatically fuse loops across subgraph boundaries, improving memory locality and reducing synchronization overhead.📝Alex Reinking
C’s designated initializers give us named argumentsIn my previous post I talked about C++’s “relatively nerfed” form of designated initializers. This time I want to show you a neat thing you can do with C’s full-power designated initializers. I first saw this pattern in Ben Klemens’ book 21st Century C (2014), pages 226–228. (Godbolt.)📝Arthur O’DwyerSunday, November 15, 2026
Lightning Talk: Our Most Treacherous Adversary - James McNellis - C++Now 2026🎥CppNow
What really kills C++The C++26 ballot failed, and everyone is arguing about contracts and the future of C++. I think we're worried about the wrong thing.📝Engineering the Craft
Can AI Make a Multiplayer Game?🎥The ChernoSaturday, November 14, 2026
Linus Called C++ Horrible. So I Read Git.🎥DeepDiveDev
Pay Up, Nerds🎥Matt Godbolt
Reading JSON at 277 GB/s in PythonMany systems log their data as JSON, one record per line (NDJSON). GitHub, for example, publishes every public event on its site that way through GH Archive: about a gigabyte per hour. Suppose you want to know which repositories received the most stars over eight hours. That is 7.6 GB of JSON, 2.2 million events. … Continue reading Reading JSON at 277 GB/s in Python📝Daniel Lemire's blog
Thoughts on the AI usage in the C++ committee🎥MeetingCpp
How I made chess move generation 20x faster #programming #chessengine #coding🎥CppCon
C++ Programming with No AI, LSP, or Debugger: Ep21-- Images Finally Placed🎥Zed A. Shaw
std::mdspan in C++23 Explained | N-Dimensional Array Views in C++🎥CppNuts
Fearless Concurrency in C++ - Tristan Brindle - ACCU 2026🎥ACCUConf