The result is Word Map. Give it a play.

At a high level it’s a daily word game similar to Wordle. You start off by guessing randomly and trying to find patterns to what the target word should be. When you get close to the goal the titular word map pops up. This map addresses the biggest flaw of Semantle: The protracted grind to get to the end. With the help of the map, Word Map is closer in difficulty to Wordle. You won’t guess right in six tries obviously, but here I solve the puzzle on most days, where in Semantle I don’t.

Development – Trying out Vibe Coding

This was my first non-trivial project that’s mostly vibe-coded. Probably 98% of the code is written by Claude Code. It was overall very pleasant. I especially like how easy it is to polish things. E.g. while doing the final edits on this blog post I thought “man the text should really increase and decrease in size as you zoom in and out, but it also shouldn’t be too big when you keep on zooming out” so I just asked Claude to do it and it was done in seconds. I could have also done it myself in minutes, but there’s so much less friction when you can just tell an AI to do things. You end up doing more iterations.

The biggest win is that I don’t know CSS and don’t know React and don’t know Typescript and don’t know what to use to draw a 3D map in a browser, but I am still able to ship a web app using those technologies. And I learned a bit about React and Typescript while I was at it, which are things I had been meaning to do for a while. (I’ll never learn CSS though. I’ve tried often enough and have concluded that I’ll just leave that one to the AIs)

It is still flawed and I like to think my programming skills are still relevant, at least for a few more months as this thing gets better. I intervened in a few places:

• Claude wanted to use cosine similarity as the distance metric (meaning normalize then do dot product). This is the most obvious thing to do but the size of the vectors contains meaning, so you really want some distance metric that takes that into account. I previously had good experiences with the Tanimoto coefficient so I used that:
• It stumbled over the map selection logic a few times. First it wrote a raycast, which makes sense. You can do two ways of selecting with raycasts, “cast with a radius and select the first hit point” or “select the point closest to the ray”, both of which have annoying edge cases. So I asked it to implement “first snap to the ground then select the nearest,” which is better but also has a few edge cases. So I started writing a very detailed description of how the approaches should be combined until I realized that this is silly and it would be faster for me to make the last little changes myself. Another problem was that this evolved over several sessions so I’d point out a selection bug to Claude and it would have forgotten why the code was the way it was and would say “oh this is complicated let me just delete all this and make it a simple raycast”. Maybe it just needed better comments, a thing that Claude does not yet do on its own. But overall this actually went fairly well and I still got this done faster and to a higher quality than if I had written it all myself.
• It couldn’t figure out a bug where the input field kept on losing keyboard focus. Turns out it was disabling the input field while the guess is being submitted. This makes sense in case the server is laggy, but also kills keyboard focus. I had to step in and debug this one because Claude couldn’t figure it out after I asked it three or four times.

But those are details, and Claude figured out many more tricky details in this than I did. The mistakes it makes now still follow clear patterns but the error-area is much smaller than it was a year ago. A year ago it would get itself confused halfway through a long piece of code. Now it gets itself confused when there are complex interactions of things.

This project is big enough where you still have to come up with a plan and make Claude do the work step by step. It was able to create a website that looked and worked like Semantle in one go (with no map). But then I still needed backend functionality to batch-generate puzzles and to deploy this to a server and to enable caching and to test performance (I still expect the server to go down if this becomes popular, but it’s fast enough that I’m not worried about hundred of users). It helped with all of this but you have to ask it. Also I had to ask it to clean up messes that it made by copy+pasting the same code five times. I noticed this because I asked it to fix a bug (the “I give up” button would still show even though you had already solved a puzzle), but I was still able to trigger the bug by doing something slightly different. Then I finally looked at the code and noticed that there were five places doing the same thing, three of which still had the bug. It can clean that up much quicker than I can, but you have to ask it to do so. I have seen people post prompts online that tell Claude to clean up duplication on its own, and I’ll have to figure out how to set that up.

This was not a quick project even though I only wrote like 2% of the code. It took three months before it was good. Since I started with an existing game, this was mostly an exercise in design and taste.

• I had a sense early on that I wanted to somehow visualize which directions you need to go. I thought of drawing arrows next to guesses but then you immediately want the landscape in which the arrows make sense.
• I wanted a rugged mountain landscape made out of words where you can see when nearby words climb up walls or lead down into valleys. The target word would be the peak of the mountain. But UMAP just wouldn’t give me layouts that made sense, and I had a hard time trying to nudge it to arrange everything around one central point. I would have had to design every single mountain by hand. (or come up with a way to get an AI to design every single mountain by hand)
• In the end I had to settle for a 1D UMAP projection and arrange all the words in a circle, with the distance to the center given by the similarity metric. It means you lose most of the semantic meaning of the words, but it’s much easier to understand and play. You still get some neat effects out of it where as you explore around the mountain you discover new aspects of the target word.

But once again overall this was a very pleasant experience. I can definitely tell that I’m running into some limits of vibe-coding already, but not in a hard way. There is always a workaround where you break down the problem a bit more. I think if I didn’t have Claude code, I would have never gotten this project done. I often just have an hour in the evening or thirty minutes in the morning and there is no way that I’d attempt something as intimidating as “figure out how to draw a map of word-embeddings” in that little time. But Claude just goes for it and gets it surprisingly right on the first try, and then you can always iterate on the details in the following days.

Mission Accomplished?

Did I actually accomplish my goal of making a game about hill climbing and stepping stones? Not fully. But there are a few things you can learn from playing this game:

• Hill climbing works really well in high-dimensional spaces.
• But hill climbing is also really difficult in high-dimensional spaces. At least when they’re visualized in low dimensions. It’s really hard to figure out the gradient that would allow you to take the next step, and to come up with a word from that.
• Stepping stones help enormously. I really like how exploring the map worked out. At some point you get a bunch of words that have an aspect of the target word that you haven’t incorporated at all, and that gets the mental gears turning.
• Near the end of the game it’s still hard to find stepping stones, mostly because I projected the high-dimensional word vector down to 1D. The “Smart Hint” feature is a bit of a clumsy way out of that, because it tells you the missing parts of the high-dimensional vector. It usually makes it pretty easy to come up with the target word. I wish I had come up with a less-big-hammer to solve that. (my best idea for that is to somehow use higher-dimensional UMAP and to draw the other dimensions as other colors or other symbols or something)

I still think this is a good game for practicing the approach for solving hard problems. To work as a game it had to be difficult in some aspects, but not too difficult, and easy in other aspects, but not too easy. I wanted a game where a human would have to use Novelty Search (the algorithm by Kenneth Stanley, who wrote the “Why Greatness Cannot Be Planned” book I referred to at the beginning), and I think I got that. And maybe it can serve as a stepping stone for someone else to make an interesting game that further explores gameplay that requires this kind of thinking.

It started when coworker had a bug where cudnn attention would crash randomly. We looked at his unreleased changes and concluded that they couldn’t possibly cause this, so we suspected that we had a lingering bug that was exposed by making harmless changes to related code.

Step 1, a few hours: My coworker tried to figure this out just by running the code repeatedly, trying out various theories. The bug was hard to reproduce so this took hours without much progress.

Step 2, 1 hour: I thought this is a good reason to try out compute sanitizer. It would be easiest to just run it on our existing tests to see if it finds any issues without my coworker’s changes. But the tests run on another box because they require certain GPUs, which means you have to run the tests through some layers. Unfortunately compute sanitizer really wants to be in charge of the program, so we have to convince those layers to let compute sanitizer run the whole thing. It keeps on failing and we can’t figure out why, until eventually I suspect that the issue is that the tests run in a sandbox, and the sandbox is strict enough that it breaks compute sanitizer somehow. This turned out to be true and we probably wasted an hour together.

Step 3, 10 minutes: Run the tests outside of the testing framework. This is surprisingly easy, taking just five minutes. Compute sanitizer immediately finds a problem. Well, almost immediately. You have to know to turn off the pytorch caching allocator because it hides memory issues. If I hadn’t known that, I could have wasted hours more.

Step 4, 10 minutes: Investigate a theory that we had: We were padding one tensor, but not a related tensor that really feels like it should be padded, too. I try to use torch.nn.functional.pad but it doesn’t work for padding the batch-dimension. So we just use torch.expand and torch.cat together. This takes like ten minutes and the bug is still there. Then I notice another tensor that should also be padded, which takes seconds to try out now and finally our cudnn invocation runs cleanly through compute sanitizer. But a nearby test for flash-attention is failing in compute sanitizer.

Step 5, 20 minutes: The padding fix didn’t fix the original issue, so my coworker decides to look more into it on his own and I look more into why flash-attention is having issues. First check if we’re doing something obvious wrong. This takes 10 minutes and I find nothing. Then check the flash-attention code. Compute sanitizer gives me a line number and it fails on an interesting line related to running in deterministic mode. That’s not used often, so maybe that’s why the test is buggy. I tried to understand the index math in that line but that led nowhere, so instead I just grepped for where that variable even comes from, and there is a glaringly obvious use-after-free bug:

The dk_semaphore and dv_sempahore will go away at the end of the scope, but the data_ptrs will still be used and will point into memory that’s no longer valid.

Fixing this would take seconds (just default-construct the tensors outside the “if”) but we’re just using flash-attention from pip, so I would have to build a new wheel to confirm the fix.

Step 6, 2 hours: I decide to build this on my home computer because experience shows that it’s easier to get random source code to build on personal computers where I can freely install anything from apt-get or download random things from the Internet. I download the flash attention source but don’t actually know how to build it. “make” doesn’t do anything even though there is a Makefile. The readme says to use “python setupy.py install” which immediately prints a message telling me to not run this command and to use some other thing instead which I hadn’t heard of before. But then it does the work anyway despite that message, so I stick with it. It fails with “unsupported architecture compute_120”. I grep for where that comes from, somehow this thinks my PC supports newer things than it actually does. I try disabling it in setup.py, but pytorch does the same thing and I can’t modify that. So instead I try to figure out why it thinks compute_120 is supported when it actually isn’t. Oops, turns out I’m running ancient CUDA 12.0. I decide to upgrade to version 12.9 instead (I avoid 13.0 because that might have unknown compatibility issues). Now the build works, but it’s super slow. After 20 minutes I kill it and rerun it with more parallelism. This OOMs. So I try again with the original setting, which now OOMs as well. So instead I run with even lower parallelism, which makes the build even slower. I decide to call it a night. Unfortunately I can’t run the build over night because the PC is in our bedroom and the build makes the fans spin loudly.

Step 7, 45 minutes: Everything is broken. For some reason the build doesn’t work the next morning. It says no Nvidia runtime detected. Nvidia-smi is also broken. Turns out I have conflicting packages after upgrading to CUDA 12.9 and for some reason that’s only a problem after a reboot. I spend like 30 minutes getting the packages to be consistent. First I try upgrading to the latest drivers, which makes my display run in a low resolution for some reason. Then I try downgrading back to the original driver, except I stay on CUDA 12.9. Then I finally rerun the build with less parallelism, which takes about an hour while I do other things.

Step 8, 30 minutes: I got things working. I write a small reproducer and… I can’t reproduce the bug. I realize I’m an idiot because the GPU in my PC only has compute capability 8.9 which means it’ll use flash-attention 2, but I already knew that the bug only happens with flash-attention 3. I had found this out in the earlier step.

Step 9, 1 hour: Overall that wasn’t so bad. I only had to install three python dependencies: torch, packaging, and wheel. So I try again to get this to compile on a work computer. But as expected everything goes wrong. It wants to use the wrong version of CUDA and the wrong version of GCC and the wrong version of Python for some reason, and then when I finally get it to start compiling, the compiler segfaults. I try switching compiler versions but it still happens. I decide that I should at least have a look at the crash to see what’s causing it, but the crash doesn’t happen when I run the compiler in gdb. So I try compiling with less parallelism and then the compiler doesn’t segfault and everything finally builds.

Step 10, 10 minutes plus waiting: I try to reproduce the bug and get a weird error when importing flash-attention. Claude tells me it’s because I compiled this with an incompatible compiler version. Right. I did switch compilers to get to the bottom of the compiler crash. I switch back and compile again.

Step 11, 10 minutes plus waiting: Finally I write a reproducer. I realize I’m an idiot again because this whole time I have been compiling flash-attention 2. The code for flash-attention 3 is actually in the “hopper” subdir. Luckily I can get that building easily now.

Step 12, 1 hour: I have a reproducer running but it doesn’t reproduce the bug. I try to make it exactly the same but find that some flags were deleted in a change that’s just described as “Big refactor and updates“. Still those flags shouldn’t matter. I realize I just pulled latest, which might have random changes in it. So let me first confirm I can reproduce the bug in the last release tag, v2.8.3. But it still doesn’t happen. So I add some print statements and verify that I’m definitely calling the right function. So why doesn’t the bug happen? I replace the use-after-free with a nullptr access, but still no crash. This is very weird. I verify that the code is the same. We still do all the buggy logic in the deterministic mode. So I check if the “deterministic” flag is set. Oh, it’s hardcoded to “false”. When was that change made? Oh right in “Big refactor and update”.

So what do I do now? The bug doesn’t happen because the “deterministic” mode doesn’t work any more. Do I just stop now? After all the pytorch caching allocator actually guarantees in this particular case that the memory isn’t freed before the kernel runs. So the only impact of this bug is that I now can’t run our tests with compute sanitizer enabled. So maybe just leave it alone and spend my time on other more important things.

Step 13, 30 minutes plus two hours waiting. While writing the blog post I notice that the “deterministic” mode should work again in the latest version on github. So I pull latest again, build (takes an hour) and try a little harder to reproduce the bug. This time I succeed. Finally. I make the trivial ten-second fix, but the bug doesn’t go away. I don’t understand why. I add print statement to print the pointer address, but nothing prints. Are incremental builds broken? I do a clean build (another hour) and the print-statement still doesn’t print. What’s going on? Then I notice that the file was copied to “flash_api_stable.cpp”. I make the change in that file and finally the bug is fixed.

Step 14, 30 minutes. Figure out the necessary github clicks and git commands to get a pull request for the fix up. I’m waiting to see if there are any comments but my change gets merged quickly the next day. I’m done.

Oh and the initial bug was actually because the changes that my coworker made could change behavior in a way that was pretty obvious in hindsight, but that’s for another time.

So overall a fix that takes about 10 seconds to write took over 10 hours of my time (I didn’t fully count the time spent waiting), spread out over days. Is this typical? No, I do often have days where I actually get to write many lines of code. Is this unusual? No, I also have many days where I produce very few lines of code for many hours of work. When maintaining complicated code these days are more common. Where did the time go?

• Trying to get around layers or punching through layers
• Fighting with build systems and compilers
• Fighting with dependencies or packages
• Running the wrong version of the code or a wrong copy of the code

I actually wish that LLM coding tools could help with this stuff. Instead of me spending hours going down a wrong path I’d rather if the LLM went down the wrong path for me. But so far they’re not good at this, and in fact they’re likely to waste hours of your time by suggesting wrong paths. I’m also terrified of letting a LLM try to upgrade my installed CUDA version. Not because I’m worried it’ll take over my computer as a first step towards taking over the world, but because I’m worried it’ll mess things up so badly that I can’t recover. So while I appreciate that LLMs can be a big help when writing code, I wish they would help with all the programming tasks where I’m barely producing any code.

The story of how LLMs keep on getting better is one of pushing for big and little improvements in a hundred different directions. Turns out hill climbing can get you to a really good place if you just climb along enough dimensions. This makes it hard to notice changes as they’re happening because they’re so small, so lets look at the last two years and see how many small changes there were to add up to the big improvements we saw.

Big Visible Changes

• models now “think” before giving an answer
• models use “tools” like web search or writing Python programs
• models have much longer context window
• the scaffolding around models is better (e.g. Claude code or “deep research”)
• models understand images and generate them

Big Invisible Changes

• Mixture of Experts – Run giant models but only use a fraction for each token
• Better GPUs – More memory and faster, especially at lower precision
• Better data – people curate their training data much more now

The main point of this blog post is that we many, many small improvements, so it’ll necessarily be long and shallow to go through it all:

Thinking Models

Models can now expend tokens to think out loud, which improves their answer in the end. This doesn’t look that complicated when you use it, but it required adding a new training phase of “reinforcement learning” which feels a bit more like traditional AI than neural networks do. You no longer just propagate a loss to predict the next token, you have to come up with good problems that make the network learn to behave the way you want and learn the right behaviors. I know very little about it. I liked that LLMs were based on text. Less worries about them having wrong objectives and wiping out humanity when all they do is predict the next token. But this reinforcement learning sure makes them better, e.g. at coding.

