Wednesday, November 18, 2026

If this page is useful, please consider donating a coffee

Tuesday, 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
Trust But Verify: Security and Privacy Considerations for Remote Build Execution (RBE) PlatformsTrust But Verify: Security and Privacy Considerations for Remote Build Execution (RBE) Platforms For organizations using Bazel and RBE, your build graph is effectively a fingerprint of your product ecosystem and the engineering hierarchy behind it. Depending on the extent to which Bazel and monorepo usage is established within your organization, your Bazel build graph may be composed of interdependent ( configured) targets , actions , and artifacts spanning every single dependency, service and test that exists within your codebase. Other highly valuable sources of metadata related to your codebase that Bazel can produce are JSON trace profiles , effectively structured recordings of what happened during a build and how long it took. Combined, and observed in time, those two data sources offer insights into release cadence, acquisition targets, engineering headcount, and products potentially being shipped before you are actually ready to ship them. In other words, they are some of the most sensitive data sources an engineering organization produces, and they are routinely treated as exhaust.📝EngFlow Blog
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 MAGAZINE

Monday, November 16, 2026

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
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
No imageGSoC 2026 - Adding Fortran Support to LLDBGSoC 2026 - Adding Fortran Support to LLDB (LLVM) While Flang has matured, the developer tooling around it has lagged behind. In particular it lacks a dedicated debugger. LLDB lacks native Fortran support, it is only able to resolve basic breakpoints via raw line tables. This project adds support for Fortran in LLDB and lays the foundations on which a fully-featured Flang-backed debugger can be built. Specifically, this work introduces native support for: Primitive types ( INTEGER , REAL , LOGICAL , COMPLEX ) Arrays Pointers Functions Current Status & Running the Code Because the upstreaming process for a project of this scale is ongoing, not all features have been merged into the LLVM main branch yet. However a working implementation is available for anyone to test. You can view the full set of changes, clone the code, and compile it yourself from my personal branch . To keep up to date with the ongoing integration of this project, you can follow the tracking issue . High-Level Architecture Adding a new language to LLDB requires teaching it how to extract, represent, and display the values from compiled binaries. This relies on three core components: DWARFASTParser : Parses compiler-generated DWARF debug information and extracts raw type metadata (e.g., symbol names, byte sizes, and layouts). TypeSystem : Represents the internal type model of the language within LLDB. It takes the metadata parsed from DWARF and constructs native LLDB type representations. Language Plugin : Registers Fortran with LLDB and supplies language-specific pretty-printers, value formatters, and synthetic children providers. For more details on how to add a new language to LLDB, see the official documentation . RFC process When proposing any significant change to LLVM, it first needs to go through the RFC process . In short, a proposal is written providing an overview of the change, the motivation behind it, the overall architecture of what will be changed, and open questions. It then receives feedback, and if consensus is reached, the change is accepted and can be upstreamed. Reaching consensus on my RFC took approximately two months since it was a major new feature, but it taught me a lot about how to communicate an idea and interact with other developers. The most important decisions we reached in the RFC were: Figuring out where and how testing would be performed, including setting up buildbots (x86_64 / AArch64) to prevent bit-rot. Expression evaluation will eventually be supported using Flang, but later in the project’s lifetime and outside the scope of GSoC. LLDB will not link directly to Flang at this stage due to Flang’s demanding build requirements. For now, only a Fortran compiler is needed to run tests. Array support will be added using synthetic children, rather than making intrusive changes to LLDB’s core infrastructure. Language-specific details like Fortran’s case insensitivity will be handled inside the plugin via DWARF attributes ( DW_AT_identifier_case ) without polluting core LLDB. Testing and Upstreaming For a large part of GSoC, development took place on my personal LLVM fork while waiting for community consensus on the RFC. Once consensus was reached, the focus shifted to breaking the work into small, incrementally testable pull requests that were easy for maintainers to review. To ensure long-term stability without regressions, the implementation leverages LLDB’s lit-based testing infrastructure across two distinct levels: Unit Tests (C++): Added three test suites to test core components in isolation: TypeSystemFortranTests : Verifies that TypeSystemFortran correctly instantiates, constructs, and queries Fortran types. DWARFASTParserFortranTests : Tests that raw DWARF debug info is parsed accurately into internal types. FortranLanguageTests : Validates language plugin registration and synthetic child provider hooks. API Tests (Python / SB API): End-to-end integration tests using LLDB’s Scripting Bridge API . These compile sample Fortran programs, launch debug sessions, and verify that the plugin, DWARF parser, and type system communicate properly to inspect variables and print output. For more details on LLDB testing standards, see the official testing documentation . Features added 1. Laying the Foundation For API tests, LLDB needs to compile sample Fortran programs. This patch updated LLDB’s test runner to automatically detect an installed Fortran compiler and conditionally enable the Fortran test suite. PR #208298 Before adding actual language features, LLDB requires substantial boilerplate to satisfy its internal interfaces, specifically the TypeSystem , which demands numerous stub methods just to compile. To keep patches incremental and easy to review, this initial scaffolding was split into three minimal PRs that contain no active feature logic (except for registering the language plugin itself): Language Plugin Registration: Registers Fortran as a supported language within LLDB. PR #218014 TypeSystem Stubs ( TypeSystemFortran ): Adds the class skeleton and required interface overrides. PR #218016 DWARF Parser Stubs ( DWARFASTParserFortran ): Adds the parser skeleton to prepare for DWARF type parsing. PR #218024 2. Primitive Types Primitive types in Fortran consist of the INTEGER, REAL, LOGICAL and COMPLEX types and they are all described by the DW_TAG_base_type DWARF tag. Type System Implementation TypeSystemFortran manages the lifetime and representation of all Fortran types in LLDB: Memory Management & Deduplication: For memory management without leaks, types are stored as unique pointers in a vector. To avoid redundant allocations, an LLVM FoldingSet uniques types so existing instances are reused whenever a matching type is requested. Primitive Type Representation: To represent basic primitive types ( INTEGER , REAL , LOGICAL , COMPLEX ), the type system tracks three essential properties: Type name Byte size Type kind Add support for basic types in TypeSystemFortran PR #218269 DWARFASTParser Implementation DWARFASTParserFortran bridges the raw debug symbols generated by the compiler and LLDB’s internal type system: Tag Recognition: Parses the DW_TAG_base_type and its children, collecting information about the type. Scope Extraction: Calculates the scope/context of the type. Type Construction: Forwards the extracted information to TypeSystemFortran to instantiate and cache the corresponding type. 3. Functions & Subroutines Type System Implementation (Functions & Subroutines) To represent Fortran functions and subroutines, TypeSystemFortran tracks three key elements: Parameters: Stores the name and type of each parameter, which are used to construct the function signature and resolve argument inspection at runtime. Name: Receives the base identifier from the DWARF parser and formats the complete Fortran signature (e.g., INTEGER sample(INTEGER arg1) ). Return Type: Tracks the return type for functions (or absence thereof for subroutines) to build the signature and provide accurate type info. DWARFASTParser Implementation (Functions & Subroutines) When encountering a Fortran function or subroutine, DWARFASTParserFortran handles two main tasks: Parsing Subprogram Information: Identifies DW_TAG_subprogram (and Fortran subroutines) and extracts the symbol name, parameter metadata, and return type, passing them to TypeSystemFortran to instantiate the function type. Calculating Frame Bounds: Determines the start and end memory addresses (low/high PC) of the subprogram. This address range is essential for stack frame unwinding and allows frame variable to correctly locate and display local variables in the current scope. 4. Variable Printing For variable values to be printed correctly, the TypeSystem provides information about how they should be displayed, such as their encoding and formatting, along with implementing DumpTypeValue to format and dump the value to a stream. With this addition, frame variable can print variables in a predictable way: (lldb) frame variable num_real (REAL) num_real = 2.71828175 (lldb) frame variable num_int (INTEGER) num_int = 152 (lldb) frame variable num_logical (LOGICAL) num_logical = true (lldb) frame variable z1 # TypeSystemFortran formats complex as (real, imaginary) to match how Fortran prints them (COMPLEX(KIND=8)) z1 = (3, 4) With this addition API tests were also added, since the output could not be tested before. 5. Pointers Pointers assosciated with non-array types are similar to C-like languages. So to handle them all that is needed is the pointee type. Type System Implementation The TypeSystem creates a pointer type from the pointee type. It can also provide the pointee type from the pointer type and vice-versa. DWARFASTParser Implementation The DW_TAG_pointer_type has a reference to the pointee type as a child, so the pointee type is recursively parsed using this reference and is forwarded to the TypeSystem. Output (lldb) frame variable target_val (INTEGER) _QFEtarget_val = 42 (lldb) frame variable int_ptr (INTEGER *) _QFEint_ptr = 0x000055555563d1e8 (lldb) frame variable &target_val (INTEGER *) &_QFEtarget_val = 0x000055555563d1e8 (lldb) frame variable func_ptr (INTEGER (INTEGER * ) *) _QFEfunc_ptr = 0x0000555555556740 (lldb) image lookup -a 0x0000555555556740 Address: pointers[0x0000000000002740] (pointers.PT_LOAD[1]..text + 896) Summary: pointers`square at pointers.f90:24 Note on output: Variables appear with a mangled name because LLDB does not have access to the Flang demangler. 6. Explicit Arrays Arrays in Fortran can have custom bounds (e.g., indexing from -1 instead of 1 ) and custom byte strides (such as creating a slice consisting of every second element). In addition, Fortran arrays are column-major, unlike C/C++ which is row-major. For example, in a 2D array, elements of each column are stored in contiguous memory locations, whereas in C/C++ the elements of each row are contiguous. Furthermore, in Fortran, partial subscripting (such as indexing only one dimension of a multi-dimensional array) is invalid, unlike in C where it yields a pointer to a sub-array. The array type structure Below is a representation of how arrays are stored in the TypeSystem: +-----------------------------------------------------------+ | ArrayType | | - Element Type : CompilerType (e.g., INTEGER) | | - Metadata : Flags, Rank | | - Dimensions : vector | +-----------------------------------------------------------+ | v (Per Dimension) +-----------------------------------------------------------+ | ArrayShape | | - Byte Stride : Memory step between elements | | - Element Count : Extent of this dimension | | - Lower Bound : ArrayBound | | - Upper Bound : ArrayBound | +-----------------------------------------------------------+ | v +-----------------------------------------------------------+ | ArrayBound | | - Kind : Explicit | Star (*) | Colon(:) | | - Value : Bound index | +-----------------------------------------------------------+ Note: Star describes assumed-size arrays and colon describes allocatable arrays. TypeSystem Implementation When executing frame variable for an array, LLDB resolves subscripts iteratively: it first resolves the base array, processes the first subscript, then resolves subsequent subscripts based on the previous result. Consequently, when a user queries arr[1] on a multi-dimensional array, LLDB should return a valid sub-array rather than an error. Because Fortran arrays are column-major, the elements of this sub-array are not contiguous in memory, but are instead separated by a byte stride.To handle this, a new sub-array type is created which strips the outermost dimension and scales the byte stride based on the extent and stride of the peeled dimension. This intermediate type is then returned, enabling LLDB to display the slice or continue stripping dimensions for chained subscripts. The diagram below illustrates this resolution process: Logical 2D Fortran Array: A(1:3, 1:2) Col 1 Col 2 +--------+ +--------+ Row 1| A(1,1) | | A(1,2) | Row 2| A(2,1) | | A(2,2) | Row 3| A(3,1) | | A(3,2) | +--------+ +--------+ Physical Memory Layout (Column-Major): Offset: 0x00 0x04 0x08 0x0C 0x10 0x14 Bytes: [ A(1,1) | A(2,1) | A(3,1) ] [ A(1,2) | A(2,2) | A(3,2) ] ^ ^ | | +------ stride = 3 * 4B ------+ (12 bytes) Intermediate Sub-Array Type created by LLDB for A[2]: - Base Offset : 0x04 (idx * sizeof(elem)) - Stride : 12 B (count(dim 1) * sizeof(elem)) - Elements : [ A(2,1), A(2,2) ] Assumed-Size Arrays (*) Assumed-size arrays use an asterisk (*) for their final dimension’s upper bound, leaving the total element count unknown in debug metadata. While handling follows the standard path, it differs in two ways: Unbounded Indexing: Upper-bound checks are bypassed, allowing direct element access (e.g., arr[10]) without failing on an unknown extent. No Trailing Sub-Array Display: Because the final dimension lacks a known element count, LLDB cannot calculate child boundaries, meaning intermediate slices cannot list or display the sub-arrays that follow. Note: While Fortran source syntax uses parentheses for multi-dimensional indexing (e.g., A(row, col) ), LLDB’s frame variable expression path parser currently only supports chained C-style bracket notation ( A[row][col] ). DWARFASTParser Implementation A DW_TAG_array_type tag is emitted in DWARF, with its children consisting of the element type as well as DW_TAG_subrange_type tags, one for each subrange, which can contain the following information: Lower and upper bound Element count Byte stride This information is collected and forwarded to TypeSystemFortran to create the array type. Output (lldb) frame variable a (INTEGER(2, 2)) a = { [1] = ([1] = 1, [2] = 3) [2] = ([1] = 2, [2] = 4) } (lldb) frame variable a[1] (INTEGER(2)) a[1] = ([1] = 1, [2] = 3) (lldb) frame variable a[1][2] (INTEGER) a[1][2] = 3 (lldb) frame variable arr (INTEGER(3, *)) arr = (lldb) frame variable arr[1] (INTEGER(*)) arr[1] = (lldb) frame variable arr[1][2] (INTEGER) arr[1][2] = 12 7. Dynamic Arrays Dynamic arrays in Fortran are described by an array descriptor, which holds information about the byte stride, lower/upper bounds, and each subrange’s element count. Because this information can change at runtime, it must be evaluated dynamically at the point of inspection. Fortran compilers expose this metadata by emitting DWARF expressions , which evaluate the target memory state to calculate the runtime address and value of each attribute. The primary architectural challenge was that LLDB as a whole assumes array geometry is static. Root structures like ValueObject and TypeSystem assume that while the values of array elements change at runtime, the structure of the array (such as its bounds and element count) does not, and if it does there is no way to know what that structure is. This model works for C, but breaks for Fortran, where the array’s true shape and element count can change during execution and the debugger can know what the array’s structure is. Rather than making intrusive changes to core LLDB interfaces, a provider for synthetic children was used. Its job is to read the runtime descriptor in target memory and instantiate a new, concrete type containing the active bounds and strides. This cleanly accommodates Fortran’s dynamic layouts while keeping the TypeSystem isolated from runtime state. Automatic-arrays For arrays whose properties depend on runtime variables (such as bounds determined by function arguments), compilers emit a hidden variable in the DWARF metadata containing the required values. Because this information resides in runtime memory, it is resolved by the synthetic children provider using the same mechanism as array descriptors. Assumed-rank arrays These arrays appear in functions, allowing callers to pass arrays of varying dimensions to the same routine. For these arrays, the compiler emits a single DW_TAG_generic_subrange instead of one subrange tag per dimension, along with a rank attribute ( DW_AT_rank ) that provides the actual rank. Using the DWARF expressions found in the generic subrange’s children, the runtime properties of each dimension are determined. This resolution is handled by the synthetic children provider. TypeSystem Implementation The required DWARF expressions are stored directly within the array type, ensuring the TypeSystem does not process arrays containing runtime information. During frame variable evaluation, LLDB first attempts to retrieve a child from the TypeSystem . If the static type cannot provide one, the request falls back to the synthetic children provider. The provider resolves the runtime metadata into a concrete type and passes that resolved type back to the TypeSystem for standard processing. DWARFASTParser implementation The DWARF information for arrays can either be a DWARF expression, a reference to a variable or a number. The DWARFASTParser has to figure out what type of array it is and activate the appropriate flags. Its job is to inform the TypeSystem what to expect and forward all information. 8. Case-insensitivity Fortran is a case insensitive language and LLDB did not have support for performing case-insensitive lookups. Compilers emit a DW_AT_identifier_case attribute which gives information regarding the casing. Using this attribute LLDB sets the correct appropriate casing.For mixed-language executables, where one language is case-insensitive and the other isn’t, LLDB defaults to being case-sensitive. Next steps Unfortunately, arrays proved to be a lot more complex and time-consuming than we originally anticipated, so the scope of the project changed. The following features will be implemented in the future: Strings Derived types As discussed in the RFC, the ideal end-point of this project is to have an expression evaluator using Flang, rather than relying only on the frame variable command (which uses a language-agnostic parser called DIL ). Biggest struggle This was my first professional project and also my first time collaborating with many people. The hardest thing for me was learning how to communicate effectively and finding my voice in a large community. Thankfully, my mentors helped me a lot with this, enabling me to become much more confident in group discussions. Learnings I learned a lot about navigating a large codebase. By the end of the project, I was completing tasks much faster and finding information more easily. Just as importantly, I realized how vital clear communication is in a big project, and how much difference a supportive, helpful community can make. Acknowledgements I want to say a big thank you to my mentors, Shivam Gupta and Tarun Prabhu. They were immensely helpful throughout this project and taught me a lot. I also want to thank the LLVM community—especially the LLDB team—for taking the time to give me feedback on the RFC for this project and helping me along the way.📝The LLVM Project Blog
How my friends and I play DoppelkopfOtto Dix, Die Skatspieler (1920). Neue Nationalgalerie, Berlin. Via Wikipedia. Alright, get it twisted, if you are for whatever reason reading this post without having read You should learn to play Doppelkopf , then you should rectify that immediately. This here is a follow-up that goes into the rules my friends and I play by. Each table has their own house rules (and that’s a good thing). This post will not teach you how trick-taking works . You should already understand trick-taking going into this! If you don’t, it’s going to be confusing. As in the last post: Doppelkopf (IPA: /ˈdɔpəlˌkɔpf/ , EN: ‘Double-Head’) is a German four-player trick-taking card game. Each card appears twice. Two players vs. two players (usually), with one team formed by the two players holding the Queens of Clubs. It also has a whole pile of bonus rules and complexity. In the following, I’ll go over the core rules that you need to play the game. I will try to introduce them in a way that makes sense. On the side, I will comment on the rules. If you ever think “Jeez, this Mond fellow is doing an awful job, this is so confusing,” please trust me when I say that most Doppelkopf tutorials online are worse. Card games are best learned in person . If you don’t have anyone who can teach you, Doppelkopf.club might be your best bet. Owned by an enthusiast, no sign-ups or other nonsense. Outline Complete Saxonian deck. Photo by Moddin, CC BY-SA 3.0, via Wikimedia Commons. In Doppelkopf all cards are dealt at the start of the game (this is normal for trick-taking games). To assemble a Doppelkopf deck, take two “standard” French decks of cards. Remove all number cards of value 8 or lower, and all jokers. That’s a Doppelkopf deck. Don’t play with German-suited cards , just use the French ones. Every player gets 12 cards, and unless a player has reservations, you are ready to start playing. No cards are ever drawn , so the game consists of exactly 12 tricks 1 . The outline of the game is the following: Gather 4 players. Shuffle the deck, and hand every player 12 cards. No cards should be left. Each player looks at their hand and decides whether they have “reservations” or they are “healthy”. This part you should completely ignore until you’ve played several normal rounds. “Reservations” are special conditions that depend on your hand and that alter how the game is played. The person to the left of the dealer plays a card, opening the first trick. The other players follow suit in order. The winner of the trick opens the next one. Team membership is determined by whether you have a Queen of Clubs or not. The two players holding the Queens of Clubs are the ‘ Re ’ team. The other two players are the ‘ Kontra ’ team. You do not know who is on which team until the Queens of Clubs have been played . After all 12 tricks have been played, each team scores all tricks they won. There are 240 points total. The team with more points wins. If it’s 120:120, the Kontra team wins. If you’re so inclined, you can keep track of ‘meta-points’ across multiple games. This only makes sense if you play regularly. This makes it reasonably simple. Once you know the rules, you just hand out the cards, and can immediately start playing. Announcing reservations is a form of bidding (i.e. you have the option to make the game harder for yourself, in return for more meta-points), but I recommend that you just ignore that completely. Are we bad at the game? Yes, probably. Are we having fun? Also yes. This is one of my pet drums, so forgive me for beating it: Social games like Doppelkopf are made to be fun. The play at our table is almost certainly not optimal, and other Doppelkopf players would probably disagree with our house rules. We like that it’s possible to just hand everyone 12 cards and jump straight into a game, without having to worry about cross-game scoring, or every player having to spend time evaluating how good their hand is. Other groups may disagree. The Game Once all cards are dealt, and players have announced whether they have any reservations, the trick-taking phase of the game starts. At this point, bless our stupid, whimsical hearts, my local group of players will start hollering and shouting all sorts of obscenities, and use language that’s decidedly non-standard. For example, ‘playing a Queen of Clubs’ reveals which team you are on. Consequently, my local group frequently dubs this act ‘coming out’. You can imagine how this would easily lead to a ‘gay’ and a ‘straight’ team, and we are using this terminology with nothing but whimsy and fondness in our hearts. Anyway. Let’s cover the numbers. As I said in my previous post , trick-taking games usually differ on 1) card ranking and trumps, 2) card scoring to determine the winner, 3) meta-points (i.e. how points are scored across games). You may hate what comes next. Doppelkopf is a European game. Worse, it’s German . As such, the scoring is ever so slightly more complex than it needs to be. (But trust me, it’s not nearly the worst of the bunch, and there are good reasons for it.) Before we start, internalize that: Whether a card “beats” another card is unrelated to the points the card scores at the end of the game. The points you score throughout the game are not the same as the meta-points you score between games. The game points determine whether you win the game. Meta-points are tracked separately, across games, to determine who wins across a season of Doppelkopf. Card Ranking In Doppelkopf (and Skat) Tens are ranked higher than Kings . So the order of, say, Spades, comes out to: Ace, Ten, King, and Nine . Next, let’s talk about trumps. Doppelkopf is a game with a lot of trumps . In fact, most of the cards are trump (this is funny, and part of what makes the game unique). The order of the trumps (high to low) is as follows: Ten of Hearts (‘Dulle’). All Queens, in order Clubs, Spades, Hearts, Diamonds. All Jacks, in order Clubs, Spades, Hearts, Diamonds. All remaining Diamonds ( Ace, Ten, King, Nine ). 20’s Love. We love the Ladies. Jackin’ off. Diamonds are Unbreakable. No Kings 2 . That’s how my friend remembers the order, anyway. At the start of the game I recommend sorting trumps separately, to make it easier to keep track of them. And yes, the Ten of Hearts and the Diamonds are “special”, in a sense. These are the trumps. This order is strict, i.e. any high trump beats any low trump. If we both play Jacks, the higher Jack wins. If we both play the same Jack, the first card beats the second 3 . This is true whether you’re playing the trump suit or a different suit. Of course, trumps always beat non-trumps. Scoring At the end of the game, look at all cards your team won. Then, add up the points according to the following list: Ace: Worth 11 points Ten: Worth 10 points King: Worth 4 points Queen: Worth 3 points Jack: Worth 2 points Nine: Worth no points In other words, Aces and Tens are valuable . Try to capture them. That’s how you win. In total, there are 240 = 2*4*(11+10+4+3+2) points. You win with 121 points. On a tie, the Kontra team wins. Often you just count the points of the team that obviously won fewer tricks. This sounds horribly annoying , but it’s really not that bad. Counting happens quite quickly once you’ve done it a few times. This is all you need to know to play the basic game of Doppelkopf. At this point, I would recommend doing exactly that, if you have someone to play with. What follows next is rules for what happens when someone is dealt both Queens of Clubs, special cases, house rules, and meta-scoring. Reservations & Weddings I’ll talk about the types of reservations we care about in my small, local group. Half a Chicken The most important reservation of all. If you hold the two Tens of Diamonds, you may announce half a chicken. Announcing half a chicken does absolutely nothing, but a true gentleman should do it regardless. When new players are introduced, it’s critical to haze them about not knowing what ‘half a chicken’ is. Schweinchen / Swine / Piglets If you hold the two Aces of Diamonds, you may announce Schweinchen. Announcing Schweinchen makes the Aces of Diamonds the highest-ranking trumps in the game. They become a new tier above the ‘Dullen’ (the Tens of Hearts). This is not balanced, and frankly, probably a bad rule. However, it is pretty funny, especially if you allow Double Swine (two Nines of Diamonds) and Triple Swine (two Tens of Diamonds), which may be announced by other players, and have to be announced in order. In other words, if you announce Swine, there is a risk that another player may announce Double Swine, making their trumps even stronger than yours. This is firmly in the category of house rules. House rules are part of what makes these games good. We’re still inventing our own. Weddings It’s possible that one player ends up holding both Queens of Clubs, making them their own partner. They have three options: Play a ‘silent solo’. No announcements, they just secretly play a solo against the other players. This is difficult, but the other players may be confused, giving them an advantage. Play a loud solo. They announce that they are going to play a solo game. This triples their meta-points , but is much harder. Announce a wedding. This is the default, and allows them to find a new partner. When a wedding is announced, the new partner is chosen as follows: The first player (other than the Re player, i.e. the player holding the two Queens of Clubs) to win a trick during the first three tricks becomes the new partner. If, however, no one else wins a trick, then the Re player is forced to play a solo. In other words, the other three players get the opportunity to deny the Re player by consistently making them win their first three tricks. However, each of the other players has an incentive to be this person’s partner. The two Queens of Clubs are strong trumps, and the Re player may already have won one or two tricks. The players may backstab each other to ‘marry’ the Re player. Tradeoffs! Everything up to this point has been ‘Doppelkopf-lite’, i.e. the version with no meta-scoring across games. Meta scoring doesn’t really matter unless you have a group you consistently play Doppelkopf with. If you really insist, Solos During the bidding / reservations phase, you are allowed to announce a solo. Solos are hard, so it’s only worth it if you have a strong hand. In the meta-scoring system, winning a solo nets you thrice as many points. Here are the solos you are allowed to announce: Jack solo: Only Jacks are trump. Queen solo: Only Queens are trump. “Meatless” solo: No trumps exist. Suit solo: Tens of Hearts, Queens, Jacks, and a suit of your choice are trump. A Diamond solo has the same trumps as the normal game. Scoring across Games Bavarian-pattern Tens. Photo by Bermicourt, CC BY-SA 4.0, via Wikimedia Commons. My local group doesn’t score points across games. I could take it upon myself to push them on it, but I’ve won a good number of games so far. Tracking a list of my own victories would not improve the experience. Besides, we try a lot of different games. Doppelkopf has been the best one so far, but it’s hard to tell if we’ll truly stick with it over, say, other card games, TTRPGs, or what have you. What I’m saying is, sorry, I don’t actually do the meta scoring as often as a True Doppelkopf player should! Let me do my best at explaining the scoring. I can give you the fundamentals, but you should look it up if you want to take this seriously. The rough idea of scoring is that Doppelkopf is zero sum . The winning party gains points, the losing party loses them. Therefore, if you win a solo, you’ll get thrice as many points. That makes solos worthwhile, even though your odds of winning are dramatically lower. You start with one point for a won game. If the Kontra party won, you add another point. Then, you get an additional point for each 30 points you are above 121. Taunting You get to taunt . The first taunt pre-announces that you expect to win. After that you pre-announce that the enemy team will receive fewer than X points. en the official rules, you taunt by announcing “Re” or “Kontra” (depending on team). This raises the stakes by two points. Any enemy may counter, raising the stakes by another two. Announcing “No 90”, “No 60”, “No 30”, or “Schwarz” raises the stakes by one point each, but also requires you to meet that bar . This means: You have to beat the opposing team, and they MUST have fewer than X points (or in case of Schwarz, win zero tricks). If you fail to achieve this, you lose the round. Taunting is an incredible mechanic. If you are confident, this increases your payout. If you are too confident, you will lose a lot more points than you otherwise would have. Taunting is only allowed early in the game, otherwise you’d just do it when you already know that you are going to win. “re/kontra” must be called while you’re still holding 11 cards. No 90 requires 10 cards, No 60 requires 9, etc. After you taunt, the opposing team always gets at least one more turn to respond. What I hate about taunting Taunting allows you to announce your team affiliation. This is morally wrong: The best part about Doppelkopf is that team affiliation is unknown, and only revealed when you play a Queen of Clubs . Calling Re or Kontra raises the stakes , so it has consequences on the game, but it still feels wrong to me. Ideally, you should be able to announce “my team is going to win” without declaring the name of the team. Of course, the problem is that (ideally) the opposing team responds by taunting back. Here this seems unlikely, since they don’t even know whether they are on your side or not! I am still trying to figure out if there is a way to resolve the conflict, or if it is a problem at all. If you have strong opinions on this, send me an e-mail. Currently I understand the rules as follows: If you track meta-points, you can taunt. Taunting announces your team membership, but it requires you to raise the stakes. You cannot announce membership otherwise. If you are not tracking meta-points, you are not allowed to taunt (or announce team membership). Bonus Points In Doppelkopf, we love our bonus rules. If you capture the enemy team’s fox (i.e. their Ace of Diamonds), the stakes are raised by another point. This can happen multiple times if the opposing team has both Aces of Diamonds. If you win a so-called “Doppelkopf” (40+ points in one trick), that’s another point. If you win the last trick of the game with the Jack of Clubs, that’s another point. Conclusion My local Doppelkopf group finds the game, and its pile of whimsical bonus rules, incredibly entertaining, but yes, that’s all just us being weird. I’d like more people to give these games a try (Doppelkopf, or Bridge if necessary). They are better than you’d think. They are social. Fun. Different. And it’s so easy to carry a deck of cards with you at all times. In my friend group we “stay strapped” (carry decks of cards at all times). Are you worried about an increasingly atomized society? Or the loss of third places after skimming ‘Bowling Alone’? Carry a deck of cards. Go grab coffee with your friends, then social-mog everyone by whipping it out and playing. Grab two or three friends and dress up nicely, go to a nearby jazz club, then invite strangers to play 4 . Be the change you want to see in the world. This is part of what makes these games work! Because no one ever draws new cards, you can learn when someone is “out of hearts”, and there’s no risk they’ll just draw a new heart. ↩︎ Other than the King of Diamonds. ↩︎ The best Doppelkopf includes plenty of house rules, and here we have one important exception: The second Ten of Hearts beats the first. This ‘balances’ the strongest trump in the game, and requires more tactical play. This house rule is then balanced out with another: The second Ten of Hearts beats the first except on the final trick of the game , ensuring people are careful about holding on to their card. ↩︎ This is on our to-do list. ↩︎📝MOND←TECH MAGAZINE

