Implement function inlining optimisations

[GearsDatapacks]

This was briefly mentioned on Discord as something which would be nice to add in future, but I wanted to create a Github discussion to figure out the details of it as I think it could be a great addition to the language. (See the Discord conversation for an example). I will convert this into an issue once we have a good idea of how this would be implemented.

A couple of initial questions I had:

• When would the compiler decide to inline a function vs calling it?
• Would there be a way, like in some languages, to tell the compiler to inline it (like #[inline] in rust, for example)

[GearsDatapacks]

As for my initial thoughts on the two questions:

• If the function only contains a single expression as the body (although maybe disallowing blocks), it should be inlined. Maybe this could be extended a bit, but I'm not sure how far we would want to go with it
• I would lean towards no, because this might get people into a mindset of premature optimisation, which doesn't really fit with Gleam's style, and also it would require adding another attribute which we probably want to have a minimal number of

[lpil]

Deciding when to inline can be quite hard, so I understand why most languages give the programmer some degree of control over this using some form of annotation.

I'm not too worried about the number of attributes growing, but I wouldn't want their use to become very common. I don't want programmers to feel that they have to worry about this unless they have performance sensitive code and they are benchmarking the result. Perhaps this is a problem we can solve with documentation and education.

I don't know anything about the theory of deciding when to inline. We would want to make sure that Lustre's functions inline, and that result.try and result.map do. I worry that if we are too eager with inline we could massively increase code size and hurt performance. It we go down the annotation route this may be considerably easier to implement.

Another thing to consider is that inlining will change the stacktrace for error message. We want to avoid being confusing.

[GearsDatapacks]

Good to know about your views on the attribute, but yeah I do see people, especially people with backgrounds in high-performance, low-level languages like rust, potentially abusing the feature when it wasn't needed.
If I have time, I might try and look into some theory behind it, and how other languages decide when to inline functions.
As for the stacktrace, I see now that this could be tricky as we don't have control over how the runtime prints it.

[giacomocavalieri]

I remember watching this video about GHC's inlining, it might be useful https://www.youtube.com/watch?v=OqrOZKESmuo

Also there's this paper that looks like a treasure trove of informations: https://www.microsoft.com/en-us/research/wp-content/uploads/2002/07/inline.pdf

[GearsDatapacks]

Just found this message in the resources channel of the programming languages discord. It has a big list of resources on inlining.

[giacomocavalieri]

Inlining Decisions in Visual Studio
https://devblogs.microsoft.com/cppblog/inlining-decisions-in-visual-studio/
C++ Inliner Improvements: The Zipliner
https://devblogs.microsoft.com/cppblog/c-inliner-improvements-the-zipliner/
John Carmack on Inlined Code
https://collincode.wordpress.com/2016/07/19/john-carmack-on-inlined-code/
John Carmack on Inlined Code
http://number-none.com/blow/john_carmack_on_inlined_code.html
How RyuJIT inlines a function (heuristics)
https://web.archive.org/web/20210517175814/https://egorbo.com/how-inlining-works.html
Smarter C/C++ inlining with attribute((flatten))
https://awesomekling.github.io/Smarter-C++-inlining-with-attribute-flatten/
Do compilers take inline as a hint?
https://blog.tartanllama.xyz/inline-hints/
cmd/compile: improve inlining cost model
golang/go#17566
What does 'inline' mean?
https://forum.dlang.org/thread/[email protected]
Zebu VM check_should_inline_func()
https://gitlab.anu.edu.au/mu/mu-impl-fast/-/blob/6572fe39ae65e424bdaf612f461fe60c8fc0b95f/src/compiler/passes/inlining.rs#L89
Warp: Improved JS performance in Firefox 83
https://hacks.mozilla.org/2020/11/warp-improved-js-performance-in-firefox-83/
shouldInline
https://searchfox.org/mozilla-central/rev/cecdac0aa5733fee515a166b6e31e38cc58abf32/js/src/jit/TrialInlining.cpp#504

Just copying the message for folks who might be interested and are not on Discord

[lpil]

@richard-viney has raised here a really good reason to have inlining: it would make functions like this stack safe in JS

import gleam/bool

pub fn main() {
  go(10_000)
}

fn go(i: Int) -> Int {
  use <- bool.guard(i < 0, -1)

  case i {
    0 -> 0
    _ -> go(i - 1)
  }
}

[GearsDatapacks]

That's a good point. I haven't had a lot of time to look into this recently; hopefully I'll be able to get back to it soon

[lpil]

RE implementing this- perhaps we could figure out just how to do the actual inlining to start and delay figuring out the heuristics for now. Just being able to do it for some predetermined functions in core packages such as the stdlib could be valuable, and we may decide to make it an attribute.

[GearsDatapacks]

Ok, I'd be up for looking into that! Should I make an issue?

[lpil]

Yes please

[yoshi-monster]

I had this idea on Discord while thinking about mutual TCO in Javascript:

all statically dispatched function calls in tail position should be inlined

statically dispatched here means any function value that the compiler can dereference at compile time. In the context of TCO, I meant that all function calls in tail position that call another local function in the same module can be transformed to a continue or goto in the mode switch (see Louis' example in #3830), without first figuring out if there even is mutatal recursion going on;

My thoughts here were that not caring about circular recursion makes it better actually, since we want to mimic Erlangs' LCO which also happens without recursion going on.

You can draw tail calls like a state machine (this is again the example from #3830):

down <-+--> up
 ^     |
 +-----+

these diagrams can include calls to arguments if those happen to be in call position:

bool.guard --> alternative
result.try --> continuation

This means that if bool.guard is called inside of a recursive call, we can find those loops by looking at the diagrams:

go --> [ bool.guard --> alternative ]
^                           |
+---------------------------+

Being able to inline bool.guard or result.try thus requires 2 things:

• TCO/inlining this analysis has to be enabled to work across module boundaries (this could be a little bit tricky because it would mean whole-program optimisation)
• The compiler needs to be able to figure out that alternative is statically known (therefore the call is statically dispatched) at the call-side, in particular when passing a function literal
• It's probably a good idea to have some other heuristic or maybe something like an @inline attribute to not have the bundle size explode

As always, I'm probably just making lots of wrong assumptions on the fly, please yell at me :)

[lpil]

Wouldn't that result in a huge explosion in code size and so negatively impact load speed and performance?

[yoshi-monster]

It's probably a good idea to have some other heuristic or maybe something like an @inline attribute to not have the bundle size explode

Yes, probably :)

The state machine graphs I made can be computed pretty efficiently; finding strongly connected components in this graph should be equivalent to finding the groups of functions where TCO should be applied. I'm not entirely sure how this interacts with variables yet. I drew those square brackets around bool.guard above, hopefully there is a way to do something similar. Or maybe solving the graph problem is fast enough to just do it every time? hm.