Copyright (C) 1997 Rich Neidinger, John Swallow, and Todd Will.  Free for
distribution to college and university instructors for personal,
non-commercial use.  If these notebooks are used in a course, the authors
request $20 per student.

22. Compilation

Last revision:  November 14 1996

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.

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.