# List.map optimization options

**URL:** <https://discourse.elm-lang.org/t/list-map-optimization-options/7426>\
**Category:** Show and Tell\
**Created:** [June 4, 2021, 1:34pm UTC](https://discourse.elm-lang.org/t/list-map-optimization-options/7426 "2021-06-04T13:34:59Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![andre-dietrich](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/andre-dietrich/32/4106_2.png) [@andre-dietrich](https://discourse.elm-lang.org/u/andre-dietrich)\
**Post date:** [June 4, 2021, 1:34pm UTC](https://discourse.elm-lang.org/t/list-map-optimization-options/7426/1 "2021-06-04T13:34:59Z")

</div>

A few hours ago I looked at the implementation of List.map, which looks like this:

```elm
map : (a -> b) -> List a -> List b
map f xs =
  foldr (\x acc -> cons (f x) acc) [] xs

```

however, for me it seems that `foldr` is not tail-call optimizable. So I tried another version:

```elm
map f =
    List.foldl (\x acc -> (::) (f x) acc) []
        >> List.reverse

```

The additional List.reverse does not seem to be a problem on Firefox as the following animation shows:

![ezgif.com-gif-maker(1)](https://user-images.githubusercontent.com/3089101/120809323-373e1780-c54a-11eb-99cd-d9a4b022face.gif)

On Chromium this is slightly different and the benefits of the `foldl` version seem to start for lists larger than 500. Below that the original `List.map` seems to perfom better, but less than 5%. However on Firefox the results seem to be constantly better on average 25%.

## Step 2

Only for curiosity, I added a local `List.map1` function that does the same as `List.map` but it uses a Kernel function … The patches look like this:

```elm
-- ~/.elm/0.19.1/packages/elm/core/1.0.5/src/List.elm

...

map1 : (a -> result) -> List a -> List result
map1 =
  Elm.Kernel.List.map1

...

```

```javascript
// ~/elm/0.19.1/packages/elm/core/1.0.5/src/Elm/Kernel/List.js

...

var _List_map1 = F2(function(f, xs)
{
	for (var arr = []; xs.b ; xs = xs.b) // WHILE_CONSES
	{
		arr.push(f(xs.a));
	}
	return _List_fromArray(arr);
});

...

```

And boom, on Chromium I got a performance boost up to 250%, seems to be constant, tested for list lengths from 5 to 5000 … On Firefox, the results seem to be similar, however it is dropping from 250% to 60% on lists with a 5000 elements…

## Conclusion

I have no idea which optimizations might be performed by the compiler with longer pipes of List.maps, etc. Although I had tested it with pipes also and it seems to be promising. But maybe this is an optimization that can be added to the core libs, not only into List …

## Appendix

```elm
module Main exposing (..)

import Benchmark exposing (..)
import Benchmark.Runner exposing (BenchmarkProgram, program)

main : BenchmarkProgram
main =
    program suite

map f =
    List.foldl (\x acc -> (::) (f x) acc) []
        >> List.reverse

suite : Benchmark
suite =
    let
        sampleList =
            List.repeat 1000 0 |> List.indexedMap (\i _ -> i)
    in
    Benchmark.compare "Mapping"
        "List.map"
        (\_ -> List.map ((*) 2) sampleList )
        "custom map"
        (\_ -> map ((*) 2) sampleList )

```

---

<div class="post-metadata">

**Author:** ![andre-dietrich](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/andre-dietrich/32/4106_2.png) [@andre-dietrich](https://discourse.elm-lang.org/u/andre-dietrich)\
**Post date:** [June 4, 2021, 1:35pm UTC](https://discourse.elm-lang.org/t/list-map-optimization-options/7426/2 "2021-06-04T13:35:32Z")

</div>

![screenshot_10](https://user-images.githubusercontent.com/3089101/120808792-b4b55800-c549-11eb-90c8-a210ab608c31.png)

---

<div class="post-metadata">

**Author:** ![andre-dietrich](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/andre-dietrich/32/4106_2.png) [@andre-dietrich](https://discourse.elm-lang.org/u/andre-dietrich)\
**Post date:** [June 4, 2021, 1:36pm UTC](https://discourse.elm-lang.org/t/list-map-optimization-options/7426/3 "2021-06-04T13:36:25Z")

</div>

![screenshot_1000](https://user-images.githubusercontent.com/3089101/120808815-bda62980-c549-11eb-9b97-7c35a719c213.png)

---

<div class="post-metadata">

**Author:** ![opvasger](https://avatars.discourse-cdn.com/v4/letter/o/8e8cbc/32.png) [@opvasger](https://discourse.elm-lang.org/u/opvasger)\
**Post date:** [June 4, 2021, 2:08pm UTC](https://discourse.elm-lang.org/t/list-map-optimization-options/7426/4 "2021-06-04T14:08:06Z")

</div>

nice work! ☀

I’m using [elm-optimize-level-2](https://discourse.elm-lang.org/t/announcing-elm-optimize-level-2/6192) for applying this sort of optimizations - I don’t know if you’re aware of the project, but it’s in the same space as the exploration you’re doing, and your work could probably find a home there!

---

<div class="post-metadata">

**Author:** ![andre-dietrich](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/andre-dietrich/32/4106_2.png) [@andre-dietrich](https://discourse.elm-lang.org/u/andre-dietrich)\
**Post date:** [June 4, 2021, 2:34pm UTC](https://discourse.elm-lang.org/t/list-map-optimization-options/7426/5 "2021-06-04T14:34:07Z")

</div>

Thanks for mentioning this project, I was playing around with it on an earlier stage, some time ago … This is a good idea, I will have a deeper look and create an issue, maybe they are already using this kind of optimization …

---

<div class="post-metadata">

**Author:** ![mdgriffith](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/mdgriffith/32/61_2.png) [@mdgriffith](https://discourse.elm-lang.org/u/mdgriffith)\
**Post date:** [June 4, 2021, 3:10pm UTC](https://discourse.elm-lang.org/t/list-map-optimization-options/7426/6 "2021-06-04T15:10:12Z")

</div>

Cool! Yeah, an alternative List.map implementation was brought up a little while ago which might be interesting to compare: [A faster `List.map` for Elm](https://discourse.elm-lang.org/t/a-faster-list-map-for-elm/6721)

That’s currently in elm-optimize-level-2, though I still need to do a release for it.

---

<div class="post-metadata">

**Author:** ![andre-dietrich](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/andre-dietrich/32/4106_2.png) [@andre-dietrich](https://discourse.elm-lang.org/u/andre-dietrich)\
**Post date:** [June 5, 2021, 4:42pm UTC](https://discourse.elm-lang.org/t/list-map-optimization-options/7426/7 "2021-06-05T16:42:33Z")

</div>

I have seen, that elm-optimize-level-2 already does this kind of optimization as native F2 function … haven’t been aware of … I will use it definitely in the future …

---

<div class="post-metadata">

**Author:** ![andre-dietrich](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/andre-dietrich/32/4106_2.png) [@andre-dietrich](https://discourse.elm-lang.org/u/andre-dietrich)\
**Post date:** [June 7, 2021, 4:30pm UTC](https://discourse.elm-lang.org/t/list-map-optimization-options/7426/8 "2021-06-07T16:30:27Z")

</div>

I played around a bit with different kinds of function definitions, and it turns out (I guess its quite obvious) that the simple pattern :

```elm
fn : List a -> List b -> List b
fn input output =
  case input of
    [] -> List.reverse output

    x :: xs ->
      fn xs (doSomething x :: output)

```

generates the most performant code … I tried this out with different List-functions and for different sizes. You can try this out here, checkout the project [GitHub - andre-dietrich/elm-blist](https://github.com/andre-dietrich/elm-blist) and with `cd benchmark` and `elm reactor` you can try it out by yourself.

However, I tried to reimplement `map`, `filter`, `indexedMap`, `partition`, and `unzip` and I got performance boosts up to **300%** and more (at least on Chromium). Firefox and Web as an Safari-alternative performed also better … Well in this case 100% means that it is two times faster compared to the original implementation, so 300% will be 4 times faster… I hope I am not mixing something up … However I did not check the Memory-consumption so far…

**If I am not making a horrible mistake somewhere** … It would be great (at least from the point of green-IT) to update the elm-core functions accordingly …

![filter](https://raw.githubusercontent.com/andre-dietrich/elm-blist/master/pics/filter.png)

---

<div class="post-metadata">

**Author:** ![andre-dietrich](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/andre-dietrich/32/4106_2.png) [@andre-dietrich](https://discourse.elm-lang.org/u/andre-dietrich)\
**Post date:** [June 7, 2021, 4:31pm UTC](https://discourse.elm-lang.org/t/list-map-optimization-options/7426/9 "2021-06-07T16:31:03Z")

</div>

![indexedMap](https://raw.githubusercontent.com/andre-dietrich/elm-blist/master/pics/indexedMap.png)

---

<div class="post-metadata">

**Author:** ![andre-dietrich](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/andre-dietrich/32/4106_2.png) [@andre-dietrich](https://discourse.elm-lang.org/u/andre-dietrich)\
**Post date:** [June 7, 2021, 4:31pm UTC](https://discourse.elm-lang.org/t/list-map-optimization-options/7426/10 "2021-06-07T16:31:33Z")

</div>

![map](https://raw.githubusercontent.com/andre-dietrich/elm-blist/master/pics/map.png)

---

<div class="post-metadata">

**Author:** ![andre-dietrich](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/andre-dietrich/32/4106_2.png) [@andre-dietrich](https://discourse.elm-lang.org/u/andre-dietrich)\
**Post date:** [June 7, 2021, 4:32pm UTC](https://discourse.elm-lang.org/t/list-map-optimization-options/7426/11 "2021-06-07T16:32:04Z")

</div>

![partition](https://raw.githubusercontent.com/andre-dietrich/elm-blist/master/pics/partition.png)

---

<div class="post-metadata">

**Author:** ![andre-dietrich](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/andre-dietrich/32/4106_2.png) [@andre-dietrich](https://discourse.elm-lang.org/u/andre-dietrich)\
**Post date:** [June 7, 2021, 4:32pm UTC](https://discourse.elm-lang.org/t/list-map-optimization-options/7426/12 "2021-06-07T16:32:41Z")

</div>

![unzip](https://raw.githubusercontent.com/andre-dietrich/elm-blist/master/pics/unzip.png)

---

<div class="post-metadata">

**Author:** ![mdgriffith](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/mdgriffith/32/61_2.png) [@mdgriffith](https://discourse.elm-lang.org/u/mdgriffith)\
**Post date:** [June 8, 2021, 5:01pm UTC](https://discourse.elm-lang.org/t/list-map-optimization-options/7426/13 "2021-06-08T17:01:28Z")

</div>

Nice! You might try it out against the implementation in elm-optimize-level-2, which is here:

> <https://github.com/mdgriffith/elm-optimize-level-2/blob/master/src/transforms/replaceListFunctions.ts>

The elm-opt-2 version is able to get away with not having to do the `List.reverse` at the end. (though of course we’re in JS land)

---

<div class="post-metadata">

**Author:** ![andre-dietrich](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/andre-dietrich/32/4106_2.png) [@andre-dietrich](https://discourse.elm-lang.org/u/andre-dietrich)\
**Post date:** [June 10, 2021, 11:33am UTC](https://discourse.elm-lang.org/t/list-map-optimization-options/7426/14 "2021-06-10T11:33:14Z")

</div>

I created two composed tests one for the original core functions and one for the elm optimized output

1. [Main](https://andre-dietrich.github.io/elm-blist/original)
2. [Main](https://andre-dietrich.github.io/elm-blist/optimized)

The source-code is here: [elm-blist/gh-pages at master · andre-dietrich/elm-blist · GitHub](https://github.com/andre-dietrich/elm-blist/tree/master/gh-pages)

It seems that elm-opt-2 is performing better (the core function in this case are the optimized functions):

 ![screenshot](https://canada1.discourse-cdn.com/flex035/uploads/elm_lang/original/2X/1/183435c81304090ab3fe11e3bf2be734efb69993.png)

> Note: I used elm-optimize-level-2 to generate the code, but after looking on the generated source-code, I could not find the new List-core functions, so I added them manually.

> <https://github.com/andre-dietrich/elm-blist/blob/d683fee04d6d916bffff2416d085b2b8c65e4892/gh-pages/optimized.html#L3835-L3852>

---

<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:** [June 20, 2021, 11:33am UTC](https://discourse.elm-lang.org/t/list-map-optimization-options/7426/15 "2021-06-20T11:33:53Z")

</div>

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