Code for this episode can be found here. I have not added any more code to the engine, but the client now has two features of great use to me; pressing space toggles whether the simulation is running or paused, and pressing “s” takes a screenshot and saves it to the desktop.

Last time on FAIC I got totally off on tangents about asymptotic performance without answering the question “what is the asymptotic performance of our naive Life algorithm?”

Asymptotic performance, as we’ve discussed, is about finding a function that relates problem size to cost, so the first thing we have to do is measure problem size.

In the episodes so far I’ve been saying a lot of “consider a 32 by 32 grid” or “consider a 256 by 256 grid” and so on. The reason why I want square grids whose sizes are powers of two will become apparent later in this series, but even without the good reason that is coming up, considering grids in these sizes enables a concise way to describe them.

I’m going to refer to a square grid where the side is a power of two as a “quad”. In episode 2 I defined the “scale” of a quad as the power of two that is the length of the side. That is, a quad of “zero scale” is a 1×1 grid, a quad of “one scale” is a 2×2 grid, and so on. In fact, we can probably just omit the “scale” much of the time and just say a “six quad” is a 64×64 grid. Or, put another way, the number of cells in an n-quad is 4ⁿ.

Through this series I’m going to use two different ways to consider the size of a grid: either the total number of cells in a grid, or the “quad scale”, which is the base-4 log of the cell count. This might seem a little silly now when we’re considering 256×256 grids — 8-quads! — but it will make more sense later, I promise.

What then are the costs we should consider when evaluating the asymptotic performance of an algorithm? Typically there are two: memory usage, and time to compute the new state after one tick. (Later on in this series we’ll consider a more sophisticated way to represent number of elapsed ticks that is analogous to the way we represent grid size by quad scale, but we won’t need that for a while yet.)

We are specifically not looking to measure the time spent drawing to the screen. Different algorithms have different raw performance when drawing to the screen, of course, but for the most part, because of the way I’ve structured the interface between the client and the engine, the cost is linear in the number of live cells in the portion of the board being drawn. That said, I will point out performance issues that affect screen drawing time.

Without further ado, let’s look at the performance of our algorithm. Let’s suppose the grid is square and has a total of n cells in it; that is, n is width times height.

bool[,] newCells = new bool[width, height]; // O(n)
for (int y = 0; y < height; y += 1)  // O(h) iterations
  for (int x = 0; x < width; x += 1) // O(n) iterations total
  {
    // O(n) total calls of constant cost each:
    int count = LivingNeighbors(x, y); 
    // O(n) total operations of constant cost each:
    newCells[x, y] = count == 3 || (cells[x, y] && count == 2);
  }
  cells = newCells; // O(1)

• Constructing a new array is O(1) but initializing the n bytes in the array to zero is O(n).
• In the outer loop we initialize y once. We compare y against height and increment y “height” times.
• In the inner loop we initialize x “height” times, and we compare and increment it n times.
• Each call to LivingNeighbors calls IsValidPoint eight times, which does some comparisons, and then we do some array accesses. Each one of these operations is O(1) but we do them once per cell, so the total cost is O(n).
• The comparisons and assignment are each O(1) but we do them n times, so the total cost is O(n)
• Assigning an array reference to a field is O(1) no matter the size of the array.

Add it all up. We have a bunch of O(1) costs, we have a bunch of O(n) costs, and we have an O(height) cost.  But we’re assuming that height is the square root of n, so what we have is:

O(1) + O(√n) + O(n)

There are two important conventions in asymptotic analysis — and are the reason it is “asymptotic”. First, we ignore constant multipliers — two O(1) costs are treated as a single O(1) cost. And second, we can ignore “small costs” when there are large costs.

Here we see that cost is growing linearly with problem size, and the smaller components due to the constant-cost factors and the square-root-cost factors will be dominated by the linear factors as the program size increases. We therefore summarize this as an O(n) algorithm, where again, n is the number of cells.

If we were giving the cost of this algorithm as a function of quad scale, then it would be an O(4^s) algorithm, which should make sense; the number of cells grows extremely rapidly as we scale up a quad, and our cost is linear in the number of cells.

What about the drawing algorithm?

long xmin = Max(0, rect.X);
long xmax = Min(width, rect.X + rect.Width);
long ymin = Max(0, rect.Y - rect.Height + 1);
long ymax = Min(height, rect.Y + 1);
for (long y = ymin; y < ymax; y += 1)
  for (long x = xmin; x < xmax; x += 1)
    if (cells[x, y])
      setPixel(new LifePoint(x, y));

The best case is that the rectangle we are asked to draw is outside the fixed size of our grid; in that case it is O(1). But the typical case is that we are asked to draw the entire grid; we do one array lookup per drawn grid cell, and so if we have n grid cells drawn, that again O(n). But be careful! Here I’m using n to mean “number of cells drawn” and not “number of cells computed by our algorithm”. Context matters in big-O analysis.

Is having time spent per tick be O(n) in the number of cells to compute one generation good?

Yes, this is a pretty good start. We know that even with a very naïve algorithm, we can assume that making the grid four times bigger will make it take about four times longer to compute, and computing ten times as many ticks will take about ten times longer to compute.

That’s good to know, because now we can do measurements to see how long it takes to compute one grid of known size, and get a sense of how big we can make the grid before the slowdown becomes unacceptable. Or, conversely, if we’re interested in the question “how many ticks can I process in my time budget?” we now have the ability to estimate what the grid scale should be to achieve that goal given a measurement.

So far I’ve only talked about consumption of time; what about memory? It seems easy; a bool is one byte, we spend one byte per cell, and so we have O(n) bytes in the original cell array, and we allocate O(n) bytes in the new array. At the end of the algorithm we throw away the old one and keep the new one, so we’ve got a total memory consumption of O(n).

Unfortunately though, that’s not the whole story. Memory allocation is not free; the more times you allocate memory, the more work the garbage collector has to do in the future, and that work does not come for free. Allocation of memory can affect time in unusual ways in GC’d languages, and can cause some linear algorithms to become quadratic as a result; I may discuss this in more detail in a later episode.

A better approach here would be to allocate two cell buffers once, and then rotate between them, switching which one is “current cells” and which one is “next step cells”. Sure, that doubles the amount of memory used by the program for the cells, but it lowers the burden on the garbage collector. And we will see later in this series that memory burden can get hard to analyze particularly when you care about GC issues.

But remember: asymptotic performance only tells us how performance will likely change as problem size changes. It does not tell us whether our algorithm actually meets our performance budget at any reasonable size!

Next time on FAIC: How fast is this algorithm? Where are we doing unnecessary work that takes time?

Code for this episode can be found here. I have not updated the Life algorithm, but I have added a new feature to the client, namely, you can now resize the form and the display box will resize along with it.

On that subject — as I noted earlier, the client is very “bare bones” right now, and I intend to gradually add more features to it as we go, but I’ll mostly concentrate on the algorithms. I’ve started getting pull requests on GitHub adding more features to the client, and though I certainly appreciate the effort and would like to thank everyone for their interest, it’s not actually my intention here to create a fully-featured Life simulator. There are plenty available already if that’s what you want.

Please do clone the repo and play around with it! But I write this blog in my spare time and have many other demands on my time even in the pandemic, so doing extra work to review PRs and figure out how to make the code I’ve already written for future episodes work with them is work I might not get to for some time. Thanks!

Last time I presented the naïve implementation of the Life algorithm, where we restricted the board to 256×256 cells and implemented it as a two-dimensional array of bools. What are the relevant performance characteristics of this solution? There are a lot of different ways we can characterize the performance of an algorithm, and I’d like to look at several of them in this series as we discuss the different algorithms.

