Synchronization is the heaviest operation in Java. It can take thousands of CPU cycles to lock on an object and pretty much disables aggresive out-of-order execution of instructions, as the JVM has to guarantee X happened before Y.

There are however optimisations in the HotSpot JVM that can replace a 'monitor enter' with a busy-loop, or even verifying that locks are never accessed concurrently, in which case the sync can be optimized away. Once the JVM determines that a lock is contented, it will rollback these optimisations.

Having said all that, the performance overhead can be negligible, depending on how much work you actually perform within the synchronized block. So as always, it depends. Benchmark it in a realworld scenario and draw conclusions from that.

I think it's simply key to get a lot done in your sync-block, so that no matter how big the overhead, it becomes negligible.

and then there is this thing called context:

In my case, I have two solutions to my problem. One is to allow the threads to modify the lists, and one is to defer the changes by saving them and execute them single-threaded after everything. I think it will be faster to use synchronization since I will not be doing many changes per update, like 80% of the time it will be 0 changes but sometimes several in a single frame. The chance of two lists being modified in the same frame is extremely low, but if synchronization is as expensive as you say...

Concerning how much work I actually do in each change, I realized that I might have to keep the lists sorted, since the order of the objects in them may have an effect if the scripts used in the game are order-dependent (I need determinism for network synchronization and replaying). I might therefore have to switch from ArrayList to some kind of sorted list or set, which would of course take more time to change...

In the end, I guess only an actual benchmark would be able to give me an answer. Thanks for all the quick responses!