Java - Synchronized methods causes program to slow down massively

Question

I'm trying to learn about threads and synchronization. I made this test program:

public class Test {
    static List<Thread> al = new ArrayList<>();

    public static void main(String[] args) throws IOException, InterruptedException {
        long startTime = System.currentTimeMillis();

        al.add(new Thread(() -> fib1(47)));
        al.add(new Thread(() -> fib2(47)));

        for (Thread t : al)
            t.start();
        for (Thread t: al)
            t.join();

        long totalTime = System.currentTimeMillis() - startTime;
        System.out.println(totalTime);
    }

    public static synchronized int fib1(int x) {
        return x <= 2 ? 1 : fib1(x-2) + fib1(x-1);
    }

    public static synchronized int fib2(int x) {
        return x <= 2 ? 1 : fib2(x-2) + fib2(x-1);
    }
}

This program takes around 273 seconds to finish, but if I remove both of the synchronized it runs in 7 seconds instead. What causes this massive difference?

EDIT: I'm aware that I'm using a terribly slow algorithm for calculating fibonacci numbers. And I'm also aware that the threads don't share resources and thus the methods don't need to be synchronized. However, this is just a test program where I'm trying to figure out how synchronized works and I choose a slow algorithm on purpose so I could measure time taken in milliseconds.

Answer 1

Your program does not get stuck - it's just terribly slow. This is due to two reasons:

1. Algorithm Complexity

As others and youself have mentioned, the way you compute the Fibonacci numbers is really slow because it computes the same values over and over again. Using a smaller input will bring down the runtime to a reasonable value. But this is not what your question is about.

2. Synchronized

This slows down your program in 2 ways:

First of all, making the methods synchronized is not necessary since they do not modify anything outside of the method itself. In fact it prevents both threads from running at the same time as the methods are static therefore preventing two thread from being in either of them at the same time. So your code is effectively using only one thread, not two.

Also synchronized adds a significant overhead to the methods since it requires acquiring a lock when entering the method - or at least checking whether the current thread already possesses the lock. These operations are quite expensive and they have to be done every single time one of the methods is entered. Since - due to the recursion - this happens a lot, it has an extreme impact on the program performance.

Interestingly the performance is much better when you run it with just a single thread - even with the methods being synchronized. The reason is the runtime optimizations done by the JVM. If you are using just one thread, the JVM can optimize the synchronized checks away since there cannot be a conflict. This reduces the runtime significantly - but not exactly to the value that it would have without synchronized due to starting with 'cold code' and some remaining runtime checks. When running with 2 threads on the other hand, the JVM cannot do this optimization, therefore leaving the expensive synchronized operations that cause the code to be so terribly slow.

Btw: fib1 and fib2 are identical, delete one of them

Answer 2

When you put static synchronized on a method that means that, in order for a thread to execute that method, it first has to acquire the lock for the class (which here is Test). The two static fib methods use the same lock. One thread gets the lock, executes the fib method, and releases the lock, then the other thread gets to execute the method. Which thread gets the lock first is up to the OS.

It was already mentioned the locks are re-entrant and there's no problem with calling a synchronized method recursively. The thread holds the lock from the time it first calls the fib method, that call doesn't complete until all the recursive calls have completed, so the method runs to completion before the thread releases the lock.

The main thread isn't doing anything but waiting, and only one of the threads calling a fib method can run at a time. It does make sense that removing the synchronized modifier would speed up things, without locking the two threads can run concurrently, possibly using different processors.

The methods do not modify any shared state so there's no reason to synchronize them. Even if they did need to be synchronized there would still be no reason to have two separate fib methods here, because in any case invoking either the fib1 or fib2 method requires acquiring the same lock.

Using synchronized without static means that the object instance, not the class, is used as the lock. The reason that all the synchronized methods use the same lock is that the point is to protect shared state, an object might have various methods that modify the object's internal state, and to protect that state from concurrent modifications no more than one thread should be executing any one of these methods at a time.

Answer 3

Your program is not deadlocked, and it also isn't appreciably slower because of unnecessary synchronization. Your program appears "stuck" because of the branching factor of your recursive function.

Branching Factor of Recursion

When N >= 4, you recurse twice. In other words, on average, your recursion has a branching factor of two, meaning if you are computing the N-th Fibonacci number recursively, you will call your function about 2^N times. 2^47 is a HUGE number (like, in the hundreds of trillions). As others have suggested, you can cut this number WAY down by saving intermediate results and returning them instead of recomputing them.

More on synchronization

Acquiring locks is expensive. However, in Java, if a thread has a lock and re-enters the same synchronized block that it already owns the lock for, it doesn't have to reacquire the lock. Since each thread already owns the respective lock for each function they enter, they only have to acquire one lock apiece for the duration of your program. The cost of acquiring one lock is weensy compared to recursing hundreds of trillions of times :)