Performance Tests

Introduction

Test cases

The test cases are took mainly from two sources:

1. Project Euler, featuring interesting mathematical and programming problems. The problems can often achieve significant performance improvements from compilation.
2. The computer language benchmarks game, featuring toy benchmark programs. The benchmark problems are closer to the use cases for compilation in real life.

Environment

• Operating System: Ubuntu 18.04
• Compiler: GCC 7.4
• Processor: Intel Coffee Lake @ ~4.3GHz
• Mathematica: v12.0

Implementation and timing notices

The functions are implemented following a few guidelines:

• Use built-in functions, unless the function is not compilable.
• Minimize the use of For and While.
• The code for the built-in compiler should not invoke MainEvaluate.

In addition, parallelization is not used in the implementations.

The overhead of each function call is nearly uniform across different functions (180±10 nanoseconds), and it is subtracted from the timing.

Summary

Problem	Not compiled	Built-in compiler	MathCompile
Mandelbrot set	254 ms	17 ms (15x)	3.2 ms (79x)
fannkuch-redux	36 μs	1.38 μs (26x)	0.135 μs (270x)
Multiples of 3 and 5	620 μs	26.8 μs (23x)	1.38 μs (450x)
Sum square difference	14.1 μs	0.16 μs (87x)	0.071 μs (200x)
Largest product in a series	356 μs	107 μs (3x)	25.9 μs (14x)
Special Pythagorean triplet	316 ms	780 μs (400x)	197 μs (1600x)
Longest Collatz sequence	6.4 s	3.5 s (1.8x)	0.185 s (35x)
Digit fifth powers	1.52 s	0.190 s (8x)	0.035 s (43x)
Import a numerical array	1.22 s		0.544 s (2.2x)
Export a numerical array	4.23 s		0.537 s (8x)

Code

• f0: the function that is not compiled;
• f1: the function compiled by MathCompile;
• f2: the function compiled by the built-in compiler, Compile is always called with options CompilationTarget->"C" and RuntimeOptions->"Speed", even if they are not included below.

Mandelbrot set

Generate a 200×200 array of Mandelbrot set between -1.5-i and 0.5+i, the the maximum number of iteration is 50.

f0=Function[{},Table[Module[{g=0.I,n=0},
  While[n<50&&Abs@g<2,++n;g=g*g+(i+j I)];Boole[Abs@g<2]],{i,-1.5,0.5,0.01},{j,-1.,1.,0.01}]];

f1=CompileToBinary[f0];

f2=Compile[{},Table[Module[{g=0.I,n=0},
  While[n<50&&Abs@g<2,++n;g=g*g+(i+j I)];Boole[Abs@g<2]],{i,-1.5,0.5,0.01},{j,-1.,1.,0.01}]];

Source: The computer language benchmarks game

fannkuch-redux

Given a permutation p of {1,…,n}, flip the first i=p[0] elements of p repeatedly, until p[0]=1. Count the number of flips.

The functions are called on all permutations of {1,…,8}, taking the average execution time for each permutation.

f0=Function[{Typed[x,{Integer,1}]},Module[{n=0},
  NestWhile[Module[{y=#,i=#[[1]]},++n;y[[;;i]]=Reverse@y[[;;i]];y]&,x,#[[1]]!=1&];n]];

f1=CompileToBinary[f0];

f2=Compile[{{x,_Integer,1}},Module[{n=0},
  NestWhile[Module[{y=#,i=#[[1]]},++n;y[[;;i]]=Reverse@y[[;;i]];y]&,x,#[[1]]!=1&];n]];

Source: The computer language benchmarks game

Multiples of 3 and 5

Find the sum of all the multiples of 3 or 5 below 1000.

f0=Function[{Typed[x,Integer]},Total@Select[Range[x],Divisible[#,3]||Divisible[#,5]&]];

f1=CompileToBinary[f0];

f2=Compile[{{x,_Integer}},Sum[If[Mod[i,3]==0||Mod[i,5]==0,1,0],{i,x}]];

Source: Project Euler #1

Sum square difference

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

f0=Function[{Typed[x,Integer]},Sum[i,{i,x}]^2-Sum[i^2,{i,x}]];

f1=CompileToBinary[f0];

f2=Compile[{{x,_Integer}},Sum[i,{i,x}]^2-Sum[i^2,{i,x}]];

Source: Project Euler #6

Largest product in a series

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product.

f0=Function[{Typed[x,{Integer,1}]},Max@Table[Times@@x[[i;;i+12]],{i,1,Length[x]-12}]];

f1=CompileToBinary[f0];

f2=Compile[{{x,_Integer,1}},Max@Table[Times@@x[[i;;i+12]],{i,1,Length[x]-12}]];

Note: the 1000-digit number is represented as a list of integers.

Source: Project Euler #8

Special Pythagorean triplet

There exists exactly one Pythagorean triplet for which a+b+c=1000. Find the product abc.

f0=Function[{},Module[{r=0,k=0},
  Do[k=1000-i-j;If[k>0&&i^2+j^2==k^2,r=i j k;Break[]],{i,1,999},{j,1,999}];r]];

f1=CompileToBinary[f0];

f2=Compile[{},Module[{r=0,k=0},
  Do[k=1000-i-j;If[k>0&&i^2+j^2==k^2,r=i j k;Break[]],{i,1,999},{j,1,999}];r]];

Source: Project Euler #9

Longest Collatz sequence

Which starting number, under one million, produces the longest chain of Collatz sequence?

f0=Function[{Typed[x,Integer]},
  Ordering[Table[Module[{n=1,g=i},While[g>1,++n;g=If[OddQ[g],3g+1,Quotient[g,2]];];n],{i,x}],-1]];

f1=CompileToBinary[f0];

f2=Ordering[#,-1]&@*Evaluate[Compile[{{x,_Integer}},
  Table[Module[{n=1,g=i},While[g>1,++n;g=If[OddQ[g],3g+1,Quotient[g,2]];];n],{i,x}]]];

Note: all three implementations do not use dynamic programming.

Source: Project Euler #14

Digit fifth powers

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

f0 = Function[{},Total@Select[Range[2,999999],Total[IntegerDigits[#]^5]==#&]];

f1=CompileToBinary[f0];

f2=Compile[{},Total@Table[Module[{sum=0,g=i},
  While[g>0,sum+=Mod[g,10]^5;g=Quotient[g,10];];If[i==sum,i,0]],{i,2,999999}]];

Note: IntegerDigits is not compilable by Compile, so its implementation is different.

Source: Project Euler #30

Import a numerical array

Import a 1000x1000 numerical array in TSV format. The elements are double-precision numbers distributed uniformly on log scale between 10^-15 and 10¹⁵.

f0 = Function[{file},Import[file,"TSV"]];

f1 = CompileToBinary[Function[{Typed[file,String]},Import[file,{"TSV","Real64"}]]];

Export a numerical array

Export a 1000x1000 numerical array in TSV format.

f0 = Function[{Typed[file,String]},Export[file,10.^RandomReal[{-15.,15.},{1000,1000}],"TSV"]];

f1 = CompileToBinary[f0];