Measure Execution time of Parallel.For

Question

I am using a Parallel.For loop to increase execution speed of a computation.

I would like to measure the approximate time left for the computation. Normally one simply has to measure the time it takes for each step and estimate the total time by multiplying the step time by the total number of steps.

e.g., If there are 100 steps and some step takes 5 seconds then one could except that the total time would be about 500 seconds. (one could average over several steps and continuously report to the user which is what I want to do).

The only way I can think to do this is by using an outer for loop that essentially resorts back to the original way by splitting up the parallel.for interval and measuring each one.

for(i;n;i += step)
    Time(Parallel.For(i, i + step - 1, ...))

This isn't a very good way in general because either a few number of very long steps or a large number of short steps cause problems with timing.

Anyone have any ideas?

(Please realize I need a real time estimation of the time it is taking the parallel.for to complete and NOT the total time. I want to let the user know how much time is left in execution).

Answer 1

This method seems to be pretty effective. We can "linearize" the parallel for loop by simply having each parallel loop increment a counter:

Parallel.For(0, n, (i) => { Thread.Sleep(1000); Interlocked.Increment(ref cnt); });     

(Note, thanks to Niclas, that ++ is not atomic and one must use lock or Interlocked.Increment)

Each loop, running in parallel, will increment cnt. The effect is that cnt is monotonically increasing to n, and cnt/n is the percentage of how much the for is complete. Since there is no contention for cnt, there are no concurrency issues and it is very fast and very perfectly accurate.

We can measure the percentage of completion of the parallel For loop at any time during the execution by simply computing cnt/n

The total computation time can be easily estimated by dividing the elapsed time since the start of the loop with the percentage the loop is at. These two quantities should have approximately the same rates of change when each loop takes approximately the same amount of time is relatively well behaved (can average out small fluctuation too).

Obviously the more unpredictable each task is, the more inaccurate the remaining computation time will be. This is to be expected and in general, there is no solution (which is why it's called an approximation). We can still get the elapsed computation time or percentage with complete accuracy.

The underlying assumption of any estimation of "time left" algorithms is each sub task takes approximately the same computation time (assuming one wants a linear result). For example, if we have a parallel approach where 99 tasks are very quick and 1 task is very slow, our estimation will be grossly inaccurate. Our counter will zip up to 99 pretty quick then sit on the last percentage until the slow task completes. We could linearly interpolate and do further estimation to get a smoother countdown but ultimately there is a breaking point.

The following code demonstrates how to measure the parallel for efficiently. Note the time at 100% is the true total execution time and can be used as a reference.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Diagnostics;

namespace ParallelForTiming
{
    class Program
    {       
        static void Main(string[] args)
        {
            var sw = new Stopwatch();
            var pct = 0.000001;
            var iter = 20;
            var time = 20 * 1000 / iter;
            var p = new ParallelOptions(); p.MaxDegreeOfParallelism = 4;

            var Done = false;
            Parallel.Invoke(() =>
            {
                sw.Start();
                Parallel.For(0, iter, p, (i) => { Thread.Sleep(time); lock(p) { pct += 1 / (double)iter; }});               
                sw.Stop(); 
                Done = true;

            }, () =>
            {
                while (!Done)
                {
                    Console.WriteLine(Math.Round(pct*100,2) + " : " + ((pct < 0.1) ? "oo" : (sw.ElapsedMilliseconds / pct /1000.0).ToString()));
                    Thread.Sleep(2000);
                }

            }
            );
            Console.WriteLine(Math.Round(pct * 100, 2) + " : " + sw.ElapsedMilliseconds / pct / 1000.0);


            Console.ReadKey();
        }
    }
}

Answer 2

This is almost impossible to answer.

First of all, it's not clear what all the steps do. Some steps may be I/O-intensive, or computationally intensive.

Furthermore, Parallel.For is a request -- you are not sure that your code will actually run in parallel. It depends on circumstances (availability of threads and memory) whether the code will actually run in parallel. Then if you have parallel code that relies on I/O, one thread will block the others while waiting for the I/O to complete. And you don't know what other processes are doing either.

This is what makes predicting how long something will take extremely error-prone and, actually, an exercise in futility.

Answer 3

This problem is a tough one to answer. The problems with timing that you refer to using very long steps or a large number of very short steps are likley related to that your loop will be working at the edges of what the parallel partitioner can handle.

Since the default partitioner is very dynamic and we know nothing about your actual problem there is no good answer that allows you to solve the problem at hand while still reaping the benefits of parallel execution with dynamic load balancing.

If it is very important to achive a reliable estimation of projected runtime perhaps you could set up a custom partitioner and then leverage your knowledge about the partioning to extrapolate timings from a few chunks on one thread.

Answer 4

Here's a possible solution to measure the average of all previously finished tasks. After each task finishes, an Action<T> is called where you could summarize all times and divide it by the total tasks finished. This is however just the current state and has no way to predict any future tasks / averages. (As others mentioned, this is quite difficult)

However: You'll have to measure if it fits for your problem because there is a possibility for lock contention on both the method level declared variables.

     static void ComputeParallelForWithTLS()
            {
                var collection = new List<int>() { 1000, 2000, 3000, 4000 }; // values used as sleep parameter
                var sync = new object();
                TimeSpan averageTime = new TimeSpan();
                int amountOfItemsDone = 0; // referenced by the TPL, increment it with lock / interlocked.increment

                Parallel.For(0, collection.Count,
                    () => new TimeSpan(),
                    (i, loopState, tlData) =>
                    {
                        var sw = Stopwatch.StartNew();
                        DoWork(collection, i);
                        sw.Stop();
                        return sw.Elapsed;
                    },
                    threadLocalData =>   // Called each time a task finishes
                    {
                        lock (sync)
                        {
                            averageTime += threadLocalData; // add time used for this task to the total.
                        }
                        Interlocked.Increment(ref amountOfItemsDone); // increment the tasks done
                        Console.WriteLine(averageTime.TotalMilliseconds / amountOfItemsDone + ms."); 
/*print out the average for all done tasks so far. For an estimation, 
multiply with the remaining items.*/
                    });
            }
            static void DoWork(List<int> items, int current)
            {
                System.Threading.Thread.Sleep(items[current]);
            }