C# Threaded Eratosthene misunderstanding

Question

I have two function generating prime numbers with the Sieves of Eratosthenes, one using simple loop, and the other using Tasks to run computations on multiple threads.

As I need to lock the list of values when using threads, I was assuming that the threaded version would not be faster than the normal version. But after some tests the normal version seems to be about 6 times worst than the threaded one.

Even stranger, when using only one Task at a time it stays 6 times faster than the normal version. What am I missing ?

Here is the code:

    public static List<int> UsualPrimesGenerator(int n)
        {
            if (n < 0)
                return new List<int>();
            List<int> res = new List<int>();
            for (int i = 2; i < n; i++) res.Add(i);

            for (int i = 2; i * 2 <= n; i++)
            {
                res.RemoveAll(p => p != i && p % i == 0);
            }

            return res;
        }

        public static List<int> MagicPrimesGenerator(int n, int nbTasks)
        {
            if (nbTasks <= 0)
                throw new ArgumentException("Nbthread must be positive");

            var threads = new Task[nbTasks];

            List<int> primes = new List<int>();
            for (int i = 2; i <= n; i++)
                primes.Add(i);

            for (int i = 2; i * 2 <= primes.Count; i++)
            {
                if (threads[i % nbTasks] == null)
                {
                    var i2 = i;
                    threads[i % nbTasks] = Task.Run(() =>
                    {
                        lock (primes)
                        {
                            primes.RemoveAll(p => p != i2 && p % i2 == 0);
                        }
                    });
                }
                else
                {
                    threads[i % nbTasks].Wait();
                    var i2 = i;
                    threads[i % nbTasks] = Task.Run(() =>
                    {
                        lock (primes)
                        {
                            primes.RemoveAll(p => p != i2 && p % i2 == 0);
                        }
                    });
                }
            }

            for (int i = 0; i < nbTasks; i++)
            {
                if (threads[i] != null)
                    threads[i].Wait();
            }

            return primes;
        }

And the result of time tests for n = 100000:

Usual Prime Generator: 2732ms
9592 Primes found
Magic Prime Generator: 397ms
9592 Primes found

These are not `threads`. These are `tasks`. Threads and tasks [are not the same](https://stackoverflow.com/questions/13429129/task-vs-thread-differences). — Theodor Zoulias, May 07 '21 at 11:32
Yes, sorry wrong words, I know that Tasks may not be executed in separate threads but the problem is the same, why asynchronous tasks are running faster than a simple for loop — JM445, May 07 '21 at 11:35
`Stopwatch sw1 = new Stopwatch(); Stopwatch sw2 = new Stopwatch(); sw1.Start(); List res = LevelThree.UsualPrimesGenerator(100000); sw1.Stop(); sw2.Start(); res = LevelThree.MagicPrimesGenerator(100000, 1); sw2.Stop();` — JM445, May 07 '21 at 11:44
Try [BenchmarkDotnet](https://benchmarkdotnet.org/) ... If the result is still the same or similar, I'd be surprised, too, at first glance. — Fildor, May 07 '21 at 11:46
I would suggest changing to a `Parallel.For` loop. That should make your code significantly easier to read. Use `ParallelOptions` to restrict the max number of concurrent threads. — JonasH, May 07 '21 at 11:51
@JonasH That's not the point. OP is wondering why he sees the opposite of the result he expected. Now either there is something wrong with the way he measured or his expectation was wrong to begin with. — Fildor, May 07 '21 at 11:57
This must be some sort of strange optimisation, but I can't find anything in MSDN Documentation — JM445, May 07 '21 at 12:02
@Fildor I agree that it is not the issue here. But making the code easier to read can make problems more obvious when it is not hidden behind a bunch of irrelevant stuff. — JonasH, May 07 '21 at 13:59

score 4 · Accepted Answer · edited May 07 '21 at 12:54

The reason there is a difference is that you do much more iterations in your simple solution. If you change the loop from:

for (int i = 2; i * 2 <= n; i++)
{
    res.RemoveAll(p => p != i && p % i == 0);
}

To utilize rs.count - then it behaves exactly like the magic method.

for (int i = 2; i * 2 <= res.count; i++)
{
    res.RemoveAll(p => p != i && p % i == 0);
}

I did not check for correctness, but I guess that is not your question. Also, your method of measuring can be improved as mentioned in the comments above. But that was not the problem in this case.

Full code with a counter in the loop.

class Program
{
    private const int n = 100000;
    
    static void Main(string[] args)
    {
        MagicPrimesGenerator(n, 12);
        MagicPrimesGenerator(n, 12);
        MagicPrimesGenerator(n, 12);
        MagicPrimesGenerator(n, 12);
        UsualPrimesGenerator(n);
        UsualPrimesGenerator(n);
        UsualPrimesGenerator(n);
        UsualPrimesGenerator(n);
        
        var sw = new Stopwatch();
        sw.Start();

        sw.Reset();
        sw.Start();
        MagicPrimesGenerator(n, 1);
        Console.WriteLine($"B: Magic Prime Generator: {sw.ElapsedMilliseconds} ms");
        
        sw.Reset();
        sw.Start();
        UsualPrimesGenerator(n);
        Console.WriteLine($"A: Usual Prime Generator: {sw.ElapsedMilliseconds} ms");
    }
    
    
    public static List<int> UsualPrimesGenerator(int n)
    {
        int count = 0;
        if (n < 0)
            return new List<int>();
        List<int> res = new List<int>();
        for (int i = 2; i < n; i++) res.Add(i);

        for (int i = 2; i * 2 <= res.Count; i++)
        {   
            res.RemoveAll(p => p != i && p % i == 0);
            count++;
        }
        
        Console.Write("usual iteration count ");
        Console.WriteLine(count);
        return res;
    }

    public static List<int> MagicPrimesGenerator(int n, int nbTasks)
    {
        if (nbTasks <= 0)
            throw new ArgumentException("Nbthread must be positive");

        var threads = new Task[nbTasks];
        int count = 0;

        List<int> primes = new List<int>();
        for (int i = 2; i <= n; i++)
            primes.Add(i);

        for (int i = 2; i * 2 <= primes.Count; i++)
        {
            if (threads[i % nbTasks] == null)
            {
                var i2 = i;
                threads[i % nbTasks] = Task.Run(() =>
                {
                    lock (primes)
                    {
                        primes.RemoveAll(p => p != i2 && p % i2 == 0);
                        count++;
                    }
                });
            }
            else
            {
                threads[i % nbTasks].Wait();
                var i2 = i;
                threads[i % nbTasks] = Task.Run(() =>
                {
                    lock (primes)
                    {
                        primes.RemoveAll(p => p != i2 && p % i2 == 0);
                        count++;
                    }
                });
            }
        }

        for (int i = 0; i < nbTasks; i++)
        {
            if (threads[i] != null)
                threads[i].Wait();
        }
        
        Console.Write("magic iteration count ");
        Console.WriteLine(count);

        return primes;
    }
}

Excellent catch! Didn't see that coming. So simple and has nothing to do with Task vs single Thread ... *dough — Fildor, May 07 '21 at 12:15

C# Threaded Eratosthene misunderstanding

1 Answers1