Slow performance of Game of Life Implementation - suggestions?

Questions / Help
,
1

Hello. As a side project, I have created various implementations of Conways Game of Life in over 20 languages. Over this past weekend, I set out to create a version with Elixir. This was my first time using a purely functional AND immutable language, so it took a little bit to get my head around the idea that I couldn’t update a struct value without having to return the updated parent struct it was nested in all the way back up to the top stack and then back down the method chain again.

Anyway, I got there in the end and this is the final result: https://github.com/KieranP/Game-Of-Life-Implementations/tree/master/elixir

However, the performance is really really bad. It currently ranks the worst of all the implementations I have done, sitting at ~3.7x slower than the next slowest, and ~7.9x slower than the latest CRuby.

I have traced the slowness down to a Map.get call I use to fetch a world cell by specific coordinates and check its alive state (see world.ex, cell_at method). Each world tick, this method is called 8 times for every cell in the world (there are 6000 cells, therefore some 48,000 calls). (see world.ex, alive_neighbours_around method).

If I change alive_neighbours_around to return 0 by default, thus bypassing the cell_at calls, avg tick time drops from 30.61ms per tick to around 2.8ms per tick, which takes it from being ~7.9x slower than CRuby to being ~1.4x faster. So it appears than the cell_at method, which only calls Map.get, accounts for 90.85% of the runtime.

The reason for the slowness compared to other languages is that other languages allow me to reference/point to the world cell from another cell (i.e. a world has many cells, and a cell has many neighbours, which are references/pointers to the world cells). In other languages, when I loop over a cells neighbours, they can fetch the current alive value from the world cell through that reference. In Elixir however, there doesn’t appear to be any concept of references, so a cells neighbours are just coordinates, and to get the current cell value, I have to make a cell_at call with those coordinates to get the latest data from the world cell.

So I understand the cause of the problem. I guess I’m looking for some advice on how I might speed up the implementation without deviating drastically from the other implementations. I guess what I need to know is:

  • Are there actually memory references in Elixir that I’ve just missed? Can a cell neighbour point to a world cell in order to fetch its value?
  • If there are not references/pointers in Elixir, is there a better/faster way of storing structs by a key other than via a Map?

Besides these things, I’d also be keen to hear how the general syntax is and whether there are general things I could do better (e.g. is building a string using for loops and reduce the right approach, see world.ex render).

Many thanks for any suggestions.

2
  1. Map keys do not have to be strings, you can just use {x, y} as key instead of "#{x}-#{y}"
  2. You don’t need to store world as a Map, you can just store it as an array, since it is fixed size. And access it like def cell_at(%World{width: w, array: a}, x, y), do: :array.get(x + y * w, a)
  3. I’d suggest storing cell data in a tuple. If you want names, you can just use Record.

NITs: Elixir has functions, not methods. Use mix new to create and set up projects. Elixir doesn’t have references, since they can’t be immutably tracked in Elixir’s semantics.

1 Like
3

Another tip: only store live cells. Often a huge percentage of cells is dead, so storing those adds some overhead. Probably mostly memory though. But it might add some performance as well.
That also means that you don’t need to do a check if the cell is alive or not

1 Like
4

Are protocols even consolidated if he’s not using a mix project? I wonder if that’s a factor here too.

1 Like
5

+1 to @hst337’s suggestion of using an {x, y} tuple as a key instead of interpolating a string.

Making that change alone drops the “world tick” time from ~55ms to ~15ms on my local machine.

The other major performance problem is too much garbage - put_in is powerful, but using it inside of loops like this may not be great for performance. The Ruby version avoids this by mutating cells in place, but you’ll need to pick an alternate approach in Elixir:

  • keep per-tick data like neighbors separate from cells and apply the alive/dead calculation in one pass over cells
  • use an ETS table for cells
  • make add_cell smarter and pre-compute neighbors when a cell’s neighbors change instead of every tick

The ultimate motivation behind all of these approaches is to do as little work as possible for “static” cells.

2 Likes
6

Thanks everyone for your input/suggestions. One of the goals of my GoL repo is to keep the implementation as similar as possible. Additionally, in my view at least, it gives a good measure of a languages overall speed when a program is not written to be highly optimised. The implementations are not designed for raw speed, but for like for like comparison.

Therefore, regarding the suggestions to convert the world cells into a 2D array or to make the cell keys into tuples, I agree that this would make things significantly faster, but it would also cause the implementation to deviate from the other implementations too much, making line for line comparison difficult.

If I change the map keys into tuples, then the tick time drops to 11ms, but as above, it would make it quite different from other implementations. I’m wondering however if this might be an indication that Elixir/Erlang has room to improve when it comes to lots of small string concatenations. At quick test, other languages don’t seem to have as much of a performance hit doing string concatenations this way.

I did however manage to find a way to improve performance by fetching multiple cells up front (using Map.take) and iterating over that map, rather than call cell_at one at a time. This reduced map access from 48,000 calls per tick to 6,000 per tick) and resulted in a 36% improvement in world tick time: Elixir: 36% improvement in tick time · KieranP/Game-Of-Life-Implementations@c395dea · GitHub

Anyway, Elixir is an interesting language and there are certainly aspects that I wish other languages had, such as the pipe (|>).