RLHF was a precursor, then OpenAI had an existence proof in the form of o1 and then everyone else fast-followed because turns out there were many ways of doing this. Deepseek r1 being the most famous one, and they did make a genuine algorithmic improvement in GRPO. But if you look at the size of the step improvement of GRPO over PPO (which came out in 2017) it really isn’t a large change. That’ll be a theme. A lot of this is down to finding good problems to train on, which we’ll also see in the “better data” section below.

Tool Use

Two years ago we were talking about emerging abilities as model scale up. Then we just started giving them more abilities directly. LLMs started using tools like “web search”. And instead of trying to do math in token-space they just write little Python programs and run them for you. These allow the LLMs to compensate for their weak spots. Instead of having to make up next tokens for answers it doesn’t know, it can google that for you. And Python is just better at math than LLMs are, so they no longer make basic mistakes.

Longer Context Windows

So many changes led to this. Remember that Llama 3 had a context length of 8192 tokens. And then Llama 3.1 had a context length of 128k tokens. That particular one was mostly better understanding of how to scale up RoPE. But there were also new extensions like YaRN. And then newer models have even longer context lengths. For a while it seemed like all the big labs were releasing one paper after another on how to get a million token context window. You also get small differences like how Deepseek applies its position embedding to only part of the query and key vectors (and leaves the rest without position embedding) or how GPT-OSS alternates between layers with small sliding windows and layers with full attention. Just different people trying different things.

And when you do run out of the long context of these models, they can now compact it and you can keep going. Which in practice just means summarizing the important bits and discarding the details. Unfortunately not much has been published on the details.

Train Using More GPUs

One problem with the long context window is that during training you just can’t fit all the activations into GPU memory. So people got really into splitting the training across as many GPUs as possible. This isn’t new, but there were dozens of little and big inventions for this, like Ring Attention and fused matmul/networking kernels.

Google released the Jax Scaling book with lots of techniques, Huggingface did their own take on this with the Ultrascale Playbook. The latter says “Reading Time: 2-4 days” which is optimistic. And after reading that you will still only have a surface-level understanding of what it says. This stuff is really difficult and you’ll tank performance a few times by e.g. sharding FSDP across too many GPUs before getting it right.

KV Cache Memory Improvements

The long context length is still a big memory problem so models found other ways to save memory. GQA is an easy way to decrease the KV-cache size. Deepseek went more aggressive with MLA. PagedAttention helps with inference. And of course people compressed their KV caches:

Smaller Data Types

Another way to save memory is to use smaller data types. Instead of float32 use bfloat16. Instead of bfloat16 use float8, or why not just use FP4? We got both good hardware support for smaller data types and also algorithmic improvements (still happening) to make models robust to the loss of precision. I mean FP4 is a crazy data type in that I can enumerate all the possible values: 0, 0.5, 1, 1.5, 2, 3, 4, 6 (plus the same numbers negative). It’s really a testament to how robust neural networks have gotten that this works at all. Ten years ago neural networks were unstable by default and you had to try many seeds to get anything working (remember that we didn’t even know how to properly initialize linear layers until 2015) and now they’re so robust that you can throw crazy low-precision data types at them and they still work. GPT-OSS uses FP4. Most of the stability improvements were not in the last two years, but the smaller data types were. You see considerations for which data type to use all over the big papers, e.g. Deepseek thought very carefully about this.

Better Hardware

We also got better hardware. B200s gave us very fast FP4 performance. But mostly we got more memory. The H100 had 80GB of memory, the H200 has 140GB, the B200 has 180GB and the B300 has 280GB. Look at my sections above for why people want this. (also as an aside, the PagedAttention paper I linked above talks about using an A100 with 40GB of memory. That seems so small now, just over two years later…)

And then everyone started using TPUs, hardware that was built specifically for neural networks. This is less of a big deal than you’d think because Nvidia GPUs are now also mostly neural network machines, but it did make things cheaper than if there had been no competition.

Also networking got faster. And Nvidia released the NVL72 which is 72 GPUs connected together with really fast networking, to make all these many-GPU training jobs run better. This again required lots of little improvements to take advantage of, and to run robustly.

More Efficient Algorithms

Flash Attention 3 came out and was better and more complicated. Everyone is anxiously waiting for the FA4 paper.

At the same time matrix multiplication became even more crazy. Since these GPUs are now mostly giant matmul machines, you’d think that it would be easy to make them do a matrix multiplication. But no, a fast matmul requires crazy code and it’s still improving all the time.

And then of course you have to fuse that with networking now so that while your matmul works on the next block, the same kernel can do networking with all the other GPUs in your cluster to combine the results of the previous block with a results from a different GPU. Because it’s not optimal to do a matmul and to then do networking, like we did two years ago. You want to do both at the same time.

Also megakernels are maybe a thing now? I haven’t seen them used in open-source models yet.

Luckily torch.compile also became good in the last two years. Often you can write reasonable code and the compiler will turn it into efficient code. Which at least makes it easier to try out the latest papers.

Mixture of Experts

Another thing you can do is just not run the whole model for every token. E.g. in GPT-OSS 120B you actually only have active 5B parameters for each token. The matmuls are split into “experts” and you only do a subset for each token, decided at runtime. This sounds easy but required algorithmic improvements to work at training time. Backpropagation alone won’t do any more, you need to encourage the model to use all the experts at training time. Also we saw lots of experimentation with hyper parameters, like how many experts, what fraction of experts is active (usual numbers are 3% in Kimi K2 to 25% in Grok), whether there are shared experts and how many, how exactly the routing works… And obviously there had to be algorithmic improvements to make this efficient at runtime, which is still very much ongoing.

Larger Tokenizers

The vocabulary size of these models keeps on going up. Apparently that makes them better somehow. Llama 2 had 32k tokens in its vocabulary, Llama 3 had 128k, GPT-OSS has 201k. This means the embedding layer and the un-embedding layer is a significant fraction of the active 5B params in that model. The hidden dimension of GPT-OSS is 2880, and 201k*2880 = 580m parameters in the embedding and unembedding layers, for a combined total of 1.16B. Meaning more than 20% of the active params are just to go from token indices to hidden dimension and back.

Slower Scaling

Models are not getting bigger at the same speed any more as they used to. Deepseek V3 came out a year ago with 671B total params, out of which 37B are active for each token, and Kimi K2.5 has 1T total params out of which 32B are active for each token. Gone are the days where the number of params multiplies by 10. And even then the big models are MoE now. I don’t think anyone has gone bigger than Llama 3’s 405B active params, and that came out 1.5 years ago.

Since we can train on very large numbers of GPUs now, each of which has enormous amounts of memory, I don’t think the limit here is ability any more. (like it would have been two years ago) Everyone can figure out how to train giant models now. I’d guess the limits are given by diminishing returns, and by high hardware prices.

Distilling Models

One way that models actually got smaller is through distillation. We saw this with Claude Opus and Sonnet. Anthropic trained a really big model, Opus, and then trained a smaller model, Sonnet, to imitate it. This makes the models cheaper and faster to run while only losing a little bit of quality.

Attention Sinks

Attention always had weird effects where the model seemed to pay a lot of attention to the first token in the sequence. Eventually the theory for this became that this happens when there are no important tokens, so the first token acts as a “sink” when nothing needs to be attended to. Recently people added explicit sinks to their attention layers (GPT-OSS) which act as a threshold for the softmax in attention. Meaning if nothing gets enough weight, the sink will zero out all the attention scores. And Qwen noticed that you can get the same benefits by putting one more gate after attention. Apparently this just makes the model straight-up better along all dimensions at the cost of minimal extra compute because the model has to compensate for less weirdness.

Better Data

The Olmo papers are always great, and you can perfectly see how better data became a focus. OLMo 2 talked about various architectural decisions, algorithmic improvements, training stability, and yes, also data. But read Olmo 3 in comparison and it’s all about training data. Once again dozens of improvements. Details about gathering, deduplicating, filtering, deciding the order… And then the whole thing again for reinforcement learning problems plus iterating on what problems work… Reading all these many pages on data quality makes me think that this must cause a big difference between other models, too. (Claude and Gemini come to mind)

Synthetic Data

Turns out you can use LLMs to generate training data for other LLMs. This is most obvious for reinforcement learning problems where you need to generate lots of problems. There were some early papers about how synthetic data is really bad, and then more work made it not so. The tl;dr version of it seems to be “keep on iterating on the synthetic data until it’s really good.”

Better Optimizers

When you train a model you have to use your loss-gradients to update the model somehow. This is the job of the “optimizer”. We got the first good optimizers ten years ago and they’re one of the big reasons why neural networks started getting good then. Right now we have a second phase of getting better optimizers. Apparently people are now speedrunning training of LLMs to a certain quality. What took 45 minutes two years ago now takes under 2 minutes. (half of this is due to better optimizers) If you can train a model to a good quality faster, it will end up at a better quality overall by the end of the training.

Learning Rate Schedules

This is a surprising point in that you’d have thought that we figured out what learning rates to use ten years ago. But almost every paper now talks about their learning rate schedules and they’re all a little different. These schedules are actually still pretty simple, so I wouldn’t be surprised if we see more improvements here. (this has to co-evolve with the optimizers and data that’s being used)

Better Scaffolding

We got Deep Research and Claude Code. These were enabled by long context windows and tool use and by reinforcement learning, but they also just allow the models to do a better job than the old call and response. Now you can tell a model to do something and it just goes and does it. There was no place for models to do this two years ago.

Big Areas I Can’t Cover

When there are dozens of directions that models improve into, there are some big areas that I can’t cover because I know little about them and because they would be too big on their own:

Better Finetuning

I mentioned RLHF, but I don’t think that is even used any more. Llama uses DPO instead and there have been more papers since. As I mentioned with the “Better Data” point above, recent papers now spend a lot of time talking about how they finetuned the models after pretraining (a term which means “read lots of text and predict the next token in all of it”) is finished. It’s too much to cover.

Multimodal Models

Models can now generate pictures and videos and sounds. I take so many pictures of things now and ask models about them. My impression is that writing about these areas would be twice as long as this whole blog post again. Luckily I know very little about all the improvements that led to that, so I won’t talk about them, but given the pace of improvements of e.g. image generation, it’s clear that they also went through dozens of improvements.

Inference Improvements

People started using speculative decoding, predicting multiple tokens at once (e.g. for the little google search AI snippets where cheap inference is important), and I’ve seen the headlines for various papers about how to better assign requests to hardware to get better batching and caching. I didn’t read any of them.

Summary and Outlook

AI is weird in that the chat interface looks very similar to two years ago, and if you look at a model’s code it looks very similar to two years ago, but in the details everything has been hill climbing in many small improvements to make better models. Does any individual improvement make a big difference? Would models be much worse without e.g. explicit attention sinks? No, but it all adds up. And sometimes enough small enough improvements allow a step change in capabilities, like the longer context did.

More papers come out than anyone can possibly keep up with (even just reading the headlines or the abstracts), and I only looked at the ones that made it into released models and that I remembered. But other areas haven’t stood still, even if no big models use their improvements. State-space models and linear attention have also been hill-climbing. I would not be surprised if they’re better than transformers soon (it would be a classic example of the theory of a cheaper, worse thing disrupting a more expensive, better thing by slowly improving). Or maybe those mixture-of-depths or H-Net approaches get adopted. And for some reason papers keep on coming out about how much better RNNs are getting. There are so many different approaches that you don’t see in LLMs yet, but have a chance of being adopted. When the next big thing comes out, it’ll probably be years in the making.

And of course even within transformers there are dozens more directions to explore. Big ones that come to mind are multiple residual streams, generalized attention, even more aggressive compression to smaller data types, more complicated attention. This architecture is not done improving. Even if every single one of these is a small step, it’ll add up.

I used to think that we need some algorithmic breakthroughs to make LLMs really good and get over their weird flaws. (where they’re really good at many things and then make the stupidest mistakes at other times) Now I think we are at a good enough starting point where we can hill-climb our way out of this. I’d be surprised if we didn’t see some big steps in addition to the many small steps, but I no longer think it’s necessary. The overall pace of improvements has just been so good.

I worked at Avalanche Studios NYC from July 2012 to December 31st 2019, seven and a half years. I wasn’t there for most of Contraband’s development but it was obvious early on that it was going to be a very difficult project. If anything I’m surprised it lasted that long before being canceled.

The studio was born out of ambition. It failed because it could not deliver on that ambition. So this will necessarily be negative. But we had a good run and made two good games. I have so many memories and thoughts that I need to get written down somewhere, so lets celebrate the good and talk about the troubles.

Founding a Studio to Make Better Games

I wasn’t there for the founding. The studio opened at the end of 2011. It was an expansion for Avalanche Studios in Stockholm. (not to be confused with Avalanche Software in Utah) That company was doing well: Both Just Cause 2 and Renegade Ops were widely considered to be surprisingly good games. theHunter was a profitable franchise, and Mad Max and Iron Man (later canceled) were under development. The story I heard was that Christofer Sundberg (co-founder of Avalanche Studios) loved New York and liked the idea of starting a studio there. Then the stars must have aligned where they got a contract from Square to develop Just Cause 3 and at the same time were able to hire a team from Kaos Studios who had just shut down. One motivation was that the NYC studio would hire talent that they didn’t have access to in Stockholm, because apparently a lot of talent isn’t interested in moving to Sweden.

Also the studio had grown like crazy after Just Cause 1 to do several different projects at once, only for all but JC2 to fail. So I think they were scared to have three projects in one studio, so why not try starting a second studio?

Joining as a Junior Among Seniors

I joined as a tools-programmer in 2012, straight out of college. I remember being shown around the office and introduced to people as a tools-programmer and designer Jesse Johansen’s reaction was “oh thank god”, in a voice that made it clear how frustrated he had been with the tools.

The team was still fairly new. We had inherited an engine that went from Just Cause 2 to Mad Max to us. So a lot of Just Cause 2 features had been ripped out (water, animals) or had broken. When I joined, a basic version of water was working again but there really wasn’t much in the game. The most exciting thing was an art test where they had set up a small town with high quality buildings. (no one knew what “next-gen” would look like and the town looks significantly better in the finished game)

There had been no tools-programmer before, so the level editor had been kept barely working by random devs helping out a little bit, so productivity for designers and artists wasn’t exactly great. My first commit on my first day was to disable a “create road” button because it would just crash whenever you clicked it.

The studio had made a point of only hiring “senior” people. I’d guess a third of the team had moved over from the Stockholm office, another third came from Kaos Studios, and another third were from other places. I was the first exception to the “only seniors” rule as someone straight out of college. I felt flattered until I learned in my second week that the level editor I was supposed to maintain was scheduled to be deprecated and deleted because the “engine team” in Stockholm was working on a new level editor together with a new terrain system that would get the engine ready for next-gen hardware. (this would all fail and we would stick with the old editor for a long time)

The Old Editor Was a Mess

Learning that I would maintain dead-end software was a bit demotivating but there was plenty of work to do. When I started, the editor would crash 30% of the time on startup. When I tracked this down to some kind of graphics bug, the graphics programmer told me that he thinks Mad Max had a fix for this already and he would try to bring it over. While we shared code with Mad Max in theory, in practice the codebases were two separate copies that were constantly diverging. After Iron Man was canceled, Mad Max had two tools-programmers, so for a while I tried to bring over improvements that they had made, but this got more and more tedious over time as the code was becoming more different, so eventually it stopped.

The editor was also just in a terrible state. The 30% crash was the least of my problems. It was very difficult to make any changes to the editor because you’d constantly break some state that wasn’t kept in sync. When opening a “location” (the term used for anything that streams in together, like a town or a military base) all the objects in the location would be created, then deleted, then created, then deleted, then created and finally kept. This happened because different pieces of code in the editor didn’t trust each other. There were observers that watched for state changes and recreated objects, but these observers could be turned off sometimes for performance reasons, and then there was a backup call that would just recreate everything. And different pieces of code would trigger this backup, just in case, so it happened twice before you even made any changes to the location. And it didn’t get better when you actually started interacting with it. This took months of incremental improvements to untangle. It was obvious what the correct thing was (just create the objects once on startup and recreate them once for changes) but if you just stopped turning off observers, you’d get infinite loops or terrible performance. Whoever wrote the editor before had simply given up and piled on more bandaids, which just made the problem worse. (they were following the “make it work, make it fast, make it good” rule by undoing step 1 in step 2 and never getting to step 3)

