Collections.Synchronizedlist and Synchronized

What is the use of Collections.synchronizedList() method? It doesn't seem to synchronize the list

A synchronized list only synchronizes methods of this list.

It means a thread won't be able to modify the list while another thread is currently running a method from this list. The object is locked while processing method.

As an example, Let's say two threads run addAllon your list, with 2 different lists (A=A1,A2,A3 and B=B1,B2,B3) as parameter.

As the method is synchronized, you can be sure those lists won't be merged randomly like A1,B1,A2,A3,B2,B3
You don't decide when a thread handover the process to the other thread. Each method call has to fully run and return before the other one could run. So you can either get A1,A2,A3,B1,B2,B3 or B1,B2,B3,A1,A2,A3 (As we don't know which thread call will run first).

In your first piece of code, both threads runs on the same time. And both try to add an element to the list. You don't have any way to block one thread except the synchronization on the add method so nothing prevent thread 1 from running multiple add operation before handing over the process to thread 2. So your output is perfectly normal.

In your second piece of code (the uncommented one), you clearly state that a thread completely lock the list from the other thread before starting the loop. Hence, you make sure one of your thread will run the full loop before the other one could access the list.

Why do I need to synchronize a list returned by Collections.synchronizedList

The list being synchronized only means that add, remove etc. operations are synchronized and therefore atomic. Iteration however is not and if a thread adds while another is iterating, you could get a ConcurrentModificationException.

By manually synchronizing your iteration block, you ensure that the list is not modified while iterating.

One alternative is to use a CopyOnWriteArrayList which provides an iterator that iterates over the list as it was known when the iteration started, regardless of subsequent modifications. That collection is however not very efficient if you need to change the content of the list very often.

In java, Vector and Collections.synchronizedList are all synchronized, what's the difference?

The main reason for this redundancy is backward compatibility with java code developed for old versions of Java.

If I remember correctly before Java 1.2 Collections were a separate library and were not part of standard JDK/JRE.

At that point the only list like data structure supplied by SDK was Vector. In Collections developers improved that Vector structure in many ways. Particularly, they removed synchronization as it proved to be unnecessary in most of the cases.

Still they wanted to allow an easy way to create a synchronized version of list like collection. Thus they introduced SynchronizedList.

The main difference now between Vector and SynchronizedList is the way you use it. By calling Collections.synchronizedList you create a wrapper around your current List implementation, which means you don't copy data to another data structure and you keep underlying structure intact. For instance, if you want LinkedList structure behind it as opposed to ArrayList.

In case of a Vector, you actually copy the data to the new list like structure Vector. So it's less efficient in case you had a list before, but if you didn't have any data structure before, then you may want to use Vector as it doesn't add method wrapping cost to every method invocation. Another disadvantage of a vector is that you can't keep alternative underlying structure (such as LinkedList), you always use what's been implemented in the Vector itself.

Why not to use synchronized ArrayList even in single thread cases?

If you get weird benchmark results, the first thing you need to do is to verify your benchmark. And your benchmark is flawed for quite a few reasons.

no proper warmup. It is not only the typical JIT warmup, but biased locking is disabled the first few seconds on JVM startup.
insufficient number of iterations
in theory the code could be optimized out due to dead code elimination

So I rewrote your benchmark using JMH: a micro benchmarking framework.

package com;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OperationsPerInvocation;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.TimeUnit;
import java.util.stream.IntStream;

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@State(Scope.Benchmark)
@OperationsPerInvocation(SyncArrayListBenchmark.OPERATIONS_PER_INVOCATION)
public class SyncArrayListBenchmark {

    public static final int OPERATIONS_PER_INVOCATION = 100_000_000;

    @Benchmark
    public int arrayList() {
        List<Integer> l1 = new ArrayList<>(OPERATIONS_PER_INVOCATION);

        IntStream.range(0, OPERATIONS_PER_INVOCATION).sequential().forEach(i -> l1.add(i));

        return l1.size();
    }

    @Benchmark
    public int synchronized_arrayList() {
        List<Integer> l1 = Collections.synchronizedList(new ArrayList<>(OPERATIONS_PER_INVOCATION));

        IntStream.range(0, OPERATIONS_PER_INVOCATION).sequential().forEach(i -> l1.add(i));

        return l1.size();
    }
}

The results of running with JDK 11:

Benchmark                                      Mode  Cnt  Score   Error  Units
SyncArrayListBenchmark.arrayList               avgt   25  4.986 ± 0.100  ns/op
SyncArrayListBenchmark.synchronized_arrayList  avgt   25  6.447 ± 0.104  ns/op

The results of running with JDK 17:

Benchmark                                      Mode  Cnt   Score   Error  Units
SyncArrayListBenchmark.arrayList               avgt   25   6.819 ± 0.300  ns/op
SyncArrayListBenchmark.synchronized_arrayList  avgt   25  10.374 ± 0.427  ns/op

Conclusion:

As you can see, the impact of synchronized ArrayList is significant.

With JDK 11, the average latency is 29% higher even though biased locking is used.

With JDK 17, the impact of synchronized ArrayList is even worse since on average latency the benchmark is 52% higher. With JDK 15, biased locking has been disabled by default and is about to be removed completely. So it is likely to be a contributing factor.

What is 'interesting' is that the synchronized version of JDK 11 is faster than the unsynchronized version of 17. I'm not sure what the cause is; perhaps related to GC changes.

I leave that as an exercise to the reader. JMH has some great profilers. The first thing I would do is to get rid of allocations and thereby excluding the garbage collector.

Synchronizing a synchronized List

do I need to wrap the above statements inside synchronized(list){ ... } to make the operations atomic?

Yes otherwise your List could be modified elsewhere in your code within the time window you call contains and add which could cause race condition issues.

It makes me thing then what is the use of
Collections.synchronizedList?

Collections.synchronizedList makes your List thread safe such that you can modify it concurrently but still all method calls are executed atomically. In the case above you call contains and add that you have to execute atomically because otherwise if elsewhere we call add the result of contains could be out dated which would lead to a race condition issue. The only way to prevent race condition issues is to use a synchronize block on the same object monitor which is list in your case.

Can I use the original list after it has been wrapped by Collections.synchronizedList(...)?

[After calling synchronizedList(...)] I shall never do anything like origList.anyMethodCall(), including: origList.add("blabla"), or origList.remove("blabla"), origList.set(1, "blabla")?

That's correct. Whenever you have multiple threads updating a list, you have to make sure that all threads are dealing with it in a synchronized manner. If one thread is accessing this list through the Collections.synchronizedList(...) wrapper and another thread is not then you can easily have data corruption issues that result in infinite loops or random runtime exceptions.

In general, once you have the synchronized wrapped version of the list I'd set the origList to be null. There is no point in using it anymore. I've written and reviewed a large amount of threaded code and never seen anyone use the original list once it is wrapped. It really feels like premature optimization and a major hack to keep using the original list. If you are really worried about performance then I'd switch to using ConcurrentLinkedQueue or ConcurrentSkipList.

Can I access "backing list" in a way not making structural modifications (origList.contains("blabla"))?

Yes, BUT no threads can make structural modifications. If a thread using the synchronized version adds an entry and then the other thread accesses the non-synchronized version then the same race conditions that can result in an partially synchronized version of the list causing problems.

Is that right, that problem arises ONLY when origList STRUCTURALLY MODIFIED AFTER I obtained iterator from mySyncList and BEFORE I finished using this iterator?

Yes, that should be ok as long as you can guarantee that fact. But again, this feel like a hack. If someone changes the behavior of another thread or if the timing is changed in the future, your code will start breaking without any warning.

For others, the problem with the synchronized list wrapper, as opposed to a fully concurrent collection like the ConcurrentSkipList, is that an iterator is multiple operations. To quote from the javadocs for Collections.synchronizedList(...):

It is imperative that the user manually synchronize on the returned list when iterating over it. [removed sample code] Failure to follow this advice may result in non-deterministic behavior.

The synchronized wrapper protects the underlying list during each method call but all bets are off if you are using an iterator to walk your list at the same time another thread is modifying it because multiple method calls are made. See the sample code in the javadocs for more info.

there are absolutely no problems so far as either thread-3 modifies origList non-structurally (contains()), or thread-3 modifies origList structurally but there is no iteration in mySyncList

As long as both threads are using the synchronized wrapper then yes, there should be no problems.

origList.add("blabla"); // prohibited by Oracle ??? :)))

We aren't talking about "prohibited" which sounds like a violation of the language definition. We are talking about properly reentrant code working with properly synchronized collections. With reentrant code, the devil is in the details.

Correct working with Collections.synchronizedList

Without context it's a bit hard to tell, from the snippets provided neither give you guaranteed atomic operations.

The documentation states:

Returns a synchronized (thread-safe) list backed by the specified
list. In order to guarantee serial access, it is critical that all
access to the backing list is accomplished through the returned list.

So even if you synchronize the method the best you'll get is a guarantee that no two objects are creating the synchronized list at the same time.

You need to wrap the original orderList with Collections.synchronizedList to begin with and return the stored result of that each time.

private static List<CurrencyBox> orderList = Collections.synchronizedList(new ArrayList<CurrencyBox>());
public static List<CurrencyBox> getOrderList() {
    return orderList
}