Fast 2D Arrays/Vectors (and the Game Of Life)

Introduction

I was recently looking at an implementation of Conway’s Game Of Life, and was struck by the way in which the developer had constructed his grid. The Game of Life requires that you construct a two-dimensional array, but Flash does not support 2D arrays natively, so work arounds have to be found. There are slow workarounds, fast workarounds, and very fast workarounds. Of course, for very fast workarounds, we use Vector and target the Flash Player 10.

An example of Conway’s Game Of Life can be found below.

I should point out at the start that in these I am using for (var x:int = 0; x < 100; x++) loops. Using while (x--) or even while(--x > -1) may well be quicker, but here I am trying to highlight the relative speeds of the data structures that are being looped around, not the loops themselves.

Slow

public function generate():void
{
	grid = [];
	for (var x:int = 0; x < 100; x++)
	{
		grid[x] = [];
		for (var y:int = 0; y < 100; y++)
		{
			grid[x][y] = Math.random() < 0.5;
		}
	}
}

public function retrieve(x:int, y:int):Boolean
{
	return grid[x][y];
}

This is the slowest good method around. It's undoubtedly good, in that it is readable and concise. It's not so good in terms of speed though, because of the double Array reference that is required to get to the relevant reference. Array lookups are slow, and should be avoided in performance-critical areas.

Fast

public function generate():void
{
	grid = [];
	for (var x:int = 0; x < 100; x++)
	{
		for (var y:int = 0; y < 100; y++)
		{
			grid[x * 100 + y] = Math.random() < 0.5;
		}
	}
}

public function retrieve(x:int, y:int):Boolean
{
	return grid[x * 100 + y];
}

Instead of putting your 2D grid in a nested array, we can just use a one-dimensional array, and use an expression x * 100 + y within the lookup to differentiate between cells.

If you're targetting the version 9 player still, then this is probably the fastest mechanism you're going to get. (there is probably no need to, the latest Flash player penetration statistics suggests about 95% adoption in the western hemisphere, and above 90% adoption elsewhere)

Fast (again, but with Vector)

public function generate():void
{
	grid = new Vector.<Boolean>(10000, true);
	for (var x:int = 0; x < 100; x++)
	{
		for (var y:int = 0; y < 100; y++)
		{
			grid[x * 100 + y] = Math.random() < 0.5;
		}
	}
}

public function retrieve(x:int, y:int):Boolean
{
	return grid[x * 100 + y];
}

Moving to use the FP10 Vector class gives you some great benefits. The Flash Player can be told up-front how big the array is going to be, and it knows the type of element. It is all-round quicker to do it this way. However, this is not the quickest structure we can use!

Faster

public function generate():void
{
	shift = 7;
	grid = new Vector.<Boolean>(100 << shift, true);

	for (var x:int = 0; x < 100; x++)
	{
		for (var y:int = 0; y < 100; y++)
		{
			grid[(x << shift) | y] = Math.random() < 0.5;
		}
	}
}

public function retrieve(x:int, y:int):Boolean
{
	return grid[(x << shift) | y];
}

By referencing the cell using [x * 100 + y] we get the computer to do a multiplication and an addition. That's pretty quick, but while we consider these two of the most primitive mathematical operations, they are not two primitive calculations for a computer! Instead, we can use [(x << shift) | y] which replaces the multiplication and addition with a bit-shift and a bitwise disjunction. They are about as simple calculations as a computer can make, and the time it gains us is small, but significant if we are working with big grids.

I do not intend to go into the details of bitwise operations here, but for further reading, try this Wikipedia article.

Interestingly, if you try this approach with Array, it does not run as quickly as the example labelled 'Fast'. This is because, as Jackson Dunstan and JP Auclair noted, it will leave 'gaps' in the Array (for example no values will be entered in the above Vector for values, 100 - 127. For a Vector of a known size, that is not a performance problem, but Arrays work differently.

Results Summary

The results on the horizontal access are milliseconds that it took to iterate through the grid 1000 times. The difference in speed by adopting Vector and the bitwise-shift approach is to cut the calculation time by nearly a quarter. The bigger the grid is, the more this technique becomes useful.

After-Thought - Game Of Life

The Game Of Life is a grid structure, in which each cell is a Boolean switch; either 'on' or 'off'. Iteratively, the grid changes, according to a very simple instruction set:

1. Each grid cell's value is determined by the values of the eight adjacent grid cells;
2. For each cell, If exactly three of those adjacent cells are 'on', then in the next iteration, that cell will be 'on';
3. For each cell, if two adjacent cells are 'on' then in the next iteration that cell will remain in it's current state;
4. Otherwise, that cell's value in the next iteration will be set to 'off'.

At the edges, either those cells just have fewer neighbours, or the neighbours are thought to 'wrap around' the 2D space, so that the cells' universe resembles a torus in 3D space.

The result of these simple rules is an interesting pattern which is very interesting for a great number of reasons. The example below should show you what I mean. It will run only when the mouse is over the application. Click on it to break the iteration cycle and populate the cells with random data.