Five Things That Make Go Fast (2/5): Function Calls are not Free

Function calls are not free

Three things happen when a function is called. A new stack frame is created, and the details of the caller recorded. Any registers which may be overwritten during the function call are saved to the stack. The processor computes the address of the function and executes a branch to that new address.

Gocon-2014-15

Because function calls are very common operations, CPU designers have worked hard to optimise this procedure, but they cannot eliminate the overhead.

Gocon-2014-16

Depending on what the function does, this overhead may be trivial or significant. A solution to reducing function call overhead is an optimisation technique called Inlining.

Gocon-2014-17

The Go compiler inlines a function by treating the body of the function as if it were part of the caller. Inlining has a cost; it increases binary size. It only makes sense to inline when the overhead of calling a function is large relative to the work the function does, so only simple functions are candidates for inlining. Complicated functions are usually not dominated by the overhead of calling them and are therefore not inlined.

Gocon-2014-18

This example shows the function Double calling util.Max . To reduce the overhead of the call to util.Max , the compiler can inline util.Max into Double , resulting in something like this:

Gocon-2014-19

After inlining there is no longer a call to util.Max , but the behaviour of Double is unchanged. Inlining isn’t exclusive to Go. Almost every compiled or JITed language performs this optimisation. But how does inlining in Go work?

The Go implementation is very simple. When a package is compiled, any small function that is suitable for inlining is marked and then compiled as usual. Then both the source of the function and the compiled version are stored.

Gocon-2014-20

This slide shows the contents of util.a . The source has been transformed a little to make it easier for the compiler to process quickly. When the compiler compiles Double it sees that util.Max is inlinable, and the source of util.Max is available. Rather than insert a call to the compiled version of util.Max , it can substitute the source of the original function. Having the source of the function enables other optimizations.

Gocon-2014-21

In this example, although the function Test always returns false, Expensive cannot know that without executing it. When Test > is inlined, we get something like this:

Gocon-2014-22

The compiler now knows that the expensive code is unreachable.

Not only does this save the cost of calling Test , it saves compiling or running any of the expensive code that is now unreachable. The Go compiler can automatically inline functions across files and even across packages. This includes code that calls inlinable functions from the standard library.

 

原文链接 发表于2014/06/07