Welcome to SwedenCpp

Latest blogs, videos, podcasts and releases in one stream

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
ToastThe Creature The Creature. The creature approaches. Within its mouth it carries a spit-drenched ball made of felt. As you reach for its head, the creature bends away, its body language signaling an unwillingness to make eye-contact. It does not desire your hand, not while it is carrying the ball. (Frankly, even if it’s not carrying the ball you find it hard to tell whether the creature enjoys being touched, or is just neutral to it.) You pull back. Perhaps two minutes later the creature spits out the ball, putting it somewhere it believes to be accessible to you. It is not accessible to you. It’s not even visible. Rather, it’s half-beneath the chair you are sitting on, and out of reach of your hand. The creature has a limited understanding of chairs. (This doesn’t surprise you. You know that the creature may fail to recognize you if you wear a hat. In a sense, wearing a hat makes you a type of chair, you think.) The creature sits, the ball positioned on a straight line between you. It looks at you. Two more minutes pass before it lets out a little whine. Then the tiniest of wruffs. You take pity, shuffle forward, extend your arm, and pick up the ball. You toss it in the general direction of the kitchen, from the conversation pit. The apartment isn’t exactly tiny (enough for a small family, the creature, and guests), but its size is hilariously spread out across four stories. In other words, ball-space (=> pitch-speed) is limited. This does not slow down the creature. It’s been waiting for this moment. It’s been watching. The instant the ball leaves your hand, its paws start scrambling in place, and the sound of claws skidding and scratching on wood veneer fills the room. Scritscritscritscritch. The creature accelerates towards the ball and then, like a Looney Tunes character stumbling onto ice, skids again in its futile effort to slow down, before finally chomping onto the ball with a surprisingly targeted movement. The play repeats several times, before the ball finally ends up somewhere the creature cannot reach. The creature looks back and forth between you and where it suspects the ball is, letting out quiet whines at irregular intervals. You pick up a second ball, play with it in your hands, then toss it, but to no avail. It must be that first ball, at least until it finally forgets about its existence. The Creature is called Toast The Creature. Toast is what scientists would formally refer to as a Mexican street mongrel type dog creature mutt thing. There is not much to say about Toast. He gets easily excited, but then struggles to know what to do with his energy. Knock at the door? He will start barking, race towards the door (hardly a rare property for dogs), and then grab something (preferably a shoe or sock) and carry it with him as some sort of doggy stress-relief toy that he just has to have with him whenever someone new shows up. He doesn’t want you to take it, he doesn’t drop it in front of you hoping you’ll pick it up, he’s just carrying the sock, whining excitedly into it while doing a little hyperstimulated tippy-tappy tapdance with his front doggy pawsies, or running up and down the stairs. Sometimes, when given the opportunity, you can find him watching other dogs from the sidelines, unsure of how to get involved. Sometimes he likes the idea of play, gets a bit too into it, and then doesn’t know what to do when the dog he’s playing with pushes back. Toast Dog. This dog (like many others) has no dogs he regularly gets to play or even interact with. The closest he gets to meeting other dogs is being walked a few times a day, and getting to see them on the other side of the road. It makes me wonder how many of his oddities are downstream of a lack of socialization. There is something to be said about getting all the toys, healthcare and food you need, but if it came at the tradeoff of having no one to talk to , you would probably be miserable. Toast is helpless to do anything about his situation. No, it’s more than that. He’s not even capable of understanding, let alone articulating what his situation is like. He can communicate acute discomfort, that’s about it. Toast is a limited creature. He will never be more than what he is right now. He will not transcend his limits. He will never be the hero in a sappy story about a dog dragging a baby out of a burning building, or detecting a gas leak and alerting his owners. This is all he is. He cannot understand the factors that determine when he gets fed, or whether his owners will move. He has no concept of societal changes or technological progress. We live in a world in which we have access to more toys than ever, modern healthcare, an abundance of food options, and a pocket rectangle with magical functionality that obsoletes face-to-face communication 1 . Unlike Toast, we are capable of articulating what it is that diminishes us. In this, I hope that we are more different than alike. If you will, it is the mystical corner chair that allows us to watch the dog on the other side of the street. ↩︎📝MOND←TECH MAGAZINE

If this page is useful, please consider donating a coffee

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
Age and AccelerationismI Here’s a belief that may be more widespread than you’d think: “In a world without an intelligence explosion, I am going to die no matter what. Therefore, I should support accelerating the development of superintelligence / a technological singularity.” This argument cleanly maps onto a traditional 2x2 Pascal’s wager: Alignment works Takeoff would go well Alignment fails Takeoff would go badly Accelerate Takeoff while alive Immortality +∞ utility You die, sooner ≈ baseline Hold back Takeoff after you die You die of old age Baseline You die of old age Baseline Now, the obvious tradeoff here is that a “bad” intelligence explosion is going to kill you and everyone you care about (or worse). In fact, depending on your AI timelines, this death may happen a lot sooner than it would in a world without an AI takeoff. For you, my hypothetical friend and strawman, this doesn’t matter: dying in 5 years is worse than dying in 50 years, but in either world you are dead for the next 20 billion years 1 . That’s bad! You’d much rather spend that time, I don’t know, playing cards with your friends, making art, learning mathematics, or exploring the universe. If none of these appeal to you, synthetic heroin and the infinite pleasure Goon-o-tron 3000 are on the table. For at least part of my life I found this whole argument pretty compelling. I don’t think I ever felt the call of the infinite pleasure machine, but death is scary . I don’t want to die! Considering the absolute state of academia, the slow pace of biological and medical research, the existence of nuclear weapons and the mess that is geopolitics, the odds of humanity reaching longevity escape velocity within my lifetime seemed pretty low. It’s not like I really had to think about it, or faced any hard moral decisions: it was all so far away , and I was in no position to have any impact on anything 2 . Knowing who Nick Bostrom is didn’t change that. Little did I know that the future would catch up faster than any of us would like. We’re now at the point where modern AI systems are capable of writing novel mathematical proofs and developing software with minimal human supervision, while venture capital is chomping at the bit to let AI loose on biomedicine. II Why isn’t the Takeoff Pascal’s Wager a compelling argument? Well, it is a compelling argument . That’s the problem. It’s compelling for people in a narrow range of takeoff timelines. If you were, say, 90+ years old, and believed an intelligence explosion would happen in exactly 30 years, then this argument would probably not move you. You’ve lived a long and hopefully fulfilling life, but the singularity is most likely going to happen without you. On the flip side, if you were a mere 12 years old, the same timeline of 30 years would have a very different effect: you would be crazy to push for a fast AI takeoff, because AGI is going to happen within your lifetime regardless of what you do . What matters to you is a safe takeoff, without societal collapse or deadly bioengineered viruses. The Takeoff Pascal’s Wager is compelling exactly as long as you fall within the band of people who are aware of the technological risks 3 , and neither too old (you’re going to miss it) nor too young (it will happen regardless), according to your own timelines. This splits the world into three distinct groups: Safety-ism, Wager, and Skepticism. X-axis "how soon you expect takeoff", Y-axis "your age". A band runs from the upper left to the lower right, titled the "Hill of Accelerationism". Thesis: As the impact of AI on the world becomes more visible, everyone’s timelines are going to shorten. This means that young people will slide off the hill, towards safety-ism 4 . On the other side, older people may slide onto the hill, towards accelerationism. As for myself, not too long ago I was wistfully staring at the night sky, hoping to explore the stars in a hypothetical future that I knew could never truly be, and yet here we are a few years later, with hacking scandals and AI progress so rapid that it feels like we’re rushing head-first into disaster. Of course, that pushed me to the left, off the hill into the safety, alignment and oh-god-how-will-society-deal-with-this camps. III Does any of this matter? Maybe. It matters insofar as you believe that there are people out there who right now have the power and influence to meaningfully impact the future of AI, and who believe that there’s a real risk they will die of old age (or a terminal illness, or revolting underlings) unless AGI happens quickly enough and they are on “the winning team” (whatever that means). Unfortunately, we just so happen to live in a society. Power exists, and power skews old. As timelines shorten across society, these powerful people might find themselves with not-quite-enough time to think through the implications of superintelligence, nor enough time (or willingness) to read the entirety of Yudkowsky’s works. Basically, there’s a chance they’ll end up on the hill of accelerationism. For many of them, we wouldn’t even know: we don’t really talk about death , so unless you’re Bryan Johnson and ready to make it your whole personality, it’s better to keep your mouth shut. So, if you find this argument remotely compelling, you should worry about what’s going to happen as powerful older people across the world become more aware of technological acceleration, and what it means for their own mortality 5 . Alignment is hard enough on its own, you do not want to be caught up in shadow battles against moguls, CEOs, and politicians who deep-down yearn to cement their legacy. But I’m sure it’s going to be fine. It’s not like anyone was ever driven mad by the hunt for immortality, right? Oh, you’re saying that did in fact happen? Multiple times, even? Well, that was like 1000 years ago. I’m sure the great leaders of the modern world are fully in touch with the transcendent, and willing to freely hand over the power that they’ve fiercely clung to for decades. Oh. "Hot mic picks up Putin and Xi discussing organ transplants and immortality" Wait, Putin and Xi were discussing that people may live to 150 this century using organ transplants and biotech?? Ah well, nevertheless. Please excuse the sleight of hand in going from self-reinforcing general-problem-solving machines to “immortality”. For the argument, all that matters is that there’s a plausible belief that an intelligence takeoff could result in your immortality, even if this turns out to be wrong (for whatever reason). That’s a whole separate discussion. ↩︎ No, really, I lived far away and had no money or leverage. I started slowly climbing up that hill, taught myself how to code, did more writing, moved countries twice, and so on, in hope of getting to a point where I would be able to have some impact . ↩︎ If you’re e/acc-pilled enough to not believe in black-ball-from-the-urn doom scenarios, then the wager doesn’t apply to you in the first place. You are pro-acceleration in either case. ↩︎ Quick note: For lack of better terminology I’m using ‘safety-ism’ to refer to a broad umbrella. People worried about the alignment of AGI/ASI are the obvious case, but here I also include people worried about “permanent underclass” and power concentration scenarios. The argument is the same. ↩︎ On the other side, you could argue that it’s good that the most powerful AI CEOs in existence are (relatively) young compared to, y’know, heads of state across the world. Not like any of this matters if your timelines are short enough. ↩︎📝MOND←TECH MAGAZINE

Wednesday, November 11, 2026

