Skip to content

Performance Tests

Jump to bottom
njpipeorgan edited this page Nov 15, 2019 · 7 revisions

Introduction

Test cases

The test cases are took 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: Windows 10
  • Compiler: GCC 8.1
  • Processor: Intel Coffee Lake @ ~3.9GHz
  • 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 60 ms (4x) 4.7 ms (54x)
fannkuch-redux 36 μs 1.80 μs (20x) 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.083 μs (170x) 0.071 μs (200x)
Largest product in a series 356 μs 123 μs (3x) 25.9 μs (14x)
Special Pythagorean triplet 4.2 s 0.90 s (5x) 0.43 s (10x)
Longest Collatz sequence 8.7 s 7.0 s (1.2x) 0.244 s (36x)
Digit fifth powers 2.08 s 0.230 s (9x) 0.034 s (61x)

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@Function[{},Table[
  Boole[Abs@NestWhile[#*#+(i+j I)&,0.0,Abs@#<2&,1,50]<2],{i,-1.5,0.5,0.01},{j,-1.,1.,0.01}]];

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[{x},
  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@Function[{Typed[x,Integer]},
  Module[{s=Module[{n=1},NestWhile[(++n;If[OddQ[#],3#+1,Quotient[#,2]])&,#,#>1&];n]&},
    Ordering[Table[s[i],{i,x}],-1]]];

f2=Ordering[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}]][#],-1]&;

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

Clone this wiki locally