Optimising the foldl operation in a recursive data structureLet’s start with a some code I plucked from an earlier implementation of an alternative Dict implementation.https://medium.com/media/4c29a6295d5b63a4ae8f60262c55221c/hrefSo, that seems like a fairly straightforward foldl implementation: Recursively execute the operation on the left side, then execute the operation on your own data using the accumulated value from before, then feed that to folding over the right hand side.There’s something here that’s going to make that fairly expensive, though. That last lambda as part of a pipeline, that comes at a cost. How much? Well, let’s come up with an alternative, and see what difference it makes.That lambda could be eliminated if that last line could take the accumulator as its last value. So let’s do some argument shuffling and make a function to flip the 2nd and third arguments of whatever function you pass in.flip2nd : (a -> b -> c -> d) -> a -> c -> b -> dflip2nd f a b c = f a c bUsing this, we can turn that lambda into the following:|> flip2nd foldl op rightAlright, now that we’ve got that, let’s do a quick micro-benchmark to verify this actually helps.https://medium.com/media/2b68f5f5c4713c9f20f18da4f1a300de/hrefResults on my machine.Alright, that’s a fairly large improvement already. Having anonymous functions in a pipeline is probably not a great idea, as far as performance is concerned. It felt more readable with a lambda, though. There has to be a better option. Wait, let’s think about this for a bit. What we’re doing with pipelines, is saying “first compute the lefthand side, then feed that into the right hand side”. We could just as well do that by using a let .. in block, which would at least allow us to remove the flip2nd call.I previously mentioned here that using a let..in expression rather than pipelining would save us the overhead of the right function application operator |> . Turns out that both <| and |> are special cased in the Elm compiler, and a |> b compiles down to b (a)! Big thanks to Richard for pointing that out.Let’s refactor a bit, and compare the result to our previous, optimised result.https://medium.com/media/a13aca4a413b6cb133175781807dd63e/hrefIn case you don’t feel like running them yourself.Alright, that’s another slight performance improvement. Let’s take a step back, and look at an alternative way to desugar the function application operator. a |> b is just sugar for b (a) . No need to store the intermediaries, we can just inline the different parts of the pipeline straight into the final result.https://medium.com/media/1b110e4a45c50d37cffb8c2b85e54d1d/hrefThat yields us another decent little performance improvement. I think that’s all we can do here for now. Let’s stack up the original “pipeline+lambda” version against this “nested/inline” version.Note, also, that readability suffered some, but not too much — I feel like we’ve found a pretty decent balance between legibility and performance, for library code.https://medium.com/media/848a79f24e188f1501ec3ff0cd9f3137/hrefThe final resultsTakeaways:
- Avoid anonymous functions in pipelines
- Avoid pipelines, preferring inline function application if and only if the result is still legible!
- 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