CODEWITHSUNDEEP
c#recursiontask-parallel-library
Tamim Al Manaseer
Tamim Al Manaseer

Reputation: 3724

Recursion with Tasks and WaitAll

Basically here is the problem, I have a function "GetAllCandidates" that accepts a list, calculates something, alters the parameters and calls itself using Task.Factory.StartNew to calculate all possible outputs with different morphs of the original array.

    private void GetAllCandidates(List<int> values)
    {
        Interlocked.Increment(ref _count);

        for (var i = values.Count - 1; i >= 1; i --)
        {
           //Do work and calculations

           Task.Factory.StartNew(
                           () => GetAllCandidatePowers(newPowers)
           );
        }
    }

I need to fully utilize the cores on my CPU and wait for all tasks to finish, and here is the problem.

any hints, on how to proceed with such a problem?

Upvotes: 2

Views: 5971

Answers (3)

Douglas
Douglas

Reputation: 54877

You can use the Task.WhenAll method (introduced in .NET 4.5) to unravel the parallelism at each step of your recursion:

private Task GetAllCandidates(List<int> values)
{
    Interlocked.Increment(ref _count);

    List<Task> tasks = new List<Task>();

    for (var i = values.Count - 1; i >= 1; i--)
    {
        //Do work and calculations

        Task task = Task.Factory.StartNew(() => GetAllCandidatePowers(newPowers));
        tasks.Add(task);
    }

    return Task.WhenAll(tasks);
}

This way, you would only need to wait on the outermost call of your GetAllCandidates method within your application (if at all), blocking just one thread.

Edit: Equivalent formulation of for loop using LINQ:

private Task GetAllCandidates(List<int> values)
{
    Interlocked.Increment(ref _count);

    var tasks = Enumerable.Range(1, values.Count - 1).Reverse().Select(i =>
    {
        //Do work and calculations

        return Task.Factory.StartNew(() => GetAllCandidatePowers(newPowers));
    });

    return Task.WhenAll(tasks);
}

Upvotes: 4

Johnathon Sullinger
Johnathon Sullinger

Reputation: 7414

It sounds like your goal is to increase the performance of the entire process. Assuming that the order in which the for-loop is executed is not important, you can use TPL. It would get you a faster result I think.

private void GetAllCandidates(List<int> values)
{
    Interlocked.Increment(ref _count);

        Parallel.ForEach(test, item =>
        {
            //Do work and calculations
            var t = new Task().Run(GetAllCandidatePowers(newPowers));
            // Although if you are waiting here, you might as well just run it synchronously.
            t.Wait(); 
       );
    }
}

Update: Use PLINQ to maintain order

I have provided an example that uses PLINQ to run the operations in parallel and then return the result set in their original order. Unless these operations are expensive, or there are a large number of them, you might not find a big performance increase. If you are doing some heavy loaded work, or have a large quantity of items to run through, then this should help you out.

private void GetAllCandidates(List<int> values)
{
    Interlocked.Increment(ref _count);

    values.AsParallel().AsOrdered().ForAll((item) => 
    {
        // Do stuff


        GetAllCandidates(newPowers);
    }
}

Upvotes: 1

usr
usr

Reputation: 171178

Make GetAllCandidates keep a function-local list of tasks started. At the end of the function wait for them. This still provides parallelism as long as you start more than 1 task.

Upvotes: 2

Related Questions