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

Answer 1

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;
    }
}