Concurrently Iterable Poor Array List

As I wrote on SO, I need an ArrayList-like structure allowing just the following operations

• get(int index)

• add(E element)

• set(int index, E element)

• iterator()

while supporting iterations concurrent with modifications. While I'm waiting for something better, I tried it myself. It was a bit harder than expected, so I used synchronization, which made it easy again. I'm linking to the full code and the test and showing here the relevant part (i.e., everything but the imports).

/**
 * A data structure implementing a tiny subset of List operations and allowing concurrent access.
 *
 * See https://stackoverflow.com/q/26424030/581205 for requirements.
 */
public class ConcurrentIterable implements Iterable {
    class MyIterator extends UnmodifiableIterator {
        @Override public boolean hasNext() {
            return index  iterator() {
        return new MyIterator();
    }

    public synchronized int size() {
        return size;
    }

    @SuppressWarnings("unchecked")
    public synchronized E get(int index) {
        checkElementIndex(index, size);
        return (E) data[index];
    }

    public synchronized void add(E element) {
        if (data.length == size) grow();
        data[size++] = element;
    }

    public synchronized void set(int index, E element) {
        checkElementIndex(index, size);
        data[index] = element;
    }

    private void grow() {
        data = Arrays.copyOf(data, newSize(data.length));
    }

    private static int newSize(int oldSize) {
        int result = oldSize + (oldSize>>3) + 4; // Grow by about 1/8 only.
        if (result-MAX_ARRAY_SIZE > 0) result = MAX_ARRAY_SIZE; // Handle overflow.
        if (result<=oldSize) throw new OutOfMemoryError();
        return result;
    }

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // See ArrayList.

    private int size;
    private Object[] data = new Object[4];
}

I'm aware that it's incompatible with the Collection or `

General

private static int newSize(int oldSize) {
    int result = oldSize + (oldSize>>3) + 4; // Grow by about 1/8 only.
    if (result-MAX_ARRAY_SIZE > 0) result = MAX_ARRAY_SIZE; // Handle overflow.
    if (result<=oldSize) throw new OutOfMemoryError();
    return result;
}

Alright, leaving aside the 1-liners (OK, I said it... it sucks), there are other things here too:

• YOU THROW OutOfMemoryError

Ouch.

Additionally, the method is only called from one place (grow()), and the call-site has only one line of code. Moving this logic in to the grow() call would be fine.

Other methods call checkElementIndex(), but that method is not included with your code.

You have the Object[] data variable. This is a horrible datatype to use because it introduces the need to do the explicit casts in the rest of the code, like:

return (E) data[index];

it is now relatively common in Java to require the class is given at the same time as the constructor. If you have the following code:

private E[] data;

public ConcurrentIterable(Class clazz) {
    @SuppressWarnings("unchecked")
    data = (E[])Array.newInstance(clazz, 4);
}

Then, when you want to create your list, you create it with:

ConcurrentIterable myiterable = new ConcurrentIterable<>(MyClass.class);

from that point on, the inner-content of the class never needs to do an explicit cast from the data store.
Synchronization

Synchronizing on the instance itself is an anti-pattern, generally. In your class, you have synchronized methods: public synchronized void add(E element), etc.

What this means is that anyone who has an instance of your class, can mess with your synchronization and create deadlocks. Someone does the following:

public class MyClass {
    private final ConcurrentIterable iterable = new ConcurrentIterable<>();

    ....

    public void doSomething() {
        synchronized(iterable) {
            Thread.sleep(100000);
        }
    }

Now, suddenly, your code hangs and does not complete.

When using synchronization it is almost always a bug to have a synchronization point on a public/leaked instance.

Apart from that issue, the synchronization looks complete, but excessively scoped. You lock the whole data structure. Your instance is 'serialized', no matter how many threads you have, only one thread can be doing anything at any one time.

There has to be a better way....
Alternate scheme

If it was me, I would consider a combination of the AtomicReferenceArray an AtomicInteger, and a ReentrantLock. The system would look something like:

import java.util.ArrayList;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReferenceArray;
import java.util.concurrent.locks.ReentrantLock;

public class ConcurrentIterable implements Iterable {
    
    private static final int CONTAINER_SHIFT = 10; // 1024 per container.
    private static final int CONTAINER_SIZE = 1 > containers = new ArrayList<>();
    
    private final AtomicReferenceArray getContainer(int index) {
        int cont = index >>> CONTAINER_SHIFT;
        lock.lock();
        try {
            while (cont >= containers.size()) {
                containers.add(new AtomicReferenceArray(CONTAINER_SIZE));
            }
            return containers.get(cont);
        } finally {
            lock.unlock();
        }
    }
    
    private void checkIndex(final int index) {
        final int sz = size.get();
        if (index >= sz) {
            throw new NoSuchElementException(String.format("No element %d in structure of size %d", index, sz));
        }
    }

    public T get(final int index) {
        checkIndex(index);
        return getContainer(index).get(index & CONTAINER_MASK);
    }

    public T set(final int index, T value) {
        checkIndex(index);
        return getContainer(index).getAndSet(index & CONTAINER_MASK, value);
    }
    
    public void add(T value) {
        int index = size.getAndIncrement();
        getContainer(index).set(index & CONTAINER_MASK, value);
    }
    
    @Override
    public Iterator iterator() {
        return new Iterator() {
            
            int next = 0;
            final int last = size.get();

            @Override
            public boolean hasNext() {
                return next < last;
            }

            @Override
            public T next() {
                return get(next++);
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
            
        };
    }

}

There is a race condition in the above, but I would probably solve it with documentation, not logic. The race condition is that there is a moment when you add a member, the size will be incremented, but the get() could return null in one thread in the instant before the value is set to the new value in an

StackExchange Code Review Q#67030, answer score: 3