I’m making it sound simpler than it really was. To illustrate the mess, know that there is a thing called “object-references” where things can refer to each other. (like “when the player enters this trigger, start that cutscene”) When the editor needed to know whether an object-reference was actually pointing at an object, it would walk the Windows tree view to see if an item existed at that position in the tree. Why did it ask the view instead of the data structure that created that view? Because the data structure (if you can call it that) was such a mess that you could not look things up in it. You needed to combine several different methods just to iterate it, and this iteration code was copy+pasted many times and was doing things incorrectly as often as not. And you certainly could not just ask if an object identified by a path existed.

Previous maintainers were also terrified of deleting code. The “create road” button that I disabled on my first day belonged to a road-system that had last been used in Just Cause 1. There was a new system where you create roads in “locations” through a different interface. The old system was still needed though because it knew how to flatten the terrain wherever you place a road, so there was a brittle set of steps you had to follow to convert roads from the new system to the old system. I made those steps not crash, then automated them, then got rid of all of the old road system except for the part that did the terrain flattening. I also ripped out several other big systems where I was certain that they had not been used in Mad Max or Just Cause 2. My lines of code for the first year were almost negative, which I was quite proud of.

All this is to say that I could see a microcosm of how Just Cause 1 and 2 ended up as buggy games.

The Game Was Almost Canceled

The game was coming along well actually. We were prototyping lots of things and the big important things (like the wingsuit) were working out. I can’t really comment on how decisions were made because I was too low-level. I think mostly this game went well because we had pretty clear direction (“next gen Just Cause 2”) with the occasional ambition that fit well. (“make crazy vertical military bases”) Sure, plenty of things were cut (underwater gameplay, multiplayer) but we kept the important things.

Also the right amount of restraint. Like the wingsuit was definitely overpowered at points during development. It still is a little overpowered in the shipped version, but you will smash your face into the ground several times before you get it right. Also we gave the player unlimited explosives but kept reloading of weapons. Need to draw the line somewhere.

The first big problem was when Square had financial troubles and almost canceled us. Somehow we avoided that fate by switching to being “free to play” (F2P) because that was a buzzword at the time. The idea was that the first island would be free and we would make people pay for extra islands and live service stuff, somehow. I have no idea how Roland and David got this through, but it kept the studio alive. Luckily Square’s finances recovered and that whole plan was scrapped. You can still see leftovers of it in the final game in that the first island is just the best island. The large island in particular was a victim of having not enough design due to being essentially canceled during most of the development.

I actually don’t have too much insight about the game itself. I was not involved in important decisions. When I boot it up now I just see all the bugs I caused. If you ever drive a car and get random unexplained bumps in the roads at intersections, that’s because road intersections required special handling (not my fault) and the tool for that was confusing (my fault). I could write a lot about why you don’t want to use Catmull-Rom splines for roads.

The New Editor and Terrain Were a Bigger Mess

Talking about my bugs means I have to talk about the new editor and new terrain. This was a giant mess. To the point where, when I left Avalanche, the new editor was going to be deleted again even though it had years of work by some of the most experienced developers in the studio. The new terrain was also a mess at first, but it could be saved with enough work.

I think the goal was that Avalanche Studios was going to license out its engine, like Unreal engine. But they recognized that the old tools were a mess and invested a lot of work into making new tools that were designed properly.

The new editor was written in Python. This was a huge mistake. The history is that, before I joined, the “location” compiler was rewritten in Python and the code was cleaner and actually ran faster than the old C++ code. So people thought Python was great and decided to use it for the new editor. I can see a case for wanting to use a memory-safe language for the editor, and I can see that Python is fun to write, but dammit Python is hard to maintain. I wasn’t there, but my theory was that the old location compiler was written by the same people who wrote the old editor. And obviously if you compare their code to a new implementation written in anything whatsoever, the new implementation will be better.

The code for the new editor was very designed. It followed lots of OOP best design practices. Everything was supposed to be a plugin. If you’re an experienced programmer you know how this went.

We hired a second tools-programmer, also a junior, whose main job was to work on the new editor once we started using it. He was constantly fighting fires. He was doing this so much that he was actually quite good at hiding how much of a problem we had on our hands. I knew, and I tried to keep my distance to the new editor. (this was easy to justify because there was enough work to do that for every month of work I finished, I would fall two months behind on my tasks) But I remember Andrew Yount (Tech Director) getting angry when he realized how this guy was spending his time. It’s weird to see Andrew get angry, that doesn’t happen.

People were constantly losing work. The new editor would crash and corrupt files, even late in development. Occasionally I would try to help out and see where the issues were and would immediately get completely lost in the layers. The way this thing wrote files to disk was so complicated that the devs thought it was a good idea if they took over version control (not a good idea if you’re also corrupting files). The team wasn’t that big, so in the old terrain you’d just make sure not to work on the same map tiles as other devs. The new editor tried to magic this away and failed miserably.

So our second tools-programmer spent a good amount of time recovering lost or corrupted files. Where in any sane environment you’d say “let me help you recover this file and then make sure this never happens again” half of his life was just “let me help you recover this file” because nobody could fix this editor. Unfortunately the fact that he was recovering the files also took the pressure off the engine team.

We had help from the “engine team” in Stockholm (who had written this editor) so they would actually ship features in the editor that we needed for the game. E.g. the new terrain had to be flattened for roads in a different way. This took much longer than in the old terrain because volumetric terrain is slower than height maps. But still this was interactive and nice at first. Then later in development it became slow and annoying to do because when you have a bad project it’s hard to keep nice things working.

Overall this whole effort was net-negative for development tools, and maybe even net-negative for JC3.

The terrain barely became shippable just before release. It almost caused us to run much too slow. I just booted up the game again on PS4 and we are nowhere near a stable 30fps. Is that entirely the terrain’s fault? No, there are other slow things, but the terrain alone was almost slow enough that we couldn’t ship, and required lots of effort that would have otherwise gone into optimizing other places.

The lesson there is to do one big rewrite at a time. Write a true 3D terrain or write a new editor. Don’t do both at the same time. Plus all the other lessons that ultimately caused the studio to fail, which I’ll get into later.

The Culture Was Actually Great

I remember the culture being pretty great. Great work/life balance and lots of young people together in NYC. The Swedes that had come over from Stockholm were great at having fun in the city. Also our address was on the corner of Broadway and Spring, which is a fantastic neighborhood.

I lived further out, in Flatbush. There were kids dealing drugs out of the front door of my building. Someone got shot outside my door in the first three months of moving to the city. I lived with a girl who was hyper-active and was constantly smoking weed to make up for that. I thought she was OCD and a little intense, but the girl I was dating explained to me that no, my roommate was actually crazy. Later I moved to Chinatown to a seventh floor walkup with five roommates who were constantly rotating. I lived there for three years and I had more than thirty different roommates in that time. It was actually great.

The development culture also felt vibrant. Cool things were constantly being added to the game. At the same time there was no pressure to stay late. When we had to do a bit of overtime at the end of development, the leadership felt so conscious about making sure that we didn’t work crazy hours, that the whole effort actually felt kinda pointless (I never worked more than 50 hours in a week).

The biggest issue is that things were also always breaking. Nobody but me wrote automated tests. (I had added the googletest library to our engine, which is one of the reasons why my “lines of code” was not negative in my first year) It was normal for the build to be broken for half a day. We also didn’t have any infrastructure around running older versions. If you synced latest and it was broken, you got to spend an hour however you like (clear out your email backlog?) until someone fixed the build. (this obviously didn’t apply to programmers who were expected to fix the build when they sync to a bad version)

At some point the company started giving out awards for doing well on certain criteria and I’m still mad that the first “craftsmanship” award went to a guy who was constantly putting out fires that he had caused. It’s not good to have a culture where you reward the guy who is causing the fires when he then puts out those fires. (this wasn’t the other tools programmer. There were multiple people who seemed to always be busy putting out fires)

But people saw how hard he was working on difficult bugs, and that was rewarded. Even as a junior I could tell that this was silly because there is clearly a better way of working where you follow better coding practices and don’t constantly write difficult bugs, and then have more time to do more productive things. Like Jacques Kerner (physics and vehicle programmer) steadily shipped one feature after another throughout all of JC3 and JC4 development. But that kind of consistency is almost boring, so it doesn’t get rewarded.

With that I want to call out some other contributors. I’m afraid I’ll forget to mention most. I remember Michael Knowland stood out as a fantastic character artist. Zach Schläppi was an art director with great taste but for some reason the team didn’t like him. (I never worked directly with him so I don’t know why) But in my mind he is the main reason why JC3 looked better than JC4. On design I remember liking Hamish Young because he always wanted things to be done better and had lots of ideas. (he was a bit of an “ideas guy” but his ideas were actually good) On programming Per Hugoson (my first boss) and Dave Barrett stood out as being able to write really difficult code that somehow never caused issues. Roland Lesterlin was probably a great game director in hindsight, but I didn’t notice it at the time. I’m still friends with Rob Meyer (though more because of JC4) and Clint Levijoki because they were great at what they do and they care about the whole project.

We Released to Good Reviews

JC3 was delayed a bit and released in 2015. Mad Max was delayed a lot and also released in 2015. This was a bit awkward because it created a bit of competition between the Stockholm office and the NYC office. Everyone in the company was pretty good about trying to not make it a competition, but it was unavoidable to notice that JC3 got better reviews. We felt pretty good in the New York office. I liked that John Walker (from Rock, Paper Shotgun) gave us their “RPS Recommended” award because I’ve been reading that site almost since it started.

I don’t know exactly what happened next but for some reason the leadership of the NYC office got fired because of some conflict with the Stockholm management. Roland Lesterlin and David Grijns had basically been the founders of the NYC office and their departure left a bit of a vacuum. They also took some devs with then but most people stayed. At this point I had been at the company long enough where I probably could have been in the know about what happened, but having started as the only junior on the team, this still felt like it was outside of my pay-grade so I only remember that there was “some conflict with Stockholm.” I heard that Stockholm didn’t appreciate the hustling where JC3 almost went free to play, and the NYC leadership didn’t like that they always had to save money. (e.g. free snacks were replaced by a vending machine)

I think both Stockholm and NYC could be a bit unyielding. Iron Man had been canceled because Stockholm refused to follow a too-tight schedule, and Mad Max had been massively delayed because there were disagreements about direction with Cory Barlog, which led to his departure and a big redesign of the whole game.

When you have such evidence of wanting things to be done a specific way, that’s going to clash with the NYC leadership who called their new studio “Defiant”.

Switching Things Up for the Next Game

I remember that Stockholm wanted to develop JC4 because they wanted their baby back but surprisingly we ended up with it again. Maybe Square really wanted to work with us again? And it superficially made sense that Stockholm would do Rage 2 after Mad Max, them both being desert games.

I was very optimistic for this game. The biggest issues in JC3 felt like they were externally imposed (going F2P for a significant amount of time, starting from Mad Max instead of JC2, the new terrain that caused so much work for so many people) and we were finally in a state where things weren’t constantly breaking. Just before shipping we had an engine where people could be really productive, and they were. We filled out that giant northern island in no time at all.

For me though I knew that I couldn’t do another round as a tools-programmer. This just wasn’t a studio that valued this work. For the entire development of JC3 we had a role unfilled for another tools-programmer. I thought the role desperately needed filling, but it wasn’t a priority. The “old editor” was still the tool used for almost everything and maintaining it really was way too much work for just me. Our second tools-programmer (who worked on the editor that could only do terrain) was going back to Stockholm, partially for health reasons but also probably because you can’t work on a terrible project like that for too long. If I stayed in my role I just knew that I would once again be worked very hard. It doesn’t feel good to constantly be falling hopelessly behind on all your tasks. Yes I shipped some good things, but I also knew that people were mostly unhappy with our tools.

As an example: I had written the “time of day editor” which was a tool for editing settings that change throughout the day. Like “color of the sky” or “fog thickness” or “wave height.” From things I had learned in college I knew that the best approach for something like this is to get a simple version working early, get it in the hand of users, and then iterate on the feedback. So I got my very first version out quickly. It was a bit buggy and had clear flaws but it got the basic job done, and it had one nice feature: hot reloading. Then I had to work on something else for a while but I was scheduled to get back to this tool in a few weeks. Then another thing came up and the time slot got moved back on the schedule a bit more. And then it got moved again. And again. And again. This tool stayed at version 0.1 throughout all of development. I got to squeeze in some small bugfixes by stealing time from other projects, and at some point a frustrated technical artist was able to help out a little bit to at least do the clear easy wins, but I never got to do the proper second pass that was needed on that tool. I was embarrassed when people used it. But when you’re sitting in a meeting to decide on the schedule and say “this tool really needs a second pass, it’s barely working” the answer is always something like “sure, but people can get work done in it and there is this other new feature that we really needed two months ago.” Which means you never get to do a really good job at anything.

Passing the Editor Torch

Between projects I had a bit of time to work on what I wanted, so I did two things:

1. I shipped a testing framework that made it really easy to write tests that can run in the editor, so that things wouldn’t constantly break.
2. I added a single Qt button. The old editor was written in MFC which was so old that Visual Studio wasn’t properly supporting it anymore. For the longest time I would repurpose existing menu items because nobody knew how to add new menu items or buttons. I figured that out eventually but the UI was clearly unmaintainable. There was an old project online that allowed interoperability between Qt and Windows MFC UIs. I got that working again and as a prototype shipped exactly one button. Just to prove that we could incrementally move to something more maintainable, like Qt. (it was also a great button: physics settling. A feature where you can select objects in the editor, hold the button and the physics simulation runs just for those objects. This allows the object to settle so that you can e.g. place a group of exploding barrels on uneven ground then hold the button for two seconds to let them settle. (It was a hotkey before it became a button))

This would in theory set up the editor for future success. We would have a more modern Qt UI and we would have tests!

I would move on to be an AI programmer. It had always been an interest of mine. And there was a slot freeing up because one programmer left to work at a different company.

I kept eyes on the tools work a little bit. A great tools-programmer (Viktor Arvidsson) had started in Stockholm and was driving the work to transition the editor to Qt. In fact the new terrain editor was going to be deprecated and the terrain-editing was going to be moved back into the old editor. The code had branched off from my state (as opposed to Mad Max) so I was happy that all my work of cleaning up was going to survive.

Sadly the “physics settling” feature broke pretty quickly and the editor tests were broken by a QA person who was trying to help out by doing some programming. I was aware of what his intentions were but I did not understand that he was submitting broken things. I only understood when the Stockholm programmer reached out to ask about the testing and I said “just run this thing” and then realized that it was completely broken and that I couldn’t easily get it working again.

Did I mention that Avalanche Studios didn’t really do code review? I’ll have to talk about that later. But it wasn’t that strange that somebody could submit something that was straight up breaking things that worked before. Since most people didn’t do testing, nobody cared that the editor tests didn’t work any more.

JC4 Tech Quickly Turned Bad

Anyway we were working on JC4. Starting off from a highly productive engine. It was going to be great. Sadly the engine became highly unproductive within months. People went back to their old habits right away. Turns out we were only stable near the end of JC3 because people mostly weren’t adding features. Most people were doing bugfixes or adding content or iterating on details. That makes it easy to keep things working. But for JC4 we were working on new functionality and immediately broke everything.

One disaster I remember was the gameplay scripting system. JC3 had shipped with two gameplay scripting systems. A “event” system which was obviously bad but was well-integrated with the engine. It led to constant bugs and because nobody could follow what even the simplest scripts were doing. And then we had another system that was inspired by Kismet from Unreal Engine. This system was written by someone on the Mad Max team over a holiday break. It was not well integrated with the engine so it could never possibly replace “events”. But at least you could see which objects were talking to which other objects and you could see in which order things were supposed to happen.

These led to so many problems and bugs in JC3 that it was an obvious point of attack for improving everyone’s work. As a result we wrote three and a half new scripting systems for JC4. If you thought that having two systems was a problem, wait until you ship with four and a half systems. Because “events” was the only system that was actually well integrated with the whole engine so we still used it.

How does this happen? Really bad planning and really bad design and not even properly thinking about the problem. Which can only happen because they didn’t have enough eyes on the proposals. (when I found out that we were doing the first two new scripting systems I immediately realized the problem and proposed a design for making “events” be graph-based to make it less error-prone, but my input came too late – the decisions had already been made)

