Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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

share|improve this question
1  
The code looks ok, but I am a little confused by your objectives. If your intention is to find which method is faster, maybe a classic benchmark (lots of iterations, not competition for resources) would be better, specially if the difference is small (also, you will learn not only which method is faster but also how much faster it is) –  SJuan76 Apr 10 at 10:28
    
@SJuan76 I understand what you're saying, but I'd like to be able to also use this pattern in a wider scope than what I've shown here. There may be cases (other than primality tests) where the input isn't one-dimensional and possibly not easily reproducible or there may be external factors (such as server load, noise, etc) playing a role in the performance of one or more of the candidate methods. –  Theodoros Chatzigiannakis Apr 10 at 10:42
add comment

2 Answers 2

up vote 11 down vote accepted

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;
}
share|improve this answer
    
Yeah, I somehow missed the fact that WaitAny returned a value! This indeed means there's no need for an outer variable and any safety issues that could have arisen from that. Thank you, this addresses my most critical concern! –  Theodoros Chatzigiannakis Apr 10 at 13:11
add comment

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' (http://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 http://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 http://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();
        }
    }
}
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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