Conway's Game of Life in Elixir

Note: this post was migrated from my old Tumblr-backed blog

For the last week or so, I’ve been trying to get a better handle on Elixir, which is a new language that compiles down to BEAM, Erlang’s weapons-grade VM (think like Scala -> JVM). To get a handle on it, I’ve built an implementation of Conway’s Game of Life since I feel that it can benefit from the fact that each generational calculation can easily be broken up into many small jobs, which is great for a platform like BEAM.

My first build didn’t use multiple processes at all, but rather stuck to a single-process, serial iterator. It wasn’t very fast, but it worked. Then, as I progressed through the book, I learned how to go multi-process with it and I managed to not only improve performance, but also take better advantage of my multi-core laptop.

I ran the single-process version through the time command and had it calculate 500 generations, which gave me the following results:

real    2m11.806s
user    2m8.933s
sys     0m2.998s

Then, when I timed the multi-process version (still a work in progress), I was able to achieve the following:

real    1m27.609s
user    4m10.059s
sys     0m36.311s

That’s a 66% speed up in total time to calculate with a nearly 90% increase in total CPU time.

Unfortunately, when building and iteratively refactoring the multi-process version, I discovered some bugs in my initial logic for wrapping the field (so I effectively have an unlimited-sized field with the left/right and top/bottom sides wrapping), but I don’t believe this impacts the overall results.

Optimizations

This code isn’t as optimized as it could be. I update the state of the cells (passing them the number of neighbors they have, so they can decide if they should be alive or dead) and then ask for the state afterwards, which should probably be returned to the caller when the update is sent.

I believe I can also speed this up by only taking into account live cells and their neighbors, since any dead cell with no neighbors would remain dead. Because it would be difficult and time consuming to ensure that no cell gets an update more than once, in the case of this optimization, I’ve already ensured that the update call is monotonic by including the current generation in the call. This way, if the update call will only update if the generation included in the call is newer than the last one it received.

Future Benchmarks

I’m not going to implement any of the above optimizations in the single-process implementation, so any future benchmarks will only be comparable to pre-optimized code.

Get the code

My code, which is still a work in progress, is available on the GitHub:

The master branch currently contains the multi-process implementation, while the single-process one is in the single-process branch.

I’m still learning Elixir and will be continually updating the code until I become comfortable with the coding style and conventions of the language, but if you see me doing anything terribly wrong, let me know.