Sunday, November 15, 2026

You should learn to play DoppelkopfJosef Wagner-Höhenberg, Die Skatpartie (before 1939). Public domain, via Wikimedia Commons. Doppelkopf (IPA: /ˈdɔpəlˌkɔpf/ , EN: ‘Double-Head’) is a German 4 player trick-taking card game which you can play using two standard decks of cards. It’s a 2 vs. 2 player game, where one team is formed by the two players holding the Queens of Clubs (meaning that partnership is secret at the start of the game). What if one player holds both Queens of Clubs? Why, they get to play a solo, or they get to announce a ‘wedding’, which results in a prisoner’s dilemma auction to determine who becomes their partner (if anyone). This sounds complicated, but is actually incredibly funny. It is the best card game I ever played. Better than Uno, Oh Hell, Rummy, Cuttle, Schnapsen, Poker, Sheepshead, even Skat or Bridge 1 . The jury is still out on whether it’s better than 找朋友. You might ask “Why would anyone in their right mind learn how to play an obscure German two hundred year old card game? One that requires exactly four players, no less?” Because it’s good. The social component is delightful. The meta-scoring is great, if you are into that (you gather ‘meta-points’ across games, and benefit from raising the stakes to increase your payout). It’s whimsical (players may announce “half a chicken”, which does nothing other than give other players free information about your hand), and there’s a real difficulty of tracking the cards that have been played, and which the other players are holding. You might not have the right people in your life to play Doppelkopf with, but your life would almost certainly improve if you did. To get there, maybe consider taking the first step, and being the person who shows up strapped with a deck of cards to the local function. Doppelkopf or otherwise, you should learn how to play card games that are actually fun . Teaching Doppelkopf is, unfortunately, a bit tricky. It’s best taught in person. In this post, I will teach you how to play general trick-taking games like Bridge, Doppelkopf, or Skat. Trick-taking is the core gameplay loop. Once you understand trick-taking, the rest is meta progression and fluff. In ‘How my friends and I play Doppelkopf’ I explain how my friends and I actually play Doppelkopf. In the meantime, if you strictly want to learn Doppelkopf, I recommend Ham Vocke ’s project Doppelkopf.club . Ham is a programmer, presumably even more passionate about the game than I am, and Doppelkopf.club allows you to play against bots online. Trick-Taking Doppelkopf is a trick-taking game. This distinguishes it from shedding games (such as Uno). In shedding games, your goal is to shed all of your cards onto the discard pile. In trick-taking games, your goal is to score points by winning as many “tricks” as possible. A “trick” consists of a single round along the table. Each player puts down exactly one card (in order), following the suit of the first player, if they are able to . The highest-ranking card wins. The winning player then “takes” the cards and puts them face-down on their side of the table. They then open the next trick. How do you determine which card wins? Basically, the highest-ranking card is the highest-ranking trump (if a trump was played), and otherwise the highest-ranking card of the first player’s suit . By the way: The phrase “to follow suit” has its origin in card games. In all trick-taking games you “follow suit”, and the suit changes every trick. What if the first player opens with a trump card? Then everyone has to follow with trump, if they can. The right way to think of trumps is as “belonging to their own suit”. Doppelkopf has a lot of trumps, including all Queens and Jacks. As an example: If you have a 10 of Spades and a Jack of Spades and the first player opens with Spades, you are not allowed to play the Jack of Spades. Why not? Because it’s part of the trump suit. It doesn’t count as Spades. (Yes, that part is important, but also confusing.) Example 10 J A 9 A Q A 10 K B J 9 A K C Q 10 9 A D K 1 9 2 10 3 J 4 Player A opens the trick. They get to play any card they want. They play a King of Clubs . Player B has clubs, so they have to play clubs. They play a 9 of Clubs . This card ranks lower than the King of Clubs . Player C does not have any clubs . Therefore, they get to play a different suit. (This may be good or bad for them.) They play a 10 of Spades . This card is not a trump, and not a Club , so (in this trick!) it also ranks lower than the King of Clubs . Player D does not have any clubs . Therefore, they get to play a different suit. They play a Jack of Diamonds . In Doppelkopf and Skat all jacks are trump. Therefore, the Jack of Diamonds ranks higher than the King of Clubs , and Player D wins this trick. This is the core gameplay loop of many different games. This is most of what you need to understand. After every player played a card, the winning player (D, in our example) claims them. They all contribute to their score at the end of the game. Finally: The winner of the trick (D) is the person who gets to play the first card of the next trick. This loop repeats until everyone is out of cards. That’s it! That’s the whole game. “Every” trick-taking game follows exactly this format, with minor variations (such as which cards are trump, and how tricks are scored at the end of the game). Why is this a good core gameplay loop? Each time you play a card, you are gambling on which cards the other players have. However, as the game goes on, because players are required to follow suit, you are obtaining a lot of information about their hands. Through this the game rewards tracking which cards have been played, and which players are out of which suits. This then allows you to gauge whether you can safely win a trick or not. This will take some time to develop a feeling for. For the record: I don’t count cards! I do it by feelings and vibes. You can probably beat me! In Doppelkopf specifically, the hidden partnership makes this even more engaging. If you are winning a trick, you want your partner to “throw in points” 2 , such that your team can secure them. Here is a common tactic: At the very start of the game (if you’re leading), play an Ace of Spades. If every player has a Spade (reasonably likely), you win this trick by default, since the Ace of Spades is the highest Spade, and none of them can play a trump. This is fairly safe, and earns you a good amount of points. There’s just one problem: At the start of the game team membership is unknown, so your partner is not going to throw in any points. This is a tradeoff. This is good game design. What’s left? Once you understand trick-taking, it will be easy for you to pick up any trick-taking game. That includes Bridge or Skat or 找朋友. (Or Oh Hell!, but it’s not very good.) Now, the next part is where trick-taking games differ. First , trick-taking games disagree on which cards are trump (or more generally, on which cards “beat” which other cards). Second , trick-taking games disagree on how tricks are scored at the end of the game (i.e. how do you determine who wins). Third , trick-taking games disagree on the meta-scoring, i.e. on how points are counted across multiple games . This is only relevant if you repeatedly play with the same group of people. Each game will have slightly different opinions on each of these, on top of its own little quirks and oddities 3 . Bidding Finally, most trick-taking games have some sort of bidding process. Bidding happens after cards are dealt, but before trick taking starts. During bidding, the players estimate how good their hand is, and then compete for getting to play. (In Skat and Bridge, this is how the “attacker” is determined. In Doppelkopf, this is where solo games are declared.) The bidding process is completely inscrutable to new players, and widely considered to be the hardest part of the game. You need to be able to estimate how good your odds of winning are before you have even played the game . Your “bid” will allow you to choose which cards are trump, and influences how many meta-points you win (or lose!) at the end of the game. Content Warning: A Skat Reiztabelle Standard German Skat Bidding Table. You might be laughing nervously, but the chart follows a predictable pattern. It’s not as bad as it looks. tl;dr: Count how many consecutive jacks you have (or how many empty consecutive slots you have) starting from the first. Then, you add +1, and multiply the result with a ‘base value’ for the suit (or 24 for the ‘grand game’ which has no trumps other than Jacks). Still, it’s intimidating! If my case for trick-taking games was remotely compelling, and you’re now looking to learn a new card game, heed the following advice: Ignore the bidding and meta-scoring completely. The bidding phase is the hardest part of the game. While learning, just rotate who attacks. Play default games. Make the obvious decisions. It’s much, much easier that way. Bidding is the meta-game on top of the game. Think about it once you’ve played a few rounds without it. Then, go slowly: Many of these games have fancy rules for special types of sub-games (null games, playing with open hands, meatless solo games, Ramsch, etc.), most of which you should ignore until curiosity wins out. Conclusion Go and pick up a deck of cards. Carry it with you. There’s no aura loss. You can play dozens of games with it. Whip it out over coffee with your friends. Schnapsen is weird, but only requires two players. Skat requires three. Bridge and Doppelkopf require four. Sheepshead is for five. 找朋友 is… crazy and can be played with arbitrary larger groups, I think? Go and have fun! If, at this point, you’re wondering if I am talking about the same Bridge you most likely associate with retirement homes , then yes, I am! The boomers are absolutely right about Bridge being a great game. ↩︎ This is different from Bridge, where you just count the number of won tricks. In Doppelkopf, some tricks score more points than others. ↩︎ Bridge, for example, has what we lovingly call ’the cuck chair’. It’s a four player game, but each round one of the players has to watch. It’s unclear to me why anyone would think that is a good idea. ↩︎📝MOND←TECH MAGAZINE

