Iterators for the copy-on-write collections

Question

An abstract from JCIP

Iterators for the copy-on-write collections retain a reference to the backing array that was current at the start of iteration, and since this will never change, they need to synchronize only briefly to ensure visibility of the array contents.

The iterators returned by the copy-on-write collections do not throw ConcurrentModificationException and return the elements exactly as they were at the time the iterator was created, regardless of subsequent modifications

Looking at the source code at #CopyOnWriteArrayList.iterator()

956         public Iterator<E> iterator() {
957              return new COWIterator<E>(getArray(), 0); // call to private constructor
958         }

993         private final Object[] snapshot;

994 
995         private int cursor;
996 
997         private COWIterator(Object[] elements, int initialCursor) {
998             cursor = initialCursor;
999             snapshot = elements;  
1000        }

You see that the snapshot points to the array returned by getArray() and since the array reference returned is volatile, any change on the reference variable is guaranteed to be reflected. (Making the array reference volatile doesn't makes the elements at each index location volatile)

where the change on the array is done inside-

386     public E More ...set(int index, E element) {
387         final ReentrantLock lock = this.lock;
388         lock.lock();
389         try {
390             Object[] elements = getArray();
391             E oldValue = get(elements, index);
392 
393             if (oldValue != element) {
394                 int len = elements.length;
395                 Object[] newElements = Arrays.copyOf(elements, len);
396                 newElements[index] = element;
397                 setArray(newElements);
398             } else {
399                 // Not quite a no-op; ensures volatile write semantics
400                 setArray(elements);
401             }
402             return oldValue;
403         } finally {
404             lock.unlock();
405         }
406     }

i.e setArray(newElements); as seen in the method.

where getArray()

92      final Object[] More ...getArray() {
93          return array;
94      }

& setArray(...)

final void More ...setArray(Object[] a) {
100         array = a;
101     }

are operations on this volatile array

private volatile transient Object[] array;

Clearly, the iterator is returning the array which (if) has been modified, and not the one created at the start of the iteration process.

So, what does the author mean-

return the elements exactly as they were at the time the iterator was created, regardless of subsequent modifications.

I looked at the code you posted here and clearly, the iterator is returning an array that's never modified. — Marko Topolnik, Oct 04 '16 at 08:53
@MarkoTopolnik: But concurrently other threads can clearly modified it through `set(int index, E element).` — Farhan stands with Palestine, Oct 04 '16 at 08:56
*"Clearly, the iterator is returning the array"* Ehh, nooo. "Clearly", the iterator is *using* the array obtained at the time the iterator was *created*. Any subsequent modification of the list will create a *new* array, so the iterator will not see those changes. — Andreas, Oct 04 '16 at 08:57
@ShirgillFarhanAnsari I see no evidence of that, instead I see modification of a new array which is subsequently assigned as the "current" array. Once assigned, it never changes. — Marko Topolnik, Oct 04 '16 at 08:59
@Andreas: I never said it doesn't creates a new array on every mutation. But the reference remains the same. `setArray(newElements);` — Farhan stands with Palestine, Oct 04 '16 at 09:00
Can you describe in your own words what the `setArray` method does? — Marko Topolnik, Oct 04 '16 at 09:02
What do you mean "the reference remains the same"? `setArray(Object[] a) { array = a; }` *updates* the reference. How can you say it "remains the same", when you yourself just showed the code that changes it? — Andreas, Oct 04 '16 at 09:02
The new array is assigned to the same reference as seen clearly in `array = a;` in `setArray` — Farhan stands with Palestine, Oct 04 '16 at 09:04
You just need a basic lesson on the semantics of Java's variables and references. "Assigned to the same reference" is a meaningless statement because a reference is just a value. A reference is assigned to a variable, not the other way. — Marko Topolnik, Oct 04 '16 at 09:06
Yes, so the `array` reference of the list is *changed*! It now points to a *different* array. However, the `snapshot` reference in the `COWIterator` is *unchanged*, and still points to the old array. — Andreas, Oct 04 '16 at 09:06
Same answer [@AR.3 already gave you](http://stackoverflow.com/a/39848135/5221149) 10+ minutes ago: *assigning its reference to the `array` field will **keep the `snapshot` of the iterator pointing to the same old reference*** — Andreas, Oct 04 '16 at 09:09
@Andreas: Not a native English speaker, sometimes it happens. I accept it's my fault. — Farhan stands with Palestine, Oct 04 '16 at 09:10
I didn't notice any offense on your part. Apologies are not due. — Marko Topolnik, Oct 04 '16 at 09:17

score 4 · Accepted Answer · answered Oct 04 '16 at 08:57

4

since the array returned is volatile, any change on the reference variable is guaranteed to be reflected.

This has nothing to do with volatile semantics. The reference to the array is created when the COWIterator constructor is called (when the iterator is created). Creating a new copy of the array and assigning its reference to the array field will keep the snapshot of the iterator pointing to the same old reference.

answered Oct 04 '16 at 08:57

M A

71,713
13
134
174

That's what I have written- the snapshot points to the array returned by getArray() – Farhan stands with Palestine Oct 04 '16 at 08:58
@ShirgillFarhanAnsari Yes but `setArray` changes the reference to a completely different array. You should read [this](http://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value). – M A Oct 04 '16 at 09:00
1

@ShirgillFarhanAnsari Exactly! The array *at the time* `getArray()` is called. Subsequent calls to `getArray()` may return a different array, but `getArray()` is never called again by the `Iterator` *during* the iteration. – Andreas Oct 04 '16 at 09:00
See my comment above on the question. – Farhan stands with Palestine Oct 04 '16 at 09:02

score 1 · Answer 2 · answered Oct 04 '16 at 09:14

1

Let's say you instanciate a CopyOnWriteArrayList, now elements is referencing an array:

elements -> [0, 1, 2]

Now you create a COWIterator, snapshot is referencing the same array:

elements -> [0, 1, 2] <- snapshot

Now you add a new element to the CopyOnWriteArrayList, a new array is created and the reference is updated to the new array:

snapshot -> [0, 1, 2]

elements -> [0, 1, 3]

So, snapshot still points to the initial array !

answered Oct 04 '16 at 09:14

Spotted

4,021
17
33

It was a language barrier problem for me. I completely misinterpreted the statement. – Farhan stands with Palestine Oct 04 '16 at 09:16

score 0 · Answer 3 · answered Oct 04 '16 at 14:56

The code that you've pasted here has these lines (not copied a few lines in between) : Object[] elements = getArray(); Object[] newElements = Arrays.copyOf(elements, len); newElements[index] = element;

Line 1 refers to the existing array that backs this collection. If you try to get an iterator before the collection is updated, then this is the array (referred to as snapshot) iterator gets.

Line 2 is a new array being created by copying (hence the COW) and then new item being added to it as seen in line 3.

This newElements array is then assigned to volatile array reference. Iterator is already referring to older snapshot array, so it doesn't even know about the array being updated.

Hope that explains.

Iterators for the copy-on-write collections

3 Answers3