Microsoft Visual Studio 2010 : Data Parallelism - Unrolling Sequential Loops into Parallel Tasks (part 2) - The Parallel For Loop

1. Evaluating Performance Considerations

Not every sequential loop should be unrolled into parallel tasks. One consideration is performance.

If the proposed tasks are relatively small, the overhead for parallel execution—thread pool scheduling, context switching, and other overhead—might exceed the gain that parallelization would provide. You should always conduct performance benchmarks to confirm potential performance improvements. When there is minimal or no performance gain, one solution is to change the chunk size. The default chunk size is set by the default partitioner of the TPL. When a larger chunk size is requested, the larger chunk size increases the amount of work assigned to an individual task. This will lower the relative percentage of parallelization overhead and hopefully improve overall performance.

Data parallelization typically iterates the same operation. However, identical operations are not guaranteed to run for the same duration. Look at the following code, which prints out a series of prime numbers. Each loop performs exactly the same operation; however, the duration of each task could vary widely. Depending on the implementation, calculating whether 1,000 is a prime number takes considerably longer than performing the same test on the number 81. This inequity of workload can cause inefficient parallelization. In this circumstance, you might create a custom partitioner that uses a weighted algorithm to dynamically determine the chunk size to keep the workload balanced across processors. This would improve task scheduling and processor core utilization.

Here is the abstracted code for rendering prime numbers.

Parallel.For(1, 1000, (index) =>
{
   if(IsPrime(index))
   {
      Console.WriteLine(index);
   }
});

Remember, the Parallel.For method might not perform the prime number calculation in sequential order. In addition, Console.WriteLine is synchronized internally, which assures that the output is thread safe.

2. The Parallel For Loop

In most programming languages, the for loop is the most commonly used statement for iterations. The following example is a serial for loop, which performs each iteration in sequence. The loop iterates from 0 to 1000 while performing some operation. When the count is equal to or greater than 1000, the loop stops.

for (int count = 0; count < 1000; ++count)
{
   DoSomething();
}

In the Task Parallel Library (TPL), the equivalent statement uses a Parallel.For method. Instead of performing the iterations sequentially, the code runs them in parallel. You can find the Parallel class in the System.Threading.Tasks namespace. For the basic overload, the first two parameters are the starting and maximum value exclusively. The increment is 1. The last parameter is an Action delegate. For this parameter, you can provide a delegate, a lambda expression, or even an anonymous method that takes the current index as its only parameter. Parallel.For returns a ParallelLoopResult structure that contains the status of the Parallel.For loop. Here is the prototype for the Parallel.For method.

public static ParallelLoopResult For(
   int fromInclusive,
   int toExclusive,
   Action<int> body
)

Next is an example of an equivalent Parallel.For loop that executes an operation 100 times. Unlike the for loop’s iterations, the parallel iterations might not execute in linear sequence, so the seven-hundredth iteration might precede the tenth. However, unless the loop is canceled or interrupted with a ParallelLoopState.Break or ParallelLoopState.Stop statement, all iterations will run—just not necessarily in order.

Parallel.For(0, 100, (count) =>
{
   DoSomething();
});

The Parallel.ForEach method in the TPL is the parallel equivalent to the standard Microsoft Visual C# foreach statement. Use the Parallel.ForEach method to enumerate a collection in parallel using the same operation. For the basic overload of the method, the first parameter is the source collection. The next parameter is an Action delegate and is the operation to be performed on each element of the collection. The Action delegate takes a single parameter, the current element.

public static ParallelLoopResult ForEach<TSource>(

   IEnumerable<TSource> source,

   Action<TSource> body
)

Here is a standard foreach loop. Of course, this loop is performed sequentially.

foreach (int item in aList)
{
  Operation(item);
}

And here’s the same loop rewritten using the Parallel.ForEach method. Each iteration is a parallel task, executed not sequentially but in parallel.

Parallel.ForEach(aList, (item)=> {
   Operation(item);
} );

To put this into practice, in this next exercise, assume that you have a retail store with inventory. Once a month, you adjust pricing for items that have been in stock for more than 90 days, discounting inventory items priced under $500.00 by 10 percent and higher-priced items by 20 percent. Higher-priced items have an additional profit margin.

Create a Parallel.For loop to adjust inventory pricing

1. Create a console application for C# in Microsoft Visual Studio 2010. With the using statement, add the namespace System.Threading.Tasks to the list of namespaces. At class scope (before the Main method), define a static integer array that contains pricing of items in stock more than 90 days.

   static int[] inventoryList = new int []
      {100, 750, 400, 75, 900, 975, 275, 750, 600, 125, 300};

2. In the Main method, define a Parallel.For loop to enumerate the inventory.

   Parallel.For( 0, inventoryList.Length, (index) => {

3. You can now write the parallel operation. Define a temporary variable to hold the price of the current inventory item. If the price is greater than $500.00, apply a 20 percent discount. Otherwise, use a 10 percent discount.

   var price= inventoryList[index];
   if (price> 500)
   {
      inventoryList[index] = (int)(price* .8);
   }
   else
   {
      inventoryList[index] = (int)(price* .9);
   }

4. Use Console.WriteLine to display the adjusted price.

5. At the end of the program, add a Console.ReadLine method to prevent the program from ending before you can view the results. You might also want to display an informative message to the user.

   Console.WriteLine("Press enter to exit");
   Console.ReadLine();

   Note

   I’ll omit the previous step in future examples, but feel free to add it at your discretion.

6. Build and run the application.

Your completed code should look like the following.

namespace PriceIncrease
{
    class Program
    {
        static int[] inventoryList = new int [] {100, 750, 400, 75, 900, 975, 275,
            750, 600, 125, 300};

        static void Main(string[] args)
        {
            Parallel.For( 0, inventoryList.Length, (index) =>
            {
                var price = inventoryList[index];
                if (price> 500)
                {
                    inventoryList[index] = (int)(price* .8);
                }
                else
                {
                    inventoryList[index] = (int)(price* .9);
                }

                Console.WriteLine("Item {0,4} Price: {1, 7:f}",
                    index, inventoryList[index]);
            });

            Console.WriteLine("Press enter to exit");
            Console.ReadLine();
        }
    }
}

Here’s the output for the application. Notice that the inventory items were not handled in sequential order. Your results might vary from these results. In addition, the results of a parallel application might change between instances. For example, the order of execution of a Parallel.For loop is not guaranteed and could change between instances.