Or we had a new “input system” to handle controls. It was outrageously bad. The person who wrote it left and nobody else could figure out how to implement remapping of controls. We almost shipped without being able to remap controls. I had continued to maintain my testing framework and was using it extensively to test AI behaviors and at some point I thought it would be a small additional lift to create tests for player behavior. But it was impossible, completely impossible, to send inputs from code. That might sound silly because clearly some code had to read the controller state and translate it into game inputs, but I could not figure it out at all. So I couldn’t write automated tests that control the player character for the silliest reason ever: because I couldn’t send inputs from code.

Other than the big screw-ups we actually improved lots of things. We were adding cool features to the grappling hook, we had more enemy variety, more vehicles, the game ran at a better framerate and had shorter loading times, it was easy to ship large content (the big city in JC3 was a major lift, in JC4 this was easy enough that we shipped several big cities) and ambitious features like the frontlines were done almost entirely by me, while they would have been very difficult in JC3.

JC4 Design Mysteriously Turned Bad

JC4 was weird because even though we improved on many things, the game came out worse. The design also had lots of improvements, going far beyond the “just blow everything up” gameplay of JC3.

When the game shipped I felt like something was off with it but I didn’t know what, so I thought we’d get better reviews than JC3 because we had improved so many things. The reviews disagreed, and reading the reviews clarified a lot for me.

The biggest problem was that where in JC3 the big bets worked out (wingsuit), in JC4 they didn’t. Like the “extreme weather” wasn’t terrible, but it also just didn’t carry a lot of weight. Also the frontlines never had any real design behind it beyond “these should exist.” I had implemented them but didn’t know what to do with them either so you can’t do much in them in the game.

The biggest bet that didn’t work out was the move away from “chaos objects”: The main criticism of JC3 was that it was repetitive. It was clear that we could never get great reviews as long as we didn’t address that. So we wanted to have more variety in the bases. And we prototyped so many different things for this. But it turns out to be impossible to design missions for Rico Rodriguez, the protagonist. Anything you put in his way can either be taken over or just walked around. How can you possibly design a mission if the protagonist can just fly over every obstacle you put in his way? Mostly we had two answers:

1. Restrict the player to a small area. Either “hold this button without being interrupted” or “don’t leave this zone for 1 minute.” I don’t know how many of these missions we shipped with but I played way too many of these during development.
2. Escort Quests. If you can’t restrict Rico, make him protect someone who is restricted. Now you have to clear all the obstacles for NPCs.

Players hate escort quests. The AI team (which I was now a member of, remember) hated escort quests. You can’t have escort quests in a Just Cause game because there is constantly debris everywhere. There is always some car wreck or a broken giant fuel tank blocking the way. Early in development the designers on our team made it clear to the rest of the design team that we would not give any support to escort quests. Our message was: don’t make these. And yet half the game is escort quests and we were very busy supporting escort quests. I think the other AI programmer on the team, Anders Südow, still has nightmares because one early mission involves escorting a car half-way across the map while it’s being chased by AI enemies and while there are roadblocks in the way. And it’s mostly systemic, only the road blocks are scripted. A crazy amount of work went into that mission because (surprise!) it’s not good to block the road that AI is supposed to drive on. And the mission is not even all that good.

How does this happen? A decision was made and we stuck with it. We weren’t going to do chaos objects any more. At first there was a notion that if things didn’t work out, we could always fall back on chaos objects. And then we never did that when things didn’t work out. Instead you get lots of missions of “go there then press the button.”

Maybe nobody realized the fundamental impossibility that you can’t design missions for Rico Rodriguez. I certainly didn’t put it together until after we shipped. (but it also wasn’t my job)

I personally liked our game director, Francesco, quite a lot. He was the lead designer on JC3 and he is clearly a good designer. But he is a bit too technical in that he likes to come up with systems and rules in the game. Somehow he missed that the basics were often not there. Like these missions aren’t fun. And a game director is also supposed to have his eyes on other things like graphics (characters look worse, water looks worse) or story. Watch a random cutscene from JC3 and it’s people having fun and is short and to the point. Watch a random cutscene from JC4 and it’s not people having fun and it’s not short and not to the point.

The main thing I remember him doing was managing Square, but I don’t actually know what that involves.

Nobody Ever Gets Credit for Fixing Problems that Never Happened

My main issue was that things were constantly broken during development. We’d ship some new feature to Square for a “milestone” and then a month later it was broken and nobody cared to get it working again because we were busy shipping the next “milestone.” Usually you couldn’t play missions anymore that were made two months ago. Only in the last months before release did everything actually work and stay working.

I was still the only person writing automated tests. There was good infrastructure for this in place now. I remember giving a talk internally where I tried to convince people to write more tests. I asked before the presentation “who already thinks we should write more tests?” and almost everyone’s hand went up. Which left me a bit surprised because what the heck are we doing then? In practice it was completely impossible to get these people to write tests even if they thought they should be doing it. One time there was an animation bug that was causing issues for me. So I wrote a little test to reproduce the issue and I showed it to the other programmer. “Look how easy this was to set up” and “look, you can restart the test from the menu or run it on repeat to make it super easy to debug the animation issue” I’d say. And he’d nod appreciatively, fix the issue (two months later) and then never write a test of his own.

I was reading a lot of project management literature at this time because I couldn’t figure out what was going wrong. The problems were so obvious. The solutions, too. Just take a moment and think about what you need for gameplay scripting before you write three and a half different systems that all don’t solve the issue. Just take like ten minutes to write an automated test so that a new feature doesn’t break in a month. Invest a little bit of time to save a lot of time.

I found the answer in the classic paper “Nobody Ever Gets Credit for Fixing Problems that Never Happened“. Man were we ever stuck in a capability trap. Or a Red Queen’s race: You have to run as fast as you can just to stay in place. Here is a quote from the paper that could have applied perfectly to Avalanche Studios:

“Supervisors never had time to make improvements or do preventative maintenance on their lines . . . they had to spend all their time just trying to keep the line going, but this meant it was always in a state of flux, which, in turn, caused them to want to hold lots of protective inventory, because everything was so unpredictable. A quality problem might not be discovered until we had produced a pile of defective parts. This of course meant we didn’t have time to figure out why the problem happened in the first place, since we were now really behind our production schedule. It was a kind of snowball effect that just kept getting worse.”

You see we never had time to keep things working because we were behind on shipping the next milestone because so many things were broken.

I remember, years later, talking to another programmer who had been on the same team. And when I talked about testing he said something like “Avalanche was always doing big games with a small team. We just didn’t have enough programmers to have time to write tests.” This blew my mind. It explained a lot actually. People thought that if you want to write tests, you have to hire more people so you have more time to write tests. For me it was always obvious that tests save you so much time because you’re not constantly breaking things. Instead of being the guy who is constantly putting out fires, you can be the guy who steadily improves things and actually ships features. Meaning a team who writes tests needs fewer programmers to achieve the same thing.

But it wasn’t just the programmers. Everyone was constantly behind on everything. There were many things in JC4 that were actively worse than in JC3. Like more things were destructible in JC3. Much of the art is worse, some environment art was ridiculously bad. And yeah, it’s kinda silly that people on reddit were making fun of us for having blurry low-res low-poly rocks in the game. Because who really cares about rocks? But it was just a symptom of this wider issue that can be felt all throughout the game. And when you have a clear example, it makes sense to highlight it.

When there are constant issues all throughout development, nobody gets to ask for really high quality things. At the time I read the literature and watched the talks and found all the quotes: John Romero talking about the early days of id software and how they would constantly fix bugs as they saw them, Rob Pardo talking about how Blizzard doesn’t just polish at the end, you polish all throughout development. Read that linked paper to see how process improvements can drastically improve output in other industries. Here is another quote that could have applied to Avalanche:

a BP team reduced butane flare-off to zero, saving $1.5 million/year and reducing pollution. The effort took two weeks and cost $5000, a return on investment of 30,000%/year. Members of the team had known about the problem and how to solve it for eight years. They already had all the engineering know-how they needed, and most of the equipment and materials were already on site. What had stopped them from solving the problem long ago? The only barrier was the mental model that there were no resources or time for improvement, that these problems were outside their control, and that they could never make a difference.

Avalanche had a couple of these lying around. E.g. I tried to convince people to implement the “not rocket science” rule of software engineering which is to “automatically maintain a repository of code that always passes all the tests”. We had almost no tests, so I would have been happy to automatically maintain a repository that builds. This is not difficult (it’s called “not rocket science” for a reason) it would have taken a few days of figuring things out in Perforce and Jenkins, and it would have paid for itself immediately, but we were too busy.

And in that culture you just cant ask for the really nice things that actually make a game good.

How Obvious Physics Bugs Ship

Here’s a fun one for learned helplessness: When John Walker posted his JC4 review it was clear that he picked up on all the issues. He pointed out so many things that were not only bad, but pointlessly bad. Like how the game always shows the controls for honking the horn when in a helicopter, and there is no way to turn that off. And at the same time it doesn’t tell you how to actually fly the damn thing. (how does that happen? It got submitted somehow, maybe as a first version, and it wasn’t bad enough that it required someone’s full attention, and it was related to the bad new input system which had a big “ugh field” around it, so it stayed)

But he also posted a video with a bunch of physics bugs. I looked at that and thought “that looks worse than it should.” Sure you could break our physics, but it shouldn’t be that broken. I thought the JC4 physics was generally better than in JC3. I had an immediate suspicion though. I went into work the next day and found the code for clamping physics impulses.

Any physics engine has problems when you present it with impossible situations. Like a car inside a rock. It really wants to push the car out, but since it’s an impossible situation, it is going to apply crazy forces. And then those crazy forces cause more impossible situations to happen so things can never calm down. And in JC4 it’s easy to cause impossible situations because we give you lots of tools to mess with the physics. To solve this we clamped all impulses that the physics engine applies to some reasonable intensity. Meaning it can’t push the car out in one step any more, but things are more stable overall. I looked at that code and found that it was not that complicated. It just had some if/else statements to check if an impulse was too big, and to log the crazy impulse during development so that we can identify what’s causing them. Except the if/else was wrong. It was supposed to disable that logging in release builds, but leave the clamping enabled. It disabled both the logging and the clamping. Meaning only in the released game could you get unclamped crazy physics impulses that we never saw during development.

I walked over to Jacques, our physics programmer (who was usually great, see above) and we had it fixed in less than five minutes. It made it into the game in the next patch, but too late for reviews.

How does something like this get through QA? How can they not catch that the physics can go completely crazy in the released game? My guess is that QA did catch this and there were probably several entries in the bug tracker for crazy broken physics. But remember how things were always kinda broken during development? We probably had hundreds of bugs for broken physics in the bug tracker. Most weren’t as bad as the things we saw in release builds, but nobody could quite tell what level of badness was acceptable and what level wasn’t. So we shipped a game where you regularly saw physics go completely crazy.

The DLC Was More Fun to Develop Than to Play

In JC3 I didn’t work on the DLCs, but in JC4 I did. Once again this was better because the engine was now in a good state, not constantly broken. When you work on the DLC you have to make absolutely sure that you don’t break the main game, so people are more careful and don’t constantly break things. So everyone is actually productive.

My favorite part of working on JC4 was the “Getting Over It” easter egg. Rob Meyer is friends with Bennett Foddy, who lives in NYC so we got him to come in. For the Racing DLC I made a second bigger version of it. It’s great, even though almost nobody has played it. While writing this I discovered that someone finally uploaded a video to Youtube a year ago.

The concept of the Demon DLC was “bring back chaos objects.” Which is a great idea. I did all the enemy AI. Sadly the DLC didn’t really work out. Since I worked on the enemies, and you could probably call me the main combat designer, I mostly blame this on the combat. Enemies keep on respawning, so many players adopt the strategy of “try to clear the base even though I’m still being attacked” which means you end up playing a game where you’re constantly being pestered by the enemies, which is just unpleasant. The best way to play the DLC is to keep on killing the enemies because they eventually switch to a mode where they respawn more slowly, at which point you can do the chaos objects, but players don’t realize that. (I had to hide this “slow respawn” mode a little to get it through) We saw the problems during internal playtests and I didn’t want to do the infinite respawning, but I was overruled because it felt weird for the towns to be empty. So once again a decision got made, we saw it was bad, and we stuck with it because we couldn’t come up with anything better.

The hoverboard DLC was great fun in that it solved the design problem we had in the main game: Turns out you can design varied content for Rico Rodriguez by reframing them as chaos objects. I didn’t work on it for long though, and my main contribution is that I added the really long hoverboard tracks. I also worked on the boss fight though, once again, I am apparently not a good combat designer because that boss fight is not that great… (I’m better as a programmer)

I tried to internally pitch that we should make a hoverboard racing game, but it was rejected because the NYC studio wasn’t supposed to work on small titles.

Lack of Faith Made me Leave

I never worked on Contraband since I was busy with JC4 DLC and a bit of Rage 2 DLC. I saw early prototypes of Contraband and heard all about the design, and it was clear to me that it was going to be trouble.

I didn’t want to work on another troubled multi-year project, so I left before joining the team. Another contributing factor was that a bunch of my code was lost, including all the work I had done on automated testing. This time the engine would continue from Call of the Wild, so if you wanted to keep something, you had to merge it into that code base. I had actually convinced people that automated testing was important, and apparently there was a meeting to decide what to do about it, but they decided to go with a different, less fleshed-out system that someone in Stockholm had recently written. It wasn’t a bad system, I just thought they made it unnecessarily hard to write and run tests, and it clearly was at best a first version of testing infrastructure, where my work had actually been used extensively and shipped in a game. But I didn’t get to make my case because I wasn’t in the meeting. Yes, they decided on the future of automated testing without involving the one person at the company (in both NYC and Stockholm) who actually had experience of doing extensive automated testing. I’m still bitter about that… I had briefly thought about adding all the nice features that my testing infrastructure had to the new system (like writing tests entirely in content using “events”, which I had actually convinced one designer to do; or being able to pause tests in the middle to debug something; or running a test on repeat), but the new system was so far from supporting nice features that my motivation quickly got deflated by how I would not only have to redo my work, but would have to put in extra work because the design of the new system wasn’t there yet.

If there’s one lesson in this, it’s that not sharing code and throwing away code at the end of a game can really hurt your engine, both in all the obvious ways and also in several non-obvious ways.

Contraband Was Going to be Very Very Difficult

I still saw lots of Contraband before leaving. The company had pitched a lot of different projects, but Contraband actually got signed. Contraband was a lot of things to a lot of people. It was going to be the justification for having a NYC studio, going back to the original motivation from 2011: A big impressive AAA game that justifies having an expensive studio. In fact the game was big enough that NYC and Stockholm would work together on it, somehow.

It was going to be a multiplayer co-op open-world heist game. The first three things made total sense: We could see how much money GTA IV was making and we had wanted to make a multiplayer game for ages (JC3 had some work done towards multiplayer in the F2P era). Co-op makes sense for that because it’s easier to make a co-op multiplayer game than a competitive one, especially in an open world. Open-world made sense because that was our strength as a studio. But what the heck is a heist game? I think the idea was to appeal to a similar audience as GTA so it had to be more grounded. The proposed gameplay sounded a bit like Hitman where you have to scout out a location and then steal something. Or maybe like Teardown, though that wouldn’t come out until years later. There were also talks of smuggling using truck convoys, both driving them in co-op and trying to steal things from AI-driven ones. There were neat ideas but I don’t think anyone actually understood what the core of the game was.

So I don’t know what the game was trying to be, but if it wanted to be a multiplayer open-world Hitman, that sounds good in theory but I don’t know a single studio in the world that could pull that off. It sounds really really difficult. Even a single-player Hitman is really really difficult and requires very strong designers, which we had just demonstrated with JC4 that we don’t have.

The game director on the project was going to be the former narrative director from JC4. This made no sense because the narrative was not good and in fact was a bit mismanaged (though we had problems with a vendor, and things could be blamed on that). The reason he ran the project was that somebody from the NYC studio had to lead this game because it would have sucked to just be a subsidiary helping out Stockholm, but Francesco had just been game director on JC4 which wasn’t good, and nobody else made sense either. The person who eventually was the lead only made sense because everyone liked him. And he was really good at selling things. So he pitched a great game concept to Microsoft and got the project signed. (and also no project pitch from the Stockholm office got signed, so there were no alternatives)

