The 
Wolfram Compiler

Tom Wickham-Jones

Init

Needs["Compile`"]

FunctionCompile[Function[Typed[arg,"Integer64"],
              arg]];

The Wolfram Compiler

The Wolfram Compiler converts Wolfram Language code into machine instructions which run directly on the CPU. It offers a powerful way to speed up programs as well as providing many opportunities for innovative programming features such as building connections to external libraries and accessing new technologies. It is also used for an increasing amount of new development such as the Data Structure library.  This talk will describe the Wolfram Compiler and its latest advances and directions.

This talk

Look at the Wolfram Language

Basic demonstration of the Compiler

Embedding in the Interpreter

Type and Function Declarations
 
Data Structures
  
Programming via DownValues

Compilation and DataStructures

Integrating with external code

The Wolfram Compiler

compiles Wolfram Language programs

generates native machine code

combines a high-level language with low-level execution

large scale application of Wolfram Language

The Wolfram Language

Mathematica first released in 1988 initially mathematical computation

features now:

calculus, equations, inequalities, differential equations, optimization, linear algebra, symbolic and numerical computation

data and statistical analysis

visualization, charting and graphics

machine learning, neural networks,  LLM

graph/network computation

UI construction

computational data

image, sound and video processing

geospatial plots, data, computation

Programming

functional programming style

execution via expression rewriting (the evaluator)

pattern matching on expression

function definition using patterns

various specialized optimizations

Core Philosophy

automation
    
think about tasks not specific solutions
  
components designed to interoperate

Uniform Expression Structure

Parser creates a Wolfram expression (tree structure object)

Expression “evaluates” (infinitely) to a fixed point 

Typeless (really runtime typing)

Not a completely pure language (side-effects in certain places)

Benefits of Expression

Everything is serializable (save in and out of files)

Easy to overload/modify/customize

Uniform structure means programs can work on diverse areas

Challenges

Everything means something

Easy to construct ‘nonsense’

Sin[ True]

Of course ‘nonsense’ is very subjective

but

verification can be hard

efficiency can be hard

core system/performant code often not written in Wolfram Language

users often prototype in Wolfram Language
	then recode e.g. C++

despite this

many very large Wolfram Language applications

the Wolfram Compiler is an example

The Wolfram Compiler

A compiler for the Wolfram Language

Long term project

Built in the Wolfram Language

Leverage latest Compiler knowledge and technology 

Released in Mathematica 12   (2019) updated every version
including 14.0

Compiler Operations

Convert Wolfram Language into native machine code

in-memory JIT compilation

dynamic library generation

type inferencing

fast execution model for Wolfram Language

implementation for Wolfram Language

integrates with Wolfram Language interpreter

standalone code generation

enhanced by compiling itself

Compiler Benefits

Faster execution

Guarantee of correctness

Fits with other code generation systems

Leverage technology otherwise inaccessible

Great way to learn about Compiler Technology

Combines

High-level language specification with low-level execution technology

Basic Demo

Compile a function

func = Function[{Typed[arg1, "Integer64"],Typed[arg2, "Integer64"]}, arg1+arg2];
comp=FunctionCompile[func]

comp[ 10, 20]

Several functions

funs =FunctionCompile[<|
"inc"->Function[Typed[arg,"Integer64"], arg+1],
"dec"->Function[Typed[arg,"Integer64"], arg-1]
|>]

Add declarations

decl = FunctionDeclaration[myFun,Typed[{"Integer64"}->"Integer64"]@Function[arg,arg+1]];

comp1 =FunctionCompile[decl, 
             Function[Typed[arg,"Integer64"], myFun[arg]]]

Also compiler environment to add declarations

Important Benefits

In memory code generation

Optimized for this specific hardware

Compiles all the code -- does not link to a library

Many cross-function optimizations

Fast because can inline code esp...  to get loop unrolling

Code Functions

comp

comp//InputForm

