A simple demo of how pure functions simplify parallelisation

One thing that bugs me about teaching computer science is the amount of ‘rote learning’ – teaching pupils facts to memorise without understanding. 

As an example, one of the rote-learned facts about ‘functional programming’ (FP) – in the AQA A-level syllabus – is that writing systems from pure, side-effect free, functions makes parallelisation easier. But can a pupil at A-level standard really experience this for themselves? Here’s a nice example in C# with a VB translation at the end. (I’m afraid I don’t know Python in enough depth to know how to do it in Python, or even if it is possible – if anyone can help please do.)

Here's a functional approach to identifying all the primes up to a given value. It’s not an efficient efficient algorithm but it serves the challenge well, because it is computationally expensive:

static List<int> Primes(int upTo) => Enumerable.Range(2, upTo - 1).Where(n => IsPrime(n)).ToList();

static bool IsPrime(int n) => !Enumerable.Range(2, n / 2 - 1).Any(f => IsFactor(f, n));

static bool IsFactor(int f, int ofN) => ofN % f == 0;

We can time this (using the system stopwatch) generating all the primes up to 1 million:

using System.Diagnostics;

var sw = new Stopwatch();
sw.Start();
var result = Primes(1000000);
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds/1000);

On my laptop (which has an Intel i7 processor) this task takes approx. 140 seconds. Because my Primes function is written using LINQ, which uses, and requires working with, side-effect free functions, I can easily parallelise this just by adding the call AsParallel() at the appropriate point, as shown here:

static List<int> Primes(int upTo) => Enumerable.Range(2, upTo + 1).AsParallel().Where(n => IsPrime(n)).ToList();

Running this again, took approx. 30 seconds on my laptop, which is a speed up of 3.8x. This is because my processor has 4 (physical) cores.

Observing the core usage

You can observe what is happening if you open the Resource Monitor (go to the Task Manager > Performance tab; there’s a link to the Resource Monitor at the bottom of the window).

Running the Primes function again, without the AsParallel(), I found that my processor was running at just under 30% capacity.  Surprisingly, perhaps, all the cores are being used, but – at least for the function execution itself (bear in mind there are other processes being run too) no more that one core is actually running the function at any given moment. (Why it is switching between cores is another discussion).

But running with the AsParallel() not only is the processor running at near 100% capacity overall but each of the cores is running at near 100%.

More detail

My processor actually has 8 ‘logical’ cores, but that is no advantage over the number of physical cores on a task like this, which is mathematically intensive, because each pair of logical cores has to share the arithmetic circuits. 

You are never going to get 4x improvement for two reasons:

• The processor is still having to run other background processors for the operating system
• There is some overhead from breaking up the data for parallelisation and then re-assembling it to generate the resulting list.

Translation into VB

Public Function Primes(upTo As Integer) As List(Of Integer)
    Return Enumerable.Range(2, upTo - 1).Where(Function(n) IsPrime(n)).ToList()
End Function

Public Function IsPrime(n As Integer) As Boolean
    Return Not Enumerable.Range(2, n / 2 - 1).Any(Function(f) IsFactor(f, n))
End Function

Public Function IsFactor(f As Integer, ofN As Integer)
    Return ofN Mod f = 0
End Function

And with the parallelism:

Public Function Primes(upTo As Integer) As List(Of Integer)
    Return Enumerable.Range(2, upTo + 1).AsParallel().Where(Function(n) IsPrime(n)).ToList()
End Function