Previous Next |
Because functional programs tend to use many small functions, and especially because they pass functions from one place to another, an important optimization technique is inline expansion of function calls: replacing a function call with a copy of the function body. For example, in Program 15.6, an observeInt is any function (like the putInt of Program 15.5) that "observes" an integer and then continues. doList is a function that applies an observer f to a list l, and then continues. In this case, the observer is not putInt but printDouble, which prints i followed by 2i. Thus, printTable prints a table of integers, each followed by its double.
printTable in PureFunJava.class list {int head; list tail;
public list (int head, list tail) {
this.head=head; this.tail=tail;
}}
type observeInt = (int,cont) -> answer;
class PrintT {
public answer doList (observeInt f, list l, cont c) {
return if (l===null)
c();
else {
public answer doRest() {return doList(f, l.tail, c);}
return f(l.head, doRest);
};
}
public int double(int j) {return j+j;}
public answer printDouble(int i, cont c) {
public answer again() {return putInt(double(i), c);}
return putInt(i, again);
}
public answer printTable(list l, cont c) {
return doList(printDouble, l, c);
}
public static void main(string argv[]) {
list mylist = ... ;
return printTable(mylist, IO.exit);
}
}
For comparison, Program 15.7a is a regular Java program that does the same thing.
Java implementation of printTable.class list {int head; int tail;}
class PrintT {
int double(int j) {return j+j;} class list {int head; int tail;}
void printDouble(int i) { class PrintT {
putInt(i); putInt(double(i)); void printTable(list l) {
} while (l != null) {
int i = l.head;
void printTable(list l) { putInt(i);
while (l != null) { putInt(i+1);
printDouble(l.head); l = l.tail;
l = l.tail; }
} }
public static void main(...){ public static void main(...){
printTable(mylist); printTable(mylist);
}} }}
(a) As written (b) Optimized
Program 15.6 uses a generic list-traverser, doList, for which any function can be plugged in. Although in this case printDouble is used, the same program could reuse doList for other purposes that print or "observe" all the integers in the list. But Program 15.7a lacks this flexibility - it calls printDouble directly. If compiled naively, the pure functional program - which passed print- Double as an argument - will do many more function calls than the imperative program. By using inline expansion and tail-call optimizations (described in ), Program 15.6 can be optimized into machine instructions equivalent to the efficient loop of Program 15.7b. Avoiding variable capture We must be careful about variable names when doing inlining in MiniJava (or Java), where a local declaration creates a "hole" in the scope of an outer variable:
class A { 1 int x = 5 2 int function g(int y) { 3 return y+x; } 4 int f(int x) { 5 return g(1)+x; } 6 void main() { ... f(2)+x ... } }
The formal parameter x on line 4 creates a hole in the scope of the variable x declared on line 1, so that the x on line 5 refers to the formal parameter, not the variable. If we were to inline-expand the call to g(1) on line 5 by substituting the body of g for the call, we could not simply write 1+x, for then we'd have
4 int f(int x) { 5 return return 1+x;+x; }
but the first x on line 5 is now incorrectly referring to f's parameter instead of the variable declared on line 1. To solve this problem, we could first rename, or α-convert, the formal parameter of f, then perform the substitution:
2 int function g(int y) { int function g(int y) { 3 return y+x; return y+x; } } 4 int f(int a) { int f(int a) { 5 return g(1)+a; return {return 1+x;}+a; } }
Alternately, we can rename the actual parameters instead of the formal parameters, and define the substitution function to avoid substituting for x inside the scope of a new definition of x. But the best solution of all for avoiding variable capture is to have an earlier pass of the compiler rename all variables so that the same variable name is never declared twice. This simplifies reasoning about, and optimizing, the program. By the way, the expression {return 1+x;} in line 5 is completely equivalent to the expression (1+x). Rules for inlining Algorithm 15.8 gives the rules for inline expansion, which can apply to imperative or functional programs. The function body B is used in place of the function call f(…), but within this copy of B, each actual parameter is substituted for the corresponding formal parameter. When the actual parameter is just a variable or a constant, the substitution is very simple (Algorithm 15.8a). But when the actual parameter is a nontrivial expression, we must first assign it to a new variable (Algorithm 15.8b).
ALGORITHM 15.8: Inline expansion of function bodies. We assume that no two declarations declare the same name.
(a) When the actual parameters are simple variables i_{1},…, i_{n}. Within the scope of: |
(b) When the actual parameters are nontrivial expressions, not just variables. Within the scope of: |
int f(a_{1},..., a_{n})B (where B is a Compound) the expression f(i_{1},..., i_{n}) rewrites to B[a_{1} ↦ i_{1},..., a_{n} ↦ i_{n}] |
int f(a_{1},..., a_{n})B the expression f(E_{1},..., E_{n}) rewrites to { int i_{1} = E_{1}; ⋮ int i_{n} = E_{n}; return B[a_{1} ↦ i_{1},..., a_{n} ↦ i_{n}]; } where i_{1},..., i_{n} are previously unused names. |
For example, in Program 15.6 the function call double(i) can be replaced by a copy of j+j in which each j is replaced by the actual parameter i. Here we have used Algorithm 15.8a, since i is a variable, not a more complicated expression. Suppose we wish to inline-expand double(g(x)); if we improperly use Algorithm 15.8a, we obtain g(x)+g(x), which computes g(x) twice. Even though the principle of equational reasoning assures that we will compute the same result each time, we do not wish to slow down the computation by repeating the (potentially expensive) computation g(x). Instead, Algorithm 15.8b yields
{int i = g(x); return i+i;}
which computes g(x) only once. In an imperative program, not only is g(x)+g(x) slower than
{int i = g(x); return i+i;}
but - because g may have side effects - it may compute a different result! Again, Algorithm 15.8b does the right thing. Dead function elimination If all the calls to a function (such as double) have been inline-expanded, and if the function is not passed as an argument or referenced in any other way, the function itself can be deleted. Inlining recursive functions Inlining doList into printTable yields this new version of printTable:
public answer printTable(list l, cont c) { return if (l===null) c(); else { public answer doRest() { return doList(printDouble, l.tail, c); } return printDouble(l.head, doRest); }; }
This is not so good: printTable calls printDouble on l.head, but to process l.tail it calls doList as before. Thus, we have inline-expanded only the first iteration of the loop. We would rather have a fully customized version of doRest; therefore, we do not inline-expand in this way. For recursive functions we use a loop-preheader transformation (Algorithm 15.9). The idea is to split f into two functions: a prelude called from outside, and a loop header called from inside. Every call to the loop header will be a recursive call from within itself, except for a single call from the prelude. Applying this transformation to doList yields
ALGORITHM 15.9: Loop-preheader transformation.public answer doList (observeInt fX, list lX, cont cX) {
public answer doListX(observeInt f, list l, cont c) {
return if (l==null)
c();
else {
public answer doRest() {return doListX(f, l.tail, c);}
return f(l.head, doRest);
};
}
return doListX(fX,lX,cX);
}
where the new doList is the prelude, and doListX is the loop header. Notice that the prelude function contains the entire loop as an internal function, so that when any call to doList is inline-expanded, a new copy of doListX comes along with it. Loop-invariant arguments In this example, the function doListX is passing around the values f and c that are invariant - they are the same in every recursive call. In each case, f is fX and c is cX. A loop-invariant hoisting transformation (Algorithm 15.10) can replace every use of f with fX, and c with cX).
ALGORITHM 15.10: Loop-invariant hoisting.If every of f′ within B is of the form f′ (E_{1}, …, E_{i − 1}, a_{i}, E_{i + 1}, …, E_{n}) such that the i th argument is always a_{i}, then rewrite
Where every call f′ (E_{1}, …, E_{i − 1}, a_{i}, E_{i + 1}, …, E_{n}) within B is rewritten as f′ (E_{1}, …, E_{i − 1}, E_{i + 1}, …, E_{n}).
Applying this transformation to doList yields
public answer doList (observeInt f, list lX, cont c) { public answer doListX(list l) { return if (l==null) c(); else { public answer doRest() {return doListX(l.tail);} return f(l.head, doRest); }; } return doListX(lX); }
Finally, in printTable, when the call doList(printDouble,l,c) is inlined, we obtain:
public answer printTable(list l, cont c) { public answer doListX(list l) { return if (l==null) c(); else { public answer doRest() {return doListX(l.tail);} return printDouble(l.head, doRest); }; } return doListX(l); }
Cascading inlining In this version of printTable,wehave printDouble applied to arguments (instead of just passed to doList), so we can inline- expand that call, yielding
public answer printTable(list l, cont c) { public answer doListX(list l) { return if (l==null) c(); else { public answer doRest() {return doListX(l.tail);} return { int i = l.head; public answer again() {return putInt(i+i, doRest);} return putInt(i, again); }; }; } return doListX(l); }
Avoiding code explosion Inline-expansion copies function bodies. This generally makes the program bigger. If done indiscriminantly, the size of the program explodes; in fact, it is easy to construct cases where expanding one function call creates new instances that can also be expanded, ad infinitum. There are several heuristics that can be used to control inlining:
Expand only those function-call sites that are very frequently executed; determine frequency either by static estimation (loop-nest depth) or by feedback from an execution profiler.
Unnesting braces Since the FunJava expression
{ Decl_{1} return { Decl_{2} return Exp}}
is exactly equivalent to
{ Decl_{1} Decl_{2} return Exp}
we end up with Program 15.11.
printTable as automatically specialized.1 public answer printTable(list l, cont c) {
2 public answer doListX(list l) {
3 return if (l==null) c()
4 else {public answer doRest() {
5 return doListX(l.tail);}
6 int i = l.head;
7 public answer again() {
8 return putInt(i+i,doRest); }
9 return putInt(i,again);
10 }
11 return doListX(l);
12 }
The optimizer has taken a program written with abstraction (with a general- purpose doList) and transformed it into a more efficient, special-purpose program (with a special-purpose doListX that calls putInt directly).
JaVa | Previous Next |