Convert via InputForm

The InputForm has everything needed to create

comp1 =ToExpression[ToString[comp, InputForm]]

comp1[ 10, 20]

Cross-Compilation

Supports other platforms

compX=FunctionCompile[func,TargetSystem->{"Linux-x86-64"}]

compX[[1]]["CompiledIR"]

Other Outputs

Library

FunctionCompileExportLibrary["myLibrary.dylib", func]

Assembler

FunctionCompileExportString[func,"Assembler"]

FunctionCompileExportString[func, "Assembler", TargetSystem->"WebAssembly"]

Assembler Cross Compile

FunctionCompileExportString[func, "Assembler", TargetSystem->"MacOSX-ARM64"]

LLVM IR

FunctionCompileExportString[func]

Unique Feature

high-level Wolfram Language (interpreted)

    tightly integrated with

fast low-level machine specific code

Interpreted/Compiled Boundary

Interpreted/Compiled Boundary

boxing code is supplied dynamically

can work with Expression memory management

Interpreted/Compiled Boundary

dynamic scripting access to external libraries

The Type System

type inferencing — minimal markup

parametric polymorphic definitions — little code goes a long way

new types

product and sum types
   
function overloading

type computations

Supported Types

“Boolean”, “String”

Integer

signed and unsigned

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

Float

“Real16”, “Real32”, “Real64”

Complex

“ComplexReal32”, “ComplexReal64”

Container

Rectangular

"PackedArray", "NumericArray"

General

“ListVector”, “ListTuple”

Data Structures

…

General

Utility

“InertExpression”, “Rule”, “Null”, “Never”

Function

{"Integer64"}->"Boolean"

Type Declarations

TypeDeclaration["Product","Container",<|"field1"->"Integer64", "field2"->"Integer64"|>]

Polymorphic

TypeDeclaration["Product","Container"["arg"],<|"field1"->"arg", "field2"->"arg"|>]

by default these are reference types and memory managed

Function Declarations

declarations
   name, type and body

FunctionDeclaration[Double,Typed[{"Integer64"}->"Integer64"]@
Function[{arg},2arg]]

Function Declarations

polymorphic declaration

FunctionDeclaration[Double,
  Typed[ForAllType[e,{e}->e]]@
Function[{arg},2arg]]

works for all inputs

better

FunctionDeclaration[Double,
  Typed[ForAllType[e,{e}->e]]@
Function[{arg},Typed[2,TypeOf[arg]]arg]]

Library Declarations

function from an external library

LibraryFunctionDeclaration["externalName",
  "MyLibrary",
{"Integer64"}->"Integer64"]

Example

decl=LibraryFunctionDeclaration["time",
 Automatic,
{}->"Integer64"];

comp=FunctionCompile[decl,Function[{},
      LibraryFunction["time"][]
]]

comp[]

Packaging Declarations

Component system to collect declarations and refer to by name

Described in other talk

Wolfram Language Support

Goal to support Wolfram Language programs

Doesn’t support everything

But will never give a false positive
     ie if compiles then supported
     
Built and extended every release

Uses techniques shown above

Data Structures

Library of classical data structures

Built from the Compiler

Can use without the Compiler

Provides new features (eg mutable state)

Introduced in Mathematica 12.1  expanded since

Library

$DataStructures

Core

Value, Counter,ExprStruct

Container

DynamicArray, ExtensibleVector, FixedArray, ImmutableVector, LinkedList, DoublyLinkedList, Queue, Stack, Deque, RingBuffer, PriorityQueue, StringVector

Set

BitVector, BloomFilter, CuckooFilter, HashSet, OrderedHashSet, DisjointSet, SortedMultiset

Tree

BinaryTree,  AVLTree, KDTree, RedBlackTree

Key Value Store

HashTable, OrderedHashTable, LeastRecentlyUsedCache, ByteTrie, SortedKeyStore

Efficiency