Saturday, November 14, 2026

Friday, November 13, 2026

MSVC Build Tools Preview updates – November 2026The MSVC Build Tools Preview is updated regularly with the latest features and fixes from the MSVC development team. This post covers the last month’s updates of the Preview build tools, currently targeting the v14.53 release. This encompasses changes across the compiler frontend, backend, linker, standard library, and related tools. Although you can acquire the […] The post MSVC Build Tools Preview updates – November 2026 appeared first on C++ Team Blog .📝C++ Team Blog
FFTs Part 2: The Basics of the FFTThis is part 2 of a series of posts about FFTs and the specific algorithms that FFT-20XX uses. The Discrete Fourier Transform The Basics of the FFT (← you are here) Some Optimizations to the FFT The Inverse FFT The FFT-20XX Complex-Input Algorithm The FFT-20XX Real-Input Algorithm(s) Part 1 went through the core of how the discrete Fourier transform (DFT) works to turn a series of samples in time into a set of samples in frequency, and ended up with the following algoritm: void CalculateDFT ( complex [ ] inputs , complex [ ] outputs , int length ) { for ( outIdx = 0 ; outIdx length ; outIdx ++ ) { // Start the sum at 0. float sum = 0 // This is the angular frequency (in radians/sample) for // the given output sample. float angularFreq = - 2 * pi * outIdx / length for ( inIdx = 0 ; inIdx length ; inIdx ++ ) { // Get the rotation value for the current input index // then use that to calculate the resulting rotation. float radians = inIdx * angularFreq complex rotation = cos ( radians ) + i * sin ( radians ) // A complex multiply with a unit complex vector is // a 2D rotation. sum += inputs [ inIdx ] * rotation } outputs [ outIdx ] = sum } } Note A reminder: we’re going to be talking about these values as complex numbers (of the form a + i b a + i b ), but if you prefer, just think of them as a 2D vector instead ( [ a , b ] [a, b] where a a is the x coordinate and b b is the y coordinate). We’ll be doing complex multiplication of these vectors with others, but in all cases a multiply like P ⋅ R P \cdot R will be a rotation of point P P by the angle that R R represents (where R = cos ⁡ θ + i sin ⁡ θ R = \cos\,\theta + i\,\sin\,\theta ). This algorithm is O ( N 2 ) O(N^2) , but there’s a much more efficient, O ( N log ⁡ N ) O(N\,\log\,N) way: the fast Fourier transform (FFT) — and we’re going to derive it. Note The algorithm we end up deriving here is going to work specifically for FFT lengths that are powers of two , because it’s the easiest to implement (plus, to be honest, power-of-two lengths were sufficient for FFT-20XX so that’s all I implemented). The following techniques can be adapted for other lengths (i.e. if you need a length that is a mutliple of 3 or 5 or, I dunno, 97), plus there are ways to do this for arbitrary lengths (for instance: Bluestein’s algorithm ). This series isn’t going to touch on any of those. Halving the Work The first step of deriving the FFT algoritm is figuring out where we can halve the amount of work. Since the DFT boils down to “every output takes every input multiplied by a rotation”, we can visualize all of the rotations as a 2D grid, where each column is an input and each row is an output. Here’s a visualization of the rotations for an FFT of length 8 (adding a dividing line between the top and bottom halves, which should make sense in a moment): 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] = + + + + + + + Each rotation (as per the above pseudocode) for a given input index n n and output index k k is n k / N n k/N turns (where N N is 8, the FFT length). But rotations are cyclical , and, for instance, turning a full turn (360 degrees) is equivalent to not turning at all. We can use this cyclicity to our advantage! If you look at the even inputs (columns indexed 0, 2, 4, and 6), you’ll note that the rotations in the bottom half are identical to the top half . For instance, with input 2, outputs 0 and 4 are both unrotated, outputs 1 and 5 both rotate a quarter turn, and so on. For the odd inputs (columns 1, 3, 5, 7), the angles aren’t the same. However, they’re still related: the bottom half rotations are always 180 degrees from the corresponding top half rotations. As an example, looking at the column for input 1, we see that output 4’s rotation is a half turn, where output 0 is unrotated — they’re facing away from each other. The other odd outputs are similar, with the bottom half rotations always pointing the opposite direction as their top-half counterparts. In other words, the bottom half rotations of the odd inputs are negated versions of the top half (because with 2D vector A , Rotate(A, 180 degrees) is the same as the 2D vector -A ). Let’s rearrange the columns of the diagram to group the even and odd inputs together (evens to the left, odds to the right): in[0] [0] in[2] [2] in[4] [4] in[6] [6] in[1] [1] in[3] [3] in[5] [5] 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] = + + + + + + + We can then rewrite the bottom-half odd inputs as negations of the top-half ones (note the minus signs in place of the usual plus signs): in[0] [0] in[2] [2] in[4] [4] in[6] [6] in[1] [1] in[3] [3] in[5] [5] 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] = + + + - - - - Now all of the corresponding top and bottom half outputs use the same corresponding rotations per input ; the only difference is that in the bottom half we subtract the rotated odd inputs instead of adding them. Our code, then, can switch to summing up all of the even and odd elements separately, then computing two outputs at once by doing evenSum + oddSum for the first (top) half of the outputs and evenSum - oddSum for the second (bottom) half, which means we’re now doing half the work as before! Note If you want this (and the next section) done algebraically instead of visually, the wiki page for the Cooley-Tukey algorithm has a fairly clear breakdown of the derivation of the whole thing. Here’s what the code looks like if we do that: void CalculateDFT ( complex [ ] inputs , complex [ ] outputs , int length ) { // NOTE: Now looping over half the length for ( outIdx = 0 ; outIdx length / 2 ; outIdx ++ ) { // Start the sums at 0. float evenSum = 0 float oddSum = 0 // angular frequency for the given output // (in radians/sample) float angularFreq = - 2 * pi * outIdx / length // NOTE: now incrementing by 2 to do odds and evens // separately. for ( inIdx = 0 ; inIdx length ; inIdx += 2 ) { // Get the rotation value for the current input index // then use that to calculate the resulting rotation. float evenRads = inIdx * angularFreq complex evenRot = cos ( radians ) + i * sin ( radians ) evenSum += inputs [ inIdx + 0 ] * evenRot // Do the same with the next index (inIdx + 1), for // the odd sum. float oddRads = ( inIdx + 1 ) * angularFreq complex oddRot = cos ( radians ) + i * sin ( radians ) oddSum += inputs [ inIdx + 1 ] * oddRot } // Computing 2 outputs in the same loop! outputs [ outIdx ] = evenSum + oddSum outputs [ outIdx + length / 2 ] = evenSum - oddSum } } If you compare this code to what we started with, it does half the rotations and (roughly) half the adds (counting subtractions) as the original: the inner loop does effectively the same amount of work in both, but the outer loop runs half as much. Unfortunately, it’s not quite to O ( N log ⁡ N ) O(N\,\log\,N) yet, so we need a way to effectively do this halving of work recursively. Halving Work Again (and Again and…) Let’s look again at just the first half of the outputs from our 8-length example: in[0] [0] in[2] [2] in[4] [4] in[6] [6] in[1] [1] in[3] [3] in[5] [5] in[7] [7] out O [0] = + + + + + + + out O [1] = + + + + + + + out O [2] = + + + + + + + out O [3] = + + + + + + + If we look at just the even inputs for a moment, the pattern of rotations in that 4×4 block of the diagram ends up being the exact same pattern of rotations as for a standard 4-element FFT (half the size of our 8-element example): in[0] in[1] in[2] in[3] out[0] = + + + out[1] = + + + out[2] = + + + out[3] = + + + Math Alert! If you care about the algebra: this is because for each even rotation ( n k N \frac{n k}{N} ), k k is a multiple of 2. So if we say 2 m = k 2m = k , then the rotation becomes 2 n m N \frac{2 n m}{N} which is equivalent to n m N / 2 \frac{n m}{N/2} , which is exactly how the angles for an FFT of length N / 2 N/2 would be specified. This means that we can calculate the even sums recursively , computing the N / 2 N/2 even sums as if they were an N / 2 N/2 -length DFT, which means we can do the same even/odd dance to halve its work as well. That’s great for the even inputs, but what about the odd inputs? They have a similar pattern, but it’s not quite the same: in[1] in[3] in[5] in[7] odd[0] = + + + odd[1] = + + + odd[2] = + + + odd[3] = + + + The first row is the same as in the 4-element DFT: no rotation. The second row, however, is different: each angle in the row is 1/8th of a turn rotated relative to the corresponding row of the 4-element DFT. The third and fourth rows are also different, with an extra 2/8th and 3/8th turn added to the angles in each row, respectively. In other words, any given output k k ’s odd inputs will have their rotations be k / N k/N turns more than doing a standard N / 2 N/2 -length FFT with those inputs. Since “rotating every vector by t then summing” is the same as “summing then rotating by t ” (that is, Rotate(A, t) + Rotate(B, t) equals Rotate(A + B, t) ), we can calculate each odd sum by doing the work as a half-length DFT (like we can with the evens), then adjust each sum by rotating by its corresponding k / N k/N -turn angle (called a twiddle factor , which is a fun name to say), like so: in[1] in[3] in[5] in[7] odd[0] = × + + + odd[1] = × + + + odd[2] = × + + + odd[3] = × + + + Using that, we can now recursively calculate the even and odd sums using half-length FFTs, apply the twiddles, then do the add and subtract to get the final outputs. Let’s write this as code again, this time recursively! To do this, for now we’ll use some temporary storage for simplicity: // Helper function to build a complex // rotation value complex Twiddle ( int k , int len ) { float angularFreq = - 2 * pi * k / len return cos ( angularFreq ) + i * sin ( angularFreq ) } void CalculateDFT ( complex [ ] inputs , complex [ ] outputs , int len ) { if ( len == 1 ) { // To end the recursion, special-case // the 1-length FFT, which sums one input, // unrotated (i.e. it does nothing). outputs [ 0 ] = inputs [ 0 ] return } // Temp storage for the recursion complex [ length / 2 ] evens complex [ length / 2 ] odds // Separate the even and odd inputs for ( k = 0 ; k len / 2 ; k ++ ) { evens [ k ] = inputs [ 2 * k ] odds [ k ] = inputs [ 2 * k + 1 ] } // Recurse into the even and odd FFTs // (each using the same array as input and // output, which is fine here) CalculateDFT ( evens , evens , len / 2 ) CalculateDFT ( odds , odds , len / 2 ) for ( k = 0 ; k len / 2 ; k ++ ) { // Get the corresponding recursively-calcualted // sum from the relevant arrays. complex evenSum = evens [ k ] complex oddSum = odds [ k ] // The odd sum needs to be rotated by this // output's twiddle factor. oddSum *= Twiddle ( k , len ) // Now, as before, calculate two outputs from // these sums. outputs [ k ] = evenSum + oddSum outputs [ k + len / 2 ] = evenSum - oddSum } } This is now truly, algorithmically O ( N log ⁡ N ) O(N\,\log\,N) ! We halve the work at each level of the FFT, which does way fewer rotations and adds than the initial DFT algorithm (for instance, the original algorithm for a 1024-length DFT would do around a million rotations, but this one does around five thousand). But it’s not ideal: it’s recursive, and uses temporary storage per recursion. We can do better! But now we get into the “fun” that is… Deinterleaving and Bit Reversal To do all of this without recursion or scratch space, we need a way to do each level of the FFT calculation in-place. So let’s look at how data is flowing through the system. Here’s a diagram of the routine (at a single recursion level) where, from left to right: The inputs are deinterleaved into evens and odds. Each of those two groups has a half-length sub-DFT performed on it (this is the recursion). Those results are then used in pairs by each step of the computation loop to write corresponding pairs of outputs. Diagram of the routine, which is laid out as described above. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 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 Even DFT Odd DFT If you look at the flow through this diagram, what’s interesting is that in the box on the right (representing the loop) each computation (one of the circles) pulls in from the same row that it writes out to (ignoring the actual index numbers). For instance, the top circle pulls in from indices ‘0’ and ‘1’, which are lined up perfectly with its outputs at ‘0’ and ‘8’. This means that, theoretically , we could compute the entire FFT in-place (where the inputs and outputs are the same array), by doing the following: Deinterleave the data in-place (separating the evens and odds). Calculate the sub-DFTs recursively (again, in-place), using the first and last halves of the data as the even and odd sub-DFTs, respectively. Then, run the computation loop over the results, each iteration of which reads from and writes to the same elements, so no rearranging needs to take place. That would look like the following — very much like the above code, except without the temporary evens and odds storage: void CalculateDFTInPlace ( complex [ ] data , int len ) { if ( len == 1 ) return // A hypothetical function to do the // deinterleave. DeinterleaveInPlace ( data , len ) // Recurse into the even and odd FFTs // (first and last halves of our data) CalculateDFTInPlace ( data , len / 2 ) CalculateDFTInPlace ( data + len / 2 , len / 2 ) for ( k = 0 ; k len / 2 ; k ++ ) { var kOdd = k + len / 2 complex evenSum = data [ k ] complex oddSum = data [ kOdd ] oddSum *= Twiddle ( k , len ) // Note that we're writing to the same // array indices that we read from! data [ k ] = evenSum + oddSum data [ kOdd ] = evenSum - oddSum } } There’s one problem with this: it turns out, efficiently deinterleaving an array in-place is one of those problems that sounds like it would be super easy, but is instead kind of a nightmare ! Note There are ways to do it, of course, even O ( N ) O(N) ways - but they don’t have particularly nice memory access patterns and end up not performing particularly well at larger sizes. To try to avoid that, let’s keep investigating the pattern of data moves. We know that, in terms of data flow, the data into the last step comes in from two half-length sub-FFTs: Diagram showing the even and odd 8-element sub-FFTs of a 16-element FFT, writing out to even and odd intermediate values (respectively), which then feed into the final step labeled "combine" which represents the final combination step. 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 Even DFT Odd DFT Combine If we were to track this pattern of deinterleaves all the way back to the lowest recursion level (the two-element FFTs), where the indices from right to left (from output to input) get deinterleaved at each step, here’s the ordering we end up with: Compact diagram showing the inputs (ordered 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15) feeding into eight 2-element sub-FFTs, then those being fed in pairs into four 4-element sub-FFTs, each of which outputs the indices in a new order where the even/odd indices are interleaved. Each pair of those feeds into one of the two 8-element sub-FFTs which, again, outputs its input indices in interleaved order, then those two finally feed into the final 16-element FFT pass, which outputs the indices in the expected 0 to 15 sequential order. 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 At a glance, the pattern of inputs on the left isn’t particularly clear, but it turns out it’s straightforward: the values are the original indices with their bits reversed ! As an example, for a 16-element FFT (like the diagrams above), we have 4 bits worth of index (since log ⁡ 2 16 ⟹ 4 \log_2 16 \implies 4 ), so here’s the table of reversals: 0 0000 ↔ 0000 0 1 000 1 ↔ 1 000 8 2 00 1 0 ↔ 0 1 00 4 3 00 11 ↔ 11 00 12 4 0 1 00 ↔ 00 1 0 2 5 0 1 0 1 ↔ 1 0 1 0 10 6 0 11 0 ↔ 0 11 0 6 7 0 111 ↔ 111 0 14 8 1 000 ↔ 000 1 1 9 1 00 1 ↔ 1 00 1 9 10 1 0 1 0 ↔ 0 1 0 1 5 11 1 0 11 ↔ 11 0 1 13 12 11 00 ↔ 00 11 3 13 11 0 1 ↔ 1 0 11 11 14 111 0 ↔ 0 111 7 15 1111 ↔ 1111 15 As you can see, the ordering on the right of this table (0, 8, 4, 12, etc) is the same as the input ordering from the previous diagram and, in their bit representations, you can see that each index is just the 4 bits of the other reversed. This is a much easier operation to perform than a deinterleave at each step, especially with separate input and output arrays! Here is a simple routine that does a bit-reversed copy from one array to another: void BitReverseCopy ( complex [ ] inputs , complex [ ] outputs , int len ) { for ( int k = 0 ; k len ; k ++ ) outputs [ k ] = inputs [ BitRev ( k , len ) ] } Note The above code doesn’t have an implementation of BitRev , because an efficient implementation on many systems isn’t particularly readable; it turns into a sequence of swapping increasingly-large groups of bits until you reach the size of the int . For a C++20 implementaton, here’s a compiler explorer link . Additionally, the above routine doesn’t work in-place, though it is totally possible to do so: a bit reversal can be written efficiently as a square matrix transpose (or two) if you get creative with the indexing of the “matrix” rows. However, the final FFT-20XX algorithms do not have an explicit bit reversal step, so I’m not going to go into those details. Sorry! Going Iterative We now have all of the pieces we need to assemble the final algorithm. Let’s go back to this earlier diagram of the data flow for a 16-element FFT: The same diagram of the flow of indices through a 16-element FFT that we saw earlier. 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 Each column of boxes in this diagram corresponds to a level of recursion in our original code (recursing from right to left because the recursion is done before the computation): the last column (with the one tall box) is the top of our recursion stack, which then recurses into its two sub-DFTs (the next column to the left), and so on, until we reach the left-most column which is the lowest level of recursion. Each box represents a computation pass at its given recursion level (the loop in the above code). If the inputs have been pre-bit-reversed (so that they’re in the order specified on the left-hand side of the above diagram), then each of the boxes reads from and writes to the same element indices , so each computation (box) acts in isolation. Rather than doing this recursively, we can instead treat each of the columns of this diagram as a single pass through the data! More specifically for this diagram, it takes the inputs in what we now know to be bit-reversed order, and does four ( log ⁡ 2 16 \log_2 16 ) passes on the inputs (where, again, each pass represents a level of recursion in our example code): The first pass does eight 2-element computation loops The next pass does four 4-element loops Next is two 8-element loops Lastly, a single 16-element loop to get the final outputs Note In each of the above passes, the number of computation loops multiplied by the number of elements in the loop is 16 ( 8 × 2 8\times2 , 4 × 4 4\times4 , 2 × 8 2\times8 , and 1 × 16 1\times16 ), which means each pass processes N N elements. Since there are log ⁡ 2 N \log_2\,N passes of N N elements each, this algorithm — like the recursive one — is our target O ( N log ⁡ N ) O(N\,\log\,N) . This process can (finally!) be done iteratively instead of recursively, by getting the elements into the expected bit-reversed order, then modifying each element in place, in passes: void CalculateDFT ( complex [ ] inputs , complex [ ] outputs , int len ) { if ( len == 1 ) { // Special case length 1. outputs [ 0 ] = inputs [ 0 ] return } // Do the bit reversal so we can do the rest // iteratively in the outputs, in-place. BitReverseCopy ( inputs , outputs , len ) // Outer loop iterates all of the subFFT lengths: // starting at 2, then doubling until we reach the // full length ... this is log2(len) iterations. // This is equivalent to each level of recursion in the // previous code example. for ( int subLen = 2 ; subLen len ; subLen *= 2 ) { // This loop iterates over each subsection, as the starting // index into the data (this is the individual sub-DFTs in // the previous example). for ( int subStart = 0 ; subStart len ; subStart += subLen ) { // The data for this subsection starts at subStart. var * data = & outputs [ subStart ] // Finally, do the computation loop for this subsection. // The logic here is unchanged from the previous code // examples, and, as with our deinterleave case, reads // and writes to the same pairs of elements. for ( int k = 0 ; k subLen / 2 ; k ++ ) { int kOdd = k + subLen / 2 complex evenSum = data [ k ] complex oddSum = data [ kOdd ] oddSum *= Twiddle ( k , subLen ) data [ k ] = evenSum + oddSum data [ kOdd ] = evenSum - oddSum } } } } Note The bit reversal does not necessarily have to come at the beginning: the algorithm could instead be written to take the inputs in natural order and end up with the outputs in bit-reversed order, then do the bit reversal in-place as the last step. The indexing within the passes would be different, but the algorithm would otherwise work the same. What we’ve ended up with is the radix-2 decimation in time Cooley-Tukey algorithm . It’s radix-2 because each “recursion” splits into two sub-FFTs, and it’s decimation in time because each pass deinterleaves the input, time domain samples. Note If you go back up to the rotation diagrams again, you might note that the rotations are diagonally symmetrical, which means you could instead split on even/odd output for the first and last half of the inputs (instead of the other way around, like we did). This will end up as a similar but different algorithm, and is the decimation in frequency version of an FFT, which we’ll get to in a later post. Room for Improvement While we’ve now gotten to the core FFT algorithm, this still isn’t anywhere near an optimal implementation, and there are a number of things we’ll want to do to get this even faster. For instance: As mentioned above, this is a radix-2 algorithm, but there are other radixes (such as radix-4 , where each FFT splits into 4 sub-FFTs ) that are more efficient and worth investigating. The sines and cosines could be done via a lookup table instead of calculating them at runtime, since for a given FFT length there are only so many unique angles that are required. Doing the bit reverse pass to get things into the correct order (either at the start or end) can be a sizeable chunk of time, and depending on implementation can wreak havoc on your CPU’s caches. And then there’s doing SIMD optimizations and otherwise trying to make the memory accesses CPU-cache-friendly. We’ll touch on the first couple of those next time! (thanks again to Neintonine for giving some feedback before it went live!)📝JoshJers' Ramblings
User-Schedulable Approximations for Quantized Tensor ProgramsQuantization lets language models run on edge devices, but it sharply increases the number of tensor kernels a library must maintain: every weight format must be paired with every activation format on every instruction set and GPU, with an encoder and a decoder that agree on the stored bytes. In GGML, the tensor library used by llama.cpp, these kernels are written by hand, and only 8 of the 54 weight-activation pairs it runs on our Arm CPU have a tiled matrix-multiplication kernel.📝Alex Reinking

Thursday, November 12, 2026

C++ Dynamic Debugging is now generally availableIntroduction We are excited to announce that C++ Dynamic Debugging is now generally available in all Visual Studio 2026 channels and the Microsoft C++ (MSVC) Build Tools version 14.52. In the traditional workflow for games or large applications, switching to a debug build gives you access to debug symbols at the expense of performance. In contrast, when […] The post C++ Dynamic Debugging is now generally available appeared first on C++ Team Blog .📝C++ Team Blog
Don't be asocial: respect the user's build systemDon't be asocial: respect the user's build system You found the library, and now you just want to consume it. Except its CMake packaging is broken, or there is none at all, so using it means copying headers by hand, guessing at include paths, and fighting compiler flags it hardcoded over your own. There is no target to link against, and it drags in a home-grown dependency you have never heard of. To adopt it you would have to bend your build around its way of doing things, so you do what most people do: you reach for another library, or you write your own.📝mp-units