while doing some cleanup in our company’s rather large Elm code base, I stumbled upon this innocent looking helper:
{-| Faster than List.concat -}
fastConcat : List (List a) -> List a
fastConcat lists =
List.foldr (++) [] lists
This immediately peaked my interest and I run some benchmarks.
I found out that on my machine the fastConcat really runs about 2x (on Google Chrome) to 3x (on Firefox) faster than the implementation which is currently present in elm/core (pasted here for reference):
concat : List (List a) -> List a
concat lists =
foldr append [] lists
I created a PR to elm/core.
I’d be grateful if someone could check the benchmark I used for testing, point out if anything is wrong with it and/or run it with other browsers if possible.
If there’s nothing wrong could someone from the core team please consider merging the PR?
Alternatively it might be good to investigate why using List.append versus Basics.++ leads to such performance difference.
I’m the author of that fastConcat in company’s codebase.
In fact this is rather about append more than about concat itself. The thing is that ++ is compiler black magic polymorphism but List.append is written in regular elm. JS magic implementation is simply faster.
So then perhaps List.append should be updated instead of List.concat.
But was there a reason why they didn’t just write append = (++) or append = Elm.Kernel.Utils.append ?
A desire to avoid relying too much on kernel code?
@robin.heggelund thank you for checking this. I’ll be interested in your findings. FYI just a minute before you wrote, I updated my PR to use Basics.++ in List.append instead of List.concat as people suggested.
My personal opinion is that there always be certain tradeoff. I think that current implementation in pure Elm is much more elegant solution than any other possibly more performant implementation can be.
On the other hand this implementation offers better performance and in cases like the one that fastAppend was used for performance was really critical due to the size of lists it was operating with.
Lastly I agree that having polymorphic ++ aliased is not effective due to the polymorphism overhead. On the other hand I would guess this overhead is negledgable (worth measuring though). Implementing native list append might be an option. It’s essentially implemented as part of polymorphic append so it can be just exposed as own kernel function. The trade of is that the surface of kernel implementations in stdlib would be bigger.
Because of those uncertnity about what is the right trade off we haven’t tried to upstream that code earlier (but I remember it was discussed on community Slack to some degree).
Also I think it’s probably fair to menttion that @rofrol was the one who did original benchmarking and discoverd there is something fishy related to performance.
