Why is inlining considered faster than a function

问题:

Now, I know it's because there's not the overhead of calling a function, but is the overhead of calling a function really that heavy (and worth the bloat of having it inlined) ?

From what I can remember, when a function is called, say f(x,y), x and y are pushed onto the stack, and the stack pointer jumps to an empty block, and begins execution. I know this is a bit of an oversimplification, but am I missing something? A few pushes and a jump to call a function, is there really that much overhead?

Let me know if I'm forgetting something, thanks!

回答1:

Aside from the fact that there's no call (and therefore no associated expenses, like parameter preparation before the call and cleanup after the call), there's another significant advantage of inlining. When the function body is inlined, it's body can be re-interpreted in the specific context of the caller. This might immediately allow the compiler to further reduce and optimize the code.

For one simple example, this function

void foo(bool b) {
  if (b) {
    // something
  }
  else {
    // something else
  }
}

will require actual branching if called as a non-inlined function

foo(true);
...
foo(false);

However, if the above calls are inlined, the compiler will immediately be able to eliminate the branching. Essentially, in the above case inlining allows the compiler to interpret the function argument as a compile-time constant (if the parameter is a compile-time constant) - something that is generally not possible with non-inlined functions.

However, it is not even remotely limited to that. In general, the optimization opportunities enabled of inlining are significantly more far-reaching. For another example, when the function body is inlined into the specific caller's context, the compiler in general case will be able to propagate the known aliasing-related relationships present in the calling code into the inlined function code, thus making it possible to optimize the function's code better.

Again, the possible examples are numerous, all of them stemming from the basic fact that inlined calls are immersed into the specific caller's context, thus enabling various inter-context optimizations, which would not be possible with non-inlined calles. With inlining you basically get many individual versions of your original function, each version is tailored and optimized individually for each specific caller context. The price of that is, obviously, the potential danger of code bloat, but if used correctly, it can provide noticeable performance benefits.

回答2:

"A few pushes and a jump to call a function, is there really that much overhead?"

It depends on the function.

If the body of the function is just one machine code instruction, the call and return overhead can be many many hundred %. Say, 6 times, 500% overhead. Then if your program consists of nothing but a gazillion calls to that function, with no inlining you've increased the running time by 500%.

However, in the other direction inlining can have a detrimental effect, e.g. because code that without inlining would fit in one page of memory doesn't.

So the answer is always when it comes to optimization, first of all MEASURE.

回答3:

There is no calling and stack activity, which certainly saves a few CPU cycles. In modern CPU's, code locality also matters: doing a call can flush the instruction pipeline and force the CPU to wait for memory being fetched. This matters a lot in tight loops, since primary memory is quite a lot slower than modern CPU's.

However, don't worry about inlining if your code is only being called a few times in your application. Worry, a lot, if it's being called millions of times while the user waits for answers!

回答4:

The classic candidate for inlining is an accessor, like std::vector<T>::size().

With inlining enabled this is just the fetching of a variable from memory, likely a single instruction on any architectures. The "few pushes and a jump" (plus the return) is easily multiple times as much.

Add to that the fact that, the more code is visible at once to an optimizer, the better it can do its work. With lots of inlining, it sees lots of code at once. That means that it might be able to keep the value in a CPU register, and completely spare the costly trip to memory. Now we might take about a difference of several orders of magnitude.

And then theres template meta-programming. Sometimes this results in calling many small functions recursively, just to fetch a single value at the end of the recursion. (Think of fetching the value of the first entry of a specific type in a tuple with dozens of objects.) With inlining enabled, the optimizer can directly access that value (which, remember, might be in a register), collapsing dozens of function calls into accessing a single value in a CPU register. This can turn a terrible performance hog into a nice and speedy program.

---

Hiding state as private data in objects (encapsulation) has its costs. Inlining was part of C++ from the very beginning in order to minimize these costs of abstraction. Back then, compilers were significantly worse in detecting good candidates for inlining (and rejecting bad ones) than they are today, so manually inlining resulted in considerable speed gainings.
Nowadays compilers are reputed to be much more clever than we are about inline. Compilers are able to inline functions automatically or don't inline functions users marked as inline, even though they could. Some say that inlining should be left to the compiler completely and we shouldn't even bother marking functions as inline. However, I have yet to see a comprehensive study showing whether manually doing so is still worth it or not. So for the time being, I'll keep doing it myself, and let the compiler override that if it thinks it can do better.

回答5:

let

int sum(const int &a,const int &b)
{
     return a + b;
}
int a = sum(b,c);

is equal to

int a = b + c

No jump - no overhead

回答6:

Consider a simple function like:

int SimpleFunc (const int X, const int Y)
{
    return (X + 3 * Y); 
}    

int main(int argc, char* argv[])
{
    int Test = SimpleFunc(11, 12);
    return 0;
}

This is converted to the following code (MSVC++ v6, debug):

10:   int SimpleFunc (const int X, const int Y)
11:   {
00401020   push        ebp
00401021   mov         ebp,esp
00401023   sub         esp,40h
00401026   push        ebx
00401027   push        esi
00401028   push        edi
00401029   lea         edi,[ebp-40h]
0040102C   mov         ecx,10h
00401031   mov         eax,0CCCCCCCCh
00401036   rep stos    dword ptr [edi]

12:       return (X + 3 * Y);
00401038   mov         eax,dword ptr [ebp+0Ch]
0040103B   imul        eax,eax,3
0040103E   mov         ecx,dword ptr [ebp+8]
00401041   add         eax,ecx

13:   }
00401043   pop         edi
00401044   pop         esi
00401045   pop         ebx
00401046   mov         esp,ebp
00401048   pop         ebp
00401049   ret

You can see that there are just 4 instructions for the function body but 15 instructions for just the function overhead not including another 3 for calling the function itself. If all instructions took the same time (they don't) then 80% of this code is function overhead.

For a trivial function like this there is a good chance that the function overhead code will take just as long to run as the main function body itself. When you have trivial functions that are called in a deep loop body millions/billions of times then the function call overhead begins to become large.

As always, the key is profiling/measuring to determine whether or not inlining a specific function yields any net performance gains. For more "complex" functions that are not called "often" the gain from inlining may be immeasurably small.

回答7:

There are multiple reasons for inlining to be faster, only one of which is obvious:

• No jump instructions.
• better localization, resulting in better cache utilization.
• more chances for the compiler's optimizer to make optimizations, leaving values in registers for example.

The cache utilization can also work against you - if inlining makes the code larger, there's more possibility of cache misses. That's a much less likely case though.

回答8:

A typical example of where it makes a big difference is in std::sort which is O(N log N) on its comparison function.

Try creating a vector of a large size and call std::sort first with an inline function and second with a non-inlined function and measure the performance.

This, by the way, is where sort in C++ is faster than qsort in C, which requires a function pointer.

回答9:

One other potential side effect of the jump is that you might trigger a page fault, either to load the code into memory the first time, or if it's used infrequently enough to get paged out of memory later.

回答10:

Andrey's answer already gives you a very comprehensive explanation. But just to add one point that he missed, inlining can also be extremely valuable on very short functions.

If a function body consists of just a few instructions, then the prologue/epilogue code (the push/pop/call instructions, basically) might actually be more expensive than the function body itself. If you call such a function often (say, from a tight loop), then unless the function is inlined, you can end up spending the majority of your CPU time on the function call, rather than the actual contents of the function.

What matters isn't really the cost of a function call in absolute terms (where it might take just 5 clock cycles or something like that), but how long it takes relative to how often the function is called. If the function is so short that it can be called every 10 clock cycles, then spending 5 cycles for every call on "unnecessary" push/pop instructions is pretty bad.

回答11:

(and worth the bloat of having it inlined)

It is not always the case that in-lining results in larger code. For example a simple data access function such as:

int getData()
{
   return data ;
}

will result in significantly more instruction cycles as a function call than as an in-line, and such functions are best suited to in-lining.

If the function body contains a significant amount of code the function call overhead will indeed be insignificant, and if it is called from a number of locations, it may indeed result in code bloat - although your compiler is as likely to simply ignore the inline directive in such cases.

You should also consider the frequency of calling; even for a large-ish code body, if the function is called frequently from one location, the saving may in some cases be worthwhile. It comes down to the ratio of call-overhead to code body size, and the frequency of use.

Of course you could just leave it up to your compiler to decide. I only ever explicitly in-line functions that comprise of a single statement not involving a further function call, and that is more for speed of development of class methods than for performance.

回答12:

Because there's no call. The function code is just copied

回答13:

Inlining a function is a suggestion to compiler to replace function call with definition. If its replaced, then there will be no function calling stack operations [push, pop]. But its not guaranteed always. :)

--Cheers

回答14:

Optimizing compilers apply a set of heuristics to determine whether or not inlining will be beneficial.

Sometimes gain from the lack of function call will outweigh the potential cost of the extra code, sometimes not.

回答15:

Inlining makes the big difference when a function is called multiple times.

回答16:

Because no jump is performed.