CODEWITHSUNDEEP
.netmultithreading.net-4.0task-parallel-library
Jason Robbins
Jason Robbins

Reputation: 83

Multithreading recursive task

I have a small program which I'm trying to increase the performance of. The program is quite simple and is largely based on a single recursive function. However the dataset behind it is quite large - requiring something in the order of 6,000,000,000 recursions, taking around 4-6hrs to run depending on the machine. There's no I/O just processing data, I've spent quite a bit of time optimising the code and managed to find ~60% of improvement.

What I want to look at now is multi-threading the code so that it takes advantage of all the cores in the host machine. However I've tried using Threads, Tasks and bits of the Parellel libary and I've been unable to find anything which doesn't hit performance in a negative way.

To give you an idea of the sort of code I'm looking at:

class Program
{
    static void Main(string[] args)
    {
        RecursiveFunction(0);
        Console.ReadLine();
    }
    static void RecursiveFunction(int currentLevel)
    {
        DoWork(currentLevel);

        if (currentLevel < 1000)
            for (int i = 0; i < (currentLevel % 6) + 1; i++)
                RecursiveFunction(currentLevel + 1);
    }
    static void DoWork(int currentLevel)
    {
        Thread.Sleep(42);
    }
}

As you can see each run of the function doesn't take long to run, so the cost of creating a thread for each recursion isn't worth it. Each branch of the recursion can be of differing lengths with no way of knowing how long each branch is going to be, so threading at a particular level isn't the right way to go.

Does anyone have any suggestions?

Upvotes: 1

Views: 2140

Answers (3)

Toan Nguyen
Toan Nguyen

Reputation: 11601

You can always chain your tasks using the code below and let the task scheduler schedule your work. 

class Program
    {
        private static int MaxLevel = 1000;
        static void Main(string[] args)
        {
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();

            Task mainTask = ParallelRecursiveFunction(0);
            mainTask.Wait();
            stopwatch.Stop();
            Console.WriteLine("Total time of parallel execution  : {0}", stopwatch.ElapsedMilliseconds);


            Console.WriteLine("Press Enter to execute the operation sequentially");
            Console.WriteLine();
            Console.ReadLine();
            stopwatch.Reset();
            stopwatch.Start();

            SequentialRecursiveFunction(0);

            stopwatch.Stop();

            Console.WriteLine("Total time of sequential execution: {0}",stopwatch.ElapsedMilliseconds);
            Console.ReadLine();
        }

        private static void SequentialRecursiveFunction(int currentLevel)
        {
            if (currentLevel >= MaxLevel)
                return;
            DoWork(currentLevel);

            SequentialRecursiveFunction(currentLevel +1);
        }

        public static Task ParallelRecursiveFunction(int currentLevel)
        {
            if (currentLevel >= MaxLevel)
                return _completedTask;
            Task t1 = Task.Factory.StartNew(() => DoWork(currentLevel));

            Task<Task> t2 = Task.Factory.StartNew(() => ParallelRecursiveFunction(currentLevel + 1));

            return Task.Factory.ContinueWhenAll(new Task[] { t1, t2.Unwrap() }, Task.WaitAll);

        }
        private static Task _completedTask = ((Func<Task>)(() =>
        {
            var tcs = new TaskCompletionSource<object>();
            tcs.SetResult(null);
            return tcs.Task;
        }))();

        static void DoWork(int currentLevel)
        {
            Console.WriteLine("Do work at level {0}", currentLevel);

            Thread.Sleep(42);

        }
    }

I tested my parallel code running approximately 4 times faster (= number of processors on my machine) than the sequential algorithm.

Please let me know what do you think.

Cheers.

Upvotes: 0

usr
usr

Reputation: 171246

Use parallelism in the upper levels of the tree. Each invocation there takes minutes to hours, so you have very little overhead due to threading.

Use the Parallel.For* methods to execute the loop in parallel.

In the lower layers of the recursive tree use a normal sequential loop.

Choose the cut-off level in a way that results in a few thousand parallelized loop iterations.

Upvotes: 2

shr
shr

Reputation: 1035

It is difficult to comment without knowing the application.

The recursive function is called many times for the same value of level. Can you harvest the results of the previous runs for the same value of level ? ... I guess not, you are probably interested in the side effects rather than the results of a run.

Have you tried using .NET 4.5 (VS 2012) TAP ? Using async / await, Tasks, you could try the Task.ContinueWith to chain recursive calls with the same ( level % CORE_COUNT ). This MAY help in balancing the load on all the Tasks and consequently all the cores. MSDN : Chain multiple tasks.

I hope you do post back on what strategy worked for you.

Upvotes: 0

Related Questions