Many data structures are mutable,  so introduces new programming technique

If you can use them get significant speed advantage

Benchmarked with C++,  very competitive

Example: ExtensibleVector

Efficient to append/prepend data

ds=CreateDataStructure["ExtensibleVector"]

Do[ds["Append",f[i]],{i,100}]

ds//Normal

Operations

Efficient to append/prepend data

ds

Information[ds]

ds["EmptyQ"]

Visualization

ds["Visualization"]

Compare with

Efficient to append/prepend data

list = {};
Do[AppendTo[list,f[i]],{i,100}]

list

Speed

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

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

New in 14.0

RedBlackTree

Similar to AVLTree,  but more efficient

New in 14.0

StringVector

Super-efficient way to hold a collection of Strings

StringVector

StringVector
Super-efficient way to hold a collection of Strings

ds = CreateDataStructure["StringVector",{"abca","efagh"}]

ds//Normal

Information[ds]

ds["StringCount","a"]

Selecting

bv=ds["StringMatchQ","a*"]

ds["Pick",bv]

%//Normal

StringVector

Super-efficient
Long list of words

Length[words = WordList[]]

Take[words, 10]

ds = CreateDataStructure["StringVector",words]

Much less storage

ds//ByteCount

words// ByteCount

Selecting

Select words ending in u

