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,
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
Many thanks for any suggestions.