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.

Pedigree

You're essentially asking why the JVM isn't optimized for an incredibly unrealistic use case. And I think that question pretty much answers itself. – Stypsis

Your Fibonacci calculations are not correct. Fib(0) = 0. There is no reason for applying synchronization to either of these methods. So why are you doing it? – Erasure

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

Cutwater

When make the methods not be synchronized it runs in 7 seconds on my computer. With synchronized methods I expect it to take around 14 seconds since only one thread can work at a time, but I have let it run for minutes without getting a result. – Pedigree

The results are in, with synchronized methods it ran in ~273 seconds. – Pedigree

In reality the difference between having synchronized and not having it will not be that big since the JVM will optimize it away. But still it's better not to add it in the first place. – Cutwater

I'm still very much curious as to what causes the massive slowdown. – Pedigree

I played around with your code and it's mainly the recursive function taking a long time for large inputs. It's kind of ok up to 40ish but then the runtime explodes. – Cutwater

We've already established that it's extremely slow (O(2^n) I believe), but the point is that it took the same argument (47) for both its 7 seconds run and its 273 seconds run. – Pedigree

As you mentioned yourself, only one thread can run at a time. But also when the methods are synchronized, then it adds the overhead of aquiring a lock - or at least of checking whether the current thread has the lock. These operations are not exactly cheap. That is why it takes so much longer. Since 2 threads are running the JVM is not able to optimize away these checks. Try running only one thread and you will see that suddenly its much faster since the JVM can skip the checks since it know that there cannot be a conflict. – Cutwater

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.

Woolgrower

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

Stupefy

Answer 4

@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.

Worcester

Answer 5

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.

Jetliner

Answer 6

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.

Wheen

They don't fight over the lock. One thread gets it and keeps it. Then the other thread runs. You don't lose a lock when you call another method, unless it's one of the Object.wait() methods. – Zacatecas

@Zacatecas Good point. If the recursion were working it's way UP, then at some point the Thread would exit from fib1(), releasing the lock so there could be contention. However, now that I look at it, the recursion is working it's way down, so you may be right - don't see how the first Thread to get started ever loses the lock! Wonder if the JVM is outsmarting itself? – Wheen

There does seem to be a missed optimization opportunity here, since creating two locks does indeed run at nearly full speed. – Zacatecas

@erickson. So my solution works, but we don't know why! Maybe the compiler or JVM can optimize away the locks when there are two, but it isn't smart enough to do so with the original code. – Wheen

Yes, it's like it can handle 1:1 lock-to-thread optimization, but when threads have the potential to acquire one lock, the optimization doesn't kick in. I wonder if the fact that a thread is currently waiting to acquire the lock is what prevents the optimization of the code run by the thread which currently owns the lock. – Zacatecas