TCO: output closure-free while loop

[matthewleon]

TCO outputs a while loop that calls a function on every iteration, incurring a performance penalty.

An example. Here is the definition of tailRec from purescript-tailrec:

tailRec :: forall a b. (a -> Step a b) -> a -> b
tailRec f = go <<< f
  where
  go (Loop a) = go (f a)
  go (Done b) = b

It compiles to the following:

var tailRec = function (f) {
    var go = function ($copy_v) {
        var $tco_done = false;
        var $tco_result;
        function $tco_loop(v) {
            if (v instanceof Loop) {
                $copy_v = f(v.value0);
                return;
            };
            if (v instanceof Done) {
                $tco_done = true;
                return v.value0;
            };
            throw new Error("Failed pattern match at Control.Monad.Rec.Class line 96, column 3 - line 96, column 25: " + [ v.constructor.name ]);
        };
        while (!$tco_done) {
            $tco_result = $tco_loop($copy_v);
        };
        return $tco_result;
    };
    return function ($53) {
        return go(f($53));
    };
};

In this case, and many others, the $tco_loop function could be inlined into the while loop, simplifying the resulting code and improving its performance.

To be sure, I imagine the TCO behavior was initially created this way with good reason, so there might be some situation where we can't safely get rid of the closure. We should seek to document this.

[natefaubion]

#2719

[matthewleon]

@natefaubion It seems that the change to which you've linked is perhaps being overprotective, then?

[matthewleon]

(particularly, the "values which might capture variables" criterion)

[natefaubion]

TCO outputs a while loop that calls a function on every iteration, incurring a performance penalty.

Do you have a benchmark that shows the difference?

[matthewleon]

https://github.com/matthewleon/purescript-tco-bench

This implements a simple sum function on lists. The FFI version is basically the TCO'd version with the closure inlined.

benchmarking for TCO:
mean = 3.74 ms
stddev = 491.69 μs
min = 3.31 ms
max = 6.79 ms

benchmarking for hand-inlined TCO:
mean = 3.24 ms
stddev = 386.21 μs
min = 2.92 ms
max = 5.34 ms

Granted, this is something of a worst case; summation is so simple that the the overhead of calling into the TCO function shows its weight here. I tried a similar benchmark on list reversal (I can link if you are curious) and the penalty only turned out to be a few %.

[matthewleon]

There is some discussion here regarding ES6 compiler output permitting us to use let(block-scoped var) in TCO:

#2574

This would be a potentially easy solution to the issue, allowing us to (maybe) revert to the behavior before the merge linked above.

Some let docs: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/let