CODEWITHSUNDEEP
c#performancealgorithmlinq
KChaloux
KChaloux

Reputation: 4038

Enumerable.Range(...).Any(...) outperforms a basic loop: Why?

I was adapting a simple prime-number generation one-liner from Scala to C# (mentioned in a comment on this blog by its author). I came up with the following:

int NextPrime(int from)
{
  while(true)
  {
    n++;
    if (!Enumerable.Range(2, (int)Math.Sqrt(n) - 1).Any((i) => n % i == 0))
      return n;
  }
}

It works, returning the same results I'd get from running the code referenced in the blog. In fact, it works fairly quickly. In LinqPad, it generated the 100,000th prime in about 1 second. Out of curiosity, I rewrote it without Enumerable.Range() and Any():

int NextPrimeB(int from)
{
  while(true)
  {
    n++;
    bool hasFactor = false;
    for (int i = 2; i <= (int)Math.Sqrt(n); i++)
    {
        if (n % i == 0) hasFactor = true;
    }
    if (!hasFactor) return n;
  }
}

Intuitively, I'd expect them to either run at the same speed, or even for the latter to run a little faster. In actuality, computing the same value (100,000th prime) with the second method, takes 12 seconds - It's a staggering difference.

So what's going on here? There must be fundamentally something extra happening in the second approach that's eating up CPU cycles, or some optimization going on the background of the Linq examples. Anybody know why?

Upvotes: 6

Views: 995

Answers (6)

interplanetjanet
interplanetjanet

Reputation: 41

In the name of optimization, you can be a little more clever about this by avoiding even numbers after 2:

if (n % 2 != 0)
{
  int quux = (int)Math.Sqrt(n);

  for (int i = 3; i <= quux; i += 2)
  {
    if (n % i == 0) return n;
  }
}

There are some other ways to optimize prime searches, but this is one of the easier to do and has a large payoff.

Edit: you may want to consider using (int)Math.Sqrt(n) + 1. FP functions + round-down could potentially cause you to miss a square of a large prime number.

Upvotes: 4

user7116
user7116

Reputation: 64078

Enumerable.Any takes an early out if the condition is successful while your loop does not.

The enumeration of source is stopped as soon as the result can be determined.

This is an example of a bad benchmark. Try modifying your loop and see the difference:

    if (n % i == 0) { hasFactor = true; break; }
}

throw new InvalidOperationException("Cannot satisfy criteria.");

Upvotes: 4

Brad M
Brad M

Reputation: 7898

For every iteration of the for loop, you are finding the square root of n. Cache it instead.

int root = (int)Math.Sqrt(n);
for (int i = 2; i <= root; i++)

And as other have mentioned, break the for loop as soon as you find a factor.

Upvotes: 9

JaredPar
JaredPar

Reputation: 754803

At least part of the problem is the number of times Math.Sqrt is executed. In the LINQ query this is executed once but in the loop example it's executed N times. Try pulling that out into a local and reprofiling the application. That will give you a more representative break down

int limit = (int)Math.Sqrt(n);
for (int i = 2; i <= limit; i++)

Upvotes: 2

Mike Dinescu
Mike Dinescu

Reputation: 55730

It looks like this is the culprit:

for (int i = 2; i <= (int)Math.Sqrt(n); i++)
{
    if (n % i == 0) hasFactor = true;
}

You should exit the loop once you find a factor:

if (n % i == 0){
   hasFactor = true;
   break;
}

And as other have pointed out, move the Math.Sqrt call outside the loop to avoid calling it each cycle.

Upvotes: 4

Servy
Servy

Reputation: 203834

The LINQ version short circuits, your loop does not. By this I mean that when you have determined that a particular integer is in fact a factor the LINQ code stops, returns it, and then moves on. Your code keeps looping until it's done.

If you change the for to include that short circuit, you should see similar performance:

int NextPrimeB(int from)
{
  while(true)
  {
    n++;
    for (int i = 2; i <= (int)Math.Sqrt(n); i++)
    {
        if (n % i == 0) return n;;
    }
  }
}

Upvotes: 4

Related Questions