stil4m/elm-syntax

Using an array for Application/FunctionCall

Opened this issue · 2 comments

jfmengels commented

The arguments for Expression.Application (renamed to FunctionCall in v8) are stored in a List. That has the unfortunate consequence that in the parser we have to append a newly discovered argument to the end:

elm-syntax/src/Elm/Parser/Expression.elm

Line 147 in 142c74a

Expression.Application (args ++ [ right ])

And as far as I understand, we have to do that for new argument. I'm pretty sure that making this operation efficient would make the parser quite faster, as function calls are very common. (Maybe we have to rethink function calls in the pratt parser, but I haven't been able to figure out how).

My proposal is to have the arguments to a function call be an Array. I'm still brainstorming so I'm not entirely convinced either.

Pros:

  • Faster parsing of function calls
  • Access to the n-th argument of a function call becomes much more performant.
  • Transforming pipelines to FunctionCalls is faster because appending to the end is fast (we do this in elm-review-simplify quite a lot for instance)

Cons:

  • No more pattern matching on arguments. This is a real shame though...
  • Iteration may be more painful in some cases, as we lose the ability to iterate through
  • We need a representation of a non-empty Array, as in v8 we introduced the guarantee that function calls have at least one argument. We could do FunctionCall fnNode firstArg arrayOfArgs ->, but that would mean that accessing the N-th argument becomes less straightforward.

Let me know what you think.

lue-bird commented

Definitely interesting, though I feel details like that should never leak, especially if they make the user experience that much worse.

I had not bothered trying optimizations with Application since common calls usually have only 1-2, maybe 3 arguments which should make the overhead minimal.
But if we find this is a problem, I do think this is "solve-able" to a degree at the parser level (e.g. reverse all arguments on the left in an operation or end)

Also in my experience, constructing an Array with push isn't all that fast in the first place, especially compared to very small lists.

Another thought: Maybe switching to a custom "snoc" will already give most of the performance gains, trying right now. ++ is faster, probably thanks to eol2 BUT this one does the trick

  • 👍1
  • ❤️1
jfmengels commented

this one does the trick

Oh that is quite nice! It's not solving the issue entirely but it at least makes it better, and solves it for the most common-cases. In breaking-changes-v8 we already do this to some extent because we have separated the function from the expression (although we still need to extract the first argument to use a non-empty list, which comes down exactly to what you're doing, without the need to :: at the end).

especially if they make the user experience that much worse.

I agree. I do think that being able to easily access the N-th element is quite nice though, but the loss of pattern matching is quite terrible.