How to make this code thread-safe using double checked locking?

Question

Single threaded version:

private final List<Element> list = new ArrayList<Element>();

public Element getElementAt(int index) {

    if (index >= list.size()) {
        for (int i = list.size(); i <= index; i++) {
            list.add(createElement(i));
        }
    }

    return list.get(index);
}

Now I am trying to make a thread-safe version with double checked locking:

import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableList.Builder;

...

private volatile List<Element> list = ImmutableList.of();

public Element getElementAt(int index) {

    if (index >= list.size()) {

        synchronized (this) {
            if (index >= list.size()) {
                Builder<Element> newListBuilder = ImmutableList.<Element> builder();
                newListBuilder.addAll(list);
                for (int i = list.size(); i <= index; i++) {
                    newListBuilder.add(createElement(i));
                }

                list = newListBuilder.build();
            }
        }
    }

    return list.get(index);
}

Is this correct?

Answer 1

What you are doing is more like a map/dictionary lookup. If you consider that your list is really behaving like a Map<Integer, Element> then you can use a concurrent map's putIfAbsent method to handle this without blocking:

private final ConcurrentMap<Integer, Element> map =
                new ConcurrentHashMap<Integer, Element>();

public Element getElementAt(int index) {

    if (index >= map.size()) {
        for (int i = map.size(); i <= index; i++) {
            map.putIfAbsent(i, createElement());
        }
    }

    return map.get(index);
}

This assumes that there's no particular ordering requirements on the elements returned from createElement - though if that's the case, you'd need much tighter constraints on how they're created anyway.

Chances are though that in reality you could simply stick a synchronized block around this method (and any other than accesses the list). It's easy to understand, and it's relatively fast. If getting elements isn't the performance hotspot of your code, I wouldn't want to do something "clever" just to shave off a couple of nanoseconds.