This is not a good way to do a Fibonacci sequence :-)
Your first thread starts two others, each of those starts two others and so forth. So when n > 16, you may end up with a very large number of threads (in the thousands) (a).
Unless your CPU has way more cores than mine, you'll be wasting your time running thousands of threads for a CPU-bound task like this. For purely CPU bound tasks, you're better off having as many threads as there are physical execution engines (cores or CPUs) available to you. Obviously that changes where you're not purely CPU bound.
If you want an efficient recursive (non-threaded) Fibonacci calculator, you should use something like (pseudo-code):
def fib(n, n ranges from 1 to infinity):
if n is 1 or 2:
return 1
return fib(n-1) + fib(n-2)
Fibonacci isn't even really that good for non-threaded recursion since the problem doesn't reduce very fast. By that, I mean calculating fib(1000) will use 1000 stack frames. Compare this with a recursive binary tree search where only ten stack frames are needed. That's because the former only removes 1/1000 of the search space for each stack frame while the latter removes one half of the remaining search space.
The best way to do Fibonacci is with iteration:
def fib(n, n ranges from 1 to infinity):
if n is 1 or 2:
return 1
last2 = 1, last1 = 1
for i ranges from 3 to n:
last0 = last2 + last1
last2 = last1
last1 = last0
return last0
Of course, if you want a blindingly fast Fibonacci generator, you write a program to generate all the ones you can store (in, for example, a long value) and write out a C structure to contain them. Then incorporate that output into your C program and your runtime "calculations" will blow any other method out of the water. This is your standard "trade off space for time" optimisation method:
long fib (size_t n) {
static long fibs[] = {0, 1, 1, 2, 3, 5, 8, 13, ...};
if (n > sizeof(fibs) / sizeof(*fibs))
return -1;
return fibs[n];
}
These guidelines apply to most situations where the search space doesn't reduce that fast (not just Fibonacci).
(a) Originally, I thought this would be 216 but, as the following program shows (and thanks to Nemo for setting me straight), it's not quite that bad - I didn't take into account the reducing nature of the spawned threads as you approached fib(0):
#include <stdio.h>
static count = 0;
static void fib(int n) {
if (n <= 2) return;
count++; fib(n-1);
count++; fib(n-2);
}
int main (int argc, char *argv[]) {
fib (atoi (argv[1]));
printf ("%d\n", count);
return 0;
}
This is equivalent to the code you have, but it simply increments a counter for each spawned thread rather than actually spawning them. The number of threads for various input values are:
N Threads
--- ---------
1 0
2 0
3 2
4 4
5 8
6 14
:
14
15 1,218
16 1,972
:
20 13,528
:
26 242,784
:
32 4,356,616
Now note that, while I said it wasn't as bad, I didn't say it was good :-) Even two thousand threads is a fair load on a system with each having their own kernel structures and stacks. And you can see that, while the increases start small, they quickly accelerate to the point where they're unmanageable. And it's not like the 32nd number is large - it's only a smidgeon over two million.
So the bottom line still stands: use recursion where it makes sense (where you can reduce the search space relatively quickly so as to not run out of stack space), and use threds where it makes sense (where you don't end up running so many that you overload the resources of the operating system).
