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.
- Part 1: Introduction
- Part 2: Optimising the foldl operation in a recursive data structure
- Part 3: Optimising the rebalancing operation in a self-balancing search tree
- Part 4: Optimising a toHex function
- Part 5: Pitfalls you may run into