c# - Parallel Fibonacci Number Calculator

Question

I'm using Task Parallel Library (TPL ) for calculating Fibonacci number. Program is given below:

        public static int Fib(int n)
        {
            if (n <= 1)
            {
                return n;
            }
            Task<int> task = Task.Factory.StartNew<int>(() => Fib(n - 1));
            var p = Fib(n - 2);
            return task.Result + p;
        }

        public static void Main(string[] args)
        {

            Stopwatch watch = new Stopwatch();
            watch.Start();
            Console.WriteLine("Answer: " + Fib(44));
            watch.Stop();
            Console.WriteLine("Time: " + watch.ElapsedMilliseconds);
        }
    }

Unfortunately this program takes a very long time to complete. But serial version of this program ( as given below ) takes less than 30 seconds to calculate 44th Fibonacci number.

 public class FibTester
    {
        public static int Fib(int n)
        {
            if (n <= 1)
            {
                return n;
            }
            var q = Fib(n - 1);
            var p = Fib(n - 2);
            return p + q;
        }

        public static void Main(string[] args)
        {

            Stopwatch watch = new Stopwatch();
            watch.Start();
            Console.WriteLine("Answer: " + Fib(44));
            watch.Stop();
            Console.WriteLine("Time: " + watch.ElapsedMilliseconds);
        }
    }

I think issue in parallel version is, it creates a thread for each Fib(n - 1) request. Is there any way to control number of thread created in TPL?

Answer 1

This is a perfect example of how not to multithread!

You are creating a new task for each iteration of a recursive function. So each task creates a new task, waits for that task to finish and then adds the numbers from the result.

Each thread has two jobs : 1 - to create a new thread, 2 - to add two numbers.

The overhead cost for creating each thread is going to far outweigh the cost of adding two numbers together.

---

To answer your question about limiting the number of threads created, the TPL uses the ThreadPool. You can limit the number of threads using ThreadPool.SetMaxThreads.