Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Consider new way to emit let functions #2020

Open
showell opened this issue Nov 17, 2019 · 1 comment
Open

Consider new way to emit let functions #2020

showell opened this issue Nov 17, 2019 · 1 comment

Comments

@showell
Copy link

showell commented Nov 17, 2019

The Elm compiler could improve its support for lazy operations with inner let functions by emitting JS that doesn't reassign inner functions on every call to the outer function.

There is a related issue here that motivates this suggestion. Html.Lazy.lazy cannot optimize inner functions because the same function keeps getting assigned to new local variables:

elm/html#201

The above issue includes an SSCCE for the particular case of Html.Lazy.

Here I'll discuss it in even more generic terms, using this repo branch as an example:

https://github.com/showell/elm-start/commits/hoist-js

Consider this Elm code:

three =
    3


fac n =
    List.product (List.range 1 n)


someMath a b c =
    let
        double x =
            x * 2

        timesThree x =
            x * three

        compute =
            double a + timesThree b + fac c
    in
    compute

The functions double and timesThree are helper functions that are lexically inside someMath, but they're not closing on a, b, or c. The Elm code is semantically equivalent to this:

three =
    3


fac n =
    List.product (List.range 1 n)


double x =
    x * 2

timesThree x =
    x * three

someMath a b c =
    let
        compute =
            double a + timesThree b + fac c
    in
    compute

The compiler currently emits this for the first Elm example above:

var $author$project$Main$someMath = F3(
    function (a, b, c) {
        var timesThree = function (x) {
            return x * $author$project$Main$three;
        };
        var _double = function (x) {
            return x * 2;
        };
        var compute = (_double(a) + timesThree(b)) + $author$project$Main$fac(c);
        return compute;
    });

Obviously, the above JS computes the correct values, but it needlessly reassigns _double and timesThree every time you call someMath, and that undermines any possible optimizations in Html.Lazy (or, more precisely, _VirtualDom_diffHelp).

I think Elm could help Html.Lazy by emitting this instead:

var $author$project$Main$someMath2 = (function() {
    var timesThree = function (x) {
        return x * $author$project$Main$three;
    };
    var _double = function (x) {
        return x * 2;
    };

    return F3(
    function (a, b, c) {
        var compute = (_double(a) + timesThree(b)) + $author$project$Main$fac(c);
        return compute;
    });

}());

It's a two-step change here:

  • Wrap someMath2 with (function () { ...}()).
  • Promote timesThree and _double by one scope. (They're still not top-level, so no collision.)

Obviously we leave any function like compute that uses a/b/c exactly where the compiler currently emits it.

Performance

For normal functions, the two semantically equivalent JS functions run at about the same speed. I've run benchmarks on Chrome/FF, and the results are inconclusive, except that either version runs in under a microsecond. The benchmarks are a bit noisy even if you have identical functions. You can run them off my branch:

https://github.com/showell/elm-start/commits/hoist-js

(Remember, don't rebuild index.html, because I manually modified it for demonstration purposes.)

The bigger performance implication here, as mentioned earlier, is that in the second JS version, we only assign timesThree and _double one time. This example is obviously too contrived for Html.Lazy.lazy, but the idea here is that any inner function that you wrap in lazy would be short circuited as long as it doesn't close outer vars.

Details

In order to decide which functions go inside F3(function(a,b,c) {...}) block, it probably makes sense to walk the graph this way:

  • first get all direct callers of a/b/c
  • keep expanding list of inside-F3 functions with any callers (or callers of callers)

The tough case looks something like this:

someMath a b c =
    let
        double x =
            x * 2

        timesThree x =
            x * three

        compute =
            double a + timesThree b + fac c

        sneakyFunctionIndirectlyDependingOnABC =
            compute
    in
    sneakyFunctionIndirectlyDependingOnABC
@showell
Copy link
Author

showell commented Nov 18, 2019

Here is example code that computes shows how you might compute which let functions are truly local, i.e. bound to the outer function's arguments (either directly or indirectly):

https://github.com/showell/elm-start/blob/truly-local-let-functions/src/CallGraph.elm

I assume the compiler could do something similar without incurring too much expense. The main logic is just streaming a bunch of list/set/graph helpers together:

getTrueLocals : Ast -> Set String
getTrueLocals ast =
    let
        localFuncNames =
            ast.lets
                |> List.map .name
                |> Set.fromList

        -- does our let function directly depend on any
        -- of the outerArgs?
        isDirectDep letF =
            Set.intersect letF.deps ast.outerArgs
                |> Set.isEmpty
                |> not

        -- exclude toplevel deps; they're just noise
        localDeps letF =
            Set.intersect
                letF.deps
                localFuncNames

        directLocals =
            ast.lets
                |> List.filter isDirectDep
                |> List.map .name
                |> Set.fromList

        depGraph =
            ast.lets
                |> List.map
                    (\letF ->
                        ( letF.name
                        , localDeps letF
                        )
                    )
                |> Dict.fromList

        reversedGraph =
            depGraph
                |> reverseGraph

        allTrueLocals =
            getAllDescendants reversedGraph directLocals
    in
    allTrueLocals

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant