1

Here is a method that does a DFS search and returns a list of all items given a top level item id. How could I modify this to take advantage of parallel processing? Currently, the call to get the sub items is made one by one for each item in the stack. It would be nice if I could get the sub items for multiple items in the stack at the same time, and populate my return list faster. How could I do this (either using async/await or TPL, or anything else) in a thread safe manner?

private async Task<IList<Item>> GetItemsAsync(string topItemId)
{
    var items = new List<Item>();   
    var topItem = await GetItemAsync(topItemId);

    Stack<Item> stack = new Stack<Item>();           
    stack.Push(topItem);
    while (stack.Count > 0)
    {
        var item = stack.Pop();
        items.Add(item);                   

        var subItems = await GetSubItemsAsync(item.SubId);

        foreach (var subItem in subItems)
        {
            stack.Push(subItem);
        }
    }

    return items;   
}

I was thinking of something along these lines, but it's not coming together:

var tasks = stack.Select(async item =>
{
    items.Add(item);           
    var subItems = await GetSubItemsAsync(item.SubId);

    foreach (var subItem in subItems)
    {
        stack.Push(subItem);
    }   
}).ToList();

if (tasks.Any())
    await Task.WhenAll(tasks);

The language I'm using is C#.

  • Between distributing the work (I don't see a way to do this without synchronizing access to the stack or stacks at least occasionally), synchronizing whatever mechanism you use to not re-visit nodes (e.g. flag in the nodes or external set data structure), and the extra work to accumulate the results from several threads, this doesn't seem like a good candidate for parallelism. Why do you want to parallelize this part? – user7043 Aug 21 '14 at 19:41
  • @delnan this is the part (the gathering of all the items in the tree) that takes up hours, when there are thousands/millions of items. I am not tied to any particular strategy. Anything to make this faster would help. – Prabhu Aug 21 '14 at 19:57
  • So it's GetSubItemsAsync that takes ages? You could start each of those tasks as soon as you have the right SubId to start it, and when any of them finishes, process the newly discovered item (i.e. start but don't await the sub-item-fetching tasks for that item too). Naturally, how much this can help depends on the nature of GetSubItemsAsync (is it CPU-bound? IO-bound?). Still, if your graph has a diameter of n, there's no way around a total minimum latency of n * latencyOfGetSubItems. – user7043 Aug 21 '14 at 20:07
  • Yes each call to GetSubItemsAsync could take up to 2 seconds to return, so ideally I would like to make multiple GetSubItemsAsync calls simultaneously. – Prabhu Aug 21 '14 at 20:18
1

It seems to me that, as you retrieve the list of subitems, rather than pushing them on a stack you should process each subitem asynchronously by processing each on its own Task. Only when all Tasks have completed (Task.WhenAll) do you take their results, push them on the stack and return.

Obviously you don't want a million Tasks so perhaps you only do this to a maximum fan out degree and fall back on the stack-based iterative approach beyond that.

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.