Concurrently Iterable Poor Array List

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<E> clazz) {
    @SuppressWarnings("unchecked")
    data = (E[])Array.newInstance(clazz, 4);
}

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

ConcurrentIterable<MyClass> 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<String> 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<T> implements Iterable<T> {

    private static final int CONTAINER_SHIFT = 10; // 1024 per container.
    private static final int CONTAINER_SIZE = 1 << CONTAINER_SHIFT;
    private static final int CONTAINER_MASK = CONTAINER_SIZE - 1;

    private final AtomicInteger size = new AtomicInteger();
    private final ReentrantLock lock = new ReentrantLock();
    private final ArrayList<AtomicReferenceArray<T>> containers = new ArrayList<>();

    private final AtomicReferenceArray<T> getContainer(int index) {
        int cont = index >>> CONTAINER_SHIFT;
        lock.lock();
        try {
            while (cont >= containers.size()) {
                containers.add(new AtomicReferenceArray<T>(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<T> iterator() {
        return new Iterator<T>() {

            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 another thread.

If you document that the container can hold null values, and that the iterator/get may return a null before the value is added, then you have the bonus of being able to support null values in the data too.

Note, it would be relatively trivial for the calling code to handle null return values.

There's a second caveat. I set up the iterator to loop to the last value that was added when the iterator was created. If you change the line:

return next < last;

to be

return next < size.get();

then you will iterate over all values added up to the last add. (but with slightly more risk that the last values may be null)