Using 2 threads to compute the nth Fibonacci number (with memoization)

Don't parallelize serial problems

In theory, I'd expect using 2 threads on a tree-recursive algorithm to work faster than a single-threaded implementation, however it seems this is clearly not the case. What am I missing here?

You are duplicating work. The problem is that generating the Fibonacci sequence is not a tree. It's a vector. This is because you don't actually care what the children are. All you care about is what the current node's two children are. But you need one of those children to generate the other. I.e. the n - 2 subtree is actually part of the n - 1 subtree.

So you take an essentially serial operation and you try to split it over two processes. Unsurprisingly, it takes longer as it tries to synchronize the processes.

Turning it into parallel problems

Is all hope lost? No. If you look at solutions to Project Euler #2: Even Fibonacci Numbers, you will find that

$$F_n = 4 \cdot F_{n-3} + F_{n-6}$$

For example, the 7th Fibonacci number:

$$F_7 = 4 \cdot F_4 + F_1$$ $$F_7 = 4 \cdot 2 + 0 = 8$$

How does that help us? Think about the 8th, 9th, and 10th Fibonacci numbers:

$$F_8 = 4 \cdot F_5 + F_2$$ $$F_9 = 4 \cdot F_6 + F_3$$ $$F_{10} = 4 \cdot F_7 + F_4$$

Notice anything? No overlap. The 7th and 10th overlap, but 7-9 don't and 8-10 don't. This will continue. In general, now you have three serial sequences. So you can parallel process into three threads.

You may also be able to come up with similar equations for two threads or more than three threads. But I knew about this problem and there's already the mathematical derivation available inside the link.

Another issue is that you are searching from n down. You might find it easier to generate the sequences from 1, 2, and 3 up with n as an upper bound. You can do that iteratively rather than recursively, which should avoid the heavy stack usage.

This will only be faster if the system can really parallelize work. If you were limited to a single core and can now use three, you gain. If you're just switching between the three threads on the same processor, it will probably still be slower than the serial solution.

Calculate just one element

If all you want to do is generate the nth Fibonacci number, there is a formula to do that directly:

static int fib(int n) {
    double sqrt_5 = Math.sqrt(5);
    double phi = (1 + sqrt_5) / 2;

    double fib_n = Math.pow(phi, n) / sqrt_5;
    return (int) (fib_n + 0.5);
}

That would be the fastest solution for a single value without precalculating the numbers. Of course, that won't parallel well.