What does Compile[] do to make code run so much faster?

Question

I am looking for an ELI5 explanation of what Compile[] in the Wolfram Language context does and why it works so much faster than uncompiled code in certain cases. I am trying to get more insight to this rather than what I know, which is, because Wolfram code becomes "machine code".

Given its power, why does Mathematica not try to compile code in its own functions? If compilation is used for internal functions, why does having a bunch of Mathematica functions followed by one another become so much slower without compiling?

Answer 1

I am looking for an ELI5 explanation ... I am trying to get more insight to this rather than what I know, which is, because Wolfram code becomes "machine code".

Given its power, why does Mathematica not try to compile code in its own functions? If compilation is used for internal functions, why does having a bunch of Mathematica functions followed by one another become so much slower without compiling?

Here is my ELI5 thought process. All code gets compiled (converted) into machine code. Without this happening the machine doesn't know what to do. The problem is that an interpreted language doesn't know if you're going to use a particular sequence of functions again so it throws away the machine code after using it. When the sequence is encountered again it has to go through the same time-consuming process of converting to machine code. A compiler, turns a whole section of high-level code into the most efficient possible machine code and remembers it. The chunk of machine code is stored with a name and doesn't have to be reinterpreted every time it is encountered.

---

P.S.

Another aspect of trying to foretell the future is that Mathematica does not know ahead of time how much flexibility is needed. For example, it may have to allow for delaying evaluation of parts of the expression according to the user's input to the function. Mathematica allows for very general forms of input. Compiling may be able to lose this flexibility in return for speed. It can do this by examining the whole of the compiled section and seeing whether flexibility is required or not.

Answer 2

One of the biggest differences between main kernel evaluation and compiled evaluation in the "Wolfram Virtual Machine" (WVM) is that in the kernel, arbitrary expressions are allowed that are rewritten according to pattern-matching rules and in the WVM things are much more restricted and predictable. For instance, the types of all variables are restricted and can all be predicted at compile time. Only certain functions or restricted versions of them are available. The restrictions and predictability allow for optimizations. The WVM execution cycle is also simpler and faster than the kernel's. The restrictions are significant, and many Mathematica programs cannot be compiled down to WVM code because they violate these restrictions. Pattern-matching is one of the signature features of Mathematica, but it is not available in the WVM.

The new FunctionCompile generalizes things somewhat, but I don't really grok it yet.

Note that Table, Map, Do, etc. do try to compile their functions when the length is long enough. See SystemOptions["CompileOptions"].

Note also that code that operates on medium to large arrays but stays in the MKL/BLAS/LAPACK functions is generally faster uncompiled, although they will be close. (This remark is for 5yo prodigies.)

Answer 3

Extended comment..

I've never come across specifics of what Compile[] specifically does.

That said, a definition re: programming languages in general provides some insight/understanding:

Compiling is the transformation from Source Code (human readable) into machine code (computer executable). ... A compiler takes the recipe (code) for a new program (written in a high level language) and transforms this Code into a new language (Machine Language) that can be understood by the computer itself.

Wolfram has developed the Wolfram Language as a very high even meta-level language.

This provides huge advantages to developers/programers, including: conciseness, clarity, ease of debugging, functional organizational paradigm, and (largely) self-documenting code.

In past conversations, with Wolfram staff, they have describe a process of developing Mathematica functions in C level languages. One would expect Wolfram to compile as much of these efforts as possible into as low a level language as possible.

One always has a trade-off in doing this. Generally the lower level of the language, the faster, BUT the lower level of the language the harder it becomes to modify, debug, and refactor the code.

Observing Wolfram's continuing refactoring of the language, especially in developing more abstract level constructs (e.g., CompiledFunction objects, TemporalData objects) leads me to surmise, that this kind of refactoring/abstraction of the language works hand-in-hand with Wolfram compiling more and more of these constructs and related functions to lower and lower levels of a code stack, with the limit of assembler/machine language.

So, Wolfram, has many incentives to compile everything it can compile.

This becomes obvious, when one runs certain speed tests of Mathematica code vs C, C#, or C++ code. As often as not, when I've done this, Mathematica code just runs faster.

Of course it doesn't do this in every such speed comparison, but it does it often enough to know that the architects at Wolfram do some very smart things.

Thinking through the above, it become clear why certain custom code can benefit from compiling and why Wolfram makes compiling possible.

A stand alone Mathematica function may run compiled code in the background (and run blazingly fast), but such functions almost invariably have connector code to enable them to interact with other native Mathematica functions.

When you or I develop custom functions using multiple native Mathematica functions, then we have an increased high-level language overhead.

One could think that using Compile[] on a custom function as stripping out any extra/unnecessary high-level language overhead. Doing this can, with a suitable custom function speed up performance considerably.

Answer 4

I start with some definitions of ELI5. ELI5 may be "explain like I am 5". 5 remain indirectly define, age of 5 years, at the level of 5 years in school or in higher education or in university or in the profession. ELI5 is too a python library dealing with explanations for predictions based on machine learning.

