Fork me on GitHub

Futhark 0.8.1 released, with reflections on Advent of Code

Posted on December 25, 2018 by Troels Henriksen

I just tagged a new release of Futhark, everyone’s favourite parallel functional array language named after the Runic alphabet (full changelog here). For this post, I want to point out the most significant changes, and then spend a bit of time talking about my surprisingly good experiences using Futhark to solve problems from the Advent of Code).

The release

This release has no big feature additions or significant new optimisations, but instead contains smaller quality-of-life improvements and a great deal of bug-fixes. This is not because we have stopped working on major improvements - quite the contrary. Indeed, the primary purpose of this release is to make conservative improvements available before we start merging the more significant changes we are working on (two new code generation backends and a rework of how parallel reductions are compiled). For this release, there have been two breaking changes:

Both of these had been deprecated for several releases, so it looks like Futhark is finally stabilising at the language level. The only significant performance-related improvement is a re-implementation of transpositions by Jakob Stokholm Bertelsen, an undergrad here at DIKU, which speeds up some transpositions by up to around 50%. Since transpositions are frequently inserted by the Futhark compiler to rearrange arrays for better locality, this can have a significant impact on some benchmarks. For example, this graph shows the impact on the LocVolCalib benchmark (about 10%), which we already considered to run quite fast.

Advent of Code

A great deal of the bugs fixed for this release were found by participating in Advent of Code, a website that every year releases a daily programming problem from the 1st to the 25th of December. On a personal level, I do not normally like programming competitions. I’m not interested in speed-coding, and I don’t have much of a competitive streak in the first place. From a Futhark point of view, many such programming problems require facilities that are not practical, such as arbitrary-size integers (bignums), or assume that the programmer will have access to a library of common data structures.

Advent of Code is delightfully different. First, the problems are simple enough that even solving one every day will (usually!) not take too much of your time. Indeed, many of them seem designed to support a straightforward and correct brute-force solution, as well as increasingly refined and efficient solutions. I enjoyed that a lot, as I often find more pleasure in refining a program’s simplicity or performance, than coming up with the program in the first place. For most other collections of problems, in particular Project Euler, I would expend a lot of effort finding the right solution in the first place, and by the end I would be too sick of the problem to want to spend any time polishing my solution.

A second unexpected quality of Advent of Code is that it assumes surprisingly little of the programming language in use. For example, you do not need (or particularly benefit from) features like bignums, regular expressions (except for input parsing), floating point numbers(!), or IO. It is almost as if the problems were made to be solved in obscure or esoteric languages. While some libraries can be useful - quite a number of the problems involved breadth-first search in some capacity, for example - they are hardly essential.

In the end, I ended up solving most of the Advent of Code problems in Futhark (my code is here), although as of this writing I have not solved the last two days, on account of Christmas and all. While I am pretty sure that the Advent of Code designer does not particularly concern himself with parallel programming, a surprisingly large proportion of the problems were amenable to elegant parallel formulations (even if the data-sets given would usually not saturate a modern GPU). For the rest, it was nice to try to really exercise Futhark’s capabilities for imperative programming. Indeed, I was surprised to find that Futhark compiled to sequential C and written with intelligent use of in-place updates is actually a really efficient functional language, often matching the hand-written C or Rust I saw other participants post.

The following problems were particularly noteworthy. Most of my solutions depend on an accompanying Python script for converting the input into a form that can be easily consumed by Futhark (remember, Futhark is not for standalone applications):

In conclusion, I am surprised that Futhark actually managed to work for me. I had expected that after a few simple problems, the remaining would require too many facilities that Futhark does not provide, but that did not happen. The limiting factor was generally my own intellect, not the language. It was nice to exercise parts of Futhark that normally do not see much use, in particular since that also allowed me to flush out a number of compiler bugs (fortunately, they were all in the front-end and caused type errors or compiler crashes - debugging code generator bugs is a sure way to lose the Christmas spirit).

I can definitely recommend inventing your own programming language and then solve Advent of Code problems with it.