Speculative execution using the TPL

Question

I have a List<Task<bool>> that I want to enumerate in parallel finding the first task to complete with a result of true and not waiting for or observe exceptions on any of the other tasks still pending.

var tasks = new List<Task<bool>>
{ 
    Task.Delay(2000).ContinueWith(x => false), 
    Task.Delay(0).ContinueWith(x => true), 
};

I have tried to use PLINQ to do something like:

var task = tasks.AsParallel().FirstOrDefault(t => t.Result);

Which executes in parallel, but doesn't return as soon as it finds a satisfying result. because accessing the Result property is blocking. In order for this to work using PLINQ, I'd have to write this aweful statement:

var cts = new CancellationTokenSource();
var task = tasks.AsParallel()
    .FirstOrDefault(t =>
    {
        try 
        { 
            t.Wait(cts.Token);
            if (t.Result)
            {
                cts.Cancel();
            }

            return t.Result;
        } 
        catch (OperationCanceledException) 
        { 
            return false;
        }
    } );

I've written up an extension method that yields tasks as they complete like so.

public static class Exts
{
    public static IEnumerable<Task<T>> InCompletionOrder<T>(this IEnumerable<Task<T>> source)
    {
        var tasks = source.ToList();
        while (tasks.Any())
        {
            var t = Task.WhenAny(tasks);
            yield return t.Result;
            tasks.Remove(t.Result);
        }
    }
}

// and run like so
var task = tasks.InCompletionOrder().FirstOrDefault(t => t.Result);

But it feels like this is something common enough that there is a better way. Suggestions?

Compost

Answer 1

Maybe something like this?

var tcs = new TaskCompletionSource<Task<bool>>();

foreach (var task in tasks)
{
    task.ContinueWith((t, state) =>
    {
        if (t.Result)
        {
            ((TaskCompletionSource<Task<bool>>)state).TrySetResult(t);
        }
    },
        tcs,
        TaskContinuationOptions.OnlyOnRanToCompletion |
        TaskContinuationOptions.ExecuteSynchronously);
}

var firstTaskToComplete = tcs.Task;

Vertebral

I think you should use TrySetResult(), to avoid uncaught exceptions (although they wouldn't actually affect the program on .Net 4.5). And possibly also cancel all the outstanding continuations after you set the result. – Enchiridion

I don't know the OP's requirements, so I don't know if the tasks should be cancelled or not. But regarding TrySetResult you have a point, thanks! Fixed. – Vertebral

I didn't mean canceling the Tasks in the collection, I meant just the continuations. After you set the result, there is no need to execute the rest of the continuation (but it won't be a big performance hit either). – Enchiridion

I like the concept here, however, I also need to know if all tasks have completed unsuccessfully. I've found a way to do that via Task.WaitAny(Task.WhenAll(tasks), tcs.Task) == 1; Thanks for the answer. – Compost

Answer 2

Perhaps you could try the Rx.Net library. Its very good for in effect providing Linq to Work.

Try this snippet in LinqPad after you reference the Microsoft Rx.Net assemblies.

using System
using System.Linq
using System.Reactive.Concurrency
using System.Reactive.Linq
using System.Reactive.Threading.Tasks
using System.Threading.Tasks

void Main()
{
    var tasks = new List<Task<bool>>
    { 
        Task.Delay(2000).ContinueWith(x => false), 
        Task.Delay(0).ContinueWith(x => true), 
    };

    var observable = (from t in tasks.ToObservable()
                      //Convert task to an observable
                      let o = t.ToObservable()
                      //SelectMany
                      from x in o
                      select x);


    var foo = observable
                .SubscribeOn(Scheduler.Default) //Run the tasks on the threadpool
                .ToList()
                .First();

    Console.WriteLine(foo);
}

Capreolate

This code will actually execute both tasks...if you want to get just the first result to return...Remote the .ToList() – Capreolate

Also I've worked with it some in the past, I'm not really looking at adding rx into my project. I ran your code just because I was curious, and after removing ToList and changing First (which is obsolete) to FirstOrDefaultAsync, I was getting the correct behavior I wanted. Thanks for the complete copy/paste-able snippet though +1 – Compost

Answer 3

First, I don't understand why are you trying to use PLINQ here. Enumerating a list of Tasks shouldn't take long, so I don't think you're going to gain anything from parallelizing it.

Now, to get the first Task that already completed with true, you can use the (non-blocking) IsCompleted property:

var task = tasks.FirstOrDefault(t => t.IsCompleted && t.Result);

If you wanted to get a collection of Tasks, ordered by their completion, have a look at Stephen Toub's article Processing tasks as they complete. If you want to list those that return true first, you would need to modify that code. If you don't want to modify it, you can use a version of this approach from Stephen Cleary's AsyncEx library.

---

Also, in the specific case in your question, you could “fix” your code by adding .WithMergeOptions(ParallelMergeOptions.NotBuffered) to the PLINQ query. But doing so still wouldn't work most of the time and can waste threads a lot even when it does. That's because PLINQ uses a constant number of threads and partitioning and using Result would block those threads most of the time.

Enchiridion

If you just enumerate the list of tasks and check IsCompleted, then FirstOrDefault will return null if the tasks have not completed yet instead of waiting until the first task has completed. – Vertebral

@Vertebral Right, I was assuming that at least one Task already completed, but actually there is no way to know that. I guess it might still be useful in some situations. – Enchiridion

@Vertebral is correct here, All the tasks I'm checking have time remaining until completion in my situation. However, that Toub article was spot on. +1 for that alone. I scoured the web looking before posting, but that gem makes me embarrassed for my googling skills. Cheers – Compost

And you're correct that it doesn't make sense to process the tasks in parallel – Compost