Probably Dance

I can program and like games

Finding the “Second Bug” in glibc’s Condition Variable

I continue to have no time for big programming projects, so here is a short blog post. Two years ago I looked into a bug in the glibc implementation of condition variables: Sometimes pthread_cond_signal() doesn’t do anything, which can easily hang your program. The bug is still not fixed, partially because a mitigation patch was available right away that seemed to make it go away. Except that people kept on showing up in the bug report saying that they still hit the bug sometimes, raising the suspicion that there might be a second bug. I finally got around to looking into this. I found that the mitigation patch only helps a little, it’s still the same bug, and the patch I submitted (unreviewed, don’t use yet) would actually fix it.

Read the rest of this entry »

Sudoku Variants as Playful Proof Practice

Doing mathematical proofs is kinda fun. Unfortunately they only make you do a few fun ones in school, then they get frustrating and tedious. So I have long been looking for a game that is about doing mathematical proofs. Euclidea was good, but eventually runs into the same problem as the hard proofs you do in school, so I never finished the game. But recently a lot of hard Sudoku variants have come along that feel exactly like doing a mathematical proof, but are designed to be fun.

The Sudoku world is currently going through an explosion of creativity and innovation, something which I have called a “Treasure Hunting System” before. It’s quite joyful to watch, especially since I never really got into Sudokus before. I found that when Sudokus get hard, they get more tedious instead of getting more interesting. They’re only fun until you get good enough to attempt the tedious ones. At least that’s what I thought until Youtube kept on recommending the Cracking the Cryptic channel, which currently features mostly Sudoku variants, and those are much more interesting.

Read the rest of this entry »

Reasons why Babies Cry in the First Three Months, How to Tell The Cries Apart, and What to Do

I have twin daughters that just turned three months old. I decided to write up the list that I wish I had before they were born. Just reasons why they cry, how to tell the cries apart, and what to do in each case. Yes it’s hard to help babies because they cry for everything, but you can definitely tell the difference between an angry cry (“feed me”) or a pained cry (“I scratched myself”) or a sad cry. (“why did you wake me up?”) You can’t fix em all, but you can do a good amount.

Read the rest of this entry »

Automated Game AI Testing

In 2018 I wrote an article for the book “Game AI Pro 4” called “Automated AI Testing: Simple tests will save you time.” The book has since been canceled, but the article is now available online on the Game AI Pro website.

The history of this is that in 2017 there was a round table at the Game Developer Conference about AI testing. And despite it being the year 2017, automated testing was barely even mentioned. It was a terrible round table. A coworker who sat in the audience with me said to me that I could have given a better talk because I had invested a lot of work into automated testing. So next year I submitted a talk about automated AI testing and was rejected. But they asked me to write for the book instead. Now the book is canceled, too. A copy of the article is below, with some follow ups at the end. It’s written for people who have never done automated testing, like the AI programmers at the round table. But I think the core trick of doing fiber-based control flow, that can wait for things to happen, could be widely useful:

Read the rest of this entry »

C++ Coroutines Do Not Spark Joy

C++20 added minimal support for coroutines. I think they’re done in a way that really doesn’t fit into C++, mostly because they don’t follow the zero-overhead principle. Calling a coroutine can be very expensive (requiring calls to new() and delete()) in a way that’s not entirely under your control, and they’re designed to make it extra hard for you to control how expensive they are. I think they were inspired by C# coroutines, and the design does fit into C# much better. But in C++ I don’t know who they are for, or who asked for this…

Before we get there I’ll have to explain what they are and what they’re useful for. Briefly, they’re very useful for code with concurrency. The classic example is if your code has multiple state machines that change state at different times: E.g. the state machine for reading data from the network is waiting for more bytes, and the code that provides bytes is also a state machine (maybe it’s decompressing) which in turn gets its bytes from another state machine (maybe it’s handling the TCP/IP layer). This is easier to do when all of these can pretend to operate on their own, as if in separate threads, maybe communicating through pipes. But the code looks nicer if the streamer can just call into the decompressor using a normal synchronous function call that returns bytes. Coroutines allow you to do that without blocking your entire system when more bytes aren’t immediately available, because code can pause and resume in the middle of the function.

One of the best things the C++ standard did is to define the word “coroutine” as different from related concepts like “fibers” or “green threads”. (this very much went against existing usage, so for example Lua coroutines are not the same thing as C++ coroutines. I think that’s fine, since the thing that was added to C++ could be useful, and there is a good case to be made that the existing usage was wrong) In the standard, a coroutine is simply a function that behaves differently when called multiple times: Instead of restarting from the start on each call, it will continue running after the return statement that last returned. To do this, it needs some state to store the information of where it last returned, and what the state of the local variables was at that point. In existing usage that meant that you need a program stack to store this state, but in C++ this is just stored in a struct.

To illustrate all of this, lets build a coroutine in plain C++, without using the language coroutines:

Read the rest of this entry »

A Logarithm is Just the Number of Digits

If you don’t have a good intuition for how logarithms work, (e.g. what does it mean that happiness scales with the log of income? Or why does an algorithm that runs in log(log(x)) steps always run in 5 steps or fewer?) here is how you can explain it to a third grader: It’s the number of digits (roughly). For example it’s the number of zeros in these:

log_{10}(100) = 2

log_{10}(1000) =3

log_{10}(0.01) = -2

log_{10}(0.001) = -3

For this to work out we have to transition through zero: log(1)=0

If it bothers you that I’m off by one, because clearly 100 has 3 digits, not 2, you can get the actual number of digits by rounding away from 0 to the next integer.

Where it gets complicated is when you have a number between two round numbers:

log_{10}(123) = ?

We can’t just count the number of digits. It’s got to be somewhere between the other two numbers, coming out to roughly 2.09. But lets not worry about those odd cases for now. Where this really helps is when trying to build an intuition for the logarithm rules:

Read the rest of this entry »

Happy Easter! I hid an Easter Egg in Just Cause 4 for You

One of my favorite things to have worked on was the Getting Over It easter egg in Just Cause 4. It was quite popular. Since I love Getting Over It, I decided to make three more easter eggs, one for each DLC. Turns out that was impossibly ambitious, but I did manage to get one out. One of the DLCs contains a second Getting Over It easter egg that nobody has found yet:

I already did a subtle leak of this a while ago, so you can find the coordinates for this on some websites. But I must have been too subtle… Last easter didn’t feel right to do this bigger reveal (I had only recently left Avalanche, plus everyone’s brain was kinda fried thinking about covid) so this easter seems more appropriate. So find the coordinates online, or go looking based on the video. Happy easter egg hunting!

Read the rest of this entry »

Understanding why the CDC Gives the Guidelines that it Does

The CDC continues to issue very puzzling guidelines about the coronavirus. The most recent strange recommendation is that even if you already had covid, you should still get the vaccine. Which… makes no sense?

Let’s assume our goal is to reduce the number of deaths. Currently in the US, something like 26 million people have tested positive for SARS-CoV2, and roughly 440,000 people have died of COVID19. I’m using these terms to make a distinction: Not everyone who gets the virus will get sick, and not everyone who gets sick will die. Let’s be generous and assume that 100 million people got the virus so far, then mortality rate is 0.44%.

What do those same numbers look like for people who already had the virus before? Obviously the first number, the chance of getting the virus, should be roughly the same. But your body has fought this virus (or a very similar virus) before, so your chance of getting sick is much lower. For a long time it was uncertain whether you can get sick a second time at all, but now there are enough confirmed cases. How many of those have died? At least one, who was on chemotherapy at the time. Let’s estimate the number at 10, which would get us to a mortality rate of 10/26,000,000 = 0.000038%.

Should we really be giving people with that second risk the vaccine when not everyone in the first group has had a vaccine yet? Either the CDC worked with different numbers that are ten thousand times bigger, or their goal is not to reduce the number of deaths. What could that other goal be?

Read the rest of this entry »

Looking for Voter Fraud (in old elections) with Data Visualization

The 2020 US election is finally over, and all the election excitement of the last week reminded me of something I had been meaning to look into: Sergey Shpilkin’s data visualizations that clearly show fraud in Russian elections.

I generated the same visualizations for all US presidential elections from 2000 to 2016. The result is that I can’t find any evidence of fraud in any of those elections. But the visualizations show clear evidence of voter suppression of democrat voters. On closer inspection that turns out to be the effects of the electoral college system, which leads to a very interesting conclusion: You might already know that if the president was elected by popular vote, the US would only have had four years of republican presidencies from 1992 to 2024, with the rest being democrat. But these visualizations suggest that just looking at the popular vote actually underestimates the distortion of the electoral college. It also acts akin to voter suppression of democrats, without which national politics would swing even stronger to the left than the popular vote suggests. But lets start by looking at Sergey Shpilkin’s work:

Read the rest of this entry »

Using TLA+ in the Real World to Understand a Glibc Bug

TLA+ is a formal specification language that you can use to verify programs. It’s different from other formal verification systems in that it’s very pragmatic. Instead of writing proofs, it works using the simple method of running all possible executions of a program. You can write assertions and if they’re not true for any possible execution, it tells you the shortest path through your program that breaks your assertion.

In fact it’s so pragmatic that it even allows you to write your code in a language that looks similar to C.

I recently heard of a bug in the glibc condition variable implementation and since I had used TLA+ before to verify my own mutexes and condition variables, I thought I would investigate. Can you use it to find this bug in real-world complex code? Yes you can, barely, and it wasn’t easy, but it gives me hope that program verification is getting really good and is already able to deal with big and messy code:

Read the rest of this entry »