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

I have run the following code to measure the time and performance difference between adding elements to ArrayList vs synchronized version of it, and surprisingly haven't find any significant difference! And by significant I mean the difference doesn't give you any information on which you can prefer one to another!

And my question is that if performance wise they are almost the same then why are they even providing the non-synchronized version in the first place? And why not to use the synchronized version for both multi-thread and single-thread cases?

FYI, as can be seen I didn't warmed up JVM, and also I understand that garbage collection will most probably run in between iterations to free up old arrays, but I don't think that matters since we have it for both cases and also even if you run it for just one iteration you would get the same result!

    int size = 100_000_000;
    long totalTime = 0;
    for(int j=0; j<20; j  ) {
        List<Integer> l1 = new ArrayList<>(size);
        //List<Integer> l1 = Collections.synchronizedList(new ArrayList<>(size));

        long t1 = System.nanoTime();

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

        long t2 = System.nanoTime();
        totalTime  = t2-t1;
    }
    System.out.println("time (ms):"   TimeUnit.NANOSECONDS.toMillis(totalTime/20));

CodePudding user response：

synchronization, when it is actually used, really does cost. However, hotspot is pretty decent at realizing that a mutex isn't actually doing anything useful and eliminating it. That's what you're seeing.

So, why isn't ArrayList just synchronized out of the box / why isn't the advice 'use Vector, not ArrayList'? Many separate reasons:

Most important take-home reason (the rest is just historic peculiarity): Because a synchronized list is mostly useless. See below.
Modern day JVMs are pretty good at eliminating synchronized where it doesn't do anything. Which is why you are having a hard time using simple timing code to see any difference. But that wasn't always the case. ArrayList was introduced in java 1.2. Vector (a synchronized arraylist with a different API) is older than that: 1.0. ArrayList was introduced for 2 separate reasons: Partly to clean up that API, and partly because 'synchronize it!' was slow. NOW it is no longer slow, but Java 1.2 is 23 years old. Rerun your code on java 1.2 if you can find it anywhere and report back to me :)
Everything about Vector is deprecated, obsolete, and non-idiomatic. Part of that is simply 'because'. 23 years ago, the advice 'use ArrayList, not Vector' was correct for a bunch of reasons. Including "Because it is faster" (even if that is no longer true today). Now the reason to use ArrayList and not Vector is mostly: "Because ArrayList is what everybody is familiar with, Vector is not, when in rome act like romans, don't rock the boat for no reason whatsoever". This shows up in all sorts of pragmatic ways: The name 'Vector' is now being reused in the java ecosystem for something completely different (accessing hardware registers that aren't exactly 64-bit, part of Project Panama), for example.

Why is a synchronized list mostly useless?

a non-synchronized ('thread safe') implementation breaks completely; the spec says: Anything can happen. A synchronized ('thread safe') implementation does not break completely; instead, you get 1 of a permutation of options, with no guarantees whatsoever about which ones are more or less likely. That's not really more useful than utter chaos, though! For example, if I write this code:

List a = new Vector<String>();
Thread x = new Thread(() -> a.add("Hello"));
Thread y = new Thread(() -> a.add("World"));
x.start();
y.start();
System.out.println(a);

Then it is legal for this app to print [Hello, World], but it is also legal for this app to print [World, Hello]. There is no way to know, and a VM is free to always return the one, or always return the other, or flip a coin, or make it depend on the phase of the moon. Vector is synchronized and this is still useless to me. Nobody wants to write algorithms that need to deal with a combinatory explosion of permutations!!

With ArrayList, however, which is not 'thread safe', it gets much much worse. There are way more permutations here. The JVM can do any of these without breaking spec:

[Hello, World]
[World, Hello]
[Hello]
[World]
[null, Hello]
[World, World]
[]
[WhatTheHeckReally]
pause, play the macarena over the speaker system, then crash.

Anything goes - the spec says the behaviour is unspecified. In practice, the first 4 are all entirely possible.

Avoiding this mess is good, but the permutations that the synchronized Vector offers is just.. less bad. But still bad, so who cares? You want this code to be 100% reliable: You want code to do the same thing every time (unless I want randomness, but then use java.util.Random which has specs that explicitly spell out how it is random. Threads are free to be non-random, so if you MUST have randomness, you can't use that either).

In order to make stuff reliable, the operation needs to be either done by the object itself (you call ONE method and that is the only interaction your thread does with it), or, you need external locks.

For example, if I want put '1' in a hashmap for a key that isn't htere yet, and increment the number if it is, this code DOES NOT WORK:

Map<String, Integer> myMap = Collections.synchronizedMap(new HashMap<>());

...

String k = ...;
if (myMap.containsKey(k)) myMap.put(k, myMap.get(k)   1);
else myMap.put(k, 1);

Seems fine? Nope, broken:

Thread 1 calls myMap.containsKey and sees the answer is false.
Thread 1 so happens to get pre-empted and freezes right there, after the if, before the put.
Thread 2 runs, and increments for the same key. It, too, finds myMap,containsKey returning false. It therefore runs myMap.put(k, 1).
Thread 1 continues running, and runs.. myMap.put(k, 1)
The map now contains k = 1, even though incrementFor(k) was run twice. Your app is broken.

See? Synchronization? It was completely useless here. What you want is either a lock:

synchronized (something) {
  String k = ...;
  if (myMap.containsKey(k)) myMap.put(k, myMap.get(k)   1);
  else myMap.put(k, 1);
}

and this is completely fine - no matter how had you try running incrementFor(k) simultaneously, it'll dutifully count every invocation, or, better yet, we ask the map to do it for us, to have a map that just has an increment function or similar. HashMap does not. I guess Collections.synchronizedList could return an object that has extra methods, but as the name suggest, that implementation then neccessarily uses locking, and there are more efficient ways to do it.

This task is better done with ConcurrentHashMap, and using the right method:

ConcurrentHashMap<String, Integer> myMap = new ConcurrentHashMap<>();

...

myMap.merge(k, 1, (a, b) -> a   b);

That does it in one call. (merge is the same as .put(k, 1) if k isn't in the map already, but if it is, it is the same as .put(k, RESULT) where RESULT is the result of running a b where a is 'what was in the map' and 'b' is the value you are trying to add (So, 1, in this case).

A non-synchronized list can still mess up a single call, but if your 'job' involves more than one call, a synchronized one in the sense of e.g. Collections.synchronizedMap or j.u.Vector cannot safely do this.

And that's, in the end, why the advice is to not use synchronized stuff - even though it is probably not really a performance issue, there is almost no point in doing it. If you actually have concurrency needs it is unlikely that synchronizing the thing internally is going to help you, and in the case where it does, it's somewhat likely that some more specific type in the java.util.concurrent package can do it faster (because when concurrency IS happening, synchronized most definitely is not free at all).

CodePudding user response：

If you get weird results in a benchmark, 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, it is 29% slower even though biased locking is used.

With JDK 15, biased locking has been disabled by default and is about to be removed completely. The impact of synchronized ArrayList is even worse since on average the benchmark is 52% slower.

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.