# Performance of tail recursive function

**URL:** <https://discourse.elm-lang.org/t/performance-of-tail-recursive-function/5279>\
**Category:** Learn\
**Created:** [March 7, 2020, 12:35am UTC](https://discourse.elm-lang.org/t/performance-of-tail-recursive-function/5279 "2020-03-07T00:35:07Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![m-shaka](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/m-shaka/32/3015_2.png) [@m-shaka](https://discourse.elm-lang.org/u/m-shaka)\
**Post date:** [March 7, 2020, 12:35am UTC](https://discourse.elm-lang.org/t/performance-of-tail-recursive-function/5279/1 "2020-03-07T00:35:08Z")

</div>

Hi. This question maybe one about JavaScript, but I think it can help Elm compiler’s improvement.

I want to know why `fibTopLevel` performs better than `fibLetIn` on Google Chrome and Firefox (probably on other browsers too).

```auto
fibLetIn n =
    let
        helper m acc acc2 =
            case m of
                0 ->
                    acc

                1 ->
                    acc2

                _ ->
                    helper (m - 1) acc2 (acc + acc2)
    in
    helper n 0 1

fibHelper n acc acc2 =
    case n of
        0 ->
            acc

        1 ->
            acc2

        _ ->
            fibHelper (n - 1) acc2 (acc + acc2)

fibTopLevel n =
    fibHelper n 0 1

```

The only diffrence between them is whether the helper function is bound in top level or let … in statement.

Also generated JavaScript codes are almost the same.

```auto
var $author$project$Main$fibLetIn = function (n) {
	var helper = F3(
		function (m, acc, acc2) {
			helper:
			while (true) {
				switch (m) {
					case 0:
						return acc;
					case 1:
						return acc2;
					default:
						var $temp$m = m - 1,
							$temp$acc = acc2,
							$temp$acc2 = acc + acc2;
						m = $temp$m;
						acc = $temp$acc;
						acc2 = $temp$acc2;
						continue helper;
				}
			}
		});
	return A3(helper, n, 0, 1);
};
var $author$project$Main$fibHelper = F3(
	function (n, acc, acc2) {
		fibHelper:
		while (true) {
			switch (n) {
				case 0:
					return acc;
				case 1:
					return acc2;
				default:
					var $temp$n = n - 1,
						$temp$acc = acc2,
						$temp$acc2 = acc + acc2;
					n = $temp$n;
					acc = $temp$acc;
					acc2 = $temp$acc2;
					continue fibHelper;
			}
		}
	});
var $author$project$Main$fibTopLevel = function (n) {
	return A3($author$project$Main$fibHelper, n, 0, 1);
};

```

Here is benchmark.  
[https://ellie-app.com/8dWrK9R93WLa1](https://ellie-app.com/8dWrK9R93WLa1)

Chrome  
 ![fib-chrome](https://canada1.discourse-cdn.com/flex035/uploads/elm_lang/original/2X/3/37b1757ef7b8617f2e5bf95b2ef4fb72fb5ddc8b.png)

---

<div class="post-metadata">

**Author:** ![rupert](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/rupert/32/1775_2.png) [@rupert](https://discourse.elm-lang.org/u/rupert)\
**Post date:** [March 7, 2020, 7:23pm UTC](https://discourse.elm-lang.org/t/performance-of-tail-recursive-function/5279/2 "2020-03-07T19:23:59Z")

</div>

Is this with the `elm --optimize` flag?

---

<div class="post-metadata">

**Author:** ![m-shaka](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/m-shaka/32/3015_2.png) [@m-shaka](https://discourse.elm-lang.org/u/m-shaka)\
**Post date:** [March 8, 2020, 2:19am UTC](https://discourse.elm-lang.org/t/performance-of-tail-recursive-function/5279/3 "2020-03-08T02:19:40Z")

</div>

`--optimize` flag makes no difference…

---

<div class="post-metadata">

**Author:** ![joakin](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/joakin/32/171_2.png) [@joakin](https://discourse.elm-lang.org/u/joakin)\
**Post date:** [March 8, 2020, 8:39am UTC](https://discourse.elm-lang.org/t/performance-of-tail-recursive-function/5279/4 "2020-03-08T08:39:18Z")

</div>

The generated code is extremely similar. Maybe the function in function definition or the size of the outer function are tripping the JITs. Very hard to debug!

---

<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:** [March 8, 2020, 3:00pm UTC](https://discourse.elm-lang.org/t/performance-of-tail-recursive-function/5279/5 "2020-03-08T15:00:14Z")

</div>

Interesting! Performance can be super tricky.

If you’re interested in checking it out further, you could see what code V8 spits out. Robin does that in this article: [https://dev.to/skinney/improving-elm-s-compiler-output-5e1h](https://dev.to/skinney/improving-elm-s-compiler-output-5e1h)

---

<div class="post-metadata">

**Author:** ![jreusch](https://avatars.discourse-cdn.com/v4/letter/j/b5e925/32.png) [@jreusch](https://discourse.elm-lang.org/u/jreusch)\
**Post date:** [March 8, 2020, 4:55pm UTC](https://discourse.elm-lang.org/t/performance-of-tail-recursive-function/5279/6 "2020-03-08T16:55:53Z")

</div>

You may be measuring the performance of the garbage collector here - The amount of work the `fib` function does is incredibly tiny - it manages to calculate the 100th fibonacci number nearly 6 million times per second! On a 3GHz machine, that would mean it takes around 500 CPU cycles per call, which means it takes approx. 5 cycles per loop body. Considering most instructions actually take more than 1 cycle to complete, this should already be as fast as you can get in a “naive” way (Elm is not exactly known for being close to metal, there is not much we can do).

I made a similar comparison using `Benchmark.scale` here, but for the sake of not running into `Infinity`, I chose the harmonic instead of the fibonacci series (it works with your original functions as well, I just wanted to avoid floating-point weirdness):

[https://ellie-app.com/8fH3hwBNfbfa1](https://ellie-app.com/8fH3hwBNfbfa1)

 ![harmonic-series-benchmark](https://canada1.discourse-cdn.com/flex035/uploads/elm_lang/original/2X/e/e60f111036a24384eabb0f4c4d8d35ace7646c09.png)

1. It takes a while until the runs/second behave like you would expect - runtime does not seem to increase 10x if there are less than 1000 iterations happening
2. Starting at around the same point, the runs/second for both versions are roughly the same

So when doing less than 1000 runs, we do not seem to benchmark our function much at all - It’s pretty much just the overhead of calling things in Javascript. The one difference being that the `fibLetIn` version **also** allocates a new function object (“closure”) on the heap on every call, which seems to take the majority of the time if `n` is small.

---

<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:** [March 9, 2020, 3:14pm UTC](https://discourse.elm-lang.org/t/performance-of-tail-recursive-function/5279/7 "2020-03-09T15:14:47Z")

</div>

Internally, `elm-explorations/benchmark` basically does the same thing @jreusch did, but it’s hard to “tune” that scaling factor at the library level because you have three basic kinds of benchmarks:

- math stuff (`fib`, `harmonic`)
- data structures (think tuning `Array.get` or `Dict.get` for performance.)
- people’s app functions (`update` or similar)

`elm-explorations/benchmark` is currently tuned to give good results for data structures since that’s the primary optimization opportunity core team members see in Elm at the moment (cf. Robin’s work to optimize `Array` for 0.19.0.)

That means when you say…

> So when doing less than 1000 runs, we do not seem to benchmark our function much at all - It’s pretty much just the overhead of calling things in Javascript.

… the benchmark harness _should_ be taking care of that for you. In this case, it looks like we start to get on a better track for a linear fit around 128 iterations of harmonic—that is, doubling the work done doubles the runtime.

 ![image](https://canada1.discourse-cdn.com/flex035/uploads/elm_lang/original/2X/5/5aa5fda69b01f12acc5d1141172b7ab3059eed1c.png)

I think there may be an opportunity to find a better algorithm for sample size. If you want to explore this yourself, [`Benchmark.LowLevel`](https://package.elm-lang.org/packages/elm-explorations/benchmark/latest/Benchmark-LowLevel) exposes the functions you’d need to create a new runner.

I haven’t done this myself, though, since it’s a lot of work to make sure the math checks out. A bad benchmark can be really misleading. I have also put my work on `elm-explorations/benchmark` on hold because the time spent in DOM stuff far outweighs algorithmic complexity stuff for most apps.

---

<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:** [March 9, 2020, 3:16pm UTC](https://discourse.elm-lang.org/t/performance-of-tail-recursive-function/5279/8 "2020-03-09T15:16:58Z")

</div>

oh, also: when you see less than 99% goodness of fit and the benchmark completes very quickly it’s a good indication that tuning the benchmark may give more accurate results.

---

<div class="post-metadata">

**Author:** ![m-shaka](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/m-shaka/32/3015_2.png) [@m-shaka](https://discourse.elm-lang.org/u/m-shaka)\
**Post date:** [March 14, 2020, 10:22am UTC](https://discourse.elm-lang.org/t/performance-of-tail-recursive-function/5279/9 "2020-03-14T10:22:15Z")

</div>

Thank you for explanation!

I found out that `F3` or `A3`, helper functions for currying generated by Elm compiler, are bottleneck.

I compared `fibLet(1)` and `fib(1)` on Chrome, Firefox and Opera.

```javascript
var fibLet = function (n) {
    var helper_ = function (m, acc, acc2) {
        helper_:
        while (true) {
            switch (m) {
                case 0:
                    return acc;
                case 1:
                    return acc2;
                default:
                    var $temp$m = m - 1,
                        $temp$acc = acc2,
                        $temp$acc2 = acc + acc2;
                    m = $temp$m;
                    acc = $temp$acc;
                    acc2 = $temp$acc2;
                    continue helper_;
            }
        }
    };
    return helper_(n, 0, 1)
}

var helper = function (m, acc, acc2) {
    helper:
    while (true) {
        switch (m) {
            case 0:
                return acc;
            case 1:
                return acc2;
            default:
                var $temp$m = m - 1,
                    $temp$acc = acc2,
                    $temp$acc2 = acc + acc2;
                m = $temp$m;
                acc = $temp$acc;
                acc2 = $temp$acc2;
                continue helper;
        }
    }
}

var fib = function (n) {
    return helper(n, 0, 1)
}

```

`fibLet` performs almost as much as `fib`. Allocation has no harm, or perhaps the browser make some optimization.

But `fibLetWrapped` is extremely slow. (differs only in being wrapped by `F3` and `A3` from `fibLet`)

```javascript
var fibLetWrapped = function (n) {
    var helper_ = F3(
        function (m, acc, acc2) {
            helper_:
            while (true) {
                switch (m) {
                    case 0:
                        return acc;
                    case 1:
                        return acc2;
                    default:
                        var $temp$m = m - 1,
                            $temp$acc = acc2,
                            $temp$acc2 = acc + acc2;
                        m = $temp$m;
                        acc = $temp$acc;
                        acc2 = $temp$acc2;
                        continue helper_;
                }
            }
        });
    return A3(helper_, n, 0, 1)
}

```

Here is the result. (Chrome)

 ![fib](https://canada1.discourse-cdn.com/flex035/uploads/elm_lang/original/2X/2/284d186773c039a6fae8d0eaf1541ce4f6d2e7aa.png)

You can try it [here](https://m-shaka.github.io/fib-bench-for-elm/index.html)

[Source code](https://github.com/m-shaka/fib-bench-for-elm/blob/master/index.html)

---

<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:** [March 24, 2020, 10:22am UTC](https://discourse.elm-lang.org/t/performance-of-tail-recursive-function/5279/10 "2020-03-24T10:22:19Z")

</div>

Closed on March 24, 2020, 10:22am UTC

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