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

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 2

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 3

The issue you see is because a static synchronized method synchronizes on the Class. So your two Threads spend an extraordinary amount of time fighting over the single lock on Test.class.

For the purposes of this learning exercise, the best way to speed it up would be to create two explicit lock objects. In Test, add

static final Object LOCK1 = new Object();
static final Object LOCK2 = new Object();

and then, in fib1() and fib2(), use a synchronized block on those two objects. e.g.

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

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

Now the first thread only needs to grab LOCK1, with no contention, and the second thread only grabs LOCK2, again, with no contention. (So long as you only have those two threads) This should run only slightly slower than the completely unsynchronized code.

Answer 4

When the fib1 (or fib2) method recurs, it doesn't release the lock. More over, it acquires the lock again (it is faster than initial locking). Good news is that synchronized methods in Java are reentrant.

You are better not to synchronize the recursion itself.

Split your recursive methods into two:

• one recursive non-synchronized method (it should be private as it is not thread-safe);
• one public synchronized method without recursion per se, which calls the second method.

Try to measure such code, you should get 14 seconds, because both threads synchronize on the same lock Test.class.

Answer 5

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 :)

Answer 6

@MartinS is correct that synchronized is not necessary here because you have no shared state. That is, there is no data that you are trying to prevent being accessed concurrently by multiple threads.

However, you are slowing your program down by the addition of the synchronized call. My guess is that without synchronized, you should see two cores spinning at 100% for however long it takes to compute this method. When you add synchronized, whichever thread grabs the lock first gets to spin at 100%. The other one sits there waiting for the lock. When the first thread finishes, the second one gets to go.

You can test this by timing your program (start with smaller values to keep it to a reasonable time). The program should run in approximately half the time without synchronized than it does with.