Today let’s start with asymptotic performance, also known as “big-O” performance. That is, how does some performance factor of interest change as the size of the problem we’re solving changes? But before we get into the details, I want to digress for a moment — three times.

First digression: what do we mean by “big-O” performance? If you’re unfamiliar with this term, the basic idea is that the cost of solving a problem is some function of the size of the problem. By “cost” I mean that there is something that is in short supply that you care about, like time, or memory, or storage space, or less commonly, actual dollars. (Though if you are buying compute power from a cloud provider, time and storage really are measured in dollars!)

The question is: what is that function?

If the cost of solving the problem is the same no matter what the size of the problem is, that is said to be a “constant order” problem, and we notate that O(1). That is, if we spend one unit of time to solve a problem of size 100, then we also spend one unit of time to solve a problem of size 100000.

Example: “I have a jar that contains zero or more pennies and nothing else; are there any pennies in this jar?” You can answer that question in the same amount of time whether there are zero pennies, one penny, or a million pennies in the jar. The cost does not scale at all with the problem size; it is always the same.

Of course most problems are not of constant order!

Example: “I have a deck of cards; each card has a number on it; the deck is unsorted. Is there a card with the number 12 on it?” The only way to find out is to look at the cards until you find a 12, in which case you’re done, or you’ve looked at every card. If you double the number of cards, you double the average search time. If you triple the number of cards, you triple the search time. We say that the problem scales linearly, and notate it as O(n). That is, if we spend one unit of time to solve a problem of size 20, then we spend ten units of time to solve a problem of size 200.

Similarly we have problems that are “quadratic”, or O(n²), where making the problem ten times bigger makes it 100 times more expensive to solve, or the really bad “exponential”, O(2ⁿ), where making the problem one bigger makes it twice as hard to solve.

Asymptotic analysis is in particular not concerned with the problem of “could we make this algorithm 10% faster for this particular case?” (We’ll discuss that kind of analysis soon.) Rather, it is solely concerned with the question of “how does performance change as a function of problem size?”

That’s a brief overview; there is much, much more to be said on this topic, including why it is called “asymptotic performance”, which is not at all obvious. I’ll leave it there; this should be enough to get us going. If this subject is new to you, there are plenty of resources to learn more on the internet.

Second digression: Why do we care about asymptotic performance in general?

There is a great deal to criticize about the way software companies conduct interviews; a critique I frequently hear is “interviews quiz you about big-O performance analysis but that’s not a skill you use on the job”.

A lot of companies blindly follow the interviewing practices of industry giants like Microsoft or Google without thinking hard enough about whether those practices make sense for their line of business. In companies where this genuinely is not an on-the-job skill, quizzing interview candidates about algorithmic performance analysis is not just a pointless and expensive acquisition of signal which is then either irrelevant or ignored, but worse, it is is gatekeeping.

Gatekeeping how? What I mean is: those sorts of questions can effectively be mere proxies for the question “did you pay attention in your second year computer science classes?” Asking that question unnecessarily introduces a strong bias against hiring people who never took second year computer science but who are otherwise capable of doing the job. That’s a totally valid reason to criticize this kind of question; it’s unwise to ask questions that are both genuinely irrelevant to the job and exclude potentially valuable talent!

When then is it appropriate to ask these sorts of questions in interviews?

I ask questions about asymptotic performance when I interview candidates, and that is because you will not be successful working in my codebase unless you can do this kind of analysis quickly and accurately. I do not expect candidates to know the Master Theorem by heart — I sure don’t! — but estimating the big-O performance of my work is a skill I have used every single day for over two decades.

Why’s that?

Because asymptotic performance tells you how the performance of your small test cases will scale to real problems. I work on problems where the problem sizes can realistically grow large, and the algorithms are not always obviously linear.

Let’s take an abstract example. Suppose we provide a software service to some customers who are throwing problems at our servers. Let’s say that we want our test case to take about a minute, and in that minute we can solve a problem of size 100.

If the time taken to solve real customer problems instead of little test case problems scales linearly then:

• A problem of size 1 000 takes ten minutes.
• A problem of size 10 000 takes about two hours.
• A problem of size 100 000 takes about seventeen hours.
• A problem of size 1 000 000 takes about seven days.

Now suppose the problem scales quadratically:

• A problem of size 1 000 takes about two hours.
• A problem of size 10 000 takes about seven days.
• A problem of size 100 000 takes about two years.
• A problem of size 1 000 000 takes about 200 years.

If the cost of solving a problem grows quadratically then the largest real-world problem you can realistically solve is only about a thousand times bigger than your typical couple-minutes test case.

Or, put another way:

If the asymptotic cost of an algorithm grows at any rate more than O(n log n) — which is the rate at which “sort this data set” problems grow — then there will very likely be a point early on where a realistically-sized problem is too expensive to solve with this algorithm.

Right now I am doing research on analyzing probabilistic models represented as graphs. My test cases typically have a few dozen nodes and take a couple seconds to run. What is the asymptotic performance of my analysis? If the answer is O(n²) then I have a big problem that needs to be solved before I make any promises to a customer, because I have apparently built an analyzer that can only analyze “toy” problems! I know that customers are going to want to analyze graphs that have millions of nodes in them, which means that I need to scale at O(n log n) or better.

That’s why we care so much about big-O analysis; we want to make software that scales to solve real customer problems without costing too much.

Third digression: Why do we care in this particular scenario?

We care because we’re trying to simulate an infinite grid. Plainly we are not going to actually implement anything of infinite size, so it makes sense to ask “if we know how much it costs in time or memory to simulate a 256 by 256 grid, how much does it cost to simulate a four-times-larger 512 by 512 grid? What about a 16-times-larger 1024 by 1024 grid?” The number of cells in a grid grows as the square, so it is very difficult to find Life algorithms that scale well when the factor that is increasing is the width of a square grid.

By knowing the asymptotic order of the growth of the costs we can very quickly get a sense of what our “budget” is. If, say, we want to compute a new tick fast enough that it looks like a smooth animation, that means we have only about 30 milliseconds to do the computation. If we know that we can do, say, 256 by 256 in two milliseconds, and we know that our algorithm is linear in the number of cells, then we can very quickly know that we will be beyond our performance budget once the graph is sixteen times larger, which is only 1024 by 1024.

Look at that, I’ve used up an entire episode in digressions! Whoops!

Next time on FAIC: How should we measure asymptotic order for our naive algorithm? And what other performance concerns might we consider?

Code for this episode can be found here.

All right, let’s get into it.

Since I want this series to concentrate on the algorithms and not the user interface, what I will probably do is make incremental improvements to the WinForms UI in each episode, but not discuss the details unless there is something particularly interesting.

In the code for the previous episode the UI consisted just of a picture box that updated every second. The UI for this episode adds a new feature: you can now scroll with the mouse wheel to change the zoom level from cells being one pixel up to 64×64 pixels, in powers of two:

It’s just like scrolling in a map application; the current position of the mouse determines the center point for the zoom.

I’ve also made the default starting configuration a Life form called “acorn”, because it is very small and grows into a surprisingly large tree. It takes over 5000 ticks to settle down into a stable configuration and throws off a bunch of gliders as it does. The screen shots above are from the early stages in acorn’s evolution; check out the whole thing. It is quite mesmerizing. (Though you might want to adjust the timing in the code to compute more than two ticks per second!)

The first problem we face when designing a Life algorithm is the unavoidable fact that the board is in theory infinite, but our time and space available are finite. There are three basic ways to deal with this problem, and they all have their own pros and cons:

Fixed subset, dead everywhere else

