# Benchmarking alternative List.map implementations

**URL:** <https://discourse.elm-lang.org/t/benchmarking-alternative-list-map-implementations/417>\
**Category:** Learn\
**Created:** [December 31, 2017, 4:25pm UTC](https://discourse.elm-lang.org/t/benchmarking-alternative-list-map-implementations/417 "2017-12-31T16:25:17Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![rtfeldman](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/rtfeldman/32/50_2.png) [@rtfeldman](https://discourse.elm-lang.org/u/rtfeldman)\
**Post date:** [December 31, 2017, 4:25pm UTC](https://discourse.elm-lang.org/t/benchmarking-alternative-list-map-implementations/417/1 "2017-12-31T16:25:18Z")

</div>

Awhile back @ilias wrote a [cool post](https://groups.google.com/forum/#!topic/elm-dev/2uXw4gw3_yw) about making `List.map` faster.

I was looking at current the current `core` implementation of `List.map` - which uses a `List.foldr` under the hood - and it occurred to me that it might be faster if it used `List.foldl` instead, which doesn’t convert to an array first.

So [I benchmarked it](https://ellie-app.com/fnnntGw2za1/0) using [`elm-benchmark`](http://package.elm-lang.org/packages/BrianHicks/elm-benchmark/latest). The results?

### Firefox 58 on macOS 10.13.2, 2013 MacBook Pro

![38 AM](https://cdck-file-uploads-canada1.s3.dualstack.ca-central-1.amazonaws.com/flex035/uploads/elm_lang/original/1X/5768ca6339ab9bd76808e068d19094b00a755fe7.png)

### Chrome 63 on macOS 10.13.2, 2013 MacBook Pro

![43 AM](https://cdck-file-uploads-canada1.s3.dualstack.ca-central-1.amazonaws.com/flex035/uploads/elm_lang/original/1X/c0df05752ee5b8d50ff3e4f960891bca62e46557.png)

### Safari 11.0.2 on macOS 10.13.2, 2013 MacBook Pro

![28 AM](https://cdck-file-uploads-canada1.s3.dualstack.ca-central-1.amazonaws.com/flex035/uploads/elm_lang/original/1X/c0c3c4d77c1d2f8ddb02401beecea6735c952806.png)

So which implementation runs faster depends on the browser. 😅

I was really surprised by this outcome. I assumed the numbers would fluctuate cross-browser, but expected a consistent winner across the three. I can’t explain why foldr wins on Safari and loses in Chrome and FF.

Does anyone know cross-browser JS engine implementations well enough to explain this result?

---

<div class="post-metadata">

**Author:** ![brian](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/brian/32/2180_2.png) [@brian](https://discourse.elm-lang.org/u/brian)\
**Post date:** [December 31, 2017, 4:43pm UTC](https://discourse.elm-lang.org/t/benchmarking-alternative-list-map-implementations/417/2 "2017-12-31T16:43:01Z")

</div>

Single thousands of runs per second is quite low. Do the results hold with shorter lists?

---

<div class="post-metadata">

**Author:** ![ilias](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/ilias/32/6_2.png) [@ilias](https://discourse.elm-lang.org/u/ilias)\
**Post date:** [December 31, 2017, 4:43pm UTC](https://discourse.elm-lang.org/t/benchmarking-alternative-list-map-implementations/417/3 "2017-12-31T16:43:42Z")

</div>

Safari often behaves pretty unpredictable in my tests, I haven’t quite figured out why that is exactly. If I rerun that benchmark a couple of times, goodness of fit fluctuates between 70 and 99, and I get mixed results on both ends of the spectrum.

Important to note, though, is that your `foldlMap` is a `reverseMap`. Hence why we come up with such complicated schemes 😃

---

<div class="post-metadata">

**Author:** ![rtfeldman](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/rtfeldman/32/50_2.png) [@rtfeldman](https://discourse.elm-lang.org/u/rtfeldman)\
**Post date:** [December 31, 2017, 4:45pm UTC](https://discourse.elm-lang.org/t/benchmarking-alternative-list-map-implementations/417/4 "2017-12-31T16:45:38Z")

</div>

> [@brian](#):
>
> Do the results hold with shorter lists?

Shorter than 5 elements?

> [@ilias](#):
>
> Important to note, though, is that your foldlMap is a reverseMap. Hence why we come up with such complicated schemes 😃

Ha, fair point! I could throw a `List.reverse` in there to fix it, but I’m mainly curious about the cross-browser discrepancy. 😄

---

<div class="post-metadata">

**Author:** ![ilias](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/ilias/32/6_2.png) [@ilias](https://discourse.elm-lang.org/u/ilias)\
**Post date:** [December 31, 2017, 4:49pm UTC](https://discourse.elm-lang.org/t/benchmarking-alternative-list-map-implementations/417/5 "2017-12-31T16:49:45Z")

</div>

> [@rtfeldman](#):
>
> Ha, fair point! I could throw a List.reverse in there to fix it, but I’m mainly curious about the cross-browser discrepancy. 😄

Fair enough! I think having the `((+) 5)` in there plays a big role, as that compiles not to partial application but to an anonymous function, created in the function you’re benchmarking. Changing that slightly gives pretty different results: [https://ellie-app.com/fMDPRWdrZa1/0](https://ellie-app.com/fMDPRWdrZa1/0)

---

<div class="post-metadata">

**Author:** ![brian](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/brian/32/2180_2.png) [@brian](https://discourse.elm-lang.org/u/brian)\
**Post date:** [December 31, 2017, 5:02pm UTC](https://discourse.elm-lang.org/t/benchmarking-alternative-list-map-implementations/417/6 "2017-12-31T17:02:33Z")

</div>

> [@rtfeldman](#):
>
> Shorter than 5 elements?

The int lists are 2,000 aren’t they?

---

<div class="post-metadata">

**Author:** ![rtfeldman](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/rtfeldman/32/50_2.png) [@rtfeldman](https://discourse.elm-lang.org/u/rtfeldman)\
**Post date:** [December 31, 2017, 5:57pm UTC](https://discourse.elm-lang.org/t/benchmarking-alternative-list-map-implementations/417/7 "2017-12-31T17:57:56Z")

</div>

Ah, I see what you meant - by “the results” you meant “Safari showing foldr as faster.” (The String lists are 5 elements, but Safari has the same winner as the other browsers on those.)

---

<div class="post-metadata">

**Author:** ![mattpiz](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/mattpiz/32/860_2.png) [@mattpiz](https://discourse.elm-lang.org/u/mattpiz)\
**Post date:** [January 1, 2018, 11:07am UTC](https://discourse.elm-lang.org/t/benchmarking-alternative-list-map-implementations/417/8 "2018-01-01T11:07:08Z")

</div>

I’ve no idea about browser differences, but if performance is really what matters most, using a [recursive definition](https://ellie-app.com/87Ncv5zWRa1/0) is what seems to be the fastest with my tests (especially with firefox, can’t test Safari though)

Firefox 57 on Arch Linux, Intel Core i5 5300U  
 ![Screenshot-2018-1-1 Ellie - (1)](https://canada1.discourse-cdn.com/flex035/uploads/elm_lang/original/1X/90242fcae36626f8af52350bd1c5db11241d03a2.png)

Chromium 63 on Arch Linux, Intel Core i5 5300U  
 ![bench-recursive-map-chromium](https://canada1.discourse-cdn.com/flex035/uploads/elm_lang/original/1X/346c457189e7348553cc70e1cffc0c0808d3efcd.png)

---

<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:** [January 1, 2018, 1:46pm UTC](https://discourse.elm-lang.org/t/benchmarking-alternative-list-map-implementations/417/9 "2018-01-01T13:46:23Z")

</div>

So… Small aside, but `List.foldr` has been changed in `master` to not convert to an Array anymore. I also hope Ilias implementation makes it in as it’s even faster, especially for large lists, although code-size is a concern.

When it comes to your benchmark results, I saw this all the time with my work on `Array`, and this is my theory for why it is so:

There are two surprises here:

1. In all results, even though `foldr` converts the list to an array, then performs the foldr operation on that array (iterating the list twice, essentially) it’s only 9% or 32% slower.

2. In Safari, `foldr` is actually faster.

(1) can be explained by the second pass through the list (the actual foldr pass) doesn’t have to chase pointers in the heap to retrieve it’s results. So the second pass will always be much faster then the first (converting a list to an array). Also, the second pass doesn’t need to constantly check if one is currently holding the empty list, as one already knows the size of the array.

(2) cannot entirely be explained by (1). My theory is simply that Safari (using their FTL jit, which uses LLVM I believe) is able to optimize a loop calling a function better than a loop sometimes calling a function (only when not the empty list), and so two simple passes is faster than one tiny bit more complex pass.

However, there are two things which are kinda important to mention when it comes to benchmarking.

(1) Both `foldl` and `foldr` calls the given function through a A2 wrapper. If the JS engine only ever sees one use of `A2` (like, if currying is never used…), it can inline that into the loop. Making sure that A2 is called differently, like having one benchmark which returns a curried result, could prevent inlining of the A2 call, thus giving you different results.

(2) JIT’s can do loop unrolling if the size of the array is somewhat even (like, say, 5 or 2000). JIT’s cannot do this if you loop until some special condition (like the empty list). Try benchmarking with a non-even number (some prime number bigger than 10) to prevent this optimization in the `foldr` benchmark.

Why create benchmarks in a way that prevents certain optimizations? Cause code in the real-world doesn’t always trigger the JIT’s happy path. This is especially true in Elm, where loops tend to be handled by the same piece of code, preventing certain optimizations to ever be made (as that looping code suddenly needs to handle many different cases instead of potentially just one).

---

<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:** [January 1, 2018, 1:49pm UTC](https://discourse.elm-lang.org/t/benchmarking-alternative-list-map-implementations/417/10 "2018-01-01T13:49:45Z")

</div>

These are assumptions btw, I’ve not digged into the actual code the respective JIT for each browser generates.