Thread-safe List (2) : Vector && SynchronizedList

preface

Thread-safe lists include Vector and SynchronizedList. In this article, we’ll take a look at the structure, methods, and implementation of these two List containers. Thread-safe List (a) : CopyOnWriteArrayList source code parsing.

Vector

Vector source code and ArrayList source code is similar, too specific source code I will not be a detailed analysis, you can see my blog: ArrayList source code learning (a) : initialization, expansion and add, delete, change, check.

The basic structure

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess.Cloneable.java.io.Serializable
{
    protected Object[] elementData;
    protected int elementCount;
    protected int capacityIncrement;
}
Copy the code

Vector extends AbstractList and implements List, RandomAccess, Cloneable, etc.

The three main properties are: elemantData, the array that stores the element data; ElementCount, how many elements the array actually has, because elementData may be longer than the actual number of elements due to operations such as expansion; CapacityIncrement indicates how much capacity is added during each capacity expansion.

Initialize the

// Specify the initial capacity and expansion increment
public Vector(int initialCapacity, int capacityIncrement) {
    super(a);if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}
// Specify the initial capacity
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}
/ / no arguments
public Vector() {
    this(10);
}
// Use set to initialize
public Vector(Collection<? extends E> c) {
    Object[] a = c.toArray();
    elementCount = a.length;
    if (c.getClass() == ArrayList.class) {
        elementData = a;
    } else {
        elementData = Arrays.copyOf(a, elementCount, Object[].class); }}Copy the code

Initialization is also very simple, you can choose whether to specify the initial capacity, expand the increment, or use a collection to initialize.

How to ensure thread safety

Let’s see how it ensures thread safety without further ado. I’ve looked at each of the methods in Vector, and the methods fall into four basic categories:

• The method itself is synchronized:

// The element at a specific index
public synchronized E elementAt(int index) {
    // omit specific code
}  
/ / set methods
public synchronized E set(int index, E element) {
    // omit specific code
}
Copy the code

• The key code is in the synchronized block:

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    modCount++;
    int numNew = a.length;
    if (numNew == 0)
        return false;
    // Enter the synchronized code block
    synchronized (this) {
       // omit specific code}}Copy the code

• The method called is synchronized:

public boolean contains(Object o) {
    return indexOf(o, 0) > =0;
}  
public synchronized int indexOf(Object o, int index) {
    // omit specific code
}
Copy the code

• Synchronized initiates the call:

public synchronized boolean add(E e) {
    modCount++;
    // Call the synchronized method
    add(e, elementData, elementCount);
    return true;
}
private void add(E e, Object[] elementData, int s) {
    // omit specific code
}
Copy the code

No matter how it’s called, it’s the same. All methods eventually have to grab the lock to complete the operation. Only one thread can operate at a time, so naturally these methods are thread-safe.

The Vector methods are fine to use singly, but if you use multiple methods together, for example:

    int lastIndex  = v.size()-1;
    v.remove(lastIndex);
Copy the code

Although individual methods are thread-safe, it’s possible that when you remove, another thread removes the lock first, and this code will throw an exception that the array is out of bounds. So compound operations still have to be locked separately…

Application of Vector: Stack

The other day, I was looking at the classes underneath java.util. I saw the Stack, which is not recommended for a long time, and clicked on it.

public class Stack<E> extends Vector<E> {
    public Stack(){}}Copy the code

The Stack constructor has nothing of its own, so it’s really just a Vector with push, pop, and so on:

public E push(E item) {
    addElement(item);
    return item;
}
public synchronized E pop() {
    E       obj;
    int     len = size();
    obj = peek();
    removeElementAt(len - 1);
    return obj;
}
// Other methods
Copy the code

Remember from the previous section we said int lastIndex = v.size()-1; v.remove(lastIndex); Isn’t this code thread safe? The Stack’s POP encapsulates these two operations in a synchronized function…

Copy a copy of Stack author’s comment:

* <p>A more complete and consistent set of LIFO stack operations is
* provided by the {@link Deque} interface and its implementations, which
* should be used in preference to this class.
Copy the code

That is, the implementation class of the Deque interface is a better choice for the stack. Think about it, sometimes we use a Stack may not have the need for thread safety, the result of the Stack is synchronized every time, how slow ah, and array as the bottom of the Stack, need to expand.

SynchronizedList

create

Let’s see how to create a SynchronizedList:

List<Integer> list = new ArrayList<>();
List<Integer> list1 = Collections.synchronizedList(list);
Copy the code

Pass an instance of the implementation class of the List interface into the constructor.

public static <T> List<T> synchronizedList(List<T> list) {
    return (list instanceof RandomAccess ?
            new SynchronizedRandomAccessList<>(list) :
            new SynchronizedList<>(list));
}
Copy the code

As you can see, different synchronizedLists are created depending on whether the Access interface is implemented.

Basic structure and initialization

SynchronizedList

static class SynchronizedList<E>
    extends SynchronizedCollection<E>
    implements List<E> {
    @java.io.Serial
    private static final long serialVersionUID = -7754090372962971524L;
    // The list passed in
    final List<E> list;
    SynchronizedList(List<E> list) {
        super(list);
        this.list = list;
    }
    SynchronizedList(List<E> list, Object mutex) {
        super(list, mutex);
        this.list = list;
    }
Copy the code

SynchronizedList is a static inner class of the Collections class that, as you can see, inherits the SynchronizedCollection class and implements the List interface. There is only one important attribute: final List

List; To initialize, call this.list = list; To set your own list properties.

It inherits its parent, SynchronizedCollection:

static class SynchronizedCollection<E> implements Collection<E>, Serializable {
    @java.io.Serial
    private static final long serialVersionUID = 3053995032091335093L;

    @SuppressWarnings("serial") // Conditionally serializable
    final Collection<E> c;  // Backing Collection
    @SuppressWarnings("serial") // Conditionally serializable
    final Object mutex;     // Object on which to synchronize

    SynchronizedCollection(Collection<E> c) {
        this.c = Objects.requireNonNull(c);
        mutex = this;
    }

    SynchronizedCollection(Collection<E> c, Object mutex) {
        this.c = Objects.requireNonNull(c);
        this.mutex = Objects.requireNonNull(mutex);
    }
Copy the code

As you can see, there is a mutex variable that acts as a lock, and then if SynchronizedList calls super(list); Mutex = this; ; otherwise, this.mutex = objects.requirenonnull (mutex); , mutex is initialized with the mutex passed in.

Then look at SynchronizedRandomAccessList:

static class SynchronizedRandomAccessList<E>
    extends SynchronizedList<E>
    implements RandomAccess {

    SynchronizedRandomAccessList(List<E> list) {
        super(list);
    }

    SynchronizedRandomAccessList(List<E> list, Object mutex) {
        super(list, mutex);
    }
Copy the code

This class has nothing on its own and relies primarily on its parent, SynchronizedList.

In short, initialization assigns the passed instance of the List interface implementation class to the List property of SynchronizedList, The mutex property (the object of a synchronized lock) is set in the SynchronizedCollection.

How to ensure thread safety

SynchronizedList also implements the List interface methods as follows:

public E get(int index) {
    synchronized (mutex) {returnlist.get(index); } } public Eset(int index, E element) {
    synchronized (mutex) {returnlist.set(index, element); } } publicvoid add(int index, E element){ synchronized (mutex) {list.add(index, element); } } public Eremove(int index) {
    synchronized (mutex) {returnlist.remove(index); } } public intindexOf(Object o) {
    synchronized (mutex) {return list.indexOf(o);}
}
// Other methods
Copy the code

SynchronizedList does this for synchronized methods, placing the action in a synchronized block and invoking its corresponding method using the list passed in at creation time. So SynchronizedList acts as a wrapper class, wrapping the list passed in and the actions in synchronized blocks, so these basic methods are of course thread-safe.

SynchronizedList iterators are not thread-safe, however:

public ListIterator<E> listIterator() {
    return list.listIterator(); // Must be manually synched by user
}
public ListIterator<E> listIterator(int index) {
    return list.listIterator(index); // Must be manually synched by user
}
Copy the code

The iterator created is just the iterator of the original list. It is not thread-safe, so it must be manually synchronized by the user:

Must be manually synched by user
Copy the code

Comparison of several lists

Comparison of insertion performance

The section meets the author’s curiosity O (￣▽￣). The author inserted hundreds of numbers for LinkedList, ArrayList, Vector, CopyOnWriteArrayList and SynchronizedList to look at their time. The following test code is used (the initialization code is omitted) :

The code is very simple, I will post a screenshot, anyway is inserted hundreds of thousands of numbers, statistical time, the result is as follows:

As you can see, CopyOnWriteArrayList is extremely inefficient to insert because it copies the array every time it is inserted.

While the SynchronizedList appears to be slower than the other three because it inserts first, running the other three first is also slower. And the insertion time of the three of them is almost the same.

Three concurrent lists are compared comprehensively

Since I have seen the source code of these three concurrent lists, I compared them according to my own understanding, as shown in the following table:

conclusion

This article discusses the basic structure of Vector and SynchronizedList and how to implement thread-safe implementation from a source perspective. In the last section, we compare several List containers.