Pick a board size: 256 x 256 cells, say. Everything outside the rectangle with corners (0, 0) and (255, 255) is considered permanently dead regardless of whether it really “ought” to be alive. We pick a size that is “big enough” for examining whatever Life form it is we wish to examine and do not worry about it further. If we end up with living cells near the border that would cause cells outside the border to come alive, we ignore that and they stay dead.

Fixed subset, wrap-around borders

Again, pick a finite size, treat everything outside that rectangle as permanently dead. But this time, make the board “wrap around” such that the “north” edge is adjacent to the “south” edge and the “east” edge is adjacent to the “west” edge.  If, say, a glider is heading towards the south edge, when it gets there it just keeps on going and appears on the north side of the rectangle.

There are two basic ways of conceptualizing this. The first and most common is that instead of an infinite flat grid, we’ve mapped a finite rectangular grid onto the surface of a torus — a doughnut. Imagine you took a rubber rectangle, rolled it into a cylinder to affix the north edge to the south edge, and then folded it to affix the now-circular west edge to the east edge. You’d end up with a torus.

The less common conceptualization is that we still have an infinite flat board, but we have tiled it with infinitely many copies of our rectangle; when we make a change to one tile, all the tiles change.

This technique is attractive from an implementation perspective because every cell has eight mutable neighbors and computing which cells are neighboring which others is simple math. However, it has a lot of problems too, particularly: if a Life form causes a glider to form that “escapes”, it ought to run off to infinity and bother no one again. But on a doughnut board it wraps around and ends up shooting straight at the cells that created it, possibly interfering with the evolution of the configuration.

We won’t be using this technique in this series.

Embiggen as needed

We start with a fixed subset that is as large as we need, but when we have a cell that might come alive on the border, we push the boundary out. There are a lot of clever ways to do this; our final algorithm in this series will use this idea to some extent.

Enough chit-chat; let’s look at the code for what I call the naïve algorithm. The basic idea is: create a 256×256 array of bools; true means alive, false means dead. On every tick, create a new array, check every cell’s neighbors in the old array to see if the cell will be alive in the next tick, and then discard the old array.

I’ll omit the boring boilerplate code.

Initialization is straightforward; the default state of a bool array is all false:

class BoolArrayLife : ILife
{
  private int height = 256;
  private int width = 256;
  private bool[,] cells;
  public BoolArrayLife()
  {
    Clear();
  }
  public void Clear()
  {
    cells = new bool[width, height];
  }

Everything outside our rectangle is always dead:

  private bool IsValidPoint(long x, long y) => 
    0 <= x && x < width && 0 <= y && y < height;

