Keeping Linq's readability (e.g. over goto statements) without sacrificing performance

Question

I'm doing Project Euler problem 5 as a kata, focussing on TDD and code readability. The challenge is:

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

For reference, a "less-readable" solution that reeks of goto was something along these lines:

public int Solution_GotoVersion()
{
    int solution = 1;
    outer: while (solution++ < int.MaxValue)
    {
        for (int j = 1; j <= 20; j++)
        {
            if (solution % j != 0)
                goto outer;
        }
        return solution;
    }
    throw new Exception("Solution not found");
}

This takes about 4 seconds to run, relative to the other solutions.

Of course I was trying to avoid such code (in light of readability, for one), I wrote it specifically to compare it to my first solution, that uses an alternative along the lines of this SO answer. So, focussing on readability, here's something a little nicer:

public int Solution_LinqVersion()
{
    var dividers = Enumerable.Range(1, 20);

    int solution = Enumerable
                    .Range(1, int.MaxValue)
                    .FirstOrDefault(candidate
                      => dividers.All(divider => candidate.IsDivisibleBy(divider)));

    return solution;
}

This performs much worse, taking about 25 seconds, relatively. I don't mind loosing some performance when traded for readability, but a factor 8 is a bit much.

I've tried an intermediate solution, like this:

public int Solution_LittleOfBothWorlds()
{
    var dividers = Enumerable.Range(1, 20).ToArray();
    int solution = 1;
    while (solution++ < int.MaxValue)
    {
        if (dividers.All(divider => solution % divider == 0))
            return solution;
    }
    throw new Exception("Solution not found");
}

This is in the middle, performance-wise, taking about 14 seconds, relatively.

What can I do to keep relative performance close to the first example, with code that utilizes Linq's readability?

Note: I'm aware there are of many other optimizations possible, amongst others in the algorithm itself. In this case however, I'm specifically interested in the performance of Linq queries relative to more "oldskool" constructs, and how to keep Linq's nice syntax without giving up too much performance (if possible).

Answer 1

Focus on optimizing the innermost loop. That's where the performance is lost. In particular try to minimize the number of indirect calls (virtual method, interface and delegate calls).

Your LINQ code has ~60 of those. My variant 1 reduces them to ~20, and my variant 2 to only a handful.

Variant 1:

Very close to linq, but using Array.TrueForAll. About twice as fast are pure linq:

public int Solution_ArrayLinqVersion()
{
    var dividers = Enumerable.Range(1, 20).ToArray();

    int solution = Enumerable
                    .Range(1, int.MaxValue)
                    .First(candidate
                      => Array.TrueForAll(dividers, divider => candidate%divider==0));

    return solution;
}

Variant 2:

Use a loop for the division testing(inner loop) and linq for the outer loop. Almost as fast as no LINQ:

int LinqOutLoopInner()
{
    return Enumerable
        .Range(1, int.MaxValue)
        .First(IsDivisibleBy1to20);
}

static bool IsDivisibleBy1to20(int candidate)
{
    for (int j = 1; j <= 20; j++)
    {
        if (candidate % j != 0)
            return false;
    }
    return true;
}

Answer 2

How about breaking it across two functions:

private boolean IsDivisibleBy1to20(int solution)
{
    for (int j = 1; j <= 20; j++)
    {
        if (solution % j != 0)
            return false;
    }
    return true;
}

public int Solution_GotoVersion()
{
    int solution = 1;
    while (solution++ < int.MaxValue)
    {
        if( IsDivisibleBy1to20(solution)
        {
            return solution;
        }
    }
    throw new Exception("Solution not found");
}

I think it would help with testability because you could test the divisibility thing seperately.

Then there is this bit:

    while (solution++ < int.MaxValue)

I think this actually works, although its a bit tricky due to post-increment and overflow concerns.

Answer 3

You can have both performance and readability using the newly-introduced (.NET 4.0) method BigInteger.GreatestCommonDivisor (a reference to System.Numerics is required).

With the BigInteger stuct, you gain an additional advantage: your code will work for arbitrarily large numbers (assuming sufficient memory).

var result = ClosedInterval(1, 20).LeastCommonMultiple();

What we are looking for is the least common multiple of all natural numbers in the interval [1, 20], so we'll need a method to generate them (closed means including both bounds and the numbers between):

static IEnumerable<BigInteger> ClosedInterval(BigInteger first, BigInteger last)
{
    for (var i = first; i <= last; i++)
    {
        yield return i;
    }
}

From Wikipedia, we know how to calculate the least common multiple of two numbers:

static BigInteger LeastCommonMultiple(BigInteger a, BigInteger b)
{
    return (a * b) / BigInteger.GreatestCommonDivisor(a, b);
}

For an arbitrary number of least common multiples, we simply aggregate them using LINQ and package the logic in an extension method:

static BigInteger LeastCommonMultiple(this IEnumerable<BigInteger> divisors)
{
    return divisors.Aggregate(LeastCommonMultiple);
}

---

The implementation calculates the correct result (232792560) in less than ten milliseconds.

In less than half a second, you can find out the answer for an input of [1, 20000]; The solution is over eight thousand digits long and therefore somewhat outside the scope of this answer.

---

What's really awesome:

• There is an implicit cast from int to BigInteger, so you can pass integer literals as arguments to ClosedInterval

• The arithmetic operators are overloaded, so you can use the same syntax for dividing, multiplying, etc. as you would with the integral numeric types

• BigInteger is extremely optimized for speed (the only thing to wary of is that it is a struct, and therefore exhibits different memory behaviour than reference types do).

• It turns out that the aggregation is highly parallelizable! Just using PLINQ like this:

  static BigInteger LeastCommonMultiple(this IEnumerable<BigInteger> divisors)
  {
      return divisors.AsParallel().Aggregate(LeastCommonMultiple);
  }
  

  leads to a performance improvement proportional to the number of cores in your machine. In my case, finding the least common multiple of all natural numbers between one and two hundred thousand completed in around six seconds (the sequential version took over 45).