RepeatedTiming[Select[words, StringEndsQ[#,"u"]&];]

faster to use Pick

RepeatedTiming[Pick[words, StringEndsQ[words, "u"]];]

faster yet with  “StringVector”

RepeatedTiming[ds["Pick",ds["StringEndsQ","u"]];]

Programming via DownValues

e.g. AllTrue

allTrue[list_,fun_]:=
Module[{res=True},
Do[ If[!fun[elem],
             res=False; Break[]],
       {elem,list}];
res
]

func =Function[Typed[a,"PackedArray"["Integer64",1]], 
            allTrue[a, #>0&]];

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

Compile

decl=FunctionDeclaration[ allTrue,
   Typed[ ForAllType[{"cont","e"},     
                {"cont"["e",1],{"e"}->"Boolean" }->"Boolean"]]@
 DownValuesFunction[allTrue]];

comp = FunctionCompile[decl,func]

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

Function Declarations Advantage

tab = Table[1,{100000}];

func[tab]//RepeatedTiming

comp[tab];//RepeatedTiming

and...

AllTrue[tab, #>0&]//RepeatedTiming

Function Declarations Benefit

develop in top-level

move to compiled code, often nice faster code

polymorphic definitions — little code goes a long way

functions written like this often very competitive with C++ (and built-in)

this is how we are compiling the compiler

Top-Level to Compiled Transition

helpers

Typed ignored in function argument

func = Function[Typed[arg,"Real64"],N[arg]];

func[ 11.2]

IfCompiled

different branches for compiled and uncompiled

func = Function[{}, IfCompiled["comp", "uncomp"]];

func[]

FunctionCompile[func][]

TypeHint

gives a hint for a type, but stripped in uncompiled

func = Function[{},TypeHint[1,"Integer8"]];

func[]

FunctionCompile[func]

Compiling with Data Structures

Data Structures built with the compiler

Can be used with the compiler

BitVector

A vector of bits,  
   very memory efficient
   very efficient

test function

testList[ list_, pred_]:=
Module[ {bv},
  bv = CreateDataStructure["BitVector",Length[list]];
  Do[ If[pred[Part[list,i]],bv["BitSet",i-1]],{i,Length[list]}];
bv
]

data=RandomInteger[{-1,1},10]

bv=testList[data, Positive[#]&]

bv//Normal

Compiling a DataStructure

decl=FunctionDeclaration[testList,
Typed[
{"PackedArray"["MachineInteger",1],{"MachineInteger"}->"Boolean"}->"BitVector"]@DownValuesFunction[testList]];

func=Function[Typed[arg,"PackedArray"["MachineInteger",1]],
    testList[arg, Positive[#]&]
];

testListComp=FunctionCompile[decl,func]

bv=testListComp[data]

bv//Normal

Efficiency

dataBig=RandomInteger[{-1,1},10^5];

testList[dataBig, Positive];//RepeatedTiming

testListComp[dataBig];//RepeatedTiming

So a lot faster

Could be even faster with Parallel

Using a Data Structure

So a data structure can be created and returned from compiled code

func=Function[{
Typed[list,"PackedArray"["MachineInteger",1]],
     Typed[bv, "BitVector"]
}, Module[ {array=CreateDataStructure["DynamicArray"]},
      Do[If[bv["BitTest", i-1],
           array["Append", Part[list,i]]],
          {i,Length[list]}];
      array
]];

funAssemble=FunctionCompile[func]

list={-3,2,1,-1};

bv=testListComp[list]

array=funAssemble[list, bv]

returns a Dynamic Array of Integers

similar to the DynamicArray of Expressions...  typically used

Compilation and Data Structures

array

Compare with

expr = CreateDataStructure["DynamicArray", {5,1,1}]

Data structure of machine integers vs expresssions

Extracting Data

Use the compiler

norm=FunctionCompile[Function[Typed[array, "DynamicArray"["Integer64"]],Normal[array]]]

norm[array]

Compare with

list

Alternatively

Cast the data going into the DataStructure to InertExpression

func=Function[{
Typed[list,"PackedArray"["MachineInteger",1]],
     Typed[bv, "BitVector"]
}, Module[ {array=CreateDataStructure["DynamicArray"]},
      Do[If[bv["BitTest", i-1],
           array["Append", Cast[Part[list,i],"InertExpression"]]],
          {i,Length[list]}];
      array
]];

funAssembleExpr=FunctionCompile[func]

list={-3,2,1,-1};

bv=testListComp[list]

array=funAssembleExpr[list, bv]

Don’t need to compile a function to extract the data

array//Normal

Data Structure Summary

So 
   
   create and return
   
   passed in as argument
   
data structures can contain different contents

Iterator Support

Great form of abstraction

Avoid writing lots of code

Fold Example

FunctionDeclaration[
Fold,
Typed[
ForAllType[{"container","value","output"},Element["container","RangeIterable"],{{"value","output"}->"output",
"output","container"["value"]}->"output"]]@Function[{function,initialValue,container},Algorithm`Fold[function,initialValue,Iterator`Begin[container],Iterator`End[container]]]]

So if RangeIterable is supported Fold is supported

Same for many other data structures

Iterator Example

What is RangeIterable?

func=Function[Typed[array,"DynamicArray"],
           Module[{iter,end},
             iter=Iterator`Begin[array];
             end=Iterator`End[array];
             While[iter=!=end,
                   Print[Iterator`Source[iter]];
                   Iterator`Increment[iter]
           ]
        ]
];

comp=FunctionCompile[func]

ds=CreateDataStructure["DynamicArray",{f[1],f[2],f[3]}];

comp[ds]

Neater

func=Function[Typed[array,"DynamicArray"],
           Do[Print[elem],{elem,array}]
];

comp=FunctionCompile[func]

comp[ds]

And

func=Function[Typed[array,"DynamicArray"],
           Scan[Print,array]
];

comp=FunctionCompile[func]

comp[ds]

All because

DynamicArray is RangeIterable

Techniques like this enables support for many types for free

Summary

Reviewed Wolfram Language

Basic demonstration of the Compiler
   advantages, key components
   optimized code,  cross-compilation

Embedding in the Interpreter
   how compiled types can be entered and returned
   from compiled functions
   leads to a very productive and unique workflow
 
Type and Function Declarations

Data Structures
  New in 14.0,  RedBlackTree and StringVectore
  
Programming via DownValues

Compilation and DataStructures
 
Benefit of Iterators

Calling external code