Computing is usually defined as the activity of using and improving computer hardware and software. It is the computer-specific part of information technology...
Compiler optimization is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the amount of memory occupied...
In programming, a call site of a function is a line in the code which calls a function. A call site passes zero or more arguments to the function, and receives zero or more return values.-Example:...
with the body of the callee. This optimization may improve time and space usage at runtime, at the possible cost of increasing the final size of the program (i.e. the binary file
Binary file
A binary file is a computer file which may contain any type of data, encoded in binary form for computer storage and processing purposes; for example, computer document files containing formatted text...
In computer science, control flow refers to the order in which the individual statements, instructions, or function calls of an imperative or a declarative program are executed or evaluated....
A branch is sequence of code in a computer program which is conditionally executed depending on whether the flow of control is altered or not . The term can be used when referring to programs in high level languages as well as program written in machine code or assembly language...
or call instruction. With inlining, control drops through directly to the code for the function, without a branch or call instruction. Inlining improves performance
Algorithmic efficiency
In computer science, efficiency is used to describe properties of an algorithm relating to how much of various types of resources it consumes. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or continuous process, where the goal is to reduce...
in several ways:
It removes the cost of the function call and return
Return statement
In computer programming, a return statement causes execution to leave the current subroutine and resume at the point in the code immediately after where the subroutine was called, known as its return address. The return address is saved, usually on the process's call stack, as part of the operation...
In assembly language programming, the function prologue is a few lines of code at the beginning of a function, which prepare the stack and registers for use within the function...
code injected into every function by the compiler.
Eliminating branches and keeping code that is executed close together in memory improves instruction cache performance by improving locality of reference
Locality of reference
In computer science, locality of reference, also known as the principle of locality, is the phenomenon of the same value or related storage locations being frequently accessed. There are two basic types of reference locality. Temporal locality refers to the reuse of specific data and/or resources...
.
Once inlining has been performed, additional intraprocedural optimizations become possible on the inlined function body. For example, a constant
Constant (programming)
In computer programming, a constant is an identifier whose associated value cannot typically be altered by the program during its execution...
passed as an argument, can often be propagated to all instances of the matching parameter, or part of the function may be "hoisted out" of a loop
Loop-invariant code motion
In computer programming, loop-invariant code consists of statements or expressions which can be moved outside the body of a loop without affecting the semantics of the program...
.
The primary cost of inlining is that it tends to increase code size, although it does not always do so. Inlining may also decrease performance in some cases - for instance, multiple copies of a function may increase code size enough that the code no longer fits in the cache, resulting in more cache misses.
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
) support the inline keyword in function definitions. This keyword serves as a "hint" to the compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
that it should try to inline the function. Compilers use a variety of mechanisms, including hints from programmers, to decide which function calls should be inlined.
A compiler is a computer program that transforms source code written in a programming language into another computer language...
usually implement statements with inlining. Loop conditions and loop bodies need lazy evaluation
Lazy evaluation
In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...
. This property is fulfilled when the code to compute loop conditions and loop bodies is inlined. Performance considerations are another reason to inline statements.
In the context of functional programming languages, inline expansion is usually followed by the beta-reduction
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
Copy and paste programming is a pejorative term to describe highly repetitive computer programming code apparently produced by copy and paste operations...
In computer science, source code is text written using the format and syntax of the programming language that it is being written in. Such a language is specially designed to facilitate the work of computer programmers, who specify the actions to be performed by a computer mostly by writing source...
. However, other methods of controlling inlining (see below) are preferable, because they do not precipitate bugs arising when the programmer overlooks a (possibly modified) duplicated version of the original function body, while fixing a bug in the inlined function.
A compiler is a computer program that transforms source code written in a programming language into another computer language...
has decided to inline a particular function, performing the inlining operation itself is usually simple. Depending on whether the compiler inlines functions across code in different languages, the compiler can do inlining on either a high-level intermediate representation (like abstract syntax tree
Abstract syntax tree
In computer science, an abstract syntax tree , or just syntax tree, is a tree representation of the abstract syntactic structure of source code written in a programming language. Each node of the tree denotes a construct occurring in the source code. The syntax is 'abstract' in the sense that it...
s) or a low-level intermediate representation. In either case, the compiler simply computes the arguments
Parameter
Parameter from Ancient Greek παρά also “para” meaning “beside, subsidiary” and μέτρον also “metron” meaning “measure”, can be interpreted in mathematics, logic, linguistics, environmental science and other disciplines....
, stores them in variables corresponding to the function's arguments, and then inserts the body of the function at the call site.
Linkers, as well as compilers, can also do function inlining. When a linker inlines functions, it may inline functions whose source is not available, such as library functions (see link-time optimization
Link-time optimization
Link-time optimization is a type of program optimization performed by a compiler to a program at link time. Link time optimization occurs in programming languages that compile programs on a file-by-file basis , rather than all at once .Once all files have been compiled separately into object files,...
A run-time system is a software component designed to support the execution of computer programs written in some computer language...
can inline function as well. Run-time inlining can use dynamic profiling information to make better decisions about which functions to inline, as in the Java Hotspot compiler.
Here is a simple example of inline expansion performed "by hand" at the source level in the C programming language
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
:
int pred(int x) {
if (x
0)
return 0;
else
return x - 1;
}
Before inlining:
int f(int y) {
return pred(y) + pred(0) + pred(y+1);
}
After inlining:
int f(int y) {
int temp = 0;
if (y 0) temp += 0; else temp += y - 1; /* (1) */
if (0
Note that this is only an example. In an actual C application, it would be preferable to use an inlining language feature such as parameterized macro
Parameterized macro
In computer science, a parameterized macro is a type of macro that is able to insert given objects into its expansion. This gives the macro some of the power of a function....
In various versions of the C and C++ programming languages, an inline function is a function upon which the compiler has been requested to perform inline expansion...
s to tell the compiler to transform the code in this way. The next section lists ways to optimize this code.
Inlining by Assembly macro expansion
Assembler macros provide an alternative approach to inlining whereby a sequence of instructions can normally be generated inline by macro expansion from a single macro source statement (with zero or more parameters). One of the parameters might be an option to alternatively generate a one-time separate subroutine
Subroutine
In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....
containing the sequence and processed instead by an inlined call to the function.
Example:
MOVE FROM=array1,TO=array2,INLINE=NO
Benefits
Inline expansion itself is an optimization, since it eliminates overhead from calls, but it is much more important as an enabling transformation
Enabling transformation
In computer science, an enabling transformation is a compiler optimization that increases the effectiveness of other compiler optimizations. Such an optimization may or may not improve program performance by itself, but it also alters the structure of the program in such a way that other...
. That is, once the compiler expands a function body in the context of its call site—often with arguments that may be fixed constants
Constant (mathematics)
In mathematics, a constant is a non-varying value, i.e. completely fixed or fixed in the context of use. The term usually occurs in opposition to variable In mathematics, a constant is a non-varying value, i.e. completely fixed or fixed in the context of use. The term usually occurs in opposition...
-- it may be able to do a variety of transformations that were not possible before. For example, a conditional branch may turn out to be always true or always false at this particular call site. This in turn may enable dead code elimination
Dead code elimination
In compiler theory, dead code elimination is a compiler optimization to remove code which does not affect the program results. Removing such code has two benefits: it shrinks program size, an important...
In computer programming, loop-invariant code consists of statements or expressions which can be moved outside the body of a loop without affecting the semantics of the program...
, or induction variable elimination.
In the C example in the previous section, optimization opportunities abound. The compiler may follow this sequence of steps:
The temp += 0 statements in the lines marked (1), (2) and (3) do nothing. The compiler can remove them.
The condition 0
0
is always true, so the compiler can replace the line marked (2) with the consequent, temp += 0 (which does nothing).
The compiler can rewrite the condition y+1 0 to y -1.
The compiler can reduce the expression (y + 1) - 1 to y (assuming wraparound overflow semantics)
The expressions y and y+1 cannot both equal zero. This lets the compiler eliminate one test.
The new function looks like:
int f(int y) {
if (y 0)
return y; /* or return 0 */
else if (y
-1)
return y - 1; /* or return -2 */
else
return y + y - 1;
}
Problems
Replacing a call site with an expanded function body can worsen performance
Algorithmic efficiency
In computer science, efficiency is used to describe properties of an algorithm relating to how much of various types of resources it consumes. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or continuous process, where the goal is to reduce...
In computer science, program optimization or software optimization is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources...
An embedded system is a computer system designed for specific control functions within a larger system. often with real-time computing constraints. It is embedded as part of a complete device often including hardware and mechanical parts. By contrast, a general-purpose computer, such as a personal...
s, inlining is usually disadvantageous except for very small functions, such as trivial mutator method
Mutator method
In computer science, a mutator method is a method used to control changes to a variable.The mutator method, sometimes called a "setter", is most often used in object-oriented programming, in keeping with the principle of encapsulation...
s.
The increase in code size may cause a small, critical section of code to no longer fit in the cache
CPU cache
A CPU cache is a cache used by the central processing unit of a computer to reduce the average time to access memory. The cache is a smaller, faster memory which stores copies of the data from the most frequently used main memory locations...
, causing cache misses and slowdown.
The added variables from the inlined procedure may consume additional registers
Processor register
In computer architecture, a processor register is a small amount of storage available as part of a CPU or other digital processor. Such registers are addressed by mechanisms other than main memory and can be accessed more quickly...
, and in an area where register pressure is already high this may force spilling, which causes additional RAM accesses.
A language specification may allow a program to make additional assumptions about arguments to procedures that it can no longer make after the procedure is inlined.
If code size is increased too much, resource constraints such as RAM size may be exceeded, leading to programs that either cannot be run or that cause thrashing. Today, this is unlikely to be an issue with desktop or server computers except with very aggressive inlining, but it can still be an issue for embedded system
Embedded system
An embedded system is a computer system designed for specific control functions within a larger system. often with real-time computing constraints. It is embedded as part of a complete device often including hardware and mechanical parts. By contrast, a general-purpose computer, such as a personal...
s.
Typically, compiler developers keep these issues in mind, and incorporate heuristics into their compilers that choose which functions to inline so as to improve performance, rather than worsening it, in most cases.
Limitations
It is not always possible to inline a subroutine. Consider the case of a subroutine that calls itself recursively until it receives a particular piece of input data from a peripheral. The compiler cannot generally determine when this process will end, so it would never finish inlining if it was designed to inline every single subroutine invocation. Thus, compilers for languages which support recursion must have restrictions on what they will automatically choose to inline.
Selection methods and language support
Many compilers aggressively inline functions wherever it is beneficial to do so. Although it can lead to larger executable
Executable
In computing, an executable file causes a computer "to perform indicated tasks according to encoded instructions," as opposed to a data file that must be parsed by a program to be meaningful. These instructions are traditionally machine code instructions for a physical CPU...
s, aggressive inlining has nevertheless become more and more desirable as memory capacity has increased faster than CPU speed. Inlining is a critical optimization in functional languages
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
This is a list of object-oriented programming programming languages.-Languages with object-oriented features:*ABAP*Ada 95*AmigaE*BETA*Blue*Boo*C++*C#*COBOL*Cobra*ColdFusion*Common Lisp*COOL*CorbaScript*Clarion*CLU*Curl*D*Dylan*E*Eiffel...
s, which rely on it to provide enough context for their typically small functions to make classical optimizations effective.
See also
In computer science, efficiency is used to describe properties of an algorithm relating to how much of various types of resources it consumes. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or continuous process, where the goal is to reduce...
In computing, partial evaluation is a technique for several different types of program optimization by specialization. The most straightforward application is to produce new programs which run faster than the originals while being guaranteed to behave in the same way...
Simon Peyton Jones is a British computer scientist who researches the implementation and applications of functional programming languages, particularly lazy functional languages...
John R. Levine is an Internet author and consultant specializing in email infrastructure, spam filtering, and software patents. He chairs the Anti-Spam Research Group of the Internet Research Task Force , is president of CAUCE , was a member of the ICANN At-Large Advisory...