  public bool this[long x, long y]
  {
    get
    {
      if (IsValidPoint(x, y))
        return cells[x, y];
      return false;
    }

And similarly for the setter; you see how this goes.

To determine how many living neighbors a cell has, we just ask the indexer for the state of each neighbor. If the cell is out of range, the indexer tells us it is dead:

  private int LivingNeighbors(int x, int y)
  {
    int sum = this[x - 1, y - 1] ? 1 : 0;
    sum += this[x - 1, y] ? 1 : 0;
    sum += this[x - 1, y + 1] ? 1 : 0;
    sum += this[x, y - 1] ? 1 : 0;
    sum += this[x, y + 1] ? 1 : 0;
    sum += this[x + 1, y - 1] ? 1 : 0;
    sum += this[x + 1, y] ? 1 : 0;
    sum += this[x + 1, y + 1] ? 1 : 0;
    return sum;
  }

And the core “inner loop” algorithm — that is, what do we do on each tick? — is as straightforward as can be:

  public void Step()
  {
    bool[,] newCells = new bool[width, height];
    for (int y = 0; y < height; y += 1)
      for (int x = 0; x < width; x += 1)
      {
        int count = LivingNeighbors(x, y);
        newCells[x, y] = count == 3 || (cells[x, y] && count == 2);
      }
    cells = newCells;
  }

Recall that the client asks the engine to call it back for every living cell inside a certain rectangle. Were you ever asked the question “how do you compute the intersection of two rectangles?” in an interview? It’s a boring and clichéd question but sometimes you actually do need to loop over the intersection of two rectangles!

public void Draw(LifeRect rect, Action<LifePoint> setPixel)
{
  long xmin = Max(0, rect.X);
  long xmax = Min(width, rect.X + rect.Width);
  long ymin = Max(0, rect.Y - rect.Height + 1);
  long ymax = Min(height, rect.Y + 1);
  for (long y = ymin; y < ymax; y += 1)
    for (long x = xmin; x < xmax; x += 1)
      if (cells[x, y])
        setPixel(new LifePoint(x, y));
}

And that’s it! Just a bunch of loops.

Next time on FAIC: We’ll start exploring some of the questions that I want to discuss in this series, like:

• What are the correctness and performance characteristics of this solution?
• Are there easy ways we could reduce the computational burden?
• How does it scale?
• What can we learn about optimization in general from optimizing to solve this problem in particular?

The mathematician John Horton Conway has died, apparently due to the covid-19 epidemic, at the age of 82. I never met him but by all accounts, he was a delightful person and brilliant mathematician; his charming book on introductory game theory, Winning Ways, is the most fun you can have reading a university level math text. I had just purchased a biography, Genius at Play, before the crisis began and I suppose I’ll have time to read it now.

I’m sad, of course; we are all diminished when we lose a delightful and brilliant teacher. I’m also angry at the frankly disgusting attitude I see in the media and in the actions of elected officials that it is somehow no great loss to society when a disease predominantly kills the elderly. Scrooge’s they had better die and reduce the surplus population was meant to be taken as the horrifyingly Malthusian ranting of a bitter, foolish man who ought to know better, not as words to live by.

But I don’t intend this to be another rant as to the utter, abject, criminal stupidity that has informed the response to this pandemic. Rather: I have been wanting for over a decade to write a series on my blog about Conway’s most famous invention (I almost said discovery, because it seems like such a natural part of my world), Conway’s Game of Life. Now seems like a good time.

When I was a teenager I collected back issues of Scientific American — mostly from the sadly now gone Casablanca Books in my home town. Lots of the articles were interesting, but mostly I wanted a set of all the Martin Gardner, Kee Dewdney and Douglas Hofstadter’s monthly columns on mathematics and programming.

ASIDE: A note to any teenagers reading this who are collecting bulky old stuff like me. Keep it. When I moved across country I took my National Geographics and Tolkien biographies, but I sold my SciAms and Doctor Who novelizations for pennies on the dollar because they were bulky and I figured I wouldn’t miss them. And now only 25 years later I wish I still had those memorabilia.

I kept photocopies of Gardner’s articles on Life in 1970 and 1971 that introduced the phenomenon to the world. I find it fascinating to think about how Conway and the other people who made initial discoveries must have worked, without fast computers and fancy graphics; Conway said in the original 1970 article “it is marvelous to sit watching on the computer screen”, so there must have been some graphical system, but I can only imagine that it was quite primitive.

Over the next few weeks I’ll recapitulate my own experience with Life, though with much better hardware, software, and coding skills than my initial forays on my Amiga 500 as a teenager. We’ll start with the basics and work our way up to an astonishing result: it is possible to compute trillions of generations per second on Life boards with trillions of cells using an ordinary desktop computer.

I have learned recently that Conway did not consider Life to be the important work that he wanted to be remembered for — though I must say, if there’s something you don’t want to be remembered for, maybe don’t spend a decade popularizing it — but Life is for the ages; it will outlive us all. Early exposure to Life made me think about programming in ways I had not before, and I am grateful to John Conway for giving me and so many others that inspiration. I’ll leave it to my mathematical betters to remember his lasting contributions to professional mathematics.

Next time on FAIC: We’ll begin at the beginning with the rules of the game and some straightforward implementations.