k776
Slow performance of Game of Life Implementation - suggestions?
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.
Most Liked
al2o3cr
+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
neighborsseparate fromcellsand apply the alive/dead calculation in one pass overcells - use an ETS table for
cells - make
add_cellsmarter and pre-computeneighborswhen 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.
hst337
- Map keys do not have to be strings, you can just use
{x, y}as key instead of"#{x}-#{y}" - 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 likedef cell_at(%World{width: w, array: a}, x, y), do: :array.get(x + y * w, a) - 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.
tcoopman
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
benwilson512
Are protocols even consolidated if he’s not using a mix project? I wonder if that’s a factor here too.
Popular in Questions
Other popular topics
Latest on Elixir Forum
Sponsor Spotlight
Supporting innovation across the BEAM ecosystem.
Categories:
Sub Categories:
Forums
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Producing high quality Elixir screencasts since 2017.
Enabling companies to succeed by building software people love.
The deployment platform built for Elixir: PaaS ease, VPS control.
Courses that'll move you from confusion to "Aha, now I get it!"