Building on the previous code, the CountFactor method would be a good candidate to be executed in parallel. It is doing the heavy calculation of finding the number of factor a number has, and it has no dependency on any other external factor.

Previously, when there is no PLINQ, we would have to do multithreading manually, and I would have probably came up with something like this:

static int SolveUsingMultiThread(int numberOfFactors)
{
	const int numberOfThreads = 2;

	ManualResetEvent[] waitHandles = new ManualResetEvent[numberOfThreads];
	int[] answers = new int[numberOfThreads];

	var triangleNumberSequence = EnumSequenceOfTriangleNumbers().GetEnumerator();

	ParameterizedThreadStart countFactorThread = delegate(object obj) {
		int n;

		do {
			lock (triangleNumberSequence) {
				triangleNumberSequence.MoveNext();
				n = triangleNumberSequence.Current;
			}
		} while (CountFactor(n) < numberOfFactors);

		int index = (int) obj;
		answers[index] = n;
		waitHandles[index].Set();
	};

	for (int i = 0; i < numberOfThreads; i++) {
		waitHandles[i] = new ManualResetEvent(false);
		Thread thread = new Thread(countFactorThread);
		thread.Start(i);
	}

	WaitHandle.WaitAll(waitHandles);
	return answers.Min();
}

Note: I written the code above after I tested on the PLINQ code just to show what multithreading code may look like. It was written quite quickly without much thought. But if you are still curious on how fast it is – well, it took 450 ms. Yes, it is even a bit slower than the normal one, and I have no intention on fixing it to be faster because I’m having fun doing PLINQ, and even more fun doing F#. :D

PLINQ Attempt 1 – Unsatisfying

PLINQ is supposed to make it easier on us compared to using the manual multithreading method. Here is my first attempt to “parallelize” the code using PLINQ:

static int SolveUsingPLinq1(int numberOfFactors)
{
	var query = from n in EnumSequenceOfTriangleNumbers()
					.AsParallel().AsOrdered()
				where CountFactor(n) >= numberOfFactors
				select n;

	return query.First();
}

The time for this is 381 ms. It was doing 403 ms for the sequential code. Not good enough. I expected something around half the time.

PLINQ Attempt 2 – Even more of a failure

static int SolveUsingPLinq2(int numberOfFactors)
{
	var query1 = from n in EnumSequenceOfTriangleNumbers()
				 select new { TriangleNumber = n,
					 FactorCount = CountFactor(n) };

	var query2 = from a in query1.AsParallel().AsOrdered()
				 where a.FactorCount >= numberOfFactors
				 select a;

	return query2.First().TriangleNumber;
}

This code is executing even longer: 590 ms. I stopped a bit and started to google around for PLINQ stuff.

PLINQ Attempt 3 – Still nowhere near what I was expecting

Then I found this article on MSDN: Understanding Speedup in PLINQ.
Reading the code example there, I came to the thought:

Aha! The source of the triangle numbers should be marked as being parallel-able, then the heavy lifting of the CountFactor method should be put in the select part of the query. This should create the select results in parallel.

Based on that thought, I then came up with the next code:

static int SolveUsingPLinq3(int numberOfFactors)
{
	var query1 = from n in EnumSequenceOfTriangleNumbers()
					 .AsParallel().AsOrdered()
				 select new { TriangleNumber = n,
					 FactorCount = CountFactor(n) };

	var query2 = from a in query1
				 where a.FactorCount >= numberOfFactors
				 select a;

	return query2.First().TriangleNumber;
}

376 ms. Still not half the time. This shouldn’t be it.

PLINQ Attempt 4 – Eureka!

I don’t remember how I came to this, but here’s the final code and the one that I’m happy with the result:

static int SolveUsingPLinq4(int numberOfFactors)
{
	var query = from n in EnumSequenceOfTriangleNumbers()
					.AsParallel().AsOrdered()
				select new { TriangleNumber = n,
					FactorCount = CountFactor(n) };

	return query
		.First(a => a.FactorCount >= numberOfFactors)
		.TriangleNumber;
}

234 ms! This is what I call parallel, though I can’t really explain much on the best way to use PLINQ. ;)

Random Conclusion

  • The source of a query (the from statement) should be something relatively cheap to generate, and it should be turned to a parallel source using the .AsParallel() extension method call.
  • The heavy computation should be put as a projection of the query (in the select statement).
  • Where you put the criteria is based on what you want from the query – I know, an easy escape statement, I don’t really have any good advise on this. :P