Returning the result of whichever method finishes first

Question

Consider a method (let's call it IsPrimeHybrid) which calls at least two methods (let's call them IsPrimeNaive and IsPrimeBySearch) that calculate an identical result using different approaches and the outer method returns the result when any of the inner methods finishes.

The following is my first attempt to write such a method, but I'd like to hear what issues it may have and what's a good way to fix them. (For example, how to implement thread safety in a scenario like this.)

    public static bool IsPrimeHybrid(BigInteger number)
    {
        var result = default(bool);
        var byPureCalc = Task.Run(() => result = IsPrimeNaive(number));
        var bySearchFirst = Task.Run(() => result = IsPrimeBySearch(number));
        Task.WaitAny(byPureCalc, bySearchFirst);
        return result;
    }

For the sake of simplicity, please assume that none of the called methods will consume any common resources, apart from processing power and memory (that is, there will never be two methods that both use file I/O or network I/O, etc).

Answer 1

Tasks can have results, you should take advantage of that, instead of assigning a local variable from a lambda. And WaitAny() returns the index of the Task that finished first. This means you can do something like:

public static bool IsPrimeHybrid(BigInteger number)
{
    var byPureCalc = Task.Run(() => IsPrimeNaive(number));
    var bySearchFirst = Task.Run(() => IsPrimeBySearch(number));
    var tasks = new[] { byPureCalc, bySearchFirst };
    int firstIndex = Task.WaitAny(tasks);
    return tasks[firstIndex].Result;
}

Also, CPU and memory are also resources that you shouldn't waste. So, you may want to cancel the slower Task, after the faster one finished. For that, you can use CancellationToken, which the two computations will periodically check (you can use ThrowIfCancellationRequested () for that):

public static bool IsPrimeHybrid(BigInteger number)
{
    var cts = new CancellationTokenSource();

    var byPureCalc = Task.Run(() => IsPrimeNaive(number, cts.Token));
    var bySearchFirst = Task.Run(() => IsPrimeBySearch(number, cts.Token));
    var tasks = new[] { byPureCalc, bySearchFirst };

    int firstIndex = Task.WaitAny(tasks);

    cts.Cancel();
    return tasks[firstIndex].Result;
}

Answer 2

Edit: since the question is already using Tasks, it is better to use Cancellation tokens instead of ManualResetEvents. Also there is no need to explicitly create a Mutex, in C# we can use lock() on any shared Object for this. I am including source code at the bottom.

It would be quite wasteful if one algorithm took 3 seconds and the other one took 1 minute, you never know with edge cases ...

rather than

 Task.Run(() => result = IsPrimeNaive(number));

you could do (see below about abortHandle)

 Task.Run(() => IsPrimeNaive(abortHandle, number, ref result));

You could Create a ManualResetEvent (which I call abortHandle) with state 'false' (https://stackoverflow.com/questions/5538902/how-to-use-wait-handles-in-c-sharp-threading) and pass it to each of the methods. Implement each method in a way that they check as often as possible if the event has been set externally, if so, simply stop the calculation and return. When a method is finishing it should check again for the abortHandle and if not set then set the result value and the event itself.

Note that there is a tiny chance that 2+ methods would finish at exactly the same time and both check the still reset abortHandle at the same time. If you want to be certain, then you would need to pass an extra Mutex or CriticalSection (see https://stackoverflow.com/questions/800383/what-is-the-difference-between-mutex-and-critical-section) to make sure only one process is setting the result.

Also about thread safety and regarding the input parameters, it is tricky : depends on which types of objects you will be passing, if you are passing primitives like int and string I believe you will be fine (see https://stackoverflow.com/questions/10792603/how-are-strings-passed-in-net), but if you are passing classes, then you might have trouble even if you only read things from it -it will depend how the classes are implemented: they need to be thread safe themselves.

using System;
using System.Threading;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {

        static void IsPrimeNaive(Object lockSync, CancellationToken cancellationToken, int n, ref bool result)
        {
            Random rnd = new Random(System.Convert.ToInt32((Thread.CurrentThread.ManagedThreadId)%Int32.MaxValue));

            for (var i=2; i<n; i++)
            {
                if (cancellationToken.IsCancellationRequested){
                    //if cancellation is set (another thread already finished, or process simply is shutting down, leave)
                    Console.WriteLine("worker: I was too slow, another thread already finished...");
                    return;
                }

                if (n%i == 0)
                {
                    //make sure we have exclusive access to the result
                    lock (lockSync)
                    {
                        result = false;
                    }
                    Console.WriteLine("worker: " + n + " is not prime.");

                    return;
                }

                Thread.Sleep(rnd.Next(3));
            }


            if (!cancellationToken.IsCancellationRequested)
            {   
                //make sure we have exclusive access to the result
                lock (lockSync)
                {
                    result = true;
                }

                Console.WriteLine("worker: " + n + " is indeed a prime.");                     
            }
        }


        static void Main(string[] args)
        {
            Object syncLock = new Object();
            ManualResetEvent abortHandle = new ManualResetEvent(false);
            CancellationTokenSource cancellationSource = new CancellationTokenSource();

            bool result = false;
            Task[] tasks = new Task[3];

            int target = 269;

            //I only have 1 implementation, but there is some  Thread.Sleep inside to make sure they end at different times
            tasks[0] = Task.Run(() => IsPrimeNaive(syncLock, cancellationSource.Token, target, ref result));
            tasks[1] = Task.Run(() => IsPrimeNaive(syncLock, cancellationSource.Token, target, ref result));
            tasks[2] = Task.Run(() => IsPrimeNaive(syncLock, cancellationSource.Token, target, ref result));

            Task.WaitAny(tasks, cancellationSource.Token);
            Console.WriteLine(String.Format("main: {0} is {1} a prime", target, result ? "" : "not"));

            //now cancel any threads still running (because they are checking for 
            cancellationSource.Cancel();


            //expect the other threads to write the 'i am too late' message at some point here

            Console.ReadLine();
        }
    }
}