Hello, I am a pig program ape, usually like to toss technology, raise “pig”, will not regularly share some technical articles. Pay attention to me, do not get lost ~

Understand fail-fast and Fail-safe mechanisms

What is fail-fast?

The fail-fast mechanism is a bug mechanism in Java collections. When iterating over a collection object, Concurrent Modification Exceptions are thrown if changes (additions, deletions) are made to the structure of the collection object during the iteration.

Therefore, in a multi-threaded environment, it is easy to throw Concurrent Modification Exceptions, such as thread 2 modifying (adding, deleting) the collection while thread 1 is traversing it. But wouldn’t a single thread throw it? Obviously, a similar situation can occur with a single thread, such as the main thread modifying the collection (adding, deleting, modifying) over time, and the main thread throws a Concurrent Modification Exception.

The principle of fail – fast

Let’s look at a couple of questions and think about them.

Which of the following situations do you think will occur when Fail-fast throws concurrent modification exceptions?

Q1:

List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
Iterator<String> iter = list.iterator();
while (iter.hasNext()) {
    String tmp = iter.next();
    System.out.println(tmp);
    if (tmp.equals("1")) {
        list.remove("1"); }}Copy the code

Q2:

List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
Iterator<String> iter = list.iterator();
while (iter.hasNext()) {
    String tmp = iter.next();
    System.out.println(tmp);
    if (tmp.equals("3")) {
        list.remove("3"); }}Copy the code

Q3:

List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
Iterator<String> iter = list.iterator();
while (iter.hasNext()) {
    String tmp = iter.next();
    System.out.println(tmp);
    if (tmp.equals("4")) {
        list.remove("4"); }}Copy the code

Q4:

List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
for (String i : list) {
    if ("1".equals(i)) {
        list.remove("1"); }}Copy the code

Q5:

List<String> list = Arrays.asList("1"."2"."3"."4");
for (String i : list) {
    if ("1".equals(i)) {
        list.remove("1"); }}Copy the code

Q6:

List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
Iterator<String> iter = list.iterator();
while (iter.hasNext()) {
    String tmp = iter.next();
    System.out.println(tmp);
    if (tmp.equals("1")) {
        iter.remove("1"); }}Copy the code

The answers are: 1, 3, 4.

Did you get that right?

Since to speak of principle, then to the source code!

Load up on the source of ArrayList!

Because we are in traversal of the collection of changes will occur fail-fast, traversal of the collection is generally used iterator, that first look at the source of the iterator ~

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    public boolean hasNext(a) {
        returncursor ! = size; }@SuppressWarnings("unchecked")
    public E next(a) {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove(a) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw newConcurrentModificationException(); }}final void checkForComodification(a) {
        if(modCount ! = expectedModCount)throw newConcurrentModificationException(); }}Copy the code

As you can see, the culprit is the checkForComodification method, which is used in modCount! = expectedModCount throws the damn exception, and checkForComodification is the first sentence in the next method, so the traversal collection can throw concurrent modification exceptions.

Also, after an iterator is created, the initial value of the expectedModCount is modCount. Modifying the set only changes the modCount, and the expectedModCount is only changed to modCount in the remove method of the iterator. More on iterator methods later.

Take a look at some of the methods of ArrayList!

Remove:

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true; }}else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true; }}return false;
}


private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}
Copy the code

ModCount ++ is configured in fastRemove, so modCount is not equal to expectedModCount, and the concurrent modification exception is thrown.

Add:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
Copy the code

So mode count ++ in the recapacity Internal method.

Set:

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
Copy the code

As you can see, the set method does not apply modCount++, so modifying an element of the collection does not fail-fast.

After analyzing a wave of source code, to look at Q1, Q2 and Q3, it is found that the remove method of list is adjusted, so modCount must not be equal to expectedModCount, so why does Q2 not fail fast occur? In fact, this situation is also mentioned in the Alibaba Java development manual (PDF can be paid attention to my public account “pig program ape” for free, reply to Alibaba Java development manual) :

The surprising counterexample is that “1” does not raise an exception, but “2” does! Why? In fact, this situation is similar to Q2, is the penultimate element of remove, however, no exception is thrown.

The iterator class has these two variables:

int cursor;       // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
Copy the code

Cursor is the index of the next variable to be returned, and lastRet is the index of the last variable to be returned.

public boolean hasNext(a) {
    returncursor ! = size; }Copy the code

The hasNext method tells us that there is a next element in the set only if the subscript of the next variable is not equal to size.

But!!!!! For Q2, remove the element “3” and change the size to 3, while the cursor is also 3. When we go to hasNext, we find that the cursor and size are equal, and the traversal will exit, and the “4” will not be traversed at all. Let’s verify the results:

Q2 does not throw an exception because it exits from the remove method before it reaches the next method

The Q3? Q3 is to delete “4”, that is, the last element, it is logical to delete the last element is not quit? Can’t get next next method?

Wrong, delete “4” did not directly exit oh! If you think about it, after remove, the size changes to 3, but the cursor is 4. If you go to hasNext, you find that the cursor is 4! =3, it will enter the loop again, so the result is predictable, go to the next method to end its evil life……

Take a look at the results:

Q4 does not differ from the previous three, except that the enhanced for loop will also raise an exception. Why?

Start by compiling the following code with Javac:

import java.util.ArrayList;
import java.util.List;

public class Main{
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        for (String i : list) {
            if ("1".equals(i)) {
                list.remove("1"); }}}}Copy the code

Get the.class file:

//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by Fernflower decompiler)
//

import java.util.ArrayList;
import java.util.Iterator;

public class Main {
    public Main(a) {}public static void main(String[] var0) {
        ArrayList var1 = new ArrayList();
        var1.add("1");
        var1.add("2");
        var1.add("3");
        var1.add("4");
        Iterator var2 = var1.iterator();

        while(var2.hasNext()) {
            String var3 = (String)var2.next();
            if ("1".equals(var3)) {
                var1.remove("1"); }}}}Copy the code

The discovery is almost identical to Q1, so iterating through a collection using an enhanced for loop is essentially the same as iterating through it.

Looking at Q5, we see no difference except that we use the array.aslist () method to generate the collection.

First look at the results:

Yi? You lied to me. Isn’t that an anomaly?

… Look closely, throw UnsupportedOperationException, not today’s leading role, concurrent modification abnormalities.

Why is that?

Look at the array. asList source code to know:

AbstractList = java.util.ArrayList = java.util.ArrayList = java.util.

public void add(int index, E element) {
    throw new UnsupportedOperationException();
}

public E remove(int index) {
    throw new UnsupportedOperationException();
}

Copy the code

So, returning or asList generated ArrayList didn’t rewrite these methods, lead to call these methods will throw an UnsupportedOperationException.

Knock on the blackboard!! We can’t add, delete, or modify the array generated by asList, and we can’t add, delete, or modify the array generated by asList. Avoid this pit during development.

Q6 is the correct operation. Because the iterator’s remove method resets the expectedModCount to modCount, there is no discrepancy.

How to avoid fail-Fast throwing exceptions?

1. If you must modify the collection while iterating, it is recommended to use iterator remove instead of collection remove. (Honestly abide by Alibaba Java development specifications……)

2. If the environment is concurrent, lock the Iterator. Also can directly use the Collections. SynchronizedList.

3.CopyOnWriteArrayList (using fail-Safe)

What is fail-safe?

ArrayList uses the Fail-fast mechanism, of course, because it enhances data security. But in some scenarios where we might want to avoid exceptions thrown by fail-Fast, we would replace ArrayList with CopyOnWriteArrayList using Fail-Safe.

Using a collection of security failure mechanism container, there is no design on the realization of the Iterator throw ConcurrentModificationException code, so as to avoid the fail – fast.

Finally, a typical fail-safe container is introduced: CopyOnWriteArrayList~

Copy on write means that when we add elements to a container, we first copy the current container into a new container, then add elements to the new container, and then reference the original container to the new container. The advantage of this is that we can do concurrent reads to the CopyOnWrite container without locking, since no elements are being added to the current container. So the CopyOnWrite container is also an idea of read-write separation, reading and writing different containers.

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally{ lock.unlock(); }}final void setArray(Object[] a) {
    array = a;
}
Copy the code

Find in the add time is the need to lock, otherwise multithreaded write time will copy N copies out……

No lock is required. If multiple threads are adding data to the ArrayList while reading, the old data will still be read because the old ArrayList will not be locked while writing.

Application scenarios of CopyOnWrite: The CopyOnWrite concurrent container is used in the concurrent scenario with more reads and less writes. Such as whitelisting, blacklisting, commodity access and update scenarios.

Disadvantages of CopyOnWrite: The CopyOnWrite container has many advantages, but it also has two problems, namely memory footprint and data consistency. So in the development of the need to pay attention to:

Memory usage is abnormal. Because CopyOnWrite write replication mechanism, so at the time of writing, in the memory will be stationed at the same time two objects of memory, the old and new writing object (note: just copy the reference in the container when copy, just at the time of writing will create a new object is added to the new container, the old container object is still in use, So there are two pieces of object memory. If these objects take up a lot of memory, say 200 MB, then writing another 100 MB of data will take up 300 MB of memory, which is likely to result in frequent Yong and Full GC.

You can reduce the memory consumption of large objects by compressing the elements in the container. For example, if the elements are all base 10 numbers, consider compressing them to base 36 or 64. Or instead of using the CopyOnWrite container, use another concurrent container, such as ConcurrentHashMap.

Data consistency issues. The CopyOnWrite container only guarantees final data consistency, not real-time data consistency. So if you want to write data that is immediately readable, don’t use the CopyOnWrite container.

conclusion

The fast failure behavior of iterators is not guaranteed (Q2, gory lesson above…). Because, in general, it is impossible to make any hard guarantees about the occurrence of out-of-sync concurrent changes. Fail fast iterator will do our best to throw ConcurrentModificationException. Therefore, it would be a mistake to write a program that relies on this exception to improve the accuracy of such iterators: the fast failure behavior of iterators should only be used to detect bugs.