Compile has undergone plenty of paradigm changes. Now the documentation page suggests that the built-in is for function just a wrapper for CompiledFunction. That is a nice start for some understanding. The function as a term is placed in the modern curricular used almost worldwide in classes 7 to 8 leaving a certain time to the teacher when to introduce it. A reference is curriculum department guidelines recommendations teaching and learning:9 key aspects of knowing and learning the concept of function.

A CAS like Mathematica implements only the process view of functions. And that is strictly not ELI5. The view is introduced late in class 10 and deepened in 11 and 12 or 13. Please read the corresponding section of my reference.

So understanding the documentation of CompiledFunction, Compile generates a CompiledFunction. CompiledFunction represents a compiled function. Both is implemented on the Mathematica or Wolfram language kernels in use. CompiledFunction objects can be used as normal Function Function objects.

The documentation for Function goes deeper in the sense of defining function head and body. It introduces the concept of pure function that makes Mathematica so fast. It presents short forms and long forms and slots and recursion that are really just for advanced users but they make up the fastness of execution. This is the next big paradox in Your question.

Speed up occurs only with the named data types machine-size integer, machine-precision approximate real number (default), machine-precision approximate complex number, and logical variable. So this defines on the fly what numbers are for Mathematica. If work shall be done with Compile prefer numbers in the sense of Mathematica. Compile handles numerical functions, matrix operations, procedural programming constructs, list manipulation functions, and functional programming constructs, etc.

In order to program fast code with Compile three terms have to be clear and governed correctly or shall be understood:

(1) The number of times and the order in which objects are evaluated by Compile may be different from ordinary Wolfram Language code.

(2) Compile has attributeHoldAll and does not by default do any evaluation before compilation.

(3) The third argument to Compile. This third argument allows for the extension of the strict concept of numbers or even more strict approximate real numbers in Compile. This extension is Compile[\[Ellipsis],Evaluate[expr]] to specify that expr should be evaluated symbolically before compilation.

All three terms or ideas are higher programming language level: define: programming language level in a SERP for example Google for "programming language generation". Mathematica is a 5th generation programming language following Fourth generation programming language. It is this in the domain of mathematical optimization. Wolfram Language is a Fourth generation programming language in the domain of data manipulation, analysis, and reporting languages. Until competences on this requirement level are posed there is no chance of understanding what Compile at the heart of Mathematica offers really. That level is for sure higher than university and not ELI5.

I understand that is frustrating and the fast track. But as already Mathematica includes and is based on a selection of best practices in computation. So no wonder that Function emphasizes that Function is analogous to $\lambda$ in LISP or formal logic. And LISP is already a 5th generation language.

Computational linguistics offers some of the main concepts included in the nth generation language qualifiers. One of the main is computational language evolution accompanying knowledge evolution. Your ideas stick to computational solution programming. You are in need of competence development. That can not be achieved by a single answer or question.

For practice, Mathematica does compilation alone to some extend. Nice catchy terms are ComplexityFunction, ExcludedForms, TransformationFunctions and more.

Good ideas can be drawn from built-ins like FunctionExpand. FunctionExpand tries to expand out special and certain other functions in expr, when possible reducing compound arguments to simpler ones.

As stated in the section Neat Examples of FullSimplify Mathematica knows a lot. Much of the knowledge has to activate. The targets were versatility and generality. First You need to know where to find the built-ins and options to activate appropriate knowledge. One place is to read the tutorials for example UsingAssumptions. That shows up how important domains are for speed.

Start with the tutorial of ScopingConstructs to get in touch with automatically in Mathematica. Know what You do with Mathematica by The Standard Evaluation Procedure and go further to NonStandard Evaluation: Function[{x},body] do not evaluate until the function is applied. Based on that a foundation to debugging is started.

The search in the documentation system of Mathematica yields 272 results for Compile. This offers a view of the messages addressed to the built-in Compile. Wolfram Inc holds statistics on how often these are called. The tutorial Compile/tutorial/Operation. From this shorten the URI in the documentation browser address box to "Compile/tutorial/". The result is another list of tutorials for Compile.

I am the opinion the best advice is to start with the tutorial Compiling Wolfram Language Expressions after the foundations that I shortened for brevity are real competences of Yours. This tutorial ends among others with a link to the guide Time Measurement And Optimization. This guide is related to the tutorial Controlling Infinite Evaluation. This starts with simple examples that show the differences between ELI5 and Mathematica very hard. Even the simple $=$ is no longer what an ELI5 thinks about it. Mathematica knows Machine Learning but not Explainability in the senses of Explainable artificial intelligence.

This is a starting point in Mathematica for explaining: Transformation Rules For Functions. This is to be accompanied by Values For Symbols and Algebraic Calculations Overview. The page Core Language Overview is another good start. Many do not comprehend why it is unavoidable to follow best practices with Mathematica for best results in Compile. This just works a path of documentation around functions and programs and that is what Compile speeds up.

In meta language, there are many targets for optimization. One of them is speed. Have a look at Multi-objective optimization to get an overview. Mathematica offers all of them. Mathematica evolved rapidly lately. Processes are a new domain of interest. For example Stochastic Differential Equation Processes and Model Connections and Manipulations. So the start of the foundations of the initial phase for offering better optimizations is made. But that is nothing compared to the advance this made: Disinformation.