The Wolfram Compiler

Tom Wickham-Jones
Wolfram Research

(RowDefault[, (Spacer1), , (Spacer1), ])  #WolframTechConf

The Wolfram Compiler

The Wolfram Compiler is a long-term project to convert Wolfram Language into native machine instructions which run directly on the CPU. It offers a powerful way to speed up Wolfram Language code. It provides  many opportunities for innovative programming features such as building connections to external libraries and accessing new technologies . A key and unique aspect of the Wolfram Compiler is its embedding in with Wolfram Language technologies. It is used for an increasing amount of new development such as the Data Structure library .

This talk will describe the Wolfram Compiler and explore its various innovative features. It will examine its various tools and workflows that help to make it a powerful addition to the Wolfram Language.

The Wolfram Compiler

Convert Wolfram Language code to native machine instructions

Dramatic speed enhancements for Wolfram Language

High-performance language with unique and innovative features

New opportunities for linking to external libraries

Powerful for accessing new technology

Increasing amount of new Wolfram Language features

Basis of the Wolfram Data Structure library

Compiled Wolfram Code

Function with type annotation:

func = Function[Typed[arg,"PackedArray"::["MachineInteger",1]],AllTrue[arg,#>0&]];

func[{1,2,3,4}]

Compile to machine code function:

comp = FunctionCompile[func]

comp[{1,2,3,4}]

Significantly Faster

data=Range[(10^5)];

comp[data]//RepeatedTiming

func[data]//RepeatedTiming

Useful

synergy between interpreted and compiled

both work the same

func[{1,2, -4}]

comp[{1,2, -4}]

but use different techniques

start with interpreted 
     move to compiled (see this more)

Usage

Fine to use with FunctionCompile on single functions

Large library of compiler support for Wolfram Language
  
Some things  benefit very well

CompilerInformation explores support

 But it is not a seamless magic
    (not yet anyway)

Going Further

Compiler code built from declarations
     
     FunctionDeclaration
     TypeDeclaration
     etc...

Lots built-in

Easy to extend to your programming work

Function Declaration

Test array for elements greater than 0

decl=FunctionDeclaration[allZeroGreater,Typed[ {"PackedArray"::["Integer64",1]}->"Boolean"]@ Function[arg,AllTrue[arg,#>0&]]];

Compile a call

FunctionCompile[decl,Function[Typed[arg,"PackedArray"::["Integer64",1]],allZeroGreater[arg]]]

More General

Test array of anything

decl=FunctionDeclaration[allZeroGreater,Typed[ForAllType[{elem},{"PackedArray"::[elem,1]}->"Boolean"]]@ Function[arg,AllTrue[arg,#>0&]]];

Compile for integers:

FunctionCompile[decl,Function[Typed[arg,"PackedArray"::["Integer64",1]],allZeroGreater[arg]]]

Also works for reals:

FunctionCompile[decl,Function[Typed[arg,"PackedArray"::["Real64",1]],allZeroGreater[arg]]]

Only have to write the code once

More Natural

Much more natural

allZeroGreater[arg_]:=
    AllTrue[arg,#>0&]

allZeroGreater[{1,2,3}]

Declaration just needs a type

decl=FunctionDeclaration[allZeroGreater,Typed[ForAllType[{elem},{"PackedArray"::[elem,1]}->"Boolean"]]@ DownValuesFunction[allZeroGreater]];

Compile a call

comp = FunctionCompile[decl,Function[Typed[arg,"PackedArray"::["Integer64",1]],allZeroGreater[arg]]]

comp[ {1,2,32}]

Integrate with regular Wolfram Language definitions

Develop interpreted code and then compile

Fallback Declaration

Not everything supported

func = Function[Typed[ arg, "Real64"],CatalanNumber[arg]];
FunctionCompile[func]

Add a Declaration

easy fallback

decl=FunctionDeclaration[CatalanNumber, Typed[{"Real64"}->"Real64"]@KernelFunction[CatalanNumber]];

comp=FunctionCompile[decl,func]

comp[ 10.5]

CatalanNumber[10.5]

Extra

We add these declarations,  CatalanNumber will actually be in 14.2

 But...   we have a process, testing etc...
 
 Always possible for you
 
 There is a cost 
      going via the interpreter is more expensive

The Type System

Key part of the compiler

type inferencing — minimal markup

parametric polymorphic definitions — little code goes a long way

new types

product (structure) types
   
function overloading

type computations

trait system

Built-in Types

"Boolean"

Integer

signed and unsigned

"Integer8","Integer16","Integer32","Integer64",  "Integer128"

Float

"Real16","Real32","Real64"

Complex

"ComplexReal32", "ComplexReal64"

Container

Rectangular

"PackedArray","NumericArray", "SparseArray"

Take arguments

Vector of integers

"PackedArray"["MachineInteger",1]

Matrix of reals

"PackedArray"["MachineReal",2]

Vector

"ByteArray",  

"ListVector", "ListTuple"

Data Structures

All data structures can be used in compiled code

General

"String", "InertExpression"

"CArray","RawPointer", "OpaqueRawPointer", 

"Null", "Managed"

External

"CInt","CUnsignedInt"

"CDouble", "CFloat"

"CByte", "CString"

Integer Example

Different integers are useful
      smaller pack into memory better
      larger have more range

cullen[n_]:=
   n *2^n+1

Table[cullen[i],{i,0,20}]

decl = FunctionDeclaration[cullen,Typed[ForAllType["int",Element["int","Integers"],{"int"}->"int"]]@ DownValuesFunction[cullen]];

comp =FunctionCompile[decl,Function[Typed[arg,"Integer64"], cullen[arg]]]

comp[ 10]

Larger Size

comp1 =FunctionCompile[decl,Function[Typed[arg,"Integer128"], cullen[arg]]]

comp1[ 60]

Wolfram DataStructures

Library of classical data structures

$DataStructures

All built with the Compiler

Good example of compiled code

Compete well with standard libraries e.g. C++

Example

Create a mutable extensible array

ds = CreateDataStructure["DynamicArray"]

Faster than appending to a list

Do[ds["Append", f[i]],{i, 10000}];//AbsoluteTiming

list = {};
Do[AppendTo[list,f[i]],{i,10000}];//AbsoluteTiming

easy way to speed code

DataStructure Operations

ds=CreateDataStructure["HashTable"]

See info

Information[ds]

Some operations

Do[ds["Insert", k[i]->val[i]],{i, 30}]

ds["Lookup", k[2]]

ds["Visualization"]

Compiler Tooling

Compiler is powerful, but can be hard to use

Everything has to compile (no partial success)

Adding features to help reduce the pain:

Error reporting

Progress Indicator

Compiler Information

TypeOf

Error Reporting

Compilation can fail

New error system indicates location of error in code

func=Function[Typed[ arg, "Boolean"], Sin[Not[arg]]];
FunctionCompile[ func];

Demo 1

Nested function

func=Function[Typed[arg,"Integer64"],Module[{f},f=Function[x,Module[{f1},f1=Function[x1,foo[x1]];
f1[x]]];
f[arg]]];
FunctionCompile[func]

Demo 2

Works with chains of declarations:

decl1 = FunctionDeclaration[MyFun1,Typed[{"Integer64"}->"Integer64"]@Function[{arg},arg1]];
decl2 = FunctionDeclaration[MyFun2,Typed[{"Integer64"}->"Integer64"]@Function[{arg},MyFun1[arg]]];
decl3 = FunctionDeclaration[MyFun3,Typed[{"Integer64"}->"Integer64"]@Function[{arg},MyFun2[arg]]];

FunctionCompile[{decl1,decl2,decl3}, Function[Typed[ arg, "Integer64"], MyFun3[arg]]];

Progress Indicator

Compiler written in Wolfram Language and is quite slow 
             being compiled though

Progress indicator helps follow and monitor progress

cmp=FunctionCompile[Function[Typed[arg,"PackedArray"::["Integer64",1]],BinCounts[arg,20]]]

Usage

data=RandomInteger[{0,100},10^4];

cmp[data];//RepeatedTiming

BinCounts[data,20];//RepeatedTiming

Nice speed up

Compiler Information

Big library of function and type declarations

Information on types

CompilerInformation["Integer64"]

and functions

CompilerInformation[Map]

Helps problem of what is supported

Compiler Information

Works with your declarations

Add a declaration

CompilerEnvironmentAppendTo[FunctionDeclaration[allGreater,Typed[ForAllType[{elem},{"PackedArray"::[elem,1]}->"Boolean"]]@ Function[arg,AllTrue[arg,#>0&]]]];

Information on your function

CompilerInformation[allGreater]

Runtime Error Handling

Runtime errors cause program termination

comp=FunctionCompile[Function[Typed[arg,"Integer64"],2arg]];

This runs fine

comp[10]

This has an error
          reruns in the evaluator

comp[2^63-1]

Runtime

comp=FunctionCompile[Function[Typed[arg,"Integer64"],2arg],CompilerRuntimeErrorAction->None];

Runtime error generates a failure

comp[2^63-1]

Tooling Progress

All sorts of new compiler workflow tools in pipeline

Profiling,   exception management (proper stack traces)

Source level debugger (lldb based)

And of course making the compiler faster

Low Level Functionality

Good access to low level functions, e.g. libraries

Sample library

FindLibrary["compilerDemoBase"]

FilePrint["LibraryLink/LibraryResources/Source/compilerDemoBase.c"]

Calling a Function

Declaration

decl=LibraryFunctionDeclaration["addone","compilerDemoBase",{"CInt"}->"CInt"];

Calling function

func = Function[Typed[arg, "CInt"],LibraryFunction["addone"][arg]];

Compile

comp=FunctionCompile[decl,func]

comp[10]

Calling via a Pointer

Declaration

decl=LibraryFunctionDeclaration["incrementInput","compilerDemoBase",{"RawPointer"::["CInt"]}->"CInt"];

Create pointer (on stack)

func = Function[Typed[arg, "CInt"],
                Module[{ptr},
               ptr = ToRawPointer[arg];
	     LibraryFunction["incrementInput"][ptr];
              FromRawPointer[ptr]
      ]];

comp=FunctionCompile[decl,func]

comp[10]

Using an Array

Call a function that takes an array

decl=LibraryFunctionDeclaration["populateArray","compilerDemoBase",{"CArray"::["CLong"], "CLong"}->"CInt"];

Memory allocation

func = Function[Typed[len, "CLong"],
                Module[{arr},
               arr = CreateTypeInstance["CArray"::["CLong"],len];
	     LibraryFunction["populateArray"][arr, len];
	     Do[Print[ FromRawPointer[arr,i]],{i,0,len-1}];
      ]];

comp=FunctionCompile[decl,func]

comp[10]

Negative because we are never freeing the array

Needs["CompileUtilities`TestSuite`TestSuiteUtilities`"]

MemoryLeakCheck[comp[10]]

Better With Managed

Wrap the creation in a Managed type

Borrows the array for the call

Frees at end

func = Function[Typed[len, "CLong"],
                Module[{arr},
               arr = CreateTypeInstance[
                     "Managed"::["CArray"::["CLong"]],len];
	     LibraryFunction["populateArray"][arr, len];
	     Do[Print[ FromRawPointer[arr,i]],{i,0,len-1}];
      ]];

compManaged=FunctionCompile[decl,func]

MemoryLeakCheck[compManaged[10]]

Foreign Function Interface

Pretty useful to call library code like this

FFI interface uses pre-built Compiled Code

addone=ForeignFunctionLoad["compilerDemoBase","addone",{"CInt"}->"CInt"]

addone[ 10]

Comparison

FFI   ⟶ don’t need to learn/run compiler

Compiler ⟶ lower overhead

Compiler ⟶ more opportunities for processing

Big tutorial on FFI 

Both allow automatic memory collection

Both better than LibraryLink

Integration with Interpreter

Compiled Wolfram code is interesting language

Can make very fast implementations

Nice modern type system

Benefits from underlying LLVM technology (GPU code generation etc...)

There are other languages that provide these

But...

Key Unique Aspect

Tight integration with interpreted Wolfram Language code

No other languages have anything like this

Many benefits

Wolfram Expression

Wolfram expression type,  core of Wolfram Language

Accessible in Compiled Code as “InertExpression” type

Works with memory management system

Write internal Kernel code with Compiler

Create lots of neat features

Interpreter  ↔  Compiler

Interpreter Execution

Wolfram Language code interpreted
  (and built-in)

only Kernel expression

Compiler Execution

Machine code executed direct on CPU
   
Many different types

Problem

How to combine these?

Data Conversion

expression ⟶ compiled object

compiled object ⟶ expression

all done with ...   compiled code

interface code is itself compiled

image

Data Conversion Example

Create a ListVector

func =Function[Typed[str,"String"], 
                 {str,str}];comp = FunctionCompile[func]

comp["abcd"]

returns as a Wolfram Expression List

Data Conversion Example

Create a BitVector

func =Function[Typed[len,"Integer64"], 
                 CreateDataStructure["BitVector",len]];comp = FunctionCompile[func]

comp[20]

Same as a BitVector created in Interpreter

comp[20]===CreateDataStructure["BitVector",20]

Programming with Compiler

Everything based on embedding in interpreter

Many interesting features and benefits

Program Interactively

Writing polymorphic code has its own sets of challenges

Workflow e.g. with C++ templates is not super easy
    writing and then instantiating templates
    complicated setup,  obscure messages,  hard to see errors

Wolfram Language is super convenient to work interactively

Example

Develop a polymorphic function

Declare and append to environment

decl = FunctionDeclaration[MyFun, 
		Typed[ForAllType[{elem,rank}, Element[rank,{1,2}],
			{"PackedArray"::[elem,rank]}->"PackedArray"::[elem, rank]]]@Function[{arg},Null]];
CompilerEnvironmentAppendTo[decl];

Result type

TypeOf[Function[Typed[arg,"PackedArray"["Real64",2]], MyFun[arg]]]

TypeOf[Function[Typed[arg,"PackedArray"["ComplexReal64",2]], MyFun[arg]]]

But with something not defined,  the error mechanism is triggered.

The definition only applies to vector and matrix.

TypeOf[Function[Typed[arg,"PackedArray"["Real64",3]], MyFun[arg]]]

TypeOf quick way to check compilation

More

take a scalar and return a matrix 
    real input ⟶ real output
    complex input ⟶ real output

use TypeEvaluate and TypeOf

decl = FunctionDeclaration[MyFun1, 
	  Typed[ForAllType[{elem}, 
          Element[elem,"Numbers"],
	   {elem}->
          "PackedArray"::[
                   TypeEvaluate[TypeOf[Re[elem]]], 
                   2]]
]@Function[{arg},Null]];
CompilerEnvironmentAppendTo[decl];

Real64 input

TypeOf[Function[Typed[arg,"Real64"], MyFun1[arg]]]

ComplexReal64 input

TypeOf[Function[Typed[arg,"ComplexReal64"], MyFun1[arg]]]

Benefits

Working with types in this way is very natural in Wolfram Language

Very hard in other languages

Break down complicated task into simpler parts

Good way to get started

Wolfram Language Contract

Need to ensure compiler supports Wolfram contract

   Multi-platform

   Expression Serialization

Serialization

Generate a CompiledCodeFunction

comp = FunctionCompile[ Function[Typed[arg, "Integer64"],arg+1]]

Use it

comp[ 10]

But can copy and paste it out...

Still works ...   deserializes quite quickly

Implementation

Contains low-level code

comp1[[1]]["CompiledIR"]

but only for this platform

Multiplatform Compilation

New compiler environment

compEnv = CreateCompilerEnvironment[TargetSystem->All];

compEnv[TargetSystem]

comp = FunctionCompile[ Function[Typed[arg, "Integer64"],arg+1],TargetSystem->All,CompilerEnvironment->compEnv]

Now contains low-level code for all WL platforms

comp[[1]]["CompiledIR"]

Take this system and run on another platform

Code Practices

Support of transition for Interpreted to Compiled transition

Develop code interactively then add FunctionDeclaration and compile

Many functions built-in

If not then perhaps use IfCompiled or TypeHint

and of course KernelFunction

saw an example previously

TypeHint

TypeOf quick way to check

This works fine

Function[ {Typed[arg, "Integer64"],Typed[len,"Integer64"]},
    Module[{res = 1},
        Do[
       res = res+arg;
      ,{i,len}];
         res
]]//TypeOf

But not

Function[ {Typed[arg, "Real64"],Typed[len,"Integer64"]},
    Module[{res = 1},
        Do[
       res = res+arg;
      ,{i,len}];
         res
]]//TypeOf

Solution

Use TypeHint

func =Function[ {Typed[arg, "Real64"],Typed[len,"Integer64"]},
    Module[{res =TypeHint[ 1,TypeOf[arg]]},
        Do[
       res = res+arg;
      ,{i,len}];
         res
]];TypeOf@@{func}

Benefit

TypeHint is hidden to the evaluator

Function still works in evaluator

func[ 1.5, 10]

IfCompiled

Easy to select code to work in compiled or not

func = Function[{Typed[arg, "Integer64"]}, Print[ IfCompiled["Compiled", "Interpreted"]];arg];
comp = FunctionCompile[func]

Both give the same result but different paths

func[ 10]

comp[10]

Usage

Working with expressions,   hard to make completely uniform

func = Function[ {Typed[arg, "InertExpression"]}, IfCompiled[Construct[InertExpression[List],arg],{arg}]];
comp = FunctionCompile[func]

Same result for both

func[ f[1]]

comp[f[1]]

Prime Testing Example

Example of a lookup table,  using a BitVector DataStructure

BitVector is like a fixed length array,  but very compressed and very efficient

Base Code

Create a bit vector of given length

len  = 20;
bv = CreateDataStructure["BitVector",len+1];

Set bits if the index is Prime

Do[If[PrimeQ[i],bv["BitSet",i]],{i,len}];

bv["OnBitList"]

Prime testing function

primeTest1[bv_,num_]:=
 Module[{},
  bv["BitTest",num]
]

primeTest1[bv,7]

Compile

decl1=FunctionDeclaration[primeTest1,Typed[{"BitVector","Integer64"}->"Boolean"]@DownValuesFunction[primeTest1]];

comp1 = FunctionCompile[decl1,Function[{Typed[bv,"BitVector"],Typed[num,"Integer64"]}, primeTest1[bv,num]]];

comp1[bv,7]

Prime Testing Example

Can do better,  e.g. miss even numbers

len  = 20;
bv = CreateDataStructure["BitVector",Quotient[len,2]+1];

Set bits if the index is Prime

Do[If[PrimeQ[i],bv["BitSet",BitShiftRight[i-1,1]]],{i,3,len,2}];

bv["OnBitList"]

Restore the primes

BitShiftLeft[%,1]+1

Prime testing function

primeTest2[bv_,num_]:=
 Module[{index},
 If[Mod[num,2]===0
,
False
,
  index =  BitShiftRight[ num -1, 1];
  bv["BitTest",index]
]
]

primeTest2[bv,8]

Compile

decl2=FunctionDeclaration[primeTest2,Typed[{"BitVector","Integer64"}->"Boolean"]@DownValuesFunction[primeTest2]];

comp2 = FunctionCompile[decl2,Function[{Typed[bv,"BitVector"],Typed[num,"Integer64"]}, primeTest2[bv,num]]];

comp2[bv,7]

Larger

Make a bigger array

len  = 2^24;
bv = CreateDataStructure["BitVector",Quotient[len,2]+1];
Do[If[PrimeQ[i],bv["BitSet",BitShiftRight[i-1,1]]],{i,3,len,2}];

ByteCount[bv]

Apply[And, Table[ comp2[bv,i]===PrimeQ[i],{i,3,1000}]]

Timings

comp2[bv, 2^10]//RepeatedTiming

primeTest2[bv, 2^10]//RepeatedTiming

PrimeQ[2^10]//RepeatedTiming

Interpreted version not terrible...   
         BitVector is actually quite helpful

Compiled version is not bad compared with built in

Random Tree Example

Code to generate a random tree

There is a built-in function,  but attempt to use data structures

TreeNode and DynamicArray

Base Code

logCatalanNumber[n_]:=
2 n Log[2]-Log[1+n]-Log[Pi]/2+LogGamma[1/2+n]-LogGamma[1+n]

randomForestProb[n_,k_]:=
Exp[logCatalanNumber[k-1]+logCatalanNumber[n-k]-logCatalanNumber[n]]

randomTreeSize[n_]:=
	Module[{u,k,s},
	u=RandomReal[{0,1}];
	k=TypeHint[1,TypeOf[n]];
	s=randomForestProb[n,k];
	While[u>s,s+=randomForestProb[n,++k]];
k]

randomForest[n_]:=
	Module[{k},
		If[n==0,
		CreateDataStructure["DynamicArray"],
		k=randomTreeSize[n];
		randomForest[n-k]["Append",randomTree[k]]
]]

randomTree[n_]:=
Module[{tree,children},
tree=CreateDataStructure["TreeNode",IfCompiled[InertExpression[1],1]];
children=randomForest[n-1];
Do[tree["AppendChild",children["Part",i]],{i,children["Length"]}];
tree]

randomTree[ 20]

Compile Code

Decide types for functions

decls =
{
FunctionDeclaration[logCatalanNumber,Typed[ {"Real64"}->"Real64"]@DownValuesFunction[logCatalanNumber]]
,
FunctionDeclaration[randomForestProb,Typed[{"Real64", "Real64"}->"Real64"]@DownValuesFunction[randomForestProb]]
,
FunctionDeclaration[randomTreeSize,Typed[{"Real64"}->"Real64"]@DownValuesFunction[randomTreeSize]]
,
FunctionDeclaration[randomForest,Typed[ {"Real64"}->"DynamicArray"]@DownValuesFunction[randomForest]]
,
FunctionDeclaration[randomTree,Typed[ {"Real64"}->"TreeNode"]@DownValuesFunction[randomTree]]};

Use in compiler

compTree = FunctionCompile[decls,Function[Typed[arg, "Real64"],randomTree[arg]]]

compTree[ 20]["Visualization"]

Speed Comparisons

randomTree[100];//RepeatedTiming

compTree[100];//RepeatedTiming

So a lot faster over interpreted

RandomTree[100];//RepeatedTiming

And faster than built-in (though it’s not quite doing the same thing).

Summary

A brief introduction to the Wolfram Compiler

Programming with the Compiler and examples of its type system

Tooling: error reporting,  progress indicator, compiler information

Low-level programming, connecting to libraries

Embedding in the Wolfram Language

Meeting Wolfram Language requirements

Programming workflow interpreted ⟶ compiled

Various examples

Also

Daniel Sanchez 
       Integrating the Wolfram Compiler with the Wolfram Engine
       11:30 CDT
       Thursday 17 October