# 2-3x faster List.concat implementation

**URL:** <https://discourse.elm-lang.org/t/2-3x-faster-list-concat-implementation/3533>\
**Category:** Request Feedback\
**Created:** [April 23, 2019, 7:18am UTC](https://discourse.elm-lang.org/t/2-3x-faster-list-concat-implementation/3533 "2019-04-23T07:18:07Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![Jan\_Hrcek](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/jan_hrcek/32/451_2.png) [@Jan\_Hrcek](https://discourse.elm-lang.org/u/Jan_Hrcek)\
**Post date:** [April 23, 2019, 7:18am UTC](https://discourse.elm-lang.org/t/2-3x-faster-list-concat-implementation/3533/1 "2019-04-23T07:18:07Z")

</div>

Hello all,

while doing some cleanup in our company’s rather large Elm code base, I stumbled upon this innocent looking helper:

```elm
{-| 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](https://github.com/jhrcek/faster-list-concat).  
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](https://github.com/elm/core/blob/master/src/List.elm#L375-L381) (pasted here for reference):

```elm
concat : List (List a) -> List a
concat lists =
  foldr append [] lists

```

I created a [PR to elm/core](https://github.com/elm/core/pull/1026).  
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.

---

<div class="post-metadata">

**Author:** ![brasilikum](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/brasilikum/32/524_2.png) [@brasilikum](https://discourse.elm-lang.org/u/brasilikum)\
**Post date:** [April 23, 2019, 12:17pm UTC](https://discourse.elm-lang.org/t/2-3x-faster-list-concat-implementation/3533/3 "2019-04-23T12:17:32Z")

</div>

Cool! Does someone have a theory why it is faster?

---

<div class="post-metadata">

**Author:** ![turboMaCk](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/turbomack/32/355_2.png) [@turboMaCk](https://discourse.elm-lang.org/u/turboMaCk)\
**Post date:** [April 23, 2019, 12:21pm UTC](https://discourse.elm-lang.org/t/2-3x-faster-list-concat-implementation/3533/4 "2019-04-23T12:21:39Z")

</div>

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.

Also there is this repository with benchmarks that was created at the time this code was written. [https://github.com/rofrol/elm-benchmark-concat-vs-fold](https://github.com/rofrol/elm-benchmark-concat-vs-fold)

---

<div class="post-metadata">

**Author:** ![brasilikum](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/brasilikum/32/524_2.png) [@brasilikum](https://discourse.elm-lang.org/u/brasilikum)\
**Post date:** [April 23, 2019, 12:50pm UTC](https://discourse.elm-lang.org/t/2-3x-faster-list-concat-implementation/3533/5 "2019-04-23T12:50:52Z")

</div>

Thanks!  
Also: the username checks out 😉

---

<div class="post-metadata">

**Author:** ![Herteby](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/herteby/32/1329_2.png) [@Herteby](https://discourse.elm-lang.org/u/Herteby)\
**Post date:** [April 23, 2019, 2:34pm UTC](https://discourse.elm-lang.org/t/2-3x-faster-list-concat-implementation/3533/6 "2019-04-23T14:34:21Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![robin.heggelund](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/robin.heggelund/32/1330_2.png) [@robin.heggelund](https://discourse.elm-lang.org/u/robin.heggelund)\
**Post date:** [April 24, 2019, 4:55am UTC](https://discourse.elm-lang.org/t/2-3x-faster-list-concat-implementation/3533/7 "2019-04-24T04:55:33Z")

</div>

Interesting. I promise to take a look at this during the weekend, and give a status update shortly thereafter.

---

<div class="post-metadata">

**Author:** ![Jan\_Hrcek](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/jan_hrcek/32/451_2.png) [@Jan\_Hrcek](https://discourse.elm-lang.org/u/Jan_Hrcek)\
**Post date:** [April 24, 2019, 5:08am UTC](https://discourse.elm-lang.org/t/2-3x-faster-list-concat-implementation/3533/8 "2019-04-24T05:08:59Z")

</div>

@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.

---

<div class="post-metadata">

**Author:** ![robin.heggelund](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/robin.heggelund/32/1330_2.png) [@robin.heggelund](https://discourse.elm-lang.org/u/robin.heggelund)\
**Post date:** [April 26, 2019, 3:49am UTC](https://discourse.elm-lang.org/t/2-3x-faster-list-concat-implementation/3533/9 "2019-04-26T03:49:56Z")

</div>

So, I’ve taken a look. As promised, here’s my take on it: [https://github.com/elm/core/pull/1026#issuecomment-486915865](https://github.com/elm/core/pull/1026#issuecomment-486915865)

---

<div class="post-metadata">

**Author:** ![turboMaCk](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/turbomack/32/355_2.png) [@turboMaCk](https://discourse.elm-lang.org/u/turboMaCk)\
**Post date:** [April 26, 2019, 4:39pm UTC](https://discourse.elm-lang.org/t/2-3x-faster-list-concat-implementation/3533/10 "2019-04-26T16:39:46Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![system](https://canada1.discourse-cdn.com/flex035/uploads/elm_lang/original/1X/50a05e53677a2c3b47776d7abd0f113eb50193a1.png) [@system](https://discourse.elm-lang.org/u/system)\
**Post date:** [May 6, 2019, 4:39pm UTC](https://discourse.elm-lang.org/t/2-3x-faster-list-concat-implementation/3533/11 "2019-05-06T16:39:49Z")

</div>

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.