Finding primes in parallel

Posted by Jonas Elfström Thu, 14 Jan 2010 21:55:00 GMT

Justin Etheredge has been blogging about his challenge to find prime numbers with LINQ. He later used AsParallel() (coming in .NET 4) to speed things up and then followed that up with a post about using The Sieve Of Eratosthenes.

As you can see in the comments of those posts I tried to speed the Sieve of Eratosthenes up by using Parallel.For in the inner loop. I also tried AsParallel() in the LINQ expression but it made no difference in either case. At most it got 5% faster. I'm not sure but it could be that because SoE is very memory intense we could have a scaling issue and maybe also memory bandwidth exhaustion. This is mere speculation.

I then searched for other algorithms and found The Sieve of Atkin. It uses less memory than SoE so I thought I'd give it a try.

I set the limit to 20,000,000 and then benchmarked it. It timed in on 2.48s so actually worse than the 2.2s that SoE took. Not good! Then I added Parallel.For in the loop that did most of the work and lo and behold, it scaled! I have two cores in my machine (T7200@2.0GHz) and the average runtime went down to 1.26s. That's almost linear and surprisingly good! If you happen have a quad core (or more) and feel like trying it out then please contact me. It would be interesting to see if it scales further. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

static List<int> FindPrimesBySieveOfAtkins(int max)
{
    var isPrime = new BitArray((int)max+1, false);
    var sqrt = (int)Math.Sqrt(max);

    Parallel.For(1, sqrt, x =>
    {
        var xx = x * x;
        for (int y = 1; y <= sqrt; y++)
        {
            var yy = y * y;
            var n = 4 * xx + yy;
            if (n <= max && (n % 12 == 1 || n % 12 == 5))
                isPrime[n] = !isPrime[n];

            n = 3 * xx + yy;
            if (n <= max && n % 12 == 7)
                isPrime[n] = !isPrime[n];

            n = 3 * xx - yy;
            if (x > y && n <= max && n % 12 == 11)
                isPrime[n] = !isPrime[n];
        }
    });

    var primes = new List<int>() { 2, 3 };
    for (int n = 5; n <= sqrt; n++)
    {
        if (isPrime[n])
        {
            primes.Add(n);
            int nn = n * n;
            for (int k = nn; k <= max; k += nn)
                isPrime[k] = false;
        }
    }

    for (int n = sqrt + 1; n <= max; n++)
        if (isPrime[n])
            primes.Add(n);

    return primes;
}

This is C# 4.0 code, compiled in Visual C# 2010 Express Beta 2.

Edit 2010-01-20

Indications are that this does in fact not scale very good on a quad core. It's even worse, it seems it scales good on my old T7200 but not on a dual core E6320. I don't know why but of course the shared state of the isPrime BitArray is a huge problem and maybe it could be that differences in CPU architecture (FSB speed, caches and so on) in the E6320 is an explanation. Average execution time on the E6320 was 1290ms in a single thread and 1064ms in two.

If you want to try this in an older version of C# than 4.0 then check out this post.

A reader asked how I timed the executions. Here's how.

1
2
3
4
5
6
7
8
9
10
11
12
13

var steps = new List<long>();
var watch = new Stopwatch();

for (int i = 0; i < 10; i++) 
{
    watch.Reset();
    watch.Start();
    var primes = FindPrimesBySieveOfAtkins(20000000);
    watch.Stop();
    Console.WriteLine(watch.ElapsedMilliseconds.ToString());
    steps.Add(watch.ElapsedMilliseconds);
}
Console.WriteLine("Average: " + steps.Average().ToString());

Posted in ,  | 9 comments

Comments

Leave a response

  1. Avatar Svish said about 12 hours later:

    Are BitArrays thread-safe, or how does that work?

    Is it possible to write a version of this without the Parrallel.For method? Well, I suppose it is possible of course, but would it be a big mess? :p

  2. Avatar Jonas Elfström said about 15 hours later:

    Replace the Parallel.For with for (int x = 1; x <= sqrt; x++) and remove ); from row 24 and you should be good to go.

    If I understand http://bit.ly/8lZagW correctly the isPrime[n] = !isPrime[n]; is an atomic operation but I have to investigate the matter of thread safety further. Thanks!

  3. Avatar Svish said about 17 hours later:

    But that would remove the parallelism :p I was wondering if it could be done in a nice way without using Parallel.For, but still have the parallelism. (So do whatever Parallel.For does yourself)

  4. Avatar Svish said about 17 hours later:

    From that link you posted: “Aside from the library functions designed for that purpose, there is no guarantee of atomic read-modify-write, such as in the case of increment or decrement.” – Wouldn’t that mean that it is not thread-safe? or?

  5. Avatar Jonas Elfström said about 17 hours later:

    That’s for “long, ulong, double, and decimal”. Read/write of booleans is atomic. I’m just not sure that isPrime[n] = !isPrime[n]; is the same as Boolean test = false; test = !test; which would be atomic.

  6. Avatar Jonas Elfström said about 19 hours later:

    If Holterman is correct then my usage is thread safe: http://stackoverflow.com/questions/1213997/is-there-a-generic-type-safe-bitarray-in-net/1214686#1214686

  7. Avatar Jonas Elfström said 1 day later:

    “I was wondering if it could be done in a nice way without using Parallel.”

    Check out: http://www.codeproject.com/KB/dotnet/PoorMansParallelForEach.aspx

  8. Avatar Svish said 4 days later:

    So should maybe use the Set method instead then? Or doesn’t make much difference perhaps…

    Thanks for the link. Will check it out :)

  9. Avatar Jonas Elfström said 5 days later:

    http://coding-time.blogspot.com/2008/03/implement-your-own-parallelfor-in-c.html - makes it possible to run FindPrimesBySieveOfAtkins unchanged in C# 2.0-3.5.

RSS feed for this post


Email will not be shown. Enter email to show Gravatar.

   Comment Markup Help Preview comment