Performing a Depth First Search iteratively using async/parallel processing?

Question

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#.

Answer 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.