Why my parallel for loop is much slower than for?

Question

I tried changing my for loop with a parallel one but it's soo much slower instead of finishing the loop in a minute it finishes in 30 minutes. What the loop does is start with a number check if it's odd and if it's even. If it's odd it multiples by 3 and adds 1. If it's even it divides it by 2. Keep repeating that until the number reaches 4, and there is a loop around that repeats that a million times each time with a number higher by one. The last loop I mentioned is the loop I try to change to a parallel one. Here is the code for the normal for loop:

        static void Main(string[] args)
        {
            
            BigInteger currenthighest =new BigInteger(Math.Pow(2,68));
            BigInteger currentValue;
            Console.WriteLine(currenthighest);
            Console.ReadKey();
            for (int i = 1; i > -1; i++)
            {
               
                for (int z = 0; z != 1000000; z++)
                 {
                     currentValue = currenthighest;
                     while (currentValue != 4)
                     {
                         if (currentValue % 2 == 0)
                         {
                             currentValue = currentValue / 2;
                         }
                         else
                         {
                             currentValue = (currentValue * 3) + 1;
                         }
                     }
                     currenthighest++;
                 }    
                Console.WriteLine(" {0} times done", i * 1000000);
            } 
        }

And here is the code for the parallel one:

        static void Main(string[] args)
        {
            
            BigInteger currenthighest =new BigInteger(Math.Pow(2,68));
            BigInteger currentValue;
            Console.WriteLine(currenthighest);
            Console.ReadKey();
            for (int i = 1; i > -1; i++)
            {
               
                Parallel.For(0, 1000000,z=>
                 {
                     currentValue = currenthighest;
                     while (currentValue != 4)
                     {
                         if (currentValue % 2 == 0)
                         {
                             currentValue = currentValue / 2;
                         }
                         else
                         {
                             currentValue = (currentValue * 3) + 1;
                         }
                     }
                     currenthighest++;
                 });   
                Console.WriteLine(" {0} times done", i * 1000000);
            } 
        }

Can someone help me make it faster than a normal for loop or is using parallel in this situation stupid and I should just use normal for loop? If I will also appreciate any help to make normal for loop faster.

Beyond being slower, the parallel version is also incorrect, since the `currenthighest++` operation [is not thread-safe](https://stackoverflow.com/questions/4628243/is-the-operator-thread-safe). — Theodor Zoulias, Jul 31 '21 at 15:40
My assumption is going to be that the workload in the thread is less than the cost of context switching. — ProgrammingLlama, Jul 31 '21 at 16:17
Related: [Multiplying arrays element-wise has unexpected performance in C#](https://stackoverflow.com/questions/59012299/multiplying-arrays-element-wise-has-unexpected-performance-in-c-sharp). This question shows that when the `Parallel.For` falls short because the workload is too granular, you can chunkify it by switching to the `Parallel.ForEach(Partitioner.Create(0, 1000000)`. Also be aware that the `Parallel.For`/`Parallel.ForEach` methods, when used without configuring the `MaxDegreeOfParallelism`, saturate the `ThreadPool`, [which is bad](https://stackoverflow.com/a/66263583/11178549). — Theodor Zoulias, Aug 01 '21 at 01:05

score 2 · Accepted Answer · answered Jul 31 '21 at 16:52

The reason for the performance deficit if as Theodor Zoulias points out probably due to it not being thread-safe. This can cause numbers to take arbitrary values and may cause totally different calculations to be performed.

To fix this you need to make each parallel loop independent. As far as I can tell this would be rather easy to do in your example since you only need to ensure that all modified values are local:

 static void Main(string[] args)
 {
        
        BigInteger startvalue =new BigInteger(Math.Pow(2,68));
        Console.WriteLine(startvalue );
        Console.ReadKey();
        for (int i = 1; i > -1; i++)
        {
            Parallel.For(0, 1000000,z=>
             {
                 var currentValue = startvalue + z;
                 while (currentValue != 4)
                 {
                     if (currentValue % 2 == 0)
                     {
                         currentValue = currentValue / 2;
                     }
                     else
                     {
                         currentValue = (currentValue * 3) + 1;
                     }
                 }
             });   
            Console.WriteLine(" {0} times done", i * 1000000);
       }
    }

Another possibility is that the work inside the parallel loop is on average quite small, causing the threading overhead to be significant. There is also the issue of work-balancing, Parallel.For will do work in 'chunks' to reduce this threading overhead, and try to adapt the size of these chunks. If the amount of work is highly variable this adaptation will probably result in inefficiencies.

thanks, JonasH. now each million take about 20 seconds. the normal for loop took a minute — yosefouad, Jul 31 '21 at 17:05

Why my parallel for loop is much slower than for?

1 Answers1