FFTs Part 1: The Discrete Fourier TransformBecause the world clearly doesn’t already have enough of them, I recently released a new FFT library: FFT-20XX . To the best of my ability to tell, it uses an algorithm that is at least slightly novel, and I thought it might be interesting to write about it. This is the first of a series of posts about FFTs and (eventually) the specific algorithms that FFT-20XX uses: The Discrete Fourier Transform (← you are here) The Basics of the FFT Some Optimizations to the FFT The Inverse FFT The FFT-20XX Complex-Input Algorithm The FFT-20XX Real-Input Algorithm(s) As a first step I thought it might be fun to start with “what even is the discrete Fourier transform ?” Fourier Transforms Any explanation of a Fourier transform would be remiss to not include a link to this fabulous 3Blue1Brown video that nicely illustrates how the Fourier transform works. I highly recommend watching it! This post, however, is specifically about the discrete Fourier transform (referred to as the DFT ), which is a Fourier transform that operates on sampled data (like, say, digital audio or images) instead of continuous data. The FFT (fast Fourier transform) is the standard algorithm used to compute the result of a DFT — we’ll get to it in the next post. What Does the DFT Even Do? Any periodic signal (i.e. a signal that repeats, such as looped audio) can be represented as the sum of a set of sine waves at different frequencies. Here is an example of a simple signal that can be broken down into three waves: Diagram of a somewhat complex wave, which is composed of the three following waves = Diagram of the lowest frequency and highest-amplitude wave that makes up the above complex wave. + Diagram of the middle frequency wave that makes up the above complex wave. It has an amplitude lower than the first component wave. + Diagram of the highest-frequency wave that makes up the above complex wave. It has a lower amplitude than the first two. This is true of any periodic signal whether it is analog or sampled — no matter how complex it may seem. The DFT answers a simple question: given a set of samples that represents a periodic signal, which frequencies are represented in that signal ? Note The “periodic signal” bit is important! The algorithm assumes that the block of samples it is processing repeats forever: Diagram showing a signal that repeating three times. However, this won’t be the case for all blocks, such as this one where there’s a hard discontinuity: Diagram showing a signal that repeats three times, however this time the wave in each signal do not line up properly at the edges, causing a discontinuity. This can cause noise in the resulting DFT output. There are a few tricks that can be done for cases like this (like windowing the signal) to effectively “pretend” that it is periodic when it’s not, but that’s out of scope for this post. To put it another way: the DFT converts a signal that is made up of samples in time (where each sample represents a point on the signal at a given time) into the same signal represented in frequency (where each sample represents the amplitude (how tall the wave is) and phase (the side-to-side position of the wave) of its corresponding frequency). These two representations are frequently referred to as time domain and frequency domain , and both encode the same signal in different ways. Note There is also an inverse DFT (the IDFT ) which converts the other way — from the frequency domain back to the time domain. Many signal processing applications convert from time to frequency space to do some operation, then use the inverse DFT to convert back. We’ll get to the inverse DFT in a later post. For a given repeating signal that is N samples long, the DFT returns contribution values for N frequencies, each with one more cycle than the previous. To put it a different way: for each frequency with index k (starting at 0 and ending at N - 1 ) there are k cycles of a wave (so index 0 has 0 cycles, index 1 has 1 cycle, etc). Here are the 8 waves for a DFT with 8 samples (the red wave with circles is the cosine and the green wave with squares is the sine): 0 Diagram of Frequency 0: all of the cosine values are '1' and all of the sine values are '0'. There are 8 points on each wave representing the samples (this is true for all subsequent waves as well). 1 Diagram of Frequency 1: there is a single up to down to up cycle of the cosine and sine waves. 2 Diagram of Frequency 2: there are two up to down to up cycles of the cosine and sine waves. 3 Diagram of Frequency 3: there are three up to down to up cycles of the cosine and sine waves. 4 Diagram of Frequency 4: there are four up to down to up cycles of the cosine and sine waves. Notably, the cosine samples alternate between '1' and '-1', and the sine samples are all '0'. 5 Diagram of Frequency 5: there are five up to down to up cycles of the cosine and sine waves. 6 Diagram of Frequency 6: there are six up to down to up cycles of the cosine and sine waves. 7 Diagram of Frequency 7: there are seven up to down to up cycles of the cosine and sine waves. Ultimately, a DFT will give you a set of values that tell you how much each of these frequencies contributes to the signal. Specifically, each frequency will have a value that represents both its amplitude and its phase . Note The frequency at index 0 always has cosine values of 1 and sine values of 0 , and this ends up measuring how “off-center” the signal is (relative to the x axis). This is known as the DC bias or DC offset . A signal with no DC bias. The wave is centered on the x axis No DC bias A signal with positive DC bias. The wave is above the x axis Positive DC bias A signal with negative DC bias. The wave is below the x axis Negative DC bias Let’s figure out how to calculate the DFT for a signal! Frequency Testing The first step of computing the DFT is to figure out how to get a single frequency out of a signal. Ignoring phase for a moment, this can be done in a surprisingly straightforward manner (to me, at least): if we multiply each sample in the signal by the cosine value of the test frequency and sum the results , you end up with a value that represents the contribution of that frequency to the signal (which is 0 if the frequency is not present in the signal). Here is an interactive example where you can set the signal and test frequencies and see the result of this process. For purposes of illustration, we’ll display the average instead of the final sum (as the sum would be too large to fit in the diagram): An interactive diagram that demonstrates how the signal and test waves are processed to detect frequencies. × Interactive diagram = avg → Signal Amplitude: 1.0 Signal Cycles: 2 Test Cycles: 2 Note that when the frequencies match (signal and test cycles), the resulting average scales with the amplitude of the signal , otherwise (with one exception we’ll touch on in a moment) it is 0 . This makes this sum effectively a frequency detector (again, ignoring phase for now)! This is still true even when there are multiple frequencies represented within the signal: this will result in a zero value for frequenices that are not in the signal and non-zero values for those that are . Math Time! If you’re interested in the math of how this works, here you go: The sum of all samples of a repeating cos ⁡ x \cos\,x signal is 0 0 , as it has the same area above and below the x x axis, which cancels out in the sum. Now, if we multiply two such waves together: cos ⁡ x ⋅ cos ⁡ y \cos\,x \cdot \cos\,y , this can be rewritten (via trig identities ) as: 1 2 [ cos ⁡ ( x − y ) + cos ⁡ ( x + y ) ] \frac{1}{2}[\cos (x - y) + \cos(x + y)] If x x and y y don’t match, these are just two repeating cosines, and each of them sums to 0 0 over all of the samples (just like the single wave above). However if x = y x = y , this becomes: 1 2 [ cos ⁡ ( x − x ) + cos ⁡ ( x + x ) ] \frac{1}{2}[\cos (x - x) + \cos(x + x)] ⟹ 1 2 [ cos ⁡ 0 + cos ⁡ 2 x ] \implies \frac{1}{2}[\cos\,0 + \cos\,2x] ⟹ 1 2 + 1 2 cos ⁡ 2 x \implies \frac{1}{2} + \frac{1}{2}\cos\,2x That remaining cos ⁡ \cos term, over all of the samples, once again sums to 0, which leaves us with a constant 1 2 \frac{1}{2} in the average. As noted, there’s an exception here, where the multiply-and-sum seems to register a match when it shouldn’t. For example: if you set the Signal Cycles to 1 and the Test Cycles to 15 (or vice versa), it will have a non-zero average even though the frequencies don’t match. In fact, with the exception of frequencies 0 and 8 , there are two matches for every other frequency. Why is that? Well, now it’s time to talk about… Aliasing and Negative Frequencies Let’s take a closer look at the cosine values for our example frequencies of 1 and 15 cycles: 1 Diagram of the cosine for frequency 1 with sixteen samples. The wave has a single cycle. 15 Diagram of the cosine for frequency 15 with sixteen samples. The wave has fifteen cycles. The sample positions in this diagram are exactly the same as in the diagram of frequency 1. Note that while the waves are different frequencies, the cosine samples are the same! This is because of aliasing , which is where a frequency above the maximum representable frequency ends up sampling as if it were a different, lower frequency. The frequency above which aliasing occurs is called the Nyquist frequency , which is the highest frequency where there can be both a high and low sample for every cycle (you need both to represent a wave). In a signal with N samples, that frequency has N / 2 cycles. For example, with 16 samples the Nyquist frequency has 8 cycles (which you can see have a clear up then down pattern): Diagram of the cosine for frequency 8 with sixteen samples. The wave has eight cycles. Every sample on the cosine wave alternates between '1' and '-1' Above this frequency, the cosine samples end up aliasing to a lower frequency and cannot be differentiated anymore. Here are some more example pairs of aliased cosines from our 16-sample example: 2 Diagram of the cosine for frequency 2 with sixteen samples. The wave has two cycles. 14 Diagram of the cosine for frequency 14 with sixteen samples. The wave has fourteen cycles. The sample positions in this diagram are exactly the same as in the diagram of frequency 2. 3 Diagram of the cosine for frequency 3 with sixteen samples. The wave has three cycles. 13 Diagram of the cosine for frequency 13 with sixteen samples. The wave has thirteen cycles. The sample positions in this diagram are exactly the same as in the diagram of frequency 3. 7 Diagram of the cosine for frequency 7 with sixteen samples. The wave has seven cycles. 9 Diagram of the cosine for frequency 9 with sixteen samples. The wave has nine cycles. The sample positions in this diagram are exactly the same as in the diagram of frequency 7. Note that each pair has matching cosine samples , despite the different wave. Specifically: with a repeating sample count of N , any frequency with N − k N - k cycles has the same cosine values as the frequency with k k cycles (that is 1 matches 15 , 2 matches 14 , etc). Note This is just like the optical illusion where rapidly-spinning things like car wheels can appear to be rotating backwards . That’s neat! But it’s not the whole picture. We can’t just look at the cosine values, we need to look at what happens to the sine values as well: 1 Diagram of the sine for frequency 1 with sixteen samples. The wave has a single cycle. 15 Diagram of the sine for frequency 15 with sixteen samples. The wave has fifteen cycles. The sample positions in this diagram are like the ones in the diagram of frequency 1, but negated. 2 Diagram of the sine for frequency 2 with sixteen samples. The wave has two cycles. 14 Diagram of the sine for frequency 14 with sixteen samples. The wave has fourteen cycles. The sample positions in this diagram are like the ones in the diagram of frequency 2, but negated. 3 Diagram of the sine for frequency 3 with sixteen samples. The wave has three cycles. 13 Diagram of the sine for frequency 13 with sixteen samples. The wave has thirteen cycles. The sample positions in this diagram are like the ones in the diagram of frequency 3, but negated. 7 Diagram of the sine for frequency 7 with sixteen samples. The wave has seven cycles. 9 Diagram of the sine for frequency 9 with sixteen samples. The wave has nine cycles. The sample positions in this diagram are like the ones in the diagram of frequency 9, but negated. While the cosines are the same in these pairs of frequencies, the sines are negated and appear vertically flipped! This means that a given frequency with N − k N - k cycles has negated sine values from the frequency with k k cycles. The relationship here is that the aliased frequencies in each pair are negated versions of the other, since cos ⁡ ( − a ) = cos ⁡ ( a ) \cos({-}a) = \cos(a) and sin ⁡ ( − a ) = − sin ⁡ ( a ) \sin({-}a) = {-}\sin(a) . Thus, frequency N − k N - k has the same angle as the hypothetical frequency at − k {-}k : Cosines: -1 Diagram of the cosine for a hypothetical frequency -1 with sixteen samples. The wave has a single cycle. 15 Diagram of the cosine of frequency 15 with sixteen samples. The wave has fifteen cycles. The sample positions in this diagram match the ones in the cosine diagram for hypothetical frequency -1 exactly. Sines: -1 Diagram of the sine for a hypothetical frequency -1 with sixteen samples. The wave has a single cycle, negated vs a standard sine wave. 15 Diagram of the sine of frequency 15 with sixteen samples. The wave has fifteen cycles. The sample positions in this diagram match the ones in the sine diagram for hypothetical frequency -1 exactly. In practice, when computing the DFT, the frequencies above Nyquist are referred to via their negative indices instead of as the positive aliased ones. This explains why all of the frequencies in the above example (except DC and Nyquist) have two matches: the cosines match at both the positive and negative versions of the angle. This may seem redundant, but it isn’t always — we’ll get into why in a bit. Note It’s also worth noting that the multiply-then-average in the example diagram results in half the signal amplitude for each match, and when both are summed, the result represents the full amplitude! However, DC and Nyquist — because they each only have a single match — have an average that matches the amplitude exactly. Measuring Phase So far we have been looking at a signal that contains a cosine, comparing it with a test wave that is also a cosine, and getting an amplitude-relative result. But the original description of the DFT mentions both amplitude and phase as being represented, so what happens if we let the phase of the signal shift around relative to the test? An interactive diagram that demonstrates how adjusting the the signal phase affects the average. × = Interactive diagram avg → Signal Phase: 0.0 Oh no! Sliding the phase around causes the resulting average to oscillate ! While we get the expected 0.5 average when the phase is 0, it is -0.5 at a phase of 0.5 (a half-wavelength offset) and, even worse, 0 at phases of 0.25 and 0.75 (quarter- and three-quarter-wavelength offsets)! Clearly there is something else we need to consider here…and it turns out it’s the sine of the test frequency. Instead of just multiplying by the cosine of the test value, we can instead multiply by both cosine and sine to get two values per sample. If we then treat those two resulting values as a 2D coordinate (where cosine corresponds to x and sine to y ), we can average them all to get our final result, which will be at the origin for non-matching frequencies and at some non-origin position for matches. Note “Multiply by both sine and cosine” is a simplification for purposes of illustration. It works for now but is not the general form, which we’ll get to in a bit. An interactive diagram that demonstrates how adjusting the the signal and test waves affects a 2D average. × Interactive diagram = avg → Amp: 0.5 Phase: 0.00 Signal Phase: Signal Cycles: Test Cycles: Some observations from this diagram: If the cycle value magnitudes don’t match , the points are all evenly distributed around the center (and thus the average is at the origin). This makes it much easier to visualize why we end up with no measured amplitude for mismatched waves. If the cycle value magnitudes do match (i.e. a signal of 2 cycles with either 2 or -2 test cycles), the points are off-center , and thus their average is also off-center. Increasing the phase causes the resulting average to spin clockwise when the test cycle count is positive , but counter-clockwise when the test cycle count is negative . The magnitude of the average remains the same no matter the phase. At Nyquist (8 cycles), the resulting points always lie on the x axis, as the test wave’s sine values are all zeros. It turns out: a phase-shifted wave at Nyquist is indistinguishable from a non-shifted wave with scaled amplitude (because there is literally no way to represent such a phase shift with the given sample rate). This gives us a new way to think about this computation: rather than thinking of the operation as a multiplication, instead we can think of each sample of the signal being rotated by the angle of the test wave at that sample position to get a new 2D position. Those 2D positions are then summed to get a value that corresponds to the frequency’s contribution. The computed amplitude (the strength of this frequency’s contribution) is the magnitude of the resulting average (its length), and the phase is the angle of the average (computed, in this case, using atan2 ). 2D Coordinates and Complex Numbers Each result of this multiplication with cosine and sine ends up as a 2D coordinate . Canonically, the Fourier transform represents these as a complex number (of the form x + i ⋅ y x + i \cdot y ). Why complex numbers? Honestly I think it’s a hack to get a 2D coordinate that is simple to represent with standard math notation (mathemeticians, don’t @ me). Note If you, like me, prefer 2D vectors to complex numbers, just pretend that x + i y x + iy is the 2D vector [ x y ] [\,x\,\,\,y\,] as you read all of this: the real component is the x x coordinate and the imaginary component is the y y coordinate. To be fair, complex numbers do have a nice property that standard 2D vectors do not: they can be multiplied in a meaningful way. The specific complex multiplications done by the DFT (an input sample [ a + i b a + ib ] multiplied by a wave value [ c o s t + i s i n t cos\,t + i\,sin\,t ]) ends up rotating the input by the angle t t ! Note If you’re familiar with matrices and linear algebra, this complex multiply (with c c and s s representing the cosine and sine values): ( x + i y ) ⋅ ( c + i s ) (x + iy) \cdot (c + is) ⟹ ( x c − y s ) ⋅ i ( x s + y c ) \implies (xc - ys) \cdot i(xs + yc) …results in exactly the same operations as multiplying a 2D vector (x, y) with a 2x2 rotation matrix representing the same angle: [ x y ] ⋅ [ c s − s c ] \begin{bmatrix}x & y\end{bmatrix} \cdot \begin{bmatrix} c & s \\ -s & c \end{bmatrix} ⟹ [ x c − y s x s + y c ] \implies\begin{bmatrix} xc - ys && xs + yc \end{bmatrix} This also finally gives us an answer to the earlier question of why we need both the positive and negative versions of a given frequency: if the input samples are complex (i.e. 2D) instead of purely real-valued (1D), the contributions to these paired frequencies can be different, and both are needed to fully reconstruct the signal. For real-valued signals , however, the paired results will be complex conjugates , where the result ( a + i b a + ib ) for frequency k k is the conjugate of the result for frequency − k {-}k : ( a − i b a - ib ); they have the same real (x) term but opposite imaginary (y) terms. When summed, these values ( a + i b a + ib and a − i b a - ib ) become 2 a 2a as the imaginary components cancel out, which is how a signal made up of real cos ⁡ \cos terms and imaginary sin ⁡ \sin terms can be a purely real-valued signal. Note It’s worth pointing out something that shows up in the standard formula for the DFT: mathematical notation has an absolutely wild shorthand for cos ⁡ t + i sin ⁡ t \cos\,t + i\,\sin\,t : e i t e^{it} That’s right, taking the mathematical constant e e to an imaginary power is the same as a rotation around the origin. Why? Well, 3blue1brown has an explanation if you’re curious. Personally I don’t like this shorthand because it obscures the meaning of the equation, especially for non-mathemeticians (which is, if I’m doing my calculations right, most people ). Calculating the DFT Okay, we finally have all of the pieces of how to calculate a DFT, it’s time to put them together. A DFT takes a set of complex input samples in the time domain and produces the same number of complex output samples in the frequency domain, where the first output sample (at index 0 ) represents the DC offset, the middle one (at index N/2 ) represents the Nyquist frequency, and the rest are either the positive or negative angles in between. There are a couple minor (but important) differences in the value calculation done in the above interactive diagrams vs how the DFT does them: Typically the DFT rotates the opposite direction as the above diagrams (i.e. using sin ⁡ ( − t ) \sin({-}t) instead of sin ⁡ t \sin\,t ), so the rotations actually spin the opposite way (clockwise becomes counter-clockwise and vice versa). Rather than averaging the results of these rotations, the DFT simply sums them — no division by N is performed. Otherwise, the process described above can be used to get the contribution of any single frequency within the signal, so then we just need to do this process for every possible frequency in the signal. Thus, here we are, finally at some pseudocode to calculate the DFT: 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 (the "test frequency" from the // earlier examples). 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 // `i` here is the imaginary unit complex rotation = cos ( radians ) + i * sin ( radians ) // A complex multiply with a unit complex vector is // a rotation. sum += inputs [ inIdx ] * rotation } outputs [ outIdx ] = sum ; } } Note As mentioned in a previous note, the standard formulation of the DFT uses an exponential shorthand (which I do not like) to represent the rotation. Thus, the DFT is written in standard mathematical notation as: X k = ∑ n = 0 N − 1 x n ⋅ e − i 2 π k N n X_k = \displaystyle\sum_{n = 0}^{N - 1} x_n \cdot e^{-i2\pi\frac{k}{N}n} …which is equivalent to the above pseudocode. We’ve finally done it! We have some code we can use to calculate the DFT for a given signal. The above algorithm is O ( N 2 ) O(N^2) , which may seem like the best that can be done. However, there’s a bit of algorithmic trickery that can be done to get that down to O ( N log ⁡ N ) O(N\,\log\,N) , which is considerably more efficient. That trickery is the fast Fourier transform (FFT) , and the next post will go into the details of how that works! (thanks to Neintonine , zerostride , and Chuck for giving me some great feedback on this before it went live!)📝JoshJers' Ramblings
Understanding C++26 hazard pointersThe C++26 standard features a new header called and a new class with the same name, which, together with hazard_pointer_obj_base, provides safe memory reclamation for lock-free data structures. In this article, we’ll see how all this works. The memory reclamation problem To understand why hazard_pointer exists, we first need to look at what makes ... Read more The post Understanding C++26 hazard pointers first appeared on Marius Bancila's Blog .📝Marius Bancila's Blog
For the first time, a C++ standard failed to pass the national bodiesBjarne Stroustrup, in the flesh. *Pops cork*. It looks like it happened! A historic first, for better or worse. This is a sign that C++ is (still) struggling with its governance (see a previous article on cultural issues within C++ here ). This is a big deal even if you do not care about programming languages. C++ is arguably the most important programming language in existence. Your computer runs on C or C++. The web browser you are using to read this is written in C++. ~All programming languages depend on C++ (often through LLVM). Likewise, ~all websites with performance requirements (e.g. YouTube) depend on C++, ~all data storage, game engines, finance, etc. In a world that is drowning in exciting new vulnerabilities in ~all software, the ability of C++ to change and adjust to changing times affects you. Let’s take a step back and get an overview. The initial source was a post by Robert Seacord on LinkedIn : = 66.66%) (P-Members having abstained are not counted in this vote.) Member bodies voting: 9 negative votes out of 22 = 41 % (requirement "Balloting has completed for C++26. Unfortunately it was Disapproved. P-Members voting: 12 in favor out of 20 = 60 % (requirement >= 66.66%) (P-Members having abstained are not counted in this vote.) Member bodies voting: 9 negative votes out of 22 = 41 % (requirement In a comment, J. Daniel García adds: “There were 12 countries that abstained. In several cases because they could not reach to a common position. That is another signal of a contested draft.” Now, before we get into the facts: This is not a good look for C++. There have been multiple fights over the future direction of the C++ language, but no C++ standard ever failed to be signed off by the national bodies. The national body vote is considered to be a formality . By the time the vote reaches the national bodies all disagreements should’ve been sorted out by WG21 (Working Group 21, i.e. the C++ Standards Committee). Truly controversial features should never make it this far, since they should never be added to the C++26 working draft in the first place. This is a sign of division in the C++ community, in some form or another, and completely independently of whether you agree with this result or not. Here, “Added to the C++26 working draft” is essentially accepting the pull request. Everyone is working towards the C++26 release, and people contribute to it with papers. Papers lead to votes, which then lead to amendments of the draft. Finally (this is where we are) wording passes happen, and it gets signed off, rubber-stamped and released. Phrased like this, the ISO process sounds sensible enough, but trust me, it’s actually kind of a nightmare. Needless to say, the debates are raging, with comments on all sides: So many discussions . Wait, how did the voting break down? What are P-members??? Quick explanation: The national bodies execute a single vote. To pass the national bodies, the draft has to meet two bars: At least two-thirds of the participating voting members have to vote Yes . At most one quarter of all voting members may vote No . If the above posts are correct , then the draft failed to meet both bars. Twelve isn’t two-thirds of twenty, and nine is more than a quarter. Visualization: Yes No ≥ 2/3 12 (60%) 8 (40%) Yes No Abstain Non-P-member ≤ 1/4 9 (41%) 13 (59%) 12 In total, there were 20 P-members, and 22 total members (ignoring abstaining). I heard that the US abstained, but take that with a grain of salt. So, what happened? tl;dr : WG21 voted to include Contracts in C++26. Several high-ranking members of WG21 are strongly opposed to Contracts, and so are several national bodies. The national body vote was the ’last resort’ place to prevent Contracts from being canonicalized as part of the C++ standard. Wait, that’s too fast for me, what are Contracts? New keywords that replace assert macros with a standardized way to enforce runtime checks. Most importantly, you can add pre and post checks to ensure that all arguments and return values fulfill certain conditions. This ends up looking roughly as follows: int wrap_index ( int i, const int size) pre (size > 0 ) // the caller must guarantee this post ( r : 0 r && r size) // the function promises this ; r is the return value { int r = i % size; if (r 0 ) r += size; contract_assert(r >= 0 ); // a check inside the body return r; } Looks simple, right? You’d think so, but no! First, due to issues with virtual functions, Contracts for virtual functions were already cut from the proposal. Second, it’s not entirely obvious how this will interact with constexpr or function inlining. Third, there are compile flags to selectively enable or disable the enforcement. E.g. “If a contract is violated, do you want to 1) kill the program, 2) call a ‘contract-violation handler’ and then kill the program, 3) log an error, 4) ignore completely (and not even perform the check, for performance reasons)?” Big question: You compile your code with enforce and are linking a prebuilt library that pulls in the same dependency as you, but with Contracts set to ignore . This is fine according to Contracts. The linker gets to keep one of the copies. What happens? Do Contracts run or not? What if a call is inlined across translation units? Is there even a way for the user to guarantee that checks always run? (The answer is no. What? You were hoping that this feature could be used to ensure certain checks guarding against Undefined Behavior would always run, no matter what? Don’t be silly—this is C++.) Oh, did I mention that code inside of predicates is just standard C++, so the compiler is allowed to elide checks due to Undefined Behavior? But do feel free to take it from the source: The “Contracts paper” can be found here , and if you read closely, you’ll find some funny statements that really ruffled some feathers: It is ill-formed, no diagnostic required (IFNDR) if multiple first declarations for the same function are in different translation units that do not have the same sequence of function contract specifiers. All of this leads to so many funny issues , some of which can be poorly summarized as “Well, who even knows whether your Contracts are even going to be enforced, this is C++, the compiler can do whatever it wants lol”. If you think “Gee, this proposal looks rather complex and messy”, keep in mind that the Contracts paper was explicitly designed to be a minimal viable product that everyone would be able to agree on. If you only faintly paid attention to C++, you might be going into this assuming that Profiles (aka Bjarne Stroustrup’s initiative to make C++ safer via magical fairy dust, also controversial and considered to be ‘impossible to implement’ by some) are the sticking point, but no, Profiles did not make it into C++26 . How do we know that it’s Contracts? Oh, y’know, it’s just because that’s all everyone has been talking about . Most obviously, the pro-Contracts camp released “Do not remove Contracts from C++26” on Oct 23rd, i.e. around the time when the national body ballot closed. Vinnie Falco (the most outspoken voice against Contracts) countered with “Do Remove Contracts From C++26” on the very same day 1 . If you’ve been paying attention, there’s a whole trail of papers and events here. We’ve got talks, and Bjarne Stroustrup, the creator of C++ himself, saying “it’s claimed to be a minimum viable product. It is not minimal. I don’t think it’s viable” . We’ve got multiple papers, say “Contract Concerns” , “Contracts make C++ less safe — full stop!” , or “Contracts’ fundamental flaws” (all reasonably short) opposing the behemoth that’s the Contracts paper and its rationale document (put together, almost 300 pages). We’ve had multiple votes. Most importantly ( Hagenberg, Feb 15th, 2025 ), the vote to formally add Contracts to the C++26 working draft, turned out 100 in favor, 14 opposed, 12 abstain. The multiple votes to remove Contracts from the draft all failed, most recently in Croydon , which is also when an amendment to support a mechanism to ensure mandatory contract enforcement failed . If your eyes are glazing over at this point, I don’t blame you! The whole situation is a mess, and trying to keep track of it from the outside is a fool’s errand: You’re basically forced to track dry meeting notes, and read between the lines looking at the various drafts people are publishing. Don’t do it. This is not Contracts’ first rodeo: A different version of Contracts was up for debate around 2018, and was kicked out not too long after. At this point SG21 (‘Study Group 21’) was formed, dedicated to revamping the Contracts concept to get us the new “Minimum Viable Product” that’s currently part of the draft. The whole situation went back and forth, resulted in fourteen revisions on the Contracts paper, many comments from the national bodies during the process, and finally in some people explicitly calling for the national bodies to veto C++26 . (We call that ’the nuclear option’. FYI, some of the people signing this are themselves sitting on national bodies.) This was then what, in fact, happened. Where are we standing? What you need to understand is that the Hagenberg vote (on adding Contracts to the working draft) was strongly in favor of Contracts. 100 in favor vs. 14 against is not a weak result. This makes it incredibly puzzling that this final vote failed so badly (12 for, 8 against is bad). One narrative on what happened is the following: “There’s a loud minority strongly opposing Contracts in C++26. This group includes people with a lot of influence, e.g. Bjarne Stroustrup. Some members of this group actively lobbied the national bodies to vote against Contracts, even though WG21 achieved alignment, and agrees that Contracts should ship in their current form.” This agrees with the evidence we’ve seen (votes in favor, some people strongly opposed). Herb Sutter is suggesting this in his latest paper, see here . (Herb Sutter, for the record, was the chair of the C++ Committee and is (next to Bjarne) perhaps the second-most-important person anyone in the C++ world listens to.) This is plausible, but I don’t believe it. Not entirely, anyway. Yes, lobbying happened, and Bjarne’s opinion is something people listen to. It’s possible it was the deciding factor, but if it was the deciding factor, then this is a sign that the process itself is broken, and puts undue value onto status. Even Herb Sutter acknowledges that Contracts were contentious. In footnote 4 on his paper, anyway. Some of the NBs that voted Disapprove had participated and had expressed concerns about contracts without having to be lobbied (importantly, those were the first-ever Disapprove votes on any C++ DIS). In other words, before any lobbying happened we already had a historical first, the strongest ever NB disagreement with a draft. Importantly, it looks to me as though the committee just repeatedly ignored the comments/feedback of the national bodies throughout the process, and then ran face-first into a wall at the vote. If you think “Oh, you are saying that the committee is just straight-up incompetent and/or evil, then?” No, not really. The committee process is just such a mess that it semi-naturally leads to situations like this. The people working within this system have become so used to the process that they’re barely capable of seeing it. (Over the years many people who did not find this process workable just left entirely. There’s a huge selection bias effect.) Part of what makes the process bad is that it’s very “all or nothing”, and the process is so slow that working on the standard is painful for everyone. More on that later. Anyway. I don’t believe that it’s all just the lobbying. The discussions were already way underway. Evidence: Exhibit A: Comments by National Bodies Taking a look at “Do not remove Contracts from C++26” , it refers to the “23 NB comments on contract assertions”. Taking a closer look at N5028 and N5031 , we see the committee rejected at least one strong anti-Contracts comment from each of the following countries: Sweden, Spain, the United States, France, Romania, the Czech Republic and Finland. These comments included multiple asks to not ship Contracts in their current form at all, resolve safety issues, make Contracts reliably non-ignorable, fix the const issues, and change it such that standard library hardening phrasing does not depend on Contracts. Again: None of these were accepted 2 ! What did the committee think? That all of these asks were completely irrelevant? Yeah, no shit people are going to vote against something or abstain if you ignore their concerns. This was preventable! People told you ahead of time that they were strongly opposed! The national bodies played their part correctly here. They gave you feedback ahead of time, and then voted accordingly. Exhibit B: Standard Library Hardening There were at least four comments asking specifically “Please do not make the work on ‘standard library hardening’ depend on the inclusion of Contracts into C++26.” As it stands, this coupling is still there, i.e. the comments were ignored. In fact, now that the future of Contracts is shaky, the “Do not remove Contracts” paper includes the following line: At the time of writing, there is no wording for removing contract assertions from C++26, and producing it is not a purely mechanical exercise. It would require: […] removing or respecifying C++26 standard-library hardening [P3471R4], which is written in terms of contract assertions and has never had complete, reviewed wording that is independent of contract assertions. The audacity. The national bodies were very explicit in saying that they do not want standard library hardening to depend on Contracts . You went and ignored those comments, and are now complaining about the effort that would be necessary to walk things back? You were given all the heads-up you needed, you just ignored it! Exhibit C: Non-ignorable Contracts I quote Footnote 6 from Herb Sutter’s paper on the situation we are in . If there is an expert, it is him: P3911 is the only technical proposal that NBs told us during CD comment processing would likely prevent multiple potential NB negative votes. It’s also a pure extension that doesn’t disturb the rest of the contracts design or interfere with future extensions, which makes it low-cost and low-risk to adopt. This is why in Kona I repeatedly encouraged EWG to pursue it. It addresses what several experts said was their principal concern motivated by safety issues: to provide a way to write a contract in source code that would be guaranteed to be enforced at execution time regardless of build mode or linking. However, it failed to be approved in the EWG 2026-01 telecon (‘encourage more work in this direction’ failed by 8-25 for-against, with 9 neutral). Now we have the new information that NBs have rejected the DIS, and several have again cited safety as a critical issue, so this change is likely to increase NB consensus. P3911 is the paper that proposes adding a way to ensure Contracts will always run, and can be enforced. (Which, yes, a lot of people believe is necessary for a safety feature. If you can’t guarantee the safety is even enforced, what’s the point?) Do Herb Sutter and I even disagree? Honestly, probably not. Herb Sutter is looking at the situaation from the political angle, and analyzing whose beliefs have more weight based on their status. Bjarne Stroustrup’s beliefs (as the creator of C++) hold a lot of weight. This is correct. Quoting Herb Sutter’s discussion on the matter : Over half of the NBs that voted Disapprove on the C++26 DIS had never participated in WG21 at all and/or never before expressed any concern about contracts in C++26 (most sent no comments on the C++26 CD comment ballot; one sent contracts-unrelated CD comments), yet voted against the DIS after being lobbied with messages citing Bjarne’s opposition. “Look! It’s just Bjarne having a lot of status!” he says, and he is completely right in saying so, but he is also acting as though putting huge pressure on members to “disagree and commit :-)” hadn’t always been part of it. The C++ Standards Committee always voted in terms of factions. It was always a political mess where Bjarne’s explicit support was absolutely critical, and where “I know you may disagree with this, but you should vote in favor to get it in” was a part of the process. Quoting Herb Sutter and Bjarne, yet again from Herb Sutter’s paper: (Ed.: Bjarne added, when reviewing this paper, that one reason previous DIS ballots were unanimous was his private and public encouragement.) Aka lobbying. Always has been. Verdict Why is C++ in this mess? Why are Contracts authors so obsessed with getting Contracts into C++26? Why not wait for the next release? Well, C++ has this funny “release train model” (also known as “ the frame rule bus stop analogy ” in Super Mario Bros. speedrunning). A new version of the C++ standard releases every three years. If your work gets voted into the standard in time, it becomes part of it. If it doesn’t, you have to wait another three years for the next release. Three years is a long time, and it’s an especially long time to work on a single C++ feature. Getting a C++ paper accepted into the standard is a process so notoriously draining that ~all of the “C++ people” I know just stopped bothering, and stopped working with WG21. It’s bad. If Contracts don’t get in this cycle , there’s a good chance they never will. They will be nitpicked over the next three years, endlessly litigated, and frankly, I think there’s a good chance several of the people working on Contracts just won’t want to deal with that, and might instead drop out of the process entirely, leaving Contracts dead and buried . Until the process itself changes , which, god knows how that could happen considering the requirements presumably imposed by ISO, it’s hard to imagine this changing. This is why the pro-Contracts side released the following statement in their paper: If the DIS ballot has failed, we should seek another ballot without altering contract assertions or removing them from C++26; In other words, they are playing a game of Chicken: “We believe you are going to give up first.” They know full well that a failed C++26 will hurt everyone . But, because the WG21 process is so insane that a loss here risks killing Contracts entirely, and would require another three years of endless litigation and fights, the stakes are high. As far as I know, the next scheduled WG21 meeting runs Nov 16–21, 2026 in Búzios. So, you might think “Ah, then it’s just a few days and they’ll sit down and sort things out, right?” Well, probably not. The WG21 + ISO process is slow and messy. Even if everyone agrees on whether Contracts should/should not go in, each ballot is open for multiple weeks. So yeah, this may take another year or so. So uh, good luck, C++. If C++26 fails, I’ll pour one out. Not for you, but for the many, many people who tried to make you better, and failed 3 . It’d be slightly easier to take Vinnie’s paper seriously if it didn’t contain Claude-isms like “The ‘purely additive’ claim turns the deferral into a dismissal” that make my eyes glaze over. There has been an uptick in AI usage within WG21, and not all of it has been responsible. ↩︎ Okay fine, there were some tiny concessions, P3878R1 decoupled parts of standard-library hardening from Contract observe mechanics. Still coupled to Contracts though, making it impossible to allow standard-library hardening to enter without Contracts getting in. In other words, the ‘standard-library hardening’ draft was written with the assumption that Contracts would definitely go in. ↩︎ This, for the record, will include the Contracts people (assuming Contracts fail). I am not a big fan of Contracts (for reasons unrelated to any of the discussion here), but I understand the case for them, and the people working on them are (like everyone else) victims of the process. ↩︎📝MOND←TECH MAGAZINE

Tuesday, November 10, 2026

Every Craft That Moved Before: What Photography, Compilers, and Looms Teach Us About AIEvery time a machine learns a new trick, skilled people panic. And every time, they say some version of the same thing: this is different. This time it’s really the end. They’re always right that it’s different. And they’re almost always wrong that it’s the end. I’ve been preparing a talk for Meeting C++ about what happened to the joy of programming in the age of AI. As part of that work, I w...📝Sandor Dargo's Blog
Automatic MSBuild configuration for the Microsoft C++ Language Server in Copilot CLIAccurate C++ code intelligence starts with understanding how your project builds. Compiler options, include paths, and preprocessor definitions all affect how the language server interprets your source files. A compilation database, such as compile_commands.json, provides that context, so that tools such as go-to-definition and find-references can resolve symbols accurately. The Microsoft C++ Language Server now […] The post Automatic MSBuild configuration for the Microsoft C++ Language Server in Copilot CLI appeared first on C++ Team Blog .📝C++ Team Blog
Fun with designated initializersC++20 (via [P0329](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0329r4.pdf)) introduced a relatively nerfed form of designated-initializer (`.field = 42`) syntax. Unlike C, C++20 doesn't support out-of-order initializers, any mixture of designated and non-designated initializers, or array-element designators. Array-element designators like `[0] = 42` aren't supported by standard C++. Why not? Read the spoiler in [diff.dcl], or, consider Clang's behavior on the following program ([Godbolt](https://godbolt.org/z/f4Psq38j7)).📝Arthur O’Dwyer
BazelCon 2026 Recap: Recordings and NotesAnother edition of BazelCon has come to a close. We gathered to discuss what matters most in the world of Bazel, learn, network and spend some quality time with like-minded folks. If you couldn’t make it to the event or want a quick refresher on the key takeaways, we’ve put together a brief summary of the highlights. TL;DR - Recordings playlist , photo album , user survey Acknowledgments The success of this year’s event is entirely due to our incredible community. A huge thank you to our sponsors , whose support made it possible to host an event of this scale free of charge. Thank you to our speakers and trainers for delivering insightful presentations packed with knowledge that sparked many conversations throughout the week. And to our attendees - both in-person and online - for your questions, hallway discussions, and engagement that truly shape the spirit of BazelCon each year. We gathered a record number of 455 people, exceeding our expectations and giving us much to consider for next events. BUILD Foundation Kicking off Day 1 during the Keynote, Helen Altshuler and Chuck Grindel announced the launch of the BUILD Foundation. Governed by the Linux Foundation with initial members ASML, Canva, Datadog, EngFlow, Figma, and Spotify, the Foundation gives the Bazel ecosystem the leadership and sustained investment needed to take on challenges no single organization can solve alone. Key priorities for the initiative include improving technical documentation, funding maintainers for bazel-contrib repositories, launching developer training and certification, and enhancing software supply chain security. By formalizing this shared investment, the community aims to keep build times fast and dependable as engineering teams and codebases continue to scale. To discover more about the launch, explore the initial member perspectives, and find out how your organization can get involved, read the rest of the Linux Foundation press release and watch the Keynote . Bazel Community Survey 2026 To understand our users and their experiences, as well as to better guide the roadmap, the BUILD Foundation launched a survey to gather your feedback. Take the 2026 Survey More Recaps and Coverage Want to see the event through the eyes of the attendees? Check out these write-ups from other members of the community: BazelCon 2026: My Notes and Observations - by Adin Ćebić BazelCon 2026 recap - by Julio Merino A Bazel Bard - a summary of the BazelCon 2026 Hallway Track - by Son Luong Ngoc Recordings [Training Day] Tuesday, October 13th Bazel Bootcamp Advanced Bazel: Rules Authoring, Performance Tuning and Remote Execution rules_{js|ts}: JavaScript & TypeScript with Bazel Writing Bazel Rules Build File Generation Using AXL How Fast Should/Can My Build Be? A Journey to Understand Build Optimization rules_py: Python Builds with Bazel [Day 1] Wednesday, October 14th Keynote: Bazel Community Update State of the Union No Token Budget: Why Agentic Software Factories Need Bazel to Maintain Entropy One Content-Addressed Store, Zero Full Clones: Backing Bazel’s Cache and Remote Execution with Lore Content-Defined Chunking for Bazel Static types in Starlark Horapha: Your Personal Warm Bazel actiond: The quest for a better sandbox Type-checking Starlark without waiting for Bazel Taming Configurations Explosion 💥 Persistent Test Runners Where Bazel Clusters Break at Scale: Field Notes from Plaid and the EngFlow Fleet Taking Humans Out of the Build Loop bviz: Seeing What Your Bazel Build Is Actually Doing One Graph to Rule Them All: Scaling Incremental Target Graph Calculations in Monorepos More expressive platforms with platforms_contrib Stop Delivering Your Whole Fleet How Canva Runs Millions of Jest Tests with Bazel RunfilesGroupInfo: Turning *_binary Runfiles into Optimal Container Layers [Day 2] Thursday, October 15th Lessons learned building a zero-sysroot fully hermetic LLVM toolchain for Bazel rules_rs: {Fast, Hermetic, Ergonomic} - Pick 3 The Sandbox Is a Filesystem: Content-Addressed Bazel Builds on macOS with FSKit Proving Equivalence in any2bazel Build System Migrations AI development: Challenges and early learnings for Bazel Discovering and eliminating 20% of redundant build actions by tracing file system operations Diffing Millions of Screenshots a Day, Hermetically Zig Package Manager Integration, Hermetically No bytes left untracked - Bazel Supply Chain Security Pretty Python Packaging One Build, Many Configurations: Comparing Configuration Features in Bazel and Buck2 Building Uber’s Automated Migration Machine on Bazel Generate build files for new rule sets with Gazelle v2 Distributed hermetic CUDA Clang compilation using Bazel What Changed? - A Better Watch Protocol for Bazel Extend Gazelle in Starlark, not Go A py_binary Should Be Enough: Fast, Simple Python Images with Bazel Flexibility Is a Trap: How We Sealed Our Bazel Platform at Adobe Scale Closing Remarks BoF notes Remote Execution C++ Android + Android slides Bazel + IDEs Bzlmod Supply-Chain Apple Unconference notes: SkyCache (Remote Analysis Caching) + SkyCache deck Config Explosion Mitigation Notes 1 & Notes 2 E2E/SystemsTesting (Tests against hermetic environments) The Psychology of Migration (Organizational struggles & solutions) Agent Mode (How to improve Bazel for Agentic usage) Resources GitHub repository: https://github.com/bazelbuild/bazel Releases: https://github.com/bazelbuild/bazel/releases Slack chat: https://slack.bazel.build Google group: bazel-discuss@googlegroups.com Special Interest Groups (SIG): Reach out the email(s) listed below if you’d like to be added to the SIG calendar invites. SIG Meeting frequency Point of contact Rules authors Every two weeks bazel-contrib@googlegroups.com Android app development Monthly ahumesky@google.com Bazel plugin for IntelliJ Monthly en@jetbrains.com Remote execution API working group Monthly chiwang@google.com Supply chain security / SBOM Weekly fwe@google.com Interested in learning about SIGs or starting a new one? Find more information on our website . Want to get your SIG listed? Please add it to the Community repository . Ideas, feedback, and submissions are welcome! Thank you for reading this edition! Let us know if you’d like to see any new information or changes in future community updates by reaching out to product@bazel.build. We look forward to hearing from you. Thanks, Google Bazel team📝Bazel Blog

Monday, November 9, 2026

Qt Champions 2026Dear Qt community! With only seven weeks left before 2026 gets branched into maintenance mode, we are pleased to open the nomination period for the Qt Champion 2026 award. It has been one of those years! We've launched Qt Bridges, held an inspiring Qt Contributor Summit in Oslo and released Qt 6.12 - our first fully CRA compliant release. Through all of it, our community kept answering questions, reviewing patches, sharing knowledge, and generally holding the Qt universe together while the rest of us were busy rearranging the furniture. Please help us recognize those outstanding contributors by nominating your favorite candidates: https://wiki.qt.io/Qt_Champions_2026 We look forward to reading your nominations! Cheers, Axel📝Qt Blog

Sunday, November 8, 2026

GSoC 2026 - Teach the Clang Static Analyzer to understand lifetime annotationsGoogle Summer of Code 2026 @ LLVM Compiler Infrastructure Commits on GitHub | Pullrequests Motivation Clang can warn about lifetime bugs. Behind -Wlifetime-safety [1] it reads the lifetime annotations a function carries and reports a warning when a pointer or a reference that outlives the object it refers to escapes the function,or when the dead object is accessed through it. The analysis runs on every translation unit of every build and examines one function at a time, so an unannotated call is treated optimistically as having no lifetime effects:the origin of the value is lost at the call and bugs that depend on it go unreported. This project extends the Clang Static Analyzer (later referred to as CSA) to cover those cases. It reads the same annotations and follows the value through the callsthe compiler cannot enter, and the three checkers that came out of it are in Clang today, reporting bugs the compiler does not. Patches These are the patches that closed the gap, taking the analyzer from missing this class of bugs to catching it. #205521 : implemented the UseAfterLifetimeEnd checker, which reports a value returned from a function while it still borrows from a local of that function. #205951 : implemented the LifetimeModeling checker and moved every state operation out of UseAfterLifetimeEnd into it. #207052 : implemented a BugReporterVisitor for UseAfterLifetimeEnd that adds the note showing where the value’s lifetime was bound to its source. #209278 : implemented DanglingPtrDeref , which reports a use of a pointer whose pointee has gone out of scope. #209862 : NFC, corrected the DanglingPtrDeref checker’s filename. #210801 : suppressed the report when a lifetimebound method is called during the destruction of an object. #211045 : added checkPostCall to DanglingPtrDeref so a dangling pointer passed as a call argument is reported. #211552 : matched dangling subobjects by their base region, so a pointer into a field, an array element or a base class subobject of a dead object is recognized. #211582 : NFC, rewrote the destructor frame walk with llvm::any_of . #211818 : added trackExpressionValue to DanglingPtrDeref so the report shows where the dangling value originated. #212158 : replaced the debug only getString() with getDescriptiveName() in the diagnostics and switched the path notes to trackStoredValue() . #212254 : NFC, added test cases to the lifetime test suite. #212883 : NFC, matched the parameter order of getEndPath and finalizeVisitor with VisitNode . #213092 : reverted a documentation change that broke the docs build. #213779 : discarded lifetime sources whose stack frame is not the frame being left, which removed most of the false positives found on LLVM. #215409 : implemented markAsReported , so DanglingPtrDeref reports only the first dereference of a given variable. #215651 : underlined only the parameter that the return value is actually bound to when a function has several parameters. #215905 : corrected the highlighted range so it matches the variable the note refers to. #216688 : documentation for UseAfterLifetimeEnd and DanglingPtrDeref . From an attribute to a report Nothing can be reported before the Clang Static Analyzer records where a value borrows from, so that recording came first. int * test_func ( int * p [[clang::lifetimebound]] ); Clang attaches [[clang::lifetimebound]] to the annotated ParmVarDecl , so the contract is in the AST before the analyzer starts. int * test_func ( int * p [[clang::lifetimebound]] ); int * variable_return () { int y = 5 ; int * p = test_func( & y); // checkPostCall records that the result borrows from 'y' // ... } In checkPostCall the call has been evaluated, so the return value has an SVal and the checker can pair it with the region of the argument it borrows from.That pair goes into the ProgramState , the object the analyzer carries from node to node, and a state belongs to one node. int * test_func ( int * p [[clang::lifetimebound]] ); int * variable_return () { int y = 5 ; int * p = test_func( & y); // checkPostCall records that the result borrows from 'y' return p; // checkEndFunction callback reports here: // warning: Returning value bound to 'y' that will go out of scope } The checkEndFunction callback asks the state what the returned value borrows from and whether those regions belong to the frame that is about to die. The two nodes below are consecutive in the ExplodedGraph and sit at the same program point. State 603 is the engine having evaluated the call. State 550 is onenode later, after LifetimeModeling ran, and it carries the borrow as Origin ... contains Loan y . -Wlifetime-safety is intra-procedural by default and path-insensitive: it analyzes one function at a time and merges the states at a join point (where branches meet), so a borrow taken on one branchis indistinguishable from one taken on the other. The analyzer performs an inter-procedural and path-sensitive analysis: it can enter a callee whose body isavailable (if the analyzer’s budget allows it) and explores each path separately, so what it records on one path never shows up on the other. One writer for the state With the borrow recorded, the next question was who is allowed to write it. LifetimeModeling owns everything that touches the program state and exposes nothing but queries. The reporting checkers( UseAfterLifetimeEnd and DanglingPtrDeref ) read it, decide whether what they see is a bug and build the report that explains the path to it. [[clang::lifetimebound]] end of a scope \ / v v +--------------------------------------------------+ | LifetimeModeling | | the only checker that writes state | | | | what borrows from what | what has died | +--------------------------------------------------+ | | | queries | queries v v +----------------------+ +--------------------------+ | UseAfterLifetimeEnd | | DanglingPtrDeref | | a returned value | | a pointer used after | | outlives its frame | | its object is gone | +----------------------+ +--------------------------+ Catching use after the scope ends The annotated case is now covered. The second kind of lifetime error needs no annotations at all: a pointer used after the object it points to has gone out ofscope. While the modelling was taking shape in June, Arseniy Zaostrovnykh and Tomasz Kaminski added CFGLifetimeEnds handling to the analyzer, which turns every end of a scopeinto a checkLifetimeEnd event and lets the CSA reason about lifetimes directly #201123 . I picked it up as soon as it landed and built DanglingPtrDeref on top ofit. LifetimeModeling listens to that event and adds the region to DeallocatedSourceSet . checkPreStmt(DeclStmt) clears a variable’s region from that setwhenever its declaration is executed, so a stale entry cannot make fresh storage look dead. DanglingPtrDeref subscribes to check::Location and asks on every load and store through a pointer whether the pointee is gone. void use_after_scope () { int * ptr = nullptr ; { int num = 5 ; ptr = & num; } * ptr = 6 ; // warning: Use of 'num' after its lifetime ended } num lives only inside the block, so by the last line its storage is gone while ptr still holds its address. checkLifetimeEnd fires at the closing braceand puts num into DeallocatedSourceSet . On the dereference checkLocation asks whether the pointee is still alive, finds the region in that set andreports. A pointer that is only passed on While evaluating the first version of the checker I found a case it did not cover: a dangling pointer handed to another function. check::Location does notfire there because the load at a call site is the load of the pointer variable itself and not an access through the pointer. DanglingPtrDeref now alsoimplements checkPostCall and inspects every argument, but only when the analyzer did not step into the callee’s body. If it did, checkLocation alreadycovers every dereference in there and reporting at the call site as well would produce the same bug twice. void escape ( int * ptr); void passing_dangling_ptr_to_opaque_func () { int * ptr = nullptr ; { int num = 5 ; ptr = & num; } escape(ptr); // warning: Use of 'num' after its lifetime ended } escape(ptr); | +-- check::Location fires once, for the load of 'ptr' | location it is given: the region of 'ptr' (alive) | 'num' is only the value that comes out of that load, never the location | so the event has nothing dead to look at | +-- checkPostCall sees the call after it was evaluated argument SVal: &num -> its lifetime has ended -> report Reporting at the call site is a deliberate choice. A dangling pointer cannot be used safely by anyone, so handing one to a function is already a bug even if the callee never dereferences it, and the caller should reset itto nullptr instead.The same holds for what a call can reach indirectly, an output parameter of type int ** or a std::pair : the dangling pointer should be cleared rather than passed on. Some of these reports can be argued tobe false positives. Flagging them anyway is a deliberate choice, because once a dangling pointer is handed on there is nothing safe left to do with it. A pointer into part of a dead object So far we only talked about primitive types, but there are aggregates and, in C++, inheritance as well. A pointer can point at a field, an array element or a base class subobject, while what the modeling checker recorded asdeallocated was the region of the whole object. struct MyBuffer { char buffer[ 8 ]; }; char member_subregion_dangling_deref () { const char * p = nullptr ; { MyBuffer tmp_buffer = {}; p = tmp_buffer.buffer; } return * p; // warning: Use of 'tmp_buffer.buffer[0]' after its lifetime ended } p points at the first element of the array inside tmp_buffer , not at tmp_buffer itself, while checkLifetimeEnd records the region of the whole variable that died. isDeallocated , the query the reporting checkersuse to ask whether a region is dead, now looks up the base region of the region it is asked about, which walks the element up through the field to tmp_buffer and finds it: p = tmp_buffer.buffer; p points at ElementRegion tmp_buffer.buffer[0] ---+ | | v | FieldRegion tmp_buffer.buffer | getBaseRegion() | | v | VarRegion tmp_buffer Before this change the checker only recognized pointers to whole variables, so a pointer into a field, an array element or a base class subobject went unreported. Also this change costs nothing in precision,because a subobject cannot outlive the object that contains it: if tmp_buffer is gone, every region inside it is gone with it. Testing the lifetime checkers Running the checkers on a real project does two things. It shows they hold up outside the cases I wrote tests for and it measures the property that decides whether a checker can stop being experimental: how rarely it reportssomething that is not a bug (false positive). A core checker is expected to have very few false positives and that number cannot come from a hand written suite. The LLVM monorepo is large, actively maintained and heavily reviewed, so itexercises shapes my tests never reach. Every report there has to be read on its own and the ones I went through fell into three classes, each a place where the model was too coarse. Closing them made both checkers moreprecise and moved them closer to the bar a core checker has to meet. A lifetimebound call during destruction A destructor is the one place where handing out a borrow of the dying object is normal: the caller is thedestructor itself and the borrow does not escape it. The fix walks the frames on the current stack and suppresses the report if any of them is a destructor, which is coarse on purpose: it asks whether a destructor is onthe stack, not whether the borrow belongs to the object being destroyed, so a function called from a destructor that returns a borrow of its own local goes unreported. struct S { call stack int x; int *get() [[clang::lifetimebound]] +----------------------+ { return &x; } | outer() | ~S() { get(); } +----------------------+ }; | passThrough() | the S dies here +----------------------+ S passThrough(S param) { return param; } | S::~S() | +----------------------+ void outer() { | S::get() | returns &x, a borrow auto f = passThrough(S()); -----------------> +----------------------+ of *this } a destructor frame is on the stack, so the borrow get() hands out is meant to die with the object -> no report A source owned by another frame This was the largest of the three classes. A returned value can only dangle if the frame that owns its lifetime source is the frame being left. When the source belongs to a caller thatstays alive, or to a frame the analyzer never entered, the storage outlives the value and there is nothing to report. const char *first(const char *buf [[clang::lifetimebound]]); void use(const char *p); call stack const char *helper(const char *buf) { +----------------------+ return first(buf); | caller() | owns 'buf' } +----------------------+ | helper() | void caller() { +----------------------+ char buf[64] = {}; returns a value bound use(helper(buf)); ----------------------------> to 'buf' } 'buf' belongs to caller(), which stays alive when helper() returns -> no report The same variable reported again and again checkLocation fires on every access through a pointer, so a dead variable used five times produced five warnings that all describe the same bug. markAsReported keeps the first and drops the rest. before after *p = 1; warning *p = 1; warning *p = 2; warning *p = 2; - use(p); warning use(p); - Results Two of the cases below come from how -Wlifetime-safety works: it analyzes one function at a time and treats a call asopaque, so the only thing it learns about a callee is what the callee’s declaration says. The third is a gap inside the analyzer itself: before the lifetime checkersit had no model of [[clang::lifetimebound]] and nothing that reported a stack object used after its scope ended. Every analyzer warning quoted in this section comes from the same command, so any of the examples can be reproduced by pasting it into a file and running: $ clang -cc1 -analyze \ -analyzer-checker=core,alpha.cplusplus.UseAfterLifetimeEnd,alpha.cplusplus.DanglingPtrDeref \ -analyzer-config cfg-lifetime=true -analyzer-output=text example.cpp Following a borrow through an unannotated call The compiler handles the direct case. With the local passed straight to the annotated parameter, -Wlifetime-safety says so: const char * findOption ( const char * config [[clang::lifetimebound]] , const char * key); const char * readTimeoutDirect () { char config[ 64 ] = "timeout=30" ; return findOption(config, "timeout" ); // warning: stack memory associated with local variable } // 'config' is returned [-Wlifetime-safety-return-stack-addr] Put one unannotated function between the local and the annotated call and the warning disappears, because the analysis cannot look inside optionValue and optionValue carries no contract of its own. A chain only has to lose one link for the diagnostic to go with it. // Defined in another translation unit. const char * findOption ( const char * config [[clang::lifetimebound]] , const char * key); const char * optionValue ( const char * config, const char * key) { return findOption(config, key); } const char * readTimeout () { char config[ 64 ] = "timeout=30" ; return optionValue(config, "timeout" ); // warning: Returning value bound to 'config[0]' } // that will go out of scope This is where inlining matters. When the body of a callee is available, the analyzer does not treat the call as a black box: it enters the body and keeps exploring the same path inside it, carrying the caller’s state in,so everything that happens in the callee is visible to the checkers on the way out. When the body is not available the call is evaluated conservatively and the analyzer knows only what the declaration says. Here optionValue is inlined, the annotated call inside it is reached and the contract on findOption stands in for the body that is not there. The report names config[0] because that is the region the array decays to atthe call. Reporting a use after the scope ends void use_after_scope () { int * ptr = nullptr ; { int num = 5 ; ptr = & num; } * ptr = 6 ; // warning: Use of 'num' after its lifetime ended } None of the analyzer’s existing checkers for this kind of error cover it, core.StackAddressEscape and cplusplus.InnerPointer included: with -analyzer-checker=core,cplusplus the analyzer produces no diagnostic at all. DanglingPtrDeref reports it, and the path in the report runs from theinitialization of num through the assignment to ptr to the closing brace where the storage dies. A borrow made in one function and used in another void submit ( const int * sample); const int * identity ( const int * value) { return value; } void collectSample ( int reading) { const int * sample = nullptr ; { int corrected = reading + 1 ; sample = identity( & corrected); } submit(sample); // warning: Use of 'corrected' after its lifetime ended } Neither function is annotated and sample is never dereferenced in collectSample . -Wlifetime-safety sees identity as an opaque call and has no origin tofollow, so it stays silent. The CSA inlines identity , follows the pointer back to corrected and reports the call that passes it on. Together the two checkers move lifetime checking past the point where the compiler has to stop. -Wlifetime-safety remains the right tool for the common case,because it is cheap enough to run on every build. What it cannot do is follow a value through a call it cannot see into, and a chain only has to lose one linkfor the warning to disappear. Every report the checkers produce carries the execution path from the borrow to the death of the storage, including the branchthat had to be taken, so the reader can judge it without rerunning the analysis. Both checkers ship in Clang today, both have been run over the LLVM monorepo,and LifetimeModeling is a base that the next lifetime checker can consume instead of rebuilding. Future work Support for LazyCompoundVal . std::string_view and std::span are among the types the annotations are written on. They are class types returned by value, which the analyzer represents as a LazyCompoundVal and none of the maps in the modeling checker cover that today, so the lifetime origin is lost: struct View { int * p; }; View makeView ( int & x [[clang::lifetimebound]] ); void caller_view () { int v = 42 ; View w = makeView(v); // FIXME: Currently none of the maps cover LazyCompoundVal. } Covering it brings the checkers to the code the annotations were introduced for. Interoperability with the MallocChecker . Both checkers reason about stack regions, so a lifetime source that lives on the heap is out of their reach. The plan is to extend them to heap sources through theinterface the MallocChecker already exposes for this in AllocationState.h , which is how cplusplus.InnerPointer works with it today, instead of modeling the heap in the lifetime checkers. The [[clang::lifetime_capture_by(X)]] annotation. The original proposal covered both annotations. During the summer I have prioritized [[clang::lifetimebound]] , because it is the annotation people currently use. Inthe LLVM monorepo alone libc++ applies _LIBCPP_LIFETIMEBOUND around 80 times across 22 headers, while lifetime_capture_by does not appear in the library at all, and outside LLVM the same asymmetry holds: Abseil ships ABSL_ATTRIBUTE_LIFETIME_BOUND [2] and uses it throughout its string and container implementations, while lifetime_capture_by is a much newer addition [3]. Supporting the capture annotation is the work I intend to doafter the summer. Special thanks I would like to say thank you to my mentors, in the order they appear on the LLVM GSoC page: Gábor Horváth, Balázs Benics and Dániel Domján, for mentoring this project, for the reviews and design discussions that shapedboth checkers and for answering my questions throughout the summer. The time they put into the project and into teaching me went well beyond what I expected. My questions were answered quickly and my patches were reviewedeven at weekends. This was the greatest summer of my life so far without a doubt. I am grateful for the opportunity and for my mentors for all their help and guidance. This project gave me a huge motivation to stay activein the LLVM community and continue working on the lifetime checkers and the Clang Static Analyzer. I would also like to say thank you to Donát Nagy for his code reviews on some of these patches and to Arseniy Zaostrovnykh and Tomasz Kaminski for the CFGLifetimeEnds support in the CFG. References [1] U. Saxena, D. Hrybenko, Y. Mandelbaum, J. Voung and K. Yasuda, “[RFC] Intra-procedural lifetime analysis in Clang”, LLVM Discussion Forums, May 2025. https://discourse.llvm.org/t/rfc-intra-procedural-lifetime-analysis-in-clang/86291 [2] Abseil, definition of ABSL_ATTRIBUTE_LIFETIME_BOUND in absl/base/attributes.h . https://github.com/abseil/abseil-cpp/blob/master/absl/base/attributes.h [3] G. Horvath and U. Saxena, “[RFC] Introduce [[clang::lifetime_capture_by(X)]] ”, LLVM Discussion Forums, November 2024. https://discourse.llvm.org/t/rfc-introduce-clang-lifetime-capture-by-x/81371📝The LLVM Project Blog

Saturday, November 7, 2026

四色滑道：从博物馆的益智玩具到一道OI题Palo Alto Junior Museum and Zoo的室内科学展区(Indoor science exhibits)墙上挂着一块大号的Montessori Slide Puzzle：下方是四条竖直滑槽，每条槽里叠着四颗彩色圆柱珠子；上方的卡片给出目标图案，玩家要通过滑动珠子把下面摆成卡片上的样子。 本文把它抽象成一道OI题，并给出题解和标准程序。 我只拍了两张照片，问了一句「能否根据这个益智玩具设计一道OI算法题？涉及编号时，从 0 开始。提供题解和C++标准程序」。 下面的题面、题解、标程、对拍程序，连同数据范围的取舍，都是Opus 5.5根据照片生成的，这篇文章也是它写的。 它自己从照片里读出了槽、木舌和滑道的结构，写暴力程序对拍，实测连通块大小来确定数据范围，还发现了「底层冻结」这个不变量。我大受震撼。 玩具 上图是摆好的状态，与卡片一致。 相邻两条槽之间是固定的木舌，木舌顶端可以搁一颗珠子；所有槽的顶上由一条只有一颗珠子高的横向滑道连通。 下图中，三颗珠子分别从槽 1、2、3 被推上滑道，停在三根木舌顶上。 木舌顶上的珠子会挡住滑道：此时槽之间无法互相传递珠子，只能把它们放回槽中。 这个「挡路」的性质让题目有了意思。 题目 下文编号均从 0 开始。 一块益智板上有 n 条竖槽，编号 0..n-1 ，每条槽最多叠放 h 颗珠子（从槽底往上紧密叠放）。 相邻的槽 j 与 j+1 之间有一个 台阶 j ，最多放一颗珠子。 所有槽和台阶的上方由一条横向滑道相连，从左到右依次为：槽 0、台阶 0、槽 1、台阶 1、……、台阶 n-2 、槽 n-1 。 每次操作可以拿起 某条槽最上面的珠子 或 某个台阶上的珠子 ，沿滑道左右移动，放到另一处 空台阶 或 未满的槽 中（落在槽的最上方）。 移动途中不能越过有珠子的台阶，但可以越过任何槽。 珠子有 R 、 G 、 B 、 Y 四种颜色，同色珠子没有区别。给定初始状态和目标状态，求最少操作次数；若无法达到，输出 -1 。 输入格式 ：第一行两个整数 n h 。接下来依次给出初始状态和目标状态，每个状态占 h+1 行： 第一行是长度为 n-1 的字符串，第 j 个字符表示台阶 j ； 接下来 h 行，每行长度为 n ， 从上到下 描述各槽，第 i 列对应槽 i 。 . 表示空位。保证同一列中 . 只出现在珠子上方。 数据范围 ： 2 ， 1 ，两个状态中的珠子数都恰好为 n*h 。时间限制 2 s，内存限制 256 MiB。 样例 0 就是上面第二张照片的局面，目标是卡片上的图案： 4 4 RGG R... BYRY YGBR YBGB ... RRGG BYRY YGBR YBGB 答案是 3：依次把台阶 0、1、2 上的珠子放入槽 1、2、3。 样例 1，两条槽都是满的，唯一能做的事是把某条槽顶的珠子放到台阶 0 上；此后台阶被占，两条槽不再连通，答案是 -1 ： 2 2 . RG BY . GR BY 样例 2，从一个打乱的局面摆回卡片，答案是 16： 4 4 ... GRGR YBYR YGBR YBGB ... RRGG BYRY YGBR YBGB 题解 建模 一个状态由每条槽自底向上的颜色序列和每个台阶的内容组成。 操作是可逆的：把珠子从 a 移到 b 之后， a 一定能再接收这颗珠子（槽刚少了一颗，或台阶刚被腾空），而 a 、 b 之间的台阶和移动前一样全空。 所以状态图是无向图，答案就是最短路，用 BFS 求解。 把滑道位置记为 0..2n-2 ：槽 i 在 2i ，台阶 j 在 2j+1 。 枚举后继时，对每个可取珠子的位置 a 向左、向右扫描：遇到空台阶就生成一个后继并继续，遇到有珠子的台阶就停止；遇到未满的槽就生成一个后继，无论满不满都继续。每个状态有 O(n^2) 个后继。 状态压缩 每条槽用 11 位：低 3 位存珠子个数，之后每颗珠子 2 位（ h 时至多 8 位）；每个台阶 3 位（0 表示空，1~4 表示颜色）。 n 时总共不超过 4*11 + 3*3 = 53 位，可以放进一个 unsigned long long 。 底层冻结 考察槽 i 自底向上第 k 颗珠子（从 0 开始）。它要移动，必须先成为槽顶，此时槽 i 恰有 k+1 颗珠子。 槽 i 之外有 (n-1)*h 个槽位和 n-1 个台阶，放着其余 n*h-k-1 颗珠子，空位数为 (n-1)(h+1) - (n*h-k-1) = n - h + k 这颗珠子要移走，槽外至少要有一个空位，即 k >= h-n+1 。因此： 每条槽最底下的 max(0, h-n+1) 层珠子永远不会移动。 若两个状态的冻结层不同，可以直接输出 -1 。 n = h = 4 时最底一行冻结， 4×4 就退化成了 4×3 ；实测两者的连通块大小都是 1587600 个状态。 不过这只是必要条件： 4×3 没有冻结层，随机生成的两个颜色组成相同的状态仍然大多不连通，所以还是要搜索。 双向 BFS 单向 BFS 已经足够：最大连通块约 160 万个状态。标程用双向 BFS，每次扩展当前队列较小的一侧，有解时几乎瞬间出答案。 正确性：设两侧已分别搜完距离 与 的全部状态，且没有公共状态。 若最短距离 D ，最短路上距起点 min(a, D) 的那个点必然同时出现在两侧，矛盾，所以 D >= a+b+1 。 扩展起点一侧的第 a+1 层时，一旦新状态 y 已在另一侧出现，就得到一条长 a+1+dist2(y) 的路径，它不可能短于 D ，所以恰好等于 D 。 因此 第一次相遇即可返回 。若某一侧队列搜空仍未相遇，说明它所在的连通块不含另一端，输出 -1 。 最坏情况是无解：两侧都要把各自的连通块搜完。标程用开放寻址哈希表，颜色均衡且无解的 4×3 、 4×4 数据实测最慢约 0.9 s、86 MB。 为什么珠子数恰好是 n*h 只要少放一颗珠子，空位就会变多，连通块急剧膨胀： n×h 珠子数 连通块大小 4×3 12 1587600 4×3 11 11550000 4×4 16 1587600 4×4 15 > 20000000 关于实物 由底层冻结，若实物每槽恰好只能放 4 颗，底行就永远无法改变：要么所有卡片的底行都相同，要么槽其实还能多放一颗。 照片中第一列装满 4 颗后上方仍有空隙，更像是后者（ h = 5 ，仍是 16 颗珠子）。 我按 h = 5 试过：空位从 3 个增加到 7 个，状态数约 10 10 ，随机两张卡片之间的最少步数通常在 21~29 之间。 双向 BFS 和以「必须移动的珠子数」为估价的 A* 都要数十秒、数 GB 内存。 所以题目把珠子数固定为 n*h 。若想贴合实物规模，可以改成构造题：只要求输出一个步数不超过某个上界的方案，用 Special Judge 判定。 标准程序 用暴力程序（字符串存状态、单向 BFS）对拍了 600 组随机数据，结果一致。 // 四色滑道 —— 标准程序：双向 BFS #include using namespace std ; typedef unsigned long long u64; int n, h; // 状态：每个槽 11 位（3 位个数 + 4×2 位颜色，自底向上），每个台阶 3 位（0 空，1..4 颜色） struct State { int cnt[ 4 ], col[ 4 ][ 4 ], shelf[ 3 ]; }; u64 encode ( const State & s ) { u64 c = 0 ; for ( int i = 0 ; i n; i ++ ) { u64 v = s.cnt[i]; for ( int k = 0 ; k s.cnt[i]; k ++ ) v |= (u64)s.col[i][k] ( 3 + 2 * k); c = c 11 | v; } for ( int j = 0 ; j + 1 n; j ++ ) c = c 3 | s.shelf[j]; return c; } State decode ( u64 c ) { State s; for ( int j = n - 2 ; j >= 0 ; j -- ) s.shelf[j] = c & 7 , c >>= 3 ; for ( int i = n - 1 ; i >= 0 ; i -- ) { u64 v = c & 2047 ; c >>= 11 ; s.cnt[i] = v & 7 ; for ( int k = 0 ; k s.cnt[i]; k ++ ) s.col[i][k] = v >> ( 3 + 2 * k) & 3 ; } return s; } // 滑道上的位置：槽 i 在 2i，台阶 j 在 2j+1 template class F > void forEachNext ( u64 code , F f ) { State s = decode (code); int m = 2 * n - 1 ; for ( int a = 0 ; a m; a ++ ) { int piece; // 取出的珠子颜色（台阶编码，即颜色+1） if (a % 2 == 0 ) { if ( ! s.cnt[a / 2 ]) continue ; piece = s.col[a / 2 ][ -- s.cnt[a / 2 ]] + 1 ; } else { if ( ! s.shelf[a / 2 ]) continue ; piece = s.shelf[a / 2 ], s.shelf[a / 2 ] = 0 ; } for ( int dir = - 1 ; dir 1 ; dir += 2 ) for ( int b = a + dir; b >= 0 && b m; b += dir) { if (b % 2 == 1 ) { // 台阶：空则可停，非空则挡路 if (s.shelf[b / 2 ]) break ; s.shelf[b / 2 ] = piece; f ( encode (s)); s.shelf[b / 2 ] = 0 ; } else if (s.cnt[b / 2 ] h) { // 槽：未满则可落入，满了也能越过 int i = b / 2 ; s.col[i][s.cnt[i] ++ ] = piece - 1 ; f ( encode (s)); s.cnt[i] -- ; } } if (a % 2 == 0 ) s.cnt[a / 2 ] ++ ; else s.shelf[a / 2 ] = piece; } } int colorId ( char ch ) { return string ( "RGBY" ). find (ch); } u64 readState () { State s; string line; cin >> line; for ( int j = 0 ; j + 1 n; j ++ ) s.shelf[j] = line[j] == '.' ? 0 : colorId (line[j]) + 1 ; vector string > g (h); for ( auto & r : g) cin >> r; for ( int i = 0 ; i n; i ++ ) { s.cnt[i] = 0 ; for ( int r = h - 1 ; r >= 0 && g[r][i] != '.' ; r -- ) s.col[i][s.cnt[i] ++ ] = colorId (g[r][i]); } return encode (s); } // 开放寻址哈希表：键为状态编码（编码不为 ~0），值为步数 struct HashMap { static constexpr u64 EMPTY = ~ 0 ULL ; vector u64 > key; vector unsigned char > val; size_t mask, used = 0 ; HashMap () : key ( 1 16 , EMPTY), val ( 1 16 ), mask (( 1 16 ) - 1 ) {} static size_t hsh ( u64 x ) { x ^= x >> 31 ; x *= 0x 9E3779B97F4A7C15 ULL ; return x ^ (x >> 29 ); } size_t slot ( u64 k ) const { size_t p = hsh (k) & mask; while (key[p] != EMPTY && key[p] != k) p = (p + 1 ) & mask; return p; } int get ( u64 k ) const { size_t p = slot (k); return key[p] == k ? val[p] : - 1 ; } void put ( u64 k , int v ) { if ((used + 1 ) * 2 > key. size ()) grow (); size_t p = slot (k); if (key[p] != k) key[p] = k, used ++ ; val[p] = v; } void grow () { vector u64 > ok; vector ov; ok. swap (key), ov. swap (val); key. assign (ok. size () * 2 , EMPTY), val. assign (ok. size () * 2 , 0 ); mask = key. size () - 1 , used = 0 ; for ( size_t i = 0 ; i ok. size (); i ++ ) if (ok[i] != EMPTY) put (ok[i], ov[i]); } }; int main () { cin >> n >> h; u64 st = readState (), ed = readState (); if (st == ed) { puts ( "0" ); return 0 ; } HashMap dist[ 2 ]; vector u64 > q[ 2 ]; dist[ 0 ]. put (st, 0 ), dist[ 1 ]. put (ed, 0 ); q[ 0 ] = {st}, q[ 1 ] = {ed}; while ( ! q[ 0 ]. empty () && ! q[ 1 ]. empty ()) { int t = q[ 0 ]. size () q[ 1 ]. size () ? 0 : 1 ; // 扩展较小的一侧 vector u64 > nq; int ans = - 1 ; for ( u64 x : q[t]) { int d = dist[t]. get (x); forEachNext (x, [ & ]( u64 y ) { if (ans >= 0 || dist[t]. get (y) >= 0 ) return ; int e = dist[ ! t]. get (y); if (e >= 0 ) { ans = d + 1 + e; return ; } // 第一次相遇即为最优 dist[t]. put (y, d + 1 ); nq. push_back (y); }); if (ans >= 0 ) { printf ( " %d\n " , ans); return 0 ; } } q[t]. swap (nq); } puts ( "-1" ); // 某一侧的连通块已搜完仍未相遇 }📝MaskRay