Optimising for performance in Elm, Pt. 1

Part 1: IntroductionFirst, let’s get the obvious disclaimers out of the way.

The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming.

— Computer Programming as an Art (1974) - Donald KnuthNow that we’re sure we’re not doing it prematurely…

We follow two rules in the matter of optimization:

1. Don’t do it.2. (for experts only). Don’t do it yet — that is, not until you have a perfectly clear and unoptimized solution.

— Principles of program design (1975) - Michael A JacksonThere, that’s better.Who is this forI’ve written this to document how I went about optimising an alternative Dict type. This type of core functionality needs to be fast, without compromising maintainability. The type of code described here would typically be library code rather than application code.If you find yourself doing such a thing, and need some pointers on how to increase performance, this document may be useful to you.

Don’t write this type of code in regular application code.

Optimise for readability, even to the point of sacrificing performance.MethodologyOptimising for performance in general demands a lot of work and attention to detail. Multiple steps are involved, which I’ll attempt to explain here.1. Identify slow codeThis means using Chrome DevTools (or equivalent) to identify where any slowness if coming from, as well as relying on logic and micro-benchmarks to identify potentially slow code. Beware: identifying slow (Elm) code using Chrome DevTools is not easy, and micro-benchmarks come with a series of pitfalls.The process of using Chrome DevTools to actually identify bottlenecks probably warrants its own series of blogposts.Knowing what goes on behind the scenes is helpful in realising why certain constructs exhibit certain performance characteristics. For this, I recommend Noah’s “Elm compiled documentation” as well as taking a good look at core/Utils.js which holds the code for comparisons, equality and some other interesting little helpers.2. Make it fasterThis is something I’ll try to explain more in-depth in the rest of this series.3. Verify invariants still holdThis is really important.An invariant is something that must hold true about your code. It is a basic assertion you should be able to make before and after calling your function.To explain this with an example, let’s imagine we’re writing a binary search tree (BST). A tree can be modelled by saying that each tree is either the empty node, or a node with a value, a lefthand side and a righthand side.type Tree v = Empty | Node v (Tree v) (Tree v)Now, in order for this tree to be a valid binary search tree, the following invariant must hold:

For each node in the tree, all values on the lefthand side must be strictly smaller and all nodes on the righthand side must be strictly larger than the value of the node itself.

The first step, before attempting to optimise any code that touches the tree — or even before simply writing any code that touches the tree — should be to turn your invariants into executable code. For a binary search tree, that would look roughly like this:https://medium.com/media/bfe9d8252ffcd1197144ef18d7b1805f/hrefNow I can easily set up a number of test-cases, preferably fuzz-tests so I can be sure that it works for random cases rather than the convoluted ones I can come up with myself, to test that my implementation of, say, an insertion algorithm does not break that invariant.Running those tests before and after each change made to some code ensures I don’t slip up and break any guarantees my code is making.4. Benchmark, benchmark and benchmark againChanges that improve performance for some input on one platform, may regress performance for a different type of input, or on a different platform. Setting yourself up with a whole stack of different platforms, browsers and types to test with, is an important part of ensuring that your performance improvement really is, in fact, an improvement at all.The performance of a a > b for example, depends heavily on the type. Some changes will work better for smaller datasets, others on larger datasets. Some changes might result in javascript that might initially perform better, but can’t be handled efficiently by an optimising JIT. Optimising for performance isn’t that clear-cut.Brian Hicks’ excellent elm-benchmark provides you with the tools to run benchmarks, and setting up a series of comparisons with different types and sizes of input is fairly easy.If you’re working on an OSS project, you may wish to apply to BrowserStack or Saucelabs for a free OSS license so you can run your performance tests against hundreds of different platform/browser combinations.5. If there are no regressions, go back to step 1By which I really mean, optimise one step at a time. Quantifying the impact of a change can only be done with that change being regarded in isolation. If you optimise everything at once, then notice a performance regression in a benchmark or an invariant being broken, good luck figuring out what to revert.So, how do I go about step 2, and actually make things faster?Showing patterns that are good candidates for improving performance is, of course, the main point of this series. Now that you’ve wrestled your way through this long introduction, it’s time to get to the good bits. In part 2.

Optimising for performance in Elm, Pt. 1 was originally published in Ilias Van Peer on Medium, where people are continuing the conversation by highlighting and responding to this story.