I remember talking to him explaining that the game he was trying to make sounded really difficult from a gameplay perspective. Especially how it wasn’t supposed to be a shooter. Like everyone knows how to make a racing game because racing is inherently fun. Or a platformer or a shooter because platforming and shooting are fun interactions on a computer. And while this game had bits of driving and bits of shooting and maybe even bits of platforming, it wasn’t going to be about any of those things and I couldn’t see which part would be inherently fun. The various ideas that I had heard all sounded really difficult, like they weren’t going to work out. And after they wouldn’t work out they would be replaced with shooting, which would have gone against the design. The response I got did not make me think that he appreciated just how difficult of a project he was taking on.

I only know how it went from second-hand reports of people who stayed longer. Apparently they kept on trying new things saying “now the game will be this” for six months, then when that didn’t work out they said “now the game will be like that instead” for six months. I don’t know if they ever got out of that mode.

Apparently there were negotiations about starting development on another project, but that fell through. So eventually the studio shut down.

It’s All About Culture, in a Wider Sense

In my mind this is all about culture. You couldn’t fulfill the ambition of the NYC office with the culture of the NYC office.

To explain what I mean by that, let’s talk about countries for a second. The main reason why China in the 21st century is doing much better than China in the middle of the 20th century is culture. I mean culture in the Joseph Heinrich sense. So not just “books” or “music” or “art” but also things like “how companies are run” and “what you learn in school” and “what politicians care about” and what I talk about in the “culture” chapter above, as “work/life balance” and other unmeasurable things. You can invoke lots of other reasons but the culture of China in the middle of the 20th century was very limiting. You just can’t become a top tier country with that culture.

What specifically is holding you back? Lots and lots of little things, and then a few big things like the Great Leap Forward. But even without that, the lots of little things will just constantly drag you down. They’ll act like a mix of gravity and friction, keeping you from the top tier countries.

This is also obvious if look at other examples. You might compare Denmark and Afghanistan and say that Denmark got lucky with Novo Nordisk and Afghanistan got all kinds of unlucky. But really the main difference is culture and all the millions of little things that Denmark does right and Afghanistan does wrong. Afghanistan is being dragged down by its culture and many other issues could be overcome with better culture.

When Avalanche Studios NYC was founded, Avalanche Studios as whole wanted to step up to the next tier of game developers. There were big investments to make the engine ready for next gen, maybe even license out the engine. Use that money to reinvest and then grow the studio. But we didn’t have the culture to level up. I don’t think Avalanche Studios Stockholm had it either.

There are also no secrets about how to do this. The paper to read here is “The Mundanity of Excellence.” It talks about excellence in the context of olympic swimmers. Having now worked at other places, I think its thesis for how excellence is achieved is spot on:

Excellence is mundane. Superlative performance is really a confluence of dozens of small skills or activities, each one learned or stumbled upon, which have been carefully drilled into habit and then are fitted together in a synthesized whole. There is nothing extraordinary or super-human in any one of those actions; only the fact that they are done consistently and correctly, and all together, produce excellence. When a swimmer learns a proper flip turn in the freestyle races, she will swim the race a bit faster; then a streamlined push off from the wall, with the arms squeezed together over the head, and a little faster; then how to place the hands in the water so no air is cupped in them, then how to lift them over the water; then how to lift weights to properly build strength, and how to eat the right foods, and to wear the best suits for racing, and on and on. Each of those tasks seems small in itself, but each allows the athlete to swim a bit faster. And having learned and consistently practiced all of them together, and many more besides, the swimmer may compete in the Olympic Games. The winning of a gold medal is nothing more than the synthesis of a countless number of such little things – even if some of them are done unwittingly or by others, and thus called “luck.”

I left video games because I was looking for a place that can ship high quality software and found it outside of video games. (I would have stayed in video games if there had been such options in NYC) Having now worked at a place that has a better culture, there really are no tricks. I think the new place writes just as many bugs as Avalanche Studios NYC did. But the rest of the culture means the bugs don’t cause as many problems. Most of them get caught before being submitted to main, and the ones that do make it through don’t cause as much damage because there are layers of defense. It just takes lots of small activities and “the fact that they are done consistently and correctly, and all together” as in the quote above. My advice for Avalanche would be to do small things, like write automated tests, do code review properly, actually share code between projects instead of copy-pasting the engine and diverging, run the autobuilder before a change gets submitted to make sure the build can’t break, do postmortems when there was a big enough issue that others noticed and actually do most of the follow-up actions that you agreed on, be curious about bugs when you run into them and try to fix them proactively. No magic, just small improvements done consistently for a better process.

I remember wasting days at Avalanche on trying to track down this weird crash. It was something about the GPU doing delayed work and crashing in a spot where you couldn’t see what originally caused the issue. Weeks later a technical artist was also trying to track this one down and together we made some good progress and finally found out “it must be something with X,” where X was written by one of our graphics programmers. We talk to him and he says right away “oh yeah X crashes sometimes.” He had known. And just left it in. And this guy wasn’t even the bad guy I had talked about before who was causing all the fires. Nothing happened as a result of this episode. The bug got fixed and that’s it. (this is obviously crazy, but at Avalanche Studios this was so normal that I have to say what to do instead: at least have a post-mortem about how this could have happened. Then decide on actions to prevent this from happening again and do those actions)

With the culture that Avalanche NYC had, you could either throw more money/people at the problem or work crazy overtime, or you could be stuck at a certain quality level. We didn’t have lots of people and we didn’t want to work crazy overtime, so we were stuck. And the companies that just throw more money at the problem are also a bit stuck. When things break at the same pace that you’re fixing them, you end up with some parts of the next game being better and some parts being worse, but ultimately you end up at the same quality level.

I think JC3 was our limit. It was a better version of JC2, and that’s all we could do. In JC4 we had ambition to do better than in JC3 and as a result we ended up in a Red Queen’s race where we just couldn’t make progress and actually ended up worse than where we started. Contraband wanted to be even better and as a result just couldn’t ship.

I actually think the company strategy was kinda smart. I think it made sense to expand to the US and to develop the new terrain at the time when they did. I think it made sense to try to redo the terrible editor code and to try to license out the engine. It made sense to go multiplayer for Contraband and to do it as a co-op game. But then there was lots of bad execution which led to us constantly being in trouble and constantly being behind, which led to us sticking to bad decisions.

I am also worried about the rest of Avalanche Studios. They were growing a lot when I left, and were working on several self-published titles like Second Extinction and Ravenbound and The Angler. Those games have shipped, to various levels of disappointment (I haven’t played any, but if I had to guess, The Angler might actually be good, the others not), and I haven’t heard about anything since. It’s not good that it’s been almost six years and they have only shipped some middling games that were already in development six years ago. (and I literally have no inside information about what they are working on) And also the track record wasn’t great before that. Rage 2 didn’t get great reviews either, and neither did theHunter: Primal or Generation Zero. They weren’t terrible games, just disappointing compared to what they could have been. And internally there wasn’t much reflection on that, the official messaging was always “they made their money back and were a success for us” which isn’t that satisfying.

Lessons Learned

Speaking of which, lets get to the lessons we learned here. One of them is that you can’t develop games any more like we did for old console generations. And one of them was that Avalanche was not good at learning lessons. It’s not like they didn’t react to mistakes, but they often drew the wrong conclusions. Lets get to these in order.

Short-Lived Code

Games used to have development cycles where it made sense to not write super high quality code. When going from SNES to Playstation to Playstation 2 to Playstation 3 you were probably going to rewrite much of your engine anyway. This stopped being true with the Playstation 4, just as I joined the company. Not just because you have to live with the same code for multiple projects, but also because each project takes longer and has more code, so the crappy practices bite you before you even ship the first game. Avalanche was stuck in the old mindset for way too long. Programmers as a craft know how to do this better, but game developers were very reluctant to adopt practices that slow down individual changes in order for the project as a whole to move faster. They like to point out how things also are done badly in other industries (Slow buggy web apps, OOP design-patterns, micro-services) and as a result they reject the successful practices, too.

It was also clear that others in the games industry had the same problem. Mass Effect: Andromeda came out the year prior and got panned for bad character art and bad animations compared to earlier Mass Effect games (from earlier console generations). Or look at that comparison video of Far Cry 2 and Far Cry 5, which came out the same year as JC4.

What can be done about this? The easiest thing is to stop having your own engine. That limits how much damage your programmers can do. The more difficult thing is figuring out how to learn the right lessons.

Postmortems

Going back to that “culture of countries” comparison, while we obviously didn’t have anything nearly as bad as the “Great Leap Forward”, it’s helpful to think about how such a colossal fuckup can happen. It’s almost calming to see that a country that can evidently be very competent can also have one of the biggest screw-ups in history. But thinking about it, I think one essential ingredient for messing up really badly is that you don’t learn lessons.

We actually did try a bunch of improvements. We tried code review for a while but we did it badly and eventually it fizzled out. We kept on trying to share code between games and we kept on doing it badly, causing us to do very little of it. I did convince some people to write automated tests, but they would write one or two bad tests and then give up. Remember that QA person who was ruining the editor tests? He also wrote some other tests that were worse than useless. They would break all the time on nonsense issues and wouldn’t actually tell you what the problem is. This is actually normal when you first start writing tests, because it’s a bit of a skill. So you need to learn your lessons, delete those tests and write better ones. This never happened.

And when we did learn lessons, it was non-public and it was not clear how we came to exactly those lessons. E.g. the “old editor” was clearly a problem when I joined and that was the reason why there was going to be a new editor. The lesson they learned was to not write it in C++ and to write it in Python instead. This certainly was going to decrease crashes due to memory-safety issues. But would it fix anything else? And wouldn’t you increase crashes due to lack of type-safety? In hindsight the correct thing was to instead do the tedious work of slowly fixing all the issues with the editor over a couple years.

Coming to that conclusion earlier is difficult, but I know how to not do it: If you don’t have a postmortem, you certainly won’t learn from last time. If there was a postmortem for the Python decision, it was never shared with me, and I was the only other tools-programmer on the team, so that would be very strange. I remember walking towards lunch with Linus Blomberg when he was visiting NYC and he was very reluctant to talk about the whole thing. He certainly wasn’t going to write a postmortem. And if you don’t write a postmortem about bad decisions, you make more bad decisions like writing multiple new scripting systems that all didn’t solve the issue. And there were no postmortems shared for any of those either.

Even if people “learned their lesson” from these mistakes, who’s to say that they were the right lessons? Part of the value of a postmortem that’s widely shared is that you get lots of comments on the document and people will tell you all the important things you forgot. (as I expect will happen with this blog post, because my view is necessarily one-sided. E.g. I remember designers being frustrated that even if we learned lessons from playtests, we didn’t act on them. But that has to be someone else’s perspective)

Reviews

Another aspect of this was the lack of serious review. Meaning code review, but I’m not just talking about programmers, but also review for designers and artists.

I now spend more than 10% of my time doing review. It easily pays for itself. When it gets to be more than 30% I try to reduce my review obligations, so the right number is somewhere between those two.

Code review done properly helps with so many issues that we had. Your code has to actually be up to a certain standard to be possible to be reviewed at all. I remember people submitting things that were just straightforwardly wrong. Like multi-threaded code where a background thread writes to a data structure and the main thread reads it, and there is no synchronization between the two, at all. When reviewing multi-threaded code, if the synchronization is not clear, I leave a blocking comment that forbids release. If it’s too confusing to review, it shouldn’t be submitted.

I remember talking to a designer who had left Avalanche to work somewhere else, and hearing his appreciation that the new place challenged him, really, to explain why an idea would be fun. I remember hearing the description for a mission in a weekly demo of new features, and all I could think was “but why is this interesting?” I don’t think the designers at Avalanche were really challenged to explain why things were good.

I don’t know the process for artists, though I’m pretty sure some of the bad assets that made it into the finished game were not reviewed.

Review as a practice just helps all around. Spreads knowledge and responsibilities, raises standards, prevents heroes or leads from acting on their own. Just make sure that every change is reviewed by at least one other person and that it doesn’t get released until the review is finished. Then iterate on the process until everyone’s productive within those rules. (e.g. if you put a change up for me to review, it should be easy for me to run your version of the build)

Thesis

My overall thesis here has been that we were hampered by bad development practices and couldn’t achieve our ambition. If you have followed Avalanche Studios and looked at all their games, this might sound obvious. The development on the inside was exactly like you expect it to be from what you see in the shipped games. But I don’t think this awareness existed on the inside, or if people were aware they saw it as an unchangeable fact of life. If I had to guess, internally the number one reason would probably have been small team sizes and budgets compared to the size of game we were making. Which is a dangerous justification because sure, Generation Zero (random game developed by a small team) would have been better with a team twice the size, or with twice the time, but you don’t get to have twice the team size if your previous game was no good. You can either be stuck in a never-ending cycle of mediocrity, or you can figure out how to level up.

Video games as an industry will eventually figure this out. Just by evolution. Studios with bad culture will die out and studios with better culture will survive a little longer. If I ever get back into gaming I would try to optimize for productivity. Games don’t have to be as robust as the software running on the Mars rovers, and aiming for that would be a drag on productivity. But if something easily pays for itself, like having a build that’s not broken, or having automated tests for the main features of your game, then you should prioritize that. Don’t even get close to a capability trap. It makes sense that the tools programmer thinks productivity is a top priority, but it made no sense that everyone else always had something more important to do.

There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.

People always use this quote wrong, and to get a feeling for that we just have to look at the original paper, and the context in which it was written. The paper isn’t actually about optimization. It’s about when we have to use goto statements because structured programming couldn’t express certain things at the time. Or at least it couldn’t do so efficiently, requiring extra checks, and that’s why Knuth has to talk about performance: The topic he is addressing is “Can we get rid of goto statements without sacrificing performance?”

The famous quote occurs just after Knuth talks about the problem of writing what C++ oxymoronically calls a multiset. (he obviously doesn’t call it that, but that’s what it is called in C++) Imagine you want to store a set of items, and the items can occur multiple times. Instead of actually storing them multiple times, you might as well just keep a count for each item. In C++ you might write it like this:

template<typename T>
struct counting_multiset
{
    int insert(const T & x)
    {
        return ++counts[x];
    }

private:
    std::map<T, int> counts;
};

I’ll leave the other methods like ‘find’ and ‘erase’ as an exercise to the reader.

Knuth builds this set using two arrays: One for the elements, one for the counts. And, for the purposes of the paper, he always assumes that there is enough space in the array. So an insert might look like this, using goto:

template<typename T>
struct knuth_multiset
{
    int insert_1(const T & x)
    {
        size_t i = 0;
        for (; i < size; ++i)
        {
            if (elems[i] == x)
                goto found;
        }
        ++size;
        elems[i] = x;
        counts[i] = 0;
      found:
        return ++counts[i];
    }

private:
    std::unique_ptr<T[]> elems;
    std::unique_ptr<int[]> counts;
    size_t size = 0;
};

So just iterate through the array until we find the element. If we don’t find it, insert it at the end.

How does this compare in performance to the map-based approach? This is O(n), the map-based approach is O(log n), but arrays are fast. Arrays win until the set has more than ~300 elements in it:

The x-axis is the number of inserts, and for this benchmark I decided that 1/3 inserts would be a new element, and 2/3 just update existing elements, so the size of the container at 1024 (when map is faster) is actually 1024/3 = ~341.

Knuth doesn’t do this comparison, he just says that this is a common example to justify gotos. So why use a goto here? Because there are two different ways of exiting the loop, which share some code afterwards but not all code. Without a goto it would have to look like this:

    int insert_1a(const T & x)
    {
        size_t i = 0;
        while (i < size && elems[i] != x)
            ++i;
        if (i == size)
        {
            ++size;
            elems[i] = x;
            counts[i] = 0;
        }
        return ++counts[i];
    }

We would need an extra check after the loop exits, to see whether the element is already in the set or not. That extra check isn’t much of a performance problem, the bigger problem is that insert_1 is easier to read, and wasn’t code supposed to be easier to read if we get rid of goto?

Except then Knuth says that he actually thinks this is a bad example. He says this is a common argument in favor of goto, but insert_1 is actually a bad way to search for the element. Instead what we should do is optimistically insert the item, so that we always know that it is present, so that we can save ourselves one condition in the loop:

    int insert_2(const T & x)
    {
        elems[size] = x;
        size_t i = 0;
        while (elems[i] != x)
            ++i;
        if (i == size)
        {
            counts[size] = 1;
            ++size;
            return 1;
        }
        else
        {
            return ++counts[i];
        }
    }

See we never have to check whether we went past the end of the array because we always know that we’ll find the item. And next Knuth goes further and says we might as well unroll this loop once to make it faster:

    int insert_2a(const T & x)
    {
        elems[size] = x;
        size_t i = 0;
        goto test;
      loop:
        i += 2;
      test:
        if (elems[i] == x)
            goto found;
        if (elems[i + 1] != x)
            goto loop;
        ++i;
      found:
        if (i == size)
        {
            ++size;
            counts[i] = 1;
            return 1;
        }
        else
        {
            return ++counts[i];
        }
    }

So this increments i by 2 per loop iteration. So instead of “add; compare; add; compare; add; compare…” we do “add; compare; compare; add; compare; compare”. (the “i+1” in the test section is free because there are instructions for “dereference pointer with fixed offset”) Knuth does some math and says that if you assume 20 elements in the set, insert_2a will be ~12% faster than insert_2, which is already 21% faster than insert_1. And in this context he talks about premature optimization:

The improvement in speed from Example 2 to Example 2a is only about 12%, and many people would pronounce that insignificant. The conventional wisdom shared by many of today’s software engineers calls for ignoring efficiency in the small; but I believe this is simply an overreaction to the abuses they see being practiced by penny-wise-and-pound-foolish programmers, who can’t debug or maintain their “optimized” programs. In established engineering disciplines a 12 % improvement, easily obtained, is never considered marginal; and I believe the same viewpoint should prevail in software engineering. Of course I wouldn’t bother making such optimizations on a one-shot job, but when it’s a question of preparing quality programs, I don’t want to restrict myself to tools that deny me such efficiencies.

There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.

Yet we should not pass up our opportunities in that critical 3 %. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified. It is often a mistake to make a priori judgments about what parts of a program are really critical, since the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail. After working with such tools for seven years, I’ve become convinced that all compilers written from now on should be designed to provide all programmers with feedback indicating what parts of their programs are costing the most; indeed, this feedback should be supplied automatically unless it has been specifically turned off.

After a programmer knows which parts of his routines are really important, a transformation like doubling up of loops will be worthwhile.

I think this says the opposite of how the quote is usually used. Usually people say “premature optimization is the root of all evil” to say “small optimizations are not worth it” but just before that paragraph Knuth says that small optimizations, like unrolling this loop once, are worth it, and should not be considered premature optimizations.

Instead what matters is whether you benchmarked your code and whether you determined that this optimization actually makes a difference to the runtime of the program. Don’t do this in a piece of the code that doesn’t even make a difference. But if you know that something matters, or if it’s in a library function that will be used all over the place, then a 12% improvement is definitely worth it.

So if you would have used this quote to tell someone to not do this last optimization, you’re using it wrong.

Measuring the Improvements

OK but does this actually matter? Optimizing compilers have gotten a lot better. Can’t they do this by themselves? They might be able to do the loop unrolling, but in practice they usually won’t. They certainly won’t do the change to optimistically insert the element first before doing the search. Even on current compilers I can measure improvements for each of these:

The left side of the graph is too noisy, with all the lines being really close together. But as I increase the number of inserts, the difference becomes clearer. At the right-most measure, insert_2 is 13.5% faster than insert_1, and insert_2a is 7% faster again. Not quite Knuth’s numbers, but noticeable. But actually that right-hand side is not interesting because you wouldn’t use linear search for a container of that size. (I’ll get later to what you should use instead) So lets zoom in on the small numbers:

I added error bars to this, which are impossible to read here (sorry, LibreOffice isn’t good but it’s easy to plot data in there…), but at least they show that all of these overlap. Meaning there is no big difference between these. But I ran these very often and the median result of all my benchmark shows that insert_1 is faster than insert_2, which is faster than insert_2a. Meaning for small number of elements, its not worth the overhead of optimistically inserting the element.

Fastest of all is a new entry, insert_0. Knuth doesn’t show insert_0 in the paper, but mentions it in a throwaway comment:

if I hadn’t seen how to remove one of the operations from the loop in Example 1, by changing to Example 2. I would probably (at least) have made the for loop run from m to 1 instead of from 1 to m, since it’s usually easier to test for zero than to compare with m.

Sometimes comparing against 0 is faster because it lines up well with the available instructions, so might as well change the loop to count to zero. My implementation looks like this:

    int insert_0(const T & x)
    {
        size_t i = size;
        while (i-- != 0)
        {
            if (elems[i] == x)
                return ++counts[i];
        }
        elems[size] = x;
        counts[size] = 1;
        ++size;
        return 1;
    }

In the loop in insert_1 there are five instructions per loop iteration:

1. Increment
2. Compare (with size)
3. Conditional jump (to end the loop)
4. Compare (with x)
5. Conditional jump (to label found)

With this version there are only four instructions:

1. Decrement
2. Conditional jump (to end the loop)
3. Compare (with x)
4. Conditional jump (out of the function)

We need one comparison less, because you there is a conditional jump instruction available that jumps if the decrement went negative.

Unfortunately both Clang and GCC mess this up. Clang removes the compare, then adds in one new instruction whose purpose I don’t understand, putting us back at five instruction. GCC doesn’t understand the optimization. So I actually had to write a custom assembly version of the loop (by taking the Clang assembly and removing the unnecessary instruction) to get proper measurements of the improvement that Knuth mentions.

So for small sets this version is actually fastest. (for large sets it’s the same speed as insert_1) But all of these have roughly the same speed, and you can only really see a difference once the set gets big enough where you would just use a hashtable anyways. Why is this? Why do they have the same speed until the set gets big?

My best guess is that none of these loops fully tax my CPU. If you’re not fully using instruction-level-parallelism, sometimes it’s free to just throw in one more instruction. Maybe when this paper was written, in 1974, you could still get a good estimate for performance by counting instructions. Today CPUs run multiple instructions per cycle, and if your loop has more instructions, all that happens is that it goes from running at 1.7 instructions per cycle to running at 1.9 instructions per cycle, but overall it takes the same amount of time. But once the sets get large, the branch prediction gets good, and the loop runs at 3.5 instructions per cycle because the CPU runs multiple iterations of the loop at once. At that point it matters how many instructions each iteration through the loop takes because you’re getting close to the hard limit of 4 instructions per cycle. (on my current CPU)

So What Should We Do?

Honestly I don’t think you should worry about most of this, and you should just use a good library. So in order of increasing sanity, lets try three things:

• Use the STL
• Use std::unordered_map
• Use a fast hashtable

Starting with the first one, how does std::find do?

For small sizes it doesn’t do as well as insert_0, but it does pretty well and is faster than insert_2a.

(note: The timings above are different from the other graphs above. I wrote most if this blog post in 2023 but hadn’t created these last graphs yet. So now these were created on different hardware with different compilers. Sorry for that…)

For large sizes it doesn’t do as well as insert_2a, but it does pretty well and is faster than insert_0.

So on average this is just the best option. It is well-optimized: the inner loop is unrolled 4 times, because the authors of std::find did not think that loop unrolling is premature optimization. For linear search you should just use the STL.

But really using linear search is silly here, and using a std::map like I did at the beginning is silly, too. Clearly you want a hash table. Lets start with unordered_map:

It does OK. Slower for small sizes, but not terrible. So lets use a fast flat hash map instead:

This does really well already at 8 insertions. With 2/3 of these being updates of existing entries, the container only contains between 2 and 4 items at that size. A fast flat hash map makes linear search unnecessary even at those sizes.

Conclusion

So what did we learn?

• A 10% improvement is not automatically a “premature optimization”. Instead what matters is whether you have benchmarked your program and determined that the optimization actually makes a difference to the program. And for library functions even smaller optimizations may be worth doing because they are used so often.
• The corollary of that is that you should use library functions that have been written by people who understand that optimizing their functions is not premature optimization.
• Compilers will not do these optimizations for you. Even 50 years after the paper was first written. In fact if a programmer does a straightforward optimizations like “iterate down to 0 instead of iterating up,” the compiler may mess that up and I ended up having to write a little bit of assembly by hand.

P.S.

My apologies to Casey Muratori who recently announced that he was going to cover the “premature optimization” paper in his (recommended) Computer, Enhance! video series. I’ve been having a hard time getting out blog posts in recent years, and when he announced that he was working on covering this paper, that reminded me that I had this mostly-finished blog post from 2023 lying around. All I had to do was insert a few more graphs at the end and write a conclusion, so I rushed to finish it before he got the video out because I was worried that my work would be redundant with his. My apologies Casey if I you were going to cover this from the same angle.

The main problems it tries to address is:

1. Getting good numbers by running benchmarks repeatedly, visualizing them in context, picking a single opinionated good visualization, handling noise and even adding a bit of well-justified noise, and being careful about what statistics to do on the numbers.
2. Dealing with the inevitable combinatorial explosion of benchmarks when you want to try different data structures (min-max heap vs interval heap vs binary heap) with different operations (make_heap, push, pop) on different types (int vs string), different compilers, debug build vs release build, different variants of the code (e.g. trying loop unrolling), different input lengths etc. The full combinatorial explosion might be millions or billions of possible benchmarks. I want to be able to get a first impression for a subset in a few minutes. And then if I want less noisy results I can let it run overnight. And then I can try a new variation and visualize it together with the overnight results in under a minute.
3. Various ergonomic issues. Making it easy to select which numbers are together on the screen. Having the numbers as a graph first, CSV second. Being robust to the code crashing halfway through a long run: Record the partial results and be able to resume the same run. Making it easy to attach a profiler to one specific benchmark that I’m interested in.

This sounds complicated, and I have to admit that this is very much an app written by a programmer for a programmer, but the whole point of a GUI is that I can make this both more powerful and easier to use at the same time. In fact I think the patterns might be more widely useful for people who do slow-running experiments of other kinds (like training a ML model).

2. Main Lessons to Take From This

The main improvements I did that are relevant for other areas are

1. Having a GUI
2. Making it easy to add tags to your runs
3. Writing down all the results in a sqlite file

All of these are about adding structure to data. It really sucks when you run a long-running experiment and your only output is a log file plus a CSV. Because then if you want to compare today’s run to the run from a week ago, you have to copy both into one spreadsheet. Do this ten times and your spreadsheet is a giant mess. You’ll be confused and unable to answer questions like

• “Which run brought the improvement again?”
• “Wait, I remember this measure being better, when did this get worse?”
• “That run from two weeks ago is still the best one we had, what changes were active in that again?”

You’ll also have trouble being confident in your improvements. The results are inherently noisy. So you just run each benchmark repeatedly until you get an idea for how much noise there is. How does that repetition compose with whatever you’re doing with your CSV files?

The sqlite database and the tags just solve this. Each result is recorded, each result is tagged. When the same run happened multiple times, you can either visualize all the runs, or show median and error bars. When you try a new variation (e.g. “don’t early-out in function foo”) just add a new tag and make sure to keep the old code working so you can run with the tag turned off and on.

With the repeated runs you have also slowed down your iteration times. Yes you could add a toggle to your scripts to switch between fast/noisy and slow/confident mode, but in practice how many times have you waited for a run that was slower than necessary because you just ran with the default? So the GUI doesn’t just help to organize all of these results, it also automatically transitions between quick/noisy runs and slow/confident runs: Whenever there is anything in your current selection that doesn’t have the quick/noisy result yet, it runs that first. When those are done it repeats runs to reduce noise.

3. Further Design Decisions and Features

This started off as very similar to Google Benchmark, and evolved from there.

3.1 The Same Interface as Google Benchmark

Google Benchmark has a good interface. Here is a benchmark for looking at a random item in memory:

void benchmark_memory_access(skb::State & state)
{
    size_t num_bytes = state.range(0) / sizeof(size_t);
    std::vector<size_t> bytes(num_bytes);
    std::iota(bytes.begin(), bytes.end(), size_t(100));
    std::uniform_int_distribution<size_t> random_index(0, num_bytes - 1);
    while (state.KeepRunning())
    {
        for (size_t i = 0; i < num_loops; ++i)
            skb::DoNotOptimize(bytes[random_index(global_randomness)]);
    }
    state.SetItemsProcessed(state.iterations() * num_loops);
}

The structure is

• Lines 3 to 6: Set up the benchmark
• Lines 9 and 10: Run the benchmark (the inner loop is part of the benchmark, not of the framework)
• Lines 1, 7 and 12 are part of the framework.

This is pretty much identical to some Google Benchmark as of a couple years ago. The “State” parameter has the arguments for the benchmark. I only support one argument, so you always have to call state.range(0). Then you get to write your setup code, and then use a loop with state.KeepRunning(). Finally since the inner loop does multiple memory lookups per outer iteration, I have to tell the benchmarking framework that I processed more items than it thought. The last line is not required if you just do one iteration in the inner loop.

3.2 Always Specify Baseline Benchmarks

The above benchmark doesn’t tell you much because calculating a random index might take longer than the actual memory lookup. So you can specify a baseline benchmark that will be subtracted out:

void benchmark_memory_access_baseline(skb::State & state)
{
    size_t num_bytes = state.range(0) / sizeof(size_t);
    std::uniform_int_distribution<size_t> random_index(0, num_bytes - 1);

    while (state.KeepRunning())
    {
        for (size_t i = 0; i < num_loops; ++i)
            skb::DoNotOptimize(random_index(global_randomness));
    }
    state.SetItemsProcessed(state.iterations() * num_loops);
}

This is a benchmark that only does the “overhead” work of the previous benchmark. The framework will run both of these together and will always subtract the second benchmark from the first. The difference is the actual cost of a memory lookup to a random location in memory. (allowing for instruction-level parallelism. I have another benchmark where each read depends on the previous read, not allowing for parallelism)

3.3 Add Noise by Running Each Benchmark in a New Process

This is inspired by stabilizer, which isn’t being maintained any more. If you run enough benchmarks you will eventually notice that you can measure noticeable differences between an identical benchmark in two different compilation units. (or compiled on different days)

When you see a speedup you have three different cases:

1. It’s too noisy to be sure if the speedup is real
2. The noise is small and the speedup is real
3. The noise is small and the speedup was caused by compilation luck and can go away on the next recompilation

Like everyone else I tried to ignore this for a long time. You just hope that the third case won’t happen that often. But then I spent way too long chasing a tiny optimization of an inner loop which made no difference. Eventually I noticed that literally the same benchmark compiled twice would give me different results that could not be explained by noise. I could reproduce big speedups over and over again for exactly the same benchmark with identical assembly. Only then did I decide to finally address this.

Since stabilizer is not maintained any more, the closest easy thing you can do is to run with “Address Space Layout Randomization” (ASLR) which means you get a randomized memory layout on each run. This isn’t as comprehensive as what stabilizer does, but I’ve found it to be good enough in practice. After turning this on and running each benchmark in a new process, you mostly remove case 3. Instead you added more noise, so some optimizations that might fall into case 2 will instead fall into case 1. But I visualize how much noise there is and if something is too noisy, you can try to redesign the benchmark until there is less noise. (usually by looping more often or by optimizing the baseline)

In practice this change allowed me to be more accurate, allowing me to measure fractions of a nanosecond. Where before you always had to doubt yourself and think that you’re fooling yourself, now you can actually go after those small improvements that will add up.

3.4 Log X Axis, Linear Y axis

The log/log plot is popular for benchmarks because that’s how your numbers grow. You want to measure sorting a list with 10 items, 10,000 items and 10,000,000 items. Putting those numbers on the same graph seems to require a log y-axis. The problem is that you can’t see anything on a log/log plot. An O(n) radix sort will look the same as a O(n log n) quick sort on a log/log plot. Mar’s law says

Everything is linear if plotted log-log with a fat magic marker.

So how do you solve that? You divide by X. Now the O(n) radix sort will look like you’re just plotting a constant value and the O(n log n) quick sort will look like you’re plotting log(x). Which are two completely different plots. I knew this was the right choice when I started seeing all kinds of interesting patterns in the radix sort plot. You can clearly see when you have to change from two passes to three passes, and when your data gets too big to fit into CPU caches.

So this is the only visualization I support: log-scale on the x-axis, and Y/X with linear scale on the Y axis. I’m actually not opposed to adding other visualizations, it’s just that this visualization is so good that I haven’t found the need to add more.

3.5 Profiler Mode

When you’re curious about why two lines look different you’ll often want to look at the assembly. (Especially when we’re talking nanoseconds) I do this so often that I had to make it easy. So there is a “Profile Mode” button, which does two things:

1. Runs a benchmark in an infinite loop. (you click on a point in a graph to decide which benchmark to run)
2. Stop recording the results. The profiler might add overhead, so we don’t want to persist those results to the database.

With this you can attach easily to the running benchmark and see what it’s doing. I demo this in the video at the beginning, where I show that Clang has a pessimization enabled by default which makes heaps much slower.

3.6 Don’t Try to Be Clever About Noise

I don’t have the answer to noisiness in benchmarking. There are lots of different opinions here. But whenever I see someone being clever, I see them get this wrong. I tried using Rust’s Criterion.rs once to benchmark something, and it gets this completely wrong: It will tell you confidence intervals for your benchmark, and then you rerun the same benchmark and the new confidence interval doesn’t even overlap with the old one. What are you supposed to do with that result? When it gets the answer this wrong, you know it’s not just a bug in the code, it’s a bug in the assumptions about how benchmarking works.

So sure, I show error bars because that tells you at a glance if the benchmark is producing exact results or not, but I also allow you to show the data as points, which shows every single time that a benchmark was run. I click that checkbox often. I think Criterion.rs should also just show all the numbers it measured, and not do extra math on it. But I understand that it’s difficult to show lots of numbers if you don’t have a GUI.

I also plot the median result by default. I know Alexandrescu’s opinion that you should choose the min, because noise is only additive. Noise can never make your benchmark faster, it can only make it slower. But I have lots of random numbers in my benchmarks. E.g. I generate a new random array to sort every time that I run my sorting benchmark. If I take the min across all runs, who’s to say that I won’t just end up with a really lucky run where the input was presorted? (especially when measuring sorting of short arrays) Could you avoid that with a deterministic seed? Sure, but now you have other problems like a branch predictor that memorizes too much. You don’t want to be in a world where you have to trick the compiler and trick the CPU. Better to generate new random numbers each time. You want the CPU to actually do the work. (my equivalent of DoNotOptimize also does actual work that can’t be eliminated) You can always subtract out that cost as a baseline.

My justification here is similar to the ASLR approach above: I’d rather have a benchmark that’s a bit more noisy but where I can trust that I get a realistic distribution of results. If one algorithm is reliably 0.5 nanoseconds faster than another on that benchmark, I can see that after enough runs and I can trust that. If the benchmark ends up too noisy to see that, I can always optimize the code until it’s less noisy. (this just means optimizing all the code that you’re not trying to measure. E.g. use Lemire’s nearly branchless range reduction to make “random numbers in a range” faster. Then the benchmark will have less noise)

3.7 Other things I tried

I spent a lot of time on trying to run benchmarks in different orders. Like also run benchmarks that are not currently visualized sometimes, to eventually fill out the whole database. Or do a halton sequence to get the rough shape of the overall line before filling in the gaps. (if your line goes from 0 to 1, then you start off running the benchmark at 0, then 1, then 0.5, then 0.25, then 0.75, then 0.125, 0.625… always filling in the largest gap between the previous numbers) I ended up removing that for the open source version because even though it used to be the default, I always ended up turning it off. Too complicated. Better to just run the benchmarks in sequence.

I also have a “Normalize for Memory” checkbox where I barely remember what that feature even did. I think it was something to do with hash tables and trying to be fair to hash tables with different amount of memory overhead. (it’s easy to have a fast hash table if set the max_load_factor to 0.25) Or something like that. I think this feature still works.

4. Code and License

The code is available here under the MIT license.

I ship the benchmark library with two examples:

1. Memory benchmarks which you can use to measure how fast the memory is on your machine
2. Heap benchmarks

The second one has a fast implementation of pairing heaps, not that those get used by many people. (I had one time where I absolutely needed a node-based heap, and I noticed that you can safely eliminate one of the two passes in merge-pairs) It also has a fast quaternary heap, which might just be the fastest heap out there. I haven’t done the work to confirm that, I was going to do that for a future blog post, but who knows when I’ll get around to that.

The way to use the library is to add another executable, following those examples. This means it’s more of a “framework”, not a “library”, meaning it’s expected that you plug your code into this framework, not plug this library into your code. I know this isn’t good, but I think copy+paste is fine for this. Just make a copy of the benchmarking library, make a copy of your code, and create a new executable. Then do your experiments in that and when you’re done, copy the results back. There is no good workflow yet since it’s a library written by me for me. I think if you have something self-contained like a hash table or a sorting algorithm, you can easily follow the examples.

1. Or anything really. I believe that if you are serious about doing a good job at something, you will eventually write a GUI for it. See e.g. GDB vs commercial debuggers, or almost all build systems. ︎

float rough_float_multiply(float a, float b) {
    constexpr uint32_t bias = 0x3f76d000;
    return bit_cast<float>(bit_cast<uint32_t>(a) + bit_cast<uint32_t>(b) - bias);
}

We’re casting the floats to ints, adding them, adjusting the exponent, and returning as float. If you think about it for a second you will realize that since the float contains the exponent, this won’t be too wrong: You can multiply two numbers by adding their exponents. So just with the exponent-addition you will be within a factor of 2 of the right result. But this will actually be much better and get within 7.5% of the right answer. Why?

It’s not the magic number. Even if you only adjust the exponent (subtract 127 to get it back into range after the addition) you get within 12.5% of the right result. There is also a mantissa offset in that constant which helps a little, but 12.5% is surprisingly good as a default.

I should also say that the above fails catastrophically when you overflow or underflow the exponent. I think the source paper doesn’t handle that, even though underflowing is really easy by doing e.g. 0.5 * 0. It’s probably fine to ignore overflow, so here is a version that just handles underflow:

float custom_multiply(float a, float b) {
    constexpr uint32_t sign_bit = 0x8000'0000;
    constexpr uint32_t exp_offset =    0b0'01111111'0000000'00000000'00000000;
    constexpr uint32_t mantissa_bias = 0b0'00000000'0001001'00110000'00000000;
    constexpr uint32_t offset = exp_offset - mantissa_bias;
    uint32_t bits_a = std::bit_cast<uint32_t>(a);
    uint32_t bits_b = std::bit_cast<uint32_t>(b);
    uint32_t c = (bits_a & ~sign_bit) + (bits_b & ~sign_bit);
    if (c <= offset)
        c = 0;
    else
        c -= offset;
    c |= ((bits_a ^ bits_b) & sign_bit);
    return std::bit_cast<float>(c);
}

Clang compiles this to a branchless version that doesn’t perform too far off from float multiplication. Is this ever worth using? The paper talks about using this to save power, but that’s probably not worth it for a few reasons:

1. Most of the power-consumption comes from moving bits around, the actual float multiplication is a small power drain compared to loading the float and saving the result
2. You wouldn’t be able to use tensor cores
3. I don’t think you can actually be faster than float multiplication because there are so many edge cases to handle

It feels close to being worth it though, so I wouldn’t be surprised if someone found a use case.

But there is still the question of why this works so well. The mantissa is not stored in log-space, it’s just stored in plain old linear space where addition does not do multiplication. But lets think about how to get the exponent from the mantissa.

In general how do you get the remaining exponent-fraction from the remaining bits? This is easier to think about for integers where you can get the log2 by determining the highest set bit:

log2(20) = log2(0b10100) ~= highest_set_bit(0b10100) = 4

The actual correct value is log2(20)=4.322. The question we need to answer is: How do you get the remaining exponent-fraction, 0.322 from the remaining bits, 0b0100?

To make this work for any number of bits we should normalize the remaining bits into the range 0 to 1, which in this case means doing the division 0b0100/float(1 << 4)=0.25. (in general you divide by the highest set bit, which you already had to calculate for the previous step)

After we brought the numbers into the range from 0 to 1, you can get the remaining exponent fraction with log2(1+x). In this case it’s log2(1+0.25) = 0.322.

If you plot y=log2(1+x) for the range from 0 to 1 you will find that it doesn’t deviate too far from y=x. So if you just want an approximate solution you might as well skip this step.

And then the mantissa is already interpreted as a fraction on floats, so you also don’t have to divide. So the whole operation cancels out and you can just add.

You still need to handle

1. The sign bit
2. Overflowing mantissa
3. Overflowing exponent
4. Underflowing exponent

Number 1 and 2 also work out naturally using addition because of how floats are represented:

• Since the sign bit is the highest bit, overflow is ignored so addition is the same as xor, which is what you want
• When the mantissa overflows you end up increasing the exponent, which is what you want. (e.g. 1.5 * 1.5 = 2.25, which has a higher base-2 exponent)

Number 3 can be ignored for most floats you care about.

Number 4 is the one that required me to write that more complicated version of the code. It’s really easy to underflow the exponent, which will wrap around and give you large numbers instead. In neural networks lots of activation functions like to return 0 or close to 0 and when you multiply with that you will underflow the initial function and get very wrong results. So you need to handle underflow. I have not found an elegant way of doing it because you only have a few cycles to work in, otherwise you might as well use float multiplication.

The last open question is that mantissa-adjustment: You can see in the graph above that the approximation y=x is never too big, so by default you will always bias towards 0. But you can add a little bias to the mantissa to shift the whole line up. I tried a few analytic ways to arrive at a good constant, but they all gave terrible results when I actually tried this on a bunch of floats. So I just tried many different constants and stuck with the one that gave the least error on 10,000 randomly generated test floats.

So even though this is probably not useful and I haven’t found a really elegant way of doing it, it’s still neat how the whole thing almost works out as a one-liner because so many things cancel out once you approximate y=log2(1+x) as y=x.

edit: Since people liked playing around with this, I have uploaded my test code here.

Memory Coalescing

If you have multiple threads operating on an array in C++, you probably want to iterate like this:

std::vector<T> vec = ...;
size_t per_thread = vec.size() / num_threads;
T * my_slice = vec.data() + per_thread * my_thread_i;
for (size_t i = 0; i < per_thread; ++i) {
    do_something(my_slice[i]);
}

Meaning each thread iterates over a contiguous chunk of memory. In CUDA this is going to be slow because you want the threads to load memory together. So if thread 0 loads bytes 0 to 15, then you want thread 1 to load bytes 16 to 31 and thread 2 to load bytes 32 to 47 etc. So the loop instead has to look like this:

T * data = ...;
size_t num_elements = ...;
for (int i = my_thread_i; i < num_elements; i += num_threads) {
    do_something(data[i]);
}

This is called “memory coalescing” where adjacent threads use adjacent memory. On a loop with a small body (dot product) this is 3x faster.

Most of the Performance is now in Specialized Hardware

Many years ago Sean Parent presented a graph that breaks down where the performance is in a modern PC. I’m reproducing it with current numbers here:

What we see here is the breakdown of theoretical performance in a PC with a Ryzen 9950X and a RTX 4090. The overall theoretical performance is ~95 TFLOPS. These are theoretical, so for example the single-threaded CPU performance is just “5.7 Ghz * 4 instructions per cycle = 22.8 GFLOPS”. That’s the blue line that you can’t see because it’s such a tiny fraction. If you use all 32 threads and AVX 512 you can multiply that performance by 32*16 = 512 to fill up the red and yellow parts of the graph. But if you really want performance, you need to use the GPU which gives you the green part of the graph.

But while these are current numbers, it’s missing most of the GPU performance. The GPU now has specialized hardware for machine learning and for raytracing. When you add those to the graph you get current performance.

This is the same graph plus specialized hardware. For the tensor core I chose the TFLOPS when doing BF16 matrix multiplies. Meaning it’s not exactly a fair comparison because it operates on lower precision (the output is in 32 bits though) but everyone uses this for matrix multiplies and thinks it’s fine.

The point is that now most of the performance in your PC is in specialized chips. If you’re just writing straightforward CUDA code, you’re leaving most of the performance on the table. The graph gets even more lopsided when looking at a deep learning GPU like the H100:

Note how the x-axis now goes above 2000 TFLOPS. If you’re not using tensor cores, the GPU is sitting >90% idle. This is changing the algorithms that are used in deep learning. If algorithm A can just do bigger matrix multiplications to get higher quality results, and algorithm B can achieve better quality results by cleverly doing lots of little pieces of work, people will choose algorithm A.

Different Kinds of Memory

Memory is more complicated in CUDA, but with my limited understanding so far I think of CUDA as having three different types of memory:

1. Normal memory
2. Shared memory (faster)
3. Registers (fastest)

Registers are particularly weird. One thread block has 65536 registers, meaning you can store 256k bytes of data in registers. Which is more than you can store in shared memory. I was trying to understand how some cuDNN kernel could possibly be as fast as it was, when I realized that they keep a particular matrix entirely in registers where each thread holds a small part of the matrix.

You get some control over how many registers you have. You can have up to 1024 threads per thread block, meaning you get 64 registers per thread by default. But you could launch fewer threads and get proportionally more registers per thread. If you need, say 150 registers because you want to cache some data, you divide 65536/150 which tells you that you can use 436 threads.

But you’re still just writing in C++ which doesn’t make it easy to say “keep this data in registers.” The best way I found to do this is to keep a fixed-size array on the stack and then use “#pragma unroll” in every single loop that uses that array. The loop needs to be unrolled because every unrolled iteration of the loop needs to refer to different registers.

Shared memory was straightforward in comparison. It allows you to dedicate some cache space for a specific purpose, and the data is shared between threads. So you can use it for two purposes:

1. To communicate between threads
2. To load data more quickly: If you want to load 512 floats and you have 512 threads, every thread can load one float into shared memory. So you don’t even have to loop.

Sharing is ~Free Within a Warp

This one was a delight when I saw code doing this for the first time: A warp is 32 threads that share one instruction pointer. They all do the same thing at the same time. So if you e.g. parallelize a dot product, the 32 threads of the warp can sum their results to get the overall result in five steps, using a parallel sum algorithm:

On a CPU this algorithm is impractical because the overhead of keeping the threads in sync is too high. But on a GPU they just are in sync, so sharing is literally five steps:

__device__ float add_warp(float x) {
    static constexpr const unsigned all = 0xffffffff;
    x += __shfl_xor_sync(all, x, 1);
    x += __shfl_xor_sync(all, x, 2);
    x += __shfl_xor_sync(all, x, 4);
    x += __shfl_xor_sync(all, x, 8);
    x += __shfl_xor_sync(all, x, 16);
    return x;
}

I verified that this compiles down to two instructions each. This compiles to 5 SHFL.BFLY instructions plus 5 FADD instructions for the addition. There are no secret locks or barriers here.

This only works within a warp (32 threads). For a thread block, up to 1024 threads, you can use shared memory, which requires using barriers because the threads won’t automatically be in sync. If you need more threads than that and want to share data between them, don’t. (you’ll often want many more threads, you just can’t share data. You need to write out the result to memory and then launch a new thread to work on the new data)

Parallelism First

My intuition for how many threads to use was wrong by a lot. If you’re iterating over some data and have to do several non-trivial things to it, it’s probably best to launch one thread for each of the things you want to do. It’s tempting to say “this thread already loaded all the relevant data, it can just do a bit of extra work” but in CUDA it’s better to launch a separate thread for that extra work, even if they both have to load the same data. It’s much cheaper for them to synchronize and share their data than it would be on a CPU.

When I ran Nsight Compute on the first couple versions of my code, the feedback that came back could always be summarized as “you’re barely using the GPU, make it more parallel.”

This also means that you often want to pull your algorithm apart. If there is one part that can run massively parallel (across tens of thousands of threads) and one part that has limited parallelism (say only a few hundred threads) then it’s probably worth to launch those as separate kernels to benefit from the massive parallelism on part of your problem, even if that part is only a small part.

So whenever you try to solve a problem, the first question should not be “how can I make this fast?” but “how can I run this in parallel?” After you solve that, worry about making the parallel code fast.

Conclusion

Writing CUDA definitely has a different feeling. It feels more puzzly because it’s so easy to accidentally only use 1% of your GPU. It actually reminds me of TIS-100, especially the trick of distributing data in the registers of multiple threads. But instead of managing a small number of chips you have to figure out how to generate work for tens of thousands of threads. My mental model is that you’ve got a bunch of container ships that can travel at 10% of the speed of light. You’re using them to ship goods around the world. They’re very fast so most of the work is in setting up your harbors so that you can load and unload these container-ships in fractions of a second so that it can sail to do the next thing. It’s not easy to feed these beasts, but if you do it right you can do huge chunks of work in almost no time.

Big plus: Languages that I don’t use as often

I don’t often write SQL statements. I can obviously write the simple ones, but SQL is a language that has all the features you could ever possibly want, and I don’t know how to use them and don’t know how to google for them. So I ask a LLM. Similarly for javascript/css/html programming. I used to hate doing web frontend work, now it’s not so bad because LLMs can help me get out of the tricky edge cases.

I have also used LLMs to translate functionality from one language to another. E.g. if I know what a function is called in C++ but I can’t find an equivalent one in the standard library of another language, an LLM will often do a decent first pass of rewriting the C++ function in the other language.

Small minus: The code is overly generic

LLMs should probably ask for more information more often. At the moment they’re a highly motivated programmer who doesn’t know enough but who can provide you with a piece of code that should work in most contexts. It won’t tell you that though, it’ll pretend that it gave you a good solution.

So for example when I ask it “I have this complicated SQL statement but I need to bring in information from one more table” it’ll give me back a nested select statement. I have to prompt it again and ask “isn’t there a way to do this with a join?” before it tells me that there is a kind of JOIN statement that does exactly what I want. Similarly for javascript it likes to just register global callbacks that listen to every mouseenter event on any element in the page.

This works fine for most languages. It leads to problems in strict languages like Rust. When someone asks me for help in LLM-assisted Rust code, usually we first have to ask “but what is this actually trying to do” a few times to undo the unnecessary genericness (RefCell) of the LLM code.

It also is going to lead to problems in the long term where you have a lot of code that’s overly broad. When you have too many pieces of code that register broad callbacks “just in case” or do nested SQL statements “just in case” you can’t build a mental model of what actually happens in your code base.

Neutral: It can fix its own mistakes

One thing I keep on forgetting to do is to ask it to fix its own mistakes. After writing the above, I realized I could just ask it how to avoid the global javascript callbacks. It told me about “mutation observers,” which are a kind of global observer that allow me to attach my other observers to only the nodes that I want. Which is better, maybe?

In general I find that you can ask it a few times “this part bothers me, can you do it better?” to get better quality. I wish it just did this on its own, but it is good that it’s happy to rewrite it for you as often as you ask. (though if you ask three times and there is no improvement, that means the LLM just can’t do what you’re asking)

Big plus: It can help you get unstuck

LLMs are undaunted. You can ask them any tricky question and they’ll provide an answer. Sometimes the answer is not bad and you immediately see how to make progress. Often the answer is pretty bad, but that doesn’t mean it’s useless. It still helps in at least two ways:

• Rubber duck debugging. LLMs are pretty good for this. Often it helps me to just explain the problem, because it forces me to actually clearly state the problem. Also if the LLM comes back with an answer that’s totally unrelated, I have to go back and be even more clear. And then once I can clearly state the problem, the solution sometimes presents itself.
• They provide another perspective. It’s not always a great perspective, but when you’re solving tricky problems you have to look at them from different angles, and LLMs are great at providing more angles. Even if I don’t go with any of the ideas that the LLM provided, it often helps me think of a good approach. I especially appreciate when the LLM provides me with something that’s simpler than what I thought of, which it does surprisingly often.

Small minus: It does not hold back even when producing garbage

E.g. there is this infamous example:

This is mostly nonsense where they wrote something that is much too complicated and then used AI to do… something with it. Any experienced programmer would have stopped halfway through writing this and thought “no, this is getting too messy, there must be another way.” But an AI will happily write this for you, and then you have to unhappily live with it.

Big plus: It knows all algorithms and libraries

Even the first early version of ChatGPT, which produced terrible code, was impressive when it came to one area: It understood what you wanted in a way that no search engine could. LLMs have only gotten better there. I love that I can ask “I have a problem that’s shaped like this and it feels like there should be a data structure or algorithm that could help here” and it’ll understand what I want and point me towards relevant algorithms. The first answer is almost never what I want, but I also love that I can have a conversation. It usually goes like this:

me: I have the following problem: … What algorithm or data structure can help with that?

LLM: Have you considered X or Y?

me: Well yes, obviously those are the first things I thought of, but they don’t work because of this part of the problem that I just told you about.

LLM: Oh I’m so sorry, you’re right. How about Z then?

me: I had heard about Z before but don’t really know about it. I thought it had the following problem: …?

LLM: Oh that can be overcome by doing Z* or with this other approach

And back and forth like that a few times. I love that it just knows this stuff and can point me at all the interesting things that exist. I also love that sometimes the first answer is “no there is no good algorithm here because this is actually really hard and you probably want to just go with this simple, partial solution that’s at least easy to understand.”

Small minus: It read the experts but it’s not an expert itself

For any algorithm there is the simple straightforward thing that everyone uses, then there is slightly more complicated solution that is useful sometimes, and then there are a dozen really complicated solutions that only exist because someone needed to publish a paper and they found one specialized benchmark where their solution artificially looks good. Nobody actually uses them.

Much of the value of experts is that they can tell you which things you have to pay attention to and which things you can safely ignore. LLMs can not be trusted when it comes to that. They will believe the claims of the paper authors and confidently tell you all the benefits that certain methods have. If you believe the LLM, you’ll have to spend a lot of time, possibly days, rediscovering all the reasons why nobody is using this algorithm in practice.

The LLM makes this mistake in all directions. It will never tell you “I don’t know” or “I’m not confident.” Instead it will tell you confidently that the simple solution is good when you should use something more complicated, and it will also confidently tell you that the complicated solution is good when you should never be using it. You just have to take that into account.

Big plus: It’s competent for simple tasks

This is obvious but it’s worth pointing out. The output of LLMs is usually high quality. If you ask it to explain, say “how do heat pumps work?” and maybe ask some follow up question, it’ll do a better job than 99% of the population. This is also true of code. Of course most of the population doesn’t program so that 99% number is irrelevant, but for simple problems it does a better job than many professional programmers would. Sure, there will be bugs and you may have to adapt the code (depending on how you asked) but it’ll be competent. LLMs would pass coding interviews.

And while I could usually nitpick and find improvements, there are a lot of places where you have to solve the kinds of simple problems that LLMs are good at solving, and where it’s fine to use code at LLM quality, unmodified.

Small minus: I have no idea how to use LLMs for maintenance

Unfortunately I don’t spend most of my days writing code. I spend most of my days maintaining code. Meaning debugging and refactoring and adding small features to existing programs. LLMs just don’t fit into that. Maybe that’s just expected because it’s “generative AI” and if I don’t need to generate much code, it can’t help.

It sure would be nice though if I could point it at a directory of files and say “I need to change the following types, which will change some interfaces. Can you update all necessary files and point out any place where I need to pay attention?” But I currently would have no confidence that it would do a good job at that.

You need to be more of a critic, editor and reviewer

So when you use LLMs to generate new code, you mostly need to be a critic with good taste. You need to know when the quality of the LLM is appropriate. When is it OK to use overly generic code? Can you voice what bothers you and ask it to do better? Usually you have to ask the question “but what do we actually need to do here” a few times.

When you ask for advice on algorithms, the LLM will enthusiastically tell you that something is a great idea, and when you tell it that it’s not, it will enthusiastically tell you that you’re right and that it was a terrible idea. So you can’t rely on it for critical thinking. You can only use it to enumerate options.

When working with junior devs who use LLMs, code review is slightly easier because on average they write better code, but there are new failure modes. They don’t have the necessary experience to know when to accept the output of the LLM and when to doubt it. You need to watch out even more for code that was written without a mental model of how the existing code works.

On average LLMs are a clear positive. They’re not good enough yet where they’ll make you hugely more productive, but they’re already good enough where you’d miss out if you weren’t at least using them occasionally. Use one of the paid options, they’re much better than the free options. I hear Claude Opus is currently best. (I haven’t done comparisons) You just have to get experience with where they’re good and where they’re bad, and I’m hoping that sharing my experience can help you with that.

It’s just an arbitrary graph with arbitrary numbers, the point is all the layout decisions that happened here: E.g. “Long First Label” extends to the left and pushes everything else over to the right by a bit. If you aren’t organized about how to express your transforms, your code ends up with lots of arbitrary offsets and multipliers. You can’t even calculate where to draw the labels on the y-axis without including an offset for potentially long labels on the x-axis. (and long labels on the y-axis can push over the x-axis, too. Uh-oh) Your first choice for visualization should probably be an existing tool (like I used to generate the graph above) but surprisingly often you’ll want to do something custom, and then you have to worry about transforms.

Game programmers have to do complicated transforms all the time, so they had to get organized about this and the result is the transform matrix. It’s remarkably simple and every programmer should probably know it, just to appreciate its beauty. There are two tricks to transform matrices:

Trick 1: Add an Extra Column for Positions

Matrices are not an obvious choice for positioning of things. It’s easy to see how to scale things with matrices, and rotations are doable by putting the sin() and cos() of the angle in the right places. But how do you do positions? Matrices can only multiply numbers, so how do you add 10 to all x coordinates? You need one more column. For 2D rendering you need a 3×3 transformation matrix. For 3D rendering you need a 4×4 matrix. Then when multiplying your matrix with a position, you use instead of just .

This is how you can add numbers using matrices. Occasionally it’s also useful to multiply with instead, which just get the rotation and scaling parts, no translation.

Trick 2: Compression through Associativity

Matrix multiplication is associative: . And, equally importantly, square matrices don’t grow after being multiplied. If you multiply two 3×3 matrices together, you get another 3×3 matrix. Meaning sizeof(a*b) == sizeof(a). This allows you to collapse multiple transform matrices into one.

For example in a video game you might express animation data as a hierarchy of matrices. (this used to be standard, now there are slightly better techniques, but they use the same “compression through associativity” trick so I’ll just stick with matrices for now) So when you animate a fingertip, your matrix would contain a translation plus a rotation, and maybe a scaling factor. But that matrix only tells you how the tip of the finger should move relative to the middle segment of the finger. And that middle segment only has a matrix that tells it how to move relative to the root of the finger, and so on all the way up the arm and down the spine until you get to the reference matrix that moves the whole body.

When rendering you have to determine the position of every vertex of every triangle on the body, so that’s going to be a lot of matrix multiplications. Instead of walking up that chain of matrices for every vertex, you collapse all the matrices down. If you have 100 matrices for your character’s skeleton, you’ll pre-multiply those 100 matrices in a topological-order loop to end up with one matrix for each bone that contains all of its parent matrices baked in. Meaning the matrix for the fingertip has in it the matrix for the middle joint of the finger, the wrist, elbow, shoulder, all the way to the reference bone. All of those translations and rotations can be collapsed down into a single 4×4 matrix that does all of the work in one step.

These matrices can be extremely complicated but it doesn’t matter because you always end up with 16 numbers in the end that contain all the collapsed information, leaving only transforms that didn’t cancel out. (and you don’t have to figure out what cancels out, it just happens)

My favorite example of this is shadow mapping. The fastest technique for getting accurate shadows is to draw the whole scene twice: Once from the perspective of the camera, and once from the perspective of the light. In both render passes you write the distance from the camera to the rendered surface into a buffer, the so-called z-buffer.

(picture from Wikipedia user -Zeus-, CC BY-SA 3.0)

Once you have a z-buffer for the camera and a z-buffer for the light, you can figure out whether a pixel in the camera-view can see the light or not. Just look in the light’s z-buffer and see if there was a closer surface blocking the light. But how do you figure out which pixel to look at in the other depth buffer? After all it was rendered from a whole different perspective.

Well the camera transform is encoded as a matrix. The perspective settings (field-of-view, aspect ratio, …) are also encoded as a matrix. The light cone is encoded in a matrix. All you have to do is pre-multiply all the relevant matrices for your camera, invert the result, and multiply with the light matrix. The result is a single 4×4 matrix which will transform any point that was rendered from the camera to the corresponding pixel coordinate in the z-buffer that encodes the distance to the light. If the value that you read in the light’s z-buffer is smaller than the z-value after the multiplication, you’re in shadow because there was some other surface that was closer to the light. It’s crazy complicated, but it’s just a 4×4 matrix multiply in the end.

Using this for 2D Rendering

Ok but how do you use this for simple things? The nice things is that transform matrices are really simple at the core and simple operations remain simple. The main convenience is that you can always operate in a local frame and that you don’t have to care about the rest of the world.

E.g. when drawing the lines in the graph at the beginning of this blog post, you shouldn’t have to do any extra math to figure out where each vertex of the line should end up at. A single matrix multiply should be enough. That matrix can contain all the offsets and scaling that you need to account for how big the canvas is, how big the labels are, what the range of your x and y-values were etc.

You still need to do the math to calculate those offsets, but the important part is that all the setup functions take in and return matrices. So here is a potential interface for the labels:

fn label_offsets(transform_so_far: &Matrix3x3, x_labels: &[string], y_labels: &[string]) -> Matrix3x3 {
    // find the longest y_label and calculate the length of the half of the first x_label
    // the longer of those two is the offset to the left. you may also want to add an offset
    // to the right if the last x_label is long.
}

Meaning you pass in the matrix that was calculated so far. So for example if you want to draw small-multiples, you can just pass a different matrix for each and nothing else has to change. Then you do whatever logic that you need to do to figure out what the resulting offsets need to be, and you return back out a new matrix that will be used by the rest of the rendering. You can decide what the format of that matrix should be. I would choose it so that you can calculate the positions for the x-labels by multiplying it with etc. and you can calculate the positions for the y-labels by multiplying it with etc. If that is awkward for drawing the lines (because the y-values in this example are in the range [0,100]), you can always add in one more scaling matrix afterwards. Or return two different matrices, one for label-drawing and one for line-drawing. These things are easy once you’re dealing with matrices because you can encapsulate so much information in a single object that can be passed around. (good luck trying to have different return values with custom hacked offset math)

Another thing that’s easy with matrices is scrolling, panning and zooming. Imagine implementing google maps, or just something that has scroll bars: You need one matrix to get the area within the page where the map should be rendered, (subtracting out any side bars or top bars) and you need a second matrix that contains the current pan/zoom position. You can then multiply those two matrices together to figure out where to draw each tile.

Oh and a last trick: If it ever bothers you that the y-axis in the HTML canvas goes down, (e.g. because the y-axis always goes up in graphs like the one above) you can flip that by chaining in a translation matrix and a flip on the y-axis so all your own math can assume that the y-axis goes up. And no other code has to care that there are now two more matrices in the chain because they all just see nine floats.

Tricky Parts

There are a few tricky parts with matrices:

1. When drawing with the HTML canvas you may be tempted to use its transform matrix API. You probably don’t want to do this because it scales everything, including the width of lines and the size of text. Instead you usually want to multiply the coordinates yourself and draw text at normal sizes.
2. Matrices are not commutative. . Meaning if you translate first and then rotate, that is different from rotating first then translating. This is a feature, not a bug, but it can be tricky and requires thinking about what you actually want to do.
3. As a follow up for the above: There are two different ways of doing everything. You either multiply with a row vector on the left, or a column vector on the right. Whichever you choose means that “translate first then rotate” means that the rotation matrix has to be on the right or on the left of the translation matrix. (and the matrices also end up transposed) For some reason the standard way of doing this is backwards so that you have to read right-to-left. If you write your own, you’re free to choose. Oh and to make it more confusing there are two different ways of thinking about it: Are you moving the object, or are you moving the coordinate system? If you’re moving the object then “translate first, then rotate” means the object will orbit around the origin. If you’re moving the reference frame then “translate first, then rotate” means the object will rotate around the given point. (how do you render a planet that should orbit the sun and rotate around its own center? rotate then translate then rotate again) There are long arguments about which one is the sane choice, which I won’t get into here. Just prepare to be confused whenever you switch to a new library/framework because everyone does this differently.

Generalizing

While matrices are probably the right choice to get you started, you can also use different solutions if you learned the right lessons. I’m actually not sure if you want to use matrices for 2D layouts. You may be better off using a custom type that just contains the current bounding-box in integer coordinates plus font size. (though if your matrices are sane, it should be easy to recover the current bounding box: Just multiply the matrix with the coordinates of the four corners) If you do write a custom type, it’s important that you learn the lessons from transformation matrices. Meaning you need the “compression through associativity” trick. You want objects that encapsulate all of the state that you need for layout information, and you want to be able to pass those objects around, and those objects need to always have the same size.

In video games there are many different ways to express transforms. Matrices were the best choice for a long time, but the current hotness is to use geometric algebra or something derived from geometric algebra. (quaternions or dual quaternions) The important parts are still there and they work better for animation: It’s hard to lerp matrices. One nice thing about geometric algebra is that it works in any number of dimensions, so you can also use it in 2D. It’s just much more complicated to explain and matrices are probably the better choice to get started. They will clean up your code a lot.