22. Compilation

Last revision:  April 15 1998

Here we explore the notion of compilation, focussing on demonstrating the advantage in speed and the limitation of using atomic data types to represent machine-precision numbers.

Mathematica operations/structures introduced: 
     Compile[]
     inline functions

Compilation

Recall that compiled programs have one overarching advantage: the great reduction in execution time.  Recall also that using machine-size integers and approximations also affords the user a great reduction in execution time.  For these reason, practically every computer application which you execute is using a compiled, rather than interpreted, program, one which uses machine-size integers and approximations whenever possible.  For instance, Mathematica itself is such a program.  We have not yet been able to write our own compiled "programs" requiring machine-size numbers because Mathematica's standard mode is to interpret all commands statement-by-statement and to evaluate all expressions with as much accuracy as possible.  We can explore compilation and the use of machine-size numbers, however, by having Mathematica compile particular functions.

Mathematica permits the compilation of Mathematica code using the "Compile[]" function.  The "Compile[]" function takes a sequence of Mathematica expressions and converts them to a language very similar to machine language, a language which the computer can execute much faster, thereby mimicing actual compilation.  In order to use the "Compile[]" function, however, we must decide what the data types of the parameters are, and we are limited to "_Integer" (machine-size integer), "_Real" (machine-precision approximate real number), and "True|False" (a boolean value).  [Complex numbers are also permitted.]  Compiled functions, because they use the internal language of computers, are not permitted to take advantage of Mathematica's predefined structured data types such as lists and patterns.  If we insist on using such structures, some intermediary must transform the structures back to these machine data types, by breaking a list into its component pieces, breaking huge integers into smaller machine-size pieces, and so on.  In a compiled setting, we would have to decide ourselves how to represent lists as sequences of machine-size integers, how to represent a string as a sequence of characters, and so forth, and such decisions form the basis for a course in data structures and algorithms.

The syntax for the basic "Compile[]" command is "Compile[list,expr]", where "list" is either a list of single names, which represent parameters of data type "_Real", or a list of pairs consisting of a name and a data type selected from the ones above, and where "expr" is some Mathematica expression.  For example, suppose we'd like a function to compute "x^y", where "x" and "y" are assumed to be names of type Real:

myPower = Compile[{x,y},x^y]

We could have specified that "x" be considered of type Real and "y" a machine-size integer by writing instead

myPowInt = Compile[{{x,_Real},{y,_Integer}},x^y]

It is important that we use the "Set" operator "=" and not the "SetDelayed" operator ":=", for the latter will perform the compilation only after the function is called, not before, and in what follows we will want to time the function without counting the time of compilation.

Comparing Speed with myPower

Here we submit compiled functions and standard Mathematica interpreted functions to a head-to-head test.  The operations we include in the functions are standard arithmetic functions, which are the real strength of compiled programs, instead of "Plot[]" calls or complicated list-based functions.  Our first attempt is to define a function "myPower" which is a compiled version of "myPower2", both of which take two arguments, presumed Real, and raise the first argument to the second.  We then compare their timings when the arguments are "2.0" and "3.0".

Clear[myPower,myPower2]
myPower = Compile[{x,y},x^y]
myPower2[x_,y_] := x^y

Timing[myPower[2.0,3.0]]
Timing[myPower2[2.0,3.0]]

Execute the above cell a couple of times to insure that you are not getting exceptional timings; the "Timing[]" function can sometimes give answers which are too small or negative, because the actual time to execute the function is too small to measure.   After executing the functions several times, however, you may have become convinced that it is difficult to tell the difference between functions which execute so quickly.  In order to get a better idea, we'll have each of the functions executed 10000 times, using the Mathematica command "Do[]".

Timing[Do[myPower[2.0,3.0],{10000}]]
Timing[Do[myPower2[2.0,3.0],{10000}]]

Now the difference should be clear.  The compiled version executes more than twice as quickly as the interpreted version.  Now notice that we're using an interpreted "Do[]" command to call the compiled function.  How would the timing speed up if we compiled the "Do[]" inside the function?

Clear[myPower3]
myPower3 = Compile[{x,y},Do[x^y,{10000}]]
Timing[myPower3[2.0,3.0]]

The conclusion:  compiling the "Power" operator "^" and the "Do[]" command both speed up the functions by a remarkable amount.

Data Type Checking in Compiled Functions

What if you give a compiled function values for the parameters which do not match the required data types?  Unlike most languages, Mathematica prevents us from encountering a serious error in this situation.  First, it tries to convert the values to the desired values, for instance by converting integers to approximations.  Second, if it cannot convert, or reaches an error in the calculation using the compiled code, Mathematica simply reverts to evaluating the original expression---in its standard interpreted mode.  One consequence is that is never hurts to compile a function in Mathematica, since if the data type values don't match, Mathematica simply executes the function in its normal fashion anyway.  Let's look at some associated timings.

Clear[myPower,myPower2]
myPower = Compile[{x,y},Do[x^y,{10000}];x^y]
myPower2[x_,y_] := (Do[x^y,{10000}];x^y)

Note that the two functions now have a return value, namely, the value of "x^y".

Timing[myPower[2.0,3.0]]
Timing[myPower2[2.0,3.0]]

Here the timings are as we would expect, and the return values are "8.".

Timing[myPower[2,3]]
Timing[myPower2[2,3]]

In the timings above, we see that the timings are still in favor of the compiled version, indicating  that the compiled version was executed, but we also note that "2" and "3" were converted to Real data (the default for parameters of compiled functions), since the result from the compiled version is "8.", not "8".

Finally, we'll give Mathematica some numbers which Mathematica can't handle in machine-precision:  we'll ask for 10^1000, which is outside the range of machine-precision real numbers, and, for that matter, machine-size integers, too.

Timing[myPower[10,1000]]
Timing[myPower2[10,1000]]

Note that the compiled version actually took longer,  because the compiled code was attempted first, resulting in an error, and the Mathematica interpreted code was then used.

It is interesting to note that many Mathematica functions actually compile a function they are given before they use the function over and over again.  One example is "Plot[]"; instead of plotting 1000 points, say, and having to interpret the function 1000 times, Mathematica compiles it first.  To see the difference, we can explicitly instruct "Plot[]" not to compile. Here are two examples.

Timing[Plot[Sin[x],{x,0,1},PlotPoints->1000,
Compiled->False]]

Timing[Plot[Sin[x],{x,0,1},PlotPoints->1000]]

(We use 1000 points in the plots in order to witness a significant difference in the timings.)

Taking a Look at Compiled Code

To gain a better idea of just what "machine language" looks like, we'll ask Mathematica to produce the compiled code  for a compiled function.  We need only use the "?" command.

Clear[myPower]
myPower = Compile[{x,y},Do[x^y,{10000}];x^y];
?myPower

As we see, the internal format of a compiled function is a list which contains, first, a list of the assumed data types, then a list of "registers" that will be used in the code, followed by a list of computer "instructions" given in a certain code, and finally the Mathematica function that will be executed if the compiled code fails or is inappropriate for the data.  One could decipher the compiled code, using information in Wolfram Research's technical reports on compiled code, but our interest here is to understand the idea of machine language without understanding how to program in machine language.

Inline Functions

Recall that we learned that inline functions were faster than functions called under standard function calls.  Let's take a look at the time/length-of-code tradeoff.  We confess at the outset that anonymous functions, which share syntactical similarities with inline functions as used in other languages, actually take longer in Mathematica.  Instead, we'll implement a true analogue of inline functions, by expanding out the function calls ourselves.

In practice, remember, inline functions are implemented by eliminating the standard function call; the code for the inline function is written directly into the compiled code each time the function is referenced.  A standard function call implementation, on the other hand, requires storing parameters, jumping to a different section of compiled code where the function code is stored, and finally copying a return value back to the original place--but only one copy of the compiled code for the function needs to be stored.

We implement a compiled version of a standard function as follows.

Clear[myPower,myPower2]
myPower = Compile[{x,y},x^y]
myPower2 = Compile[{x,y},Do[myPower[x,y],{100}]]

Notice that "myPower" is compiled and placed in memory somewhere, while "myPower2" references "myPower" 100 times, thereby executing a function call 100 times.

We implement an inline version of the function by simply repeating "x^y" 100 times, thereby eliminating the function call at all, instead inserting whatever compiled code is necessary 100 times.

Clear[myPower3]
myPower3 = Compile[{x,y},
	x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;
	x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;
	x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;
	x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;
	x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;
	x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;
	x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;
	x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;
	x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;
	x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;x^y;]

Now we do a head-to-head test.

Timing[myPower2[2.,3.]]

Timing[myPower3[2.,3.]]

To make the timing more accurate, let's execute each 100 times.

Timing[Do[myPower2[2.,3.],{100}]]

Timing[Do[myPower3[2.,3.],{100}]]

A fairly dramatic difference:  function calls take time!  Now let's look at the length of the compiled code.  For the standard function call, we have two functions:

?myPower

?myPower2

For the inline function implementation, we have only one (long) function:

?myPower3

Notes

It is also possible to require that, during compilation of an expressions, certain quantities have certain data types, using a third argument to the "Compile[]" command; see "?Compile".

The reason that anonymous functions take just as long, or longer, is that Mathematica actually uses them to define a function, complete with necessary function calls, instead of copying the expression directly, as an inline function implementation would do.