6
\$\begingroup\$

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<E> implements Iterable<E> {
    class MyIterator extends UnmodifiableIterator<E> {
        @Override public boolean hasNext() {
            return index < size();
        }

        @Override public E next() {
            try {
                return get(index++); // Safe as the array never shrinks.
            } catch (final IndexOutOfBoundsException e) {
                // This is hacky, but better than checking the size upfront, as the size may change.
                throw new NoSuchElementException();
            }
        }

        private int index;
    }

    /**
     * The returned iterator may or may not see the changes made after its creation.
     * The only guarantee in case of concurrent modifications is is that
     * it sees no garbage provided that the items are immutable.
     */
    @Override public Iterator<E> 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 List interfaces, but it's not meant to be general use class (though it may change). I need no additional constructors or other features.

Concerning spacing and single line conditional statements... yes, I know, I just don't care (my own conventions differ slightly).

I'll probably try to re-implement this without synchronization as a challenge.

\$\endgroup\$
  • \$\begingroup\$ Question... is there no need for any 'remove()' type functionality? \$\endgroup\$ – rolfl Oct 17 '14 at 17:58
  • \$\begingroup\$ @rolfl No, never. Once added, the thing must stay there forever or be replaced by an updated version (just some added information, no real change). There may be some cleanup some day, but it'll surely involve re-creation of this list. \$\endgroup\$ – maaartinus Oct 17 '14 at 18:12
3
\$\begingroup\$

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)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ +1 OutOfMemoryError - Have a look at my inspiration. But agreed, it's plain stupid. +++ checkElementIndex() - It's Guava, see my link above the code for (static) imports. +++ E[] - But is it worth it? I have a single cast in the whole code. +++ Synchronizing on the instance itself, agreed, but it's a single shot class. +++ Someone does the following... Thread.sleep - Nobody will. They know I'd kill them at once. \$\endgroup\$ – maaartinus Oct 17 '14 at 20:33
  • \$\begingroup\$ "when you add a member, the size will be incremented, but the get() could return null in one thread" - I guess, I have a solutions, but this will be the next question. +++ "If you document that the container can hold null values," - then I have to live with it. And I really don't want. +++ "Note, it would be relatively trivial for the calling code to handle null return values." - trivial to handle but even more trivial to forget. And with the error happening once in a blue moon, I'm not gonna risk to have to chase it down. \$\endgroup\$ – maaartinus Oct 17 '14 at 20:34
  • \$\begingroup\$ I can't understand the disparity you have in your attitude, in the one sense you consider this to be a 'one-shot class', and in the other sense it's too much to risk. If null is a problem and you can't handle it outside the class, then you can make each member a mini container class, and lock on that, instead of using an atomic. The memory overhead will be greater. On the other hand, you can just stick with what you have if you don't care that much about the concurrent performance. \$\endgroup\$ – rolfl Oct 17 '14 at 20:37
  • \$\begingroup\$ I see. It's "one-shot class" in the sense that I'm planning to use it in a single place for a single thing. At the same time, it'll be a rather central piece, as this single thing is sort of "registry of everything" and gets iterated in many places. As I know myself, I'd forget to check for null somewhere. The concurrent performance is indeed not an issue, but the problem is interesting enough to try. \$\endgroup\$ – maaartinus Oct 17 '14 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.