Parallel factorial with multiple threads

Question

I'm trying to make a function that calculates factorial of a number in parallel, just for testing purposes. Let's say I have 4 cores on my cpu, so I will split the "problem" in 4 chunks.

Saying that, I made this:

public class FactorialPTest
{
    public static object _locker = new object();

    public static long Factorial(int x)
    {
        long result = 1;
        int right = 0;
        int nr = x;
        bool done = false;

        for (int i = 0; i < nr; i += (nr / 4))
        {
            int step = i;

            new Thread(new ThreadStart(() =>
                {
                    right = (step + nr / 4) > nr ? nr : (step + nr / 4);
                    long chunkResult = ChunkFactorial(step + 1, right);

                    lock (_locker)
                    {
                        result *= chunkResult;
                        if (right == nr)
                            done = true;
                    }
                })).Start();
        }

        while(!done)
        { 
            Thread.Sleep(10);
        }

        return result;
    }

    public static long ChunkFactorial(int left, int right)
    {
        //Console.WriteLine("left: {0} ; right: {1}", left, right);
        Console.WriteLine("ChunkFactorial Thread ID :" + Thread.CurrentThread.ManagedThreadId);
        if (left == right)
            return left == 0 ? 1 : left;
        else return right * ChunkFactorial(left, right - 1);
    }

    public static void main()
    {
        Console.WriteLine(Factorial(15));
    }
}

Sometimes is working, sometimes it gives me intermediary results and sometimes a deadlock happens.

Why is this happening? Shouldn't Thread.Sleep(10) pause the main thread until I get the final result ?

Answer 1

You could use one of the Parallel.For overloads with aggregation, it will handle parallelism, partitioning of the workload and aggregation of the results for you. For long type of result, you can only do factorial of 21, if I am not mistaken. It also makes sense to add checked {...} to catch overflows. The code could looks like:

    public long CalculateFactorial(long value)
    {
        var result = 1L;
        var syncRoot = new object();
        checked
        {
            Parallel.For(
                // always 1
                1L,
                // target value
                value,
                // if need more control, add { MaxDegreeOfParallelism = 4}
                new ParallelOptions(),
                // thread local result init
                () => 1L,
                // next value
                (i, state, localState) => localState * i,
                // aggregate local thread results
                localState =>
                {
                    lock (syncRoot)
                    {
                        result *= localState;
                    }
                }
                );                
        }
        return result;
    }

Hope this helps.

Answer 2

I'd suggest looking into the Task Parallel Library. Among other things it will abstract away a lot of the low concerns relating to multi-threading.

You can represent each chunk of work with a task, add to a collection and then wait for them all to finish:

public static long Factorial(int x)
{
    long result = 1;
    int right = 0;
    int nr = x;
    bool done = false;

    var tasks = new List<Task>();

    for (int i = 0; i < nr; i += (nr / 4))
    {
        int step = i;
        tasks.Add(Task.Run(() =>
            {
                right = (step + nr / 4) > nr ? nr : (step + nr / 4);
                long chunkResult = ChunkFactorial(step + 1, right);

                lock (_locker)
                {
                    result *= chunkResult;
                }
            }));
    }

    Task.WaitAll(tasks.ToArray());

    return result;
}

In your original code the last chunk could conceivably complete it's work first and right would equal nr even though the other chunks hadn't been calculated. Also, right was getting shared between all the threads so this could also lead to some unpredictable results, i.e, all threads are trying to use this variable to hold different values at the same time.

Generally you should try to avoid sharing state between threads if possible. The code above could be improved by having each task return it's result and then use these results to calculate the final one:

public static long Factorial(int x)
{
    int nr = x;

    var tasks = new List<Task<long>>();

    for (int i = 0; i < nr; i += (nr / 4))
    {
        int step = i;
        tasks.Add(Task.Run(() =>
            {
                int right = (step + nr / 4) > nr ? nr : (step + nr / 4);
                return ChunkFactorial(step + 1, right);
            }));
    }

    Task.WaitAll(tasks.ToArray());

    return tasks.Select(t => t.Result).Aggregate(((i, next) => i * next));
}