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?

That will not work. You need a full lock or an immutable or lock-free data structure. See http://blog.slaks.net/2013-07-22/thread-safe-data-structures/ — SLaks, Aug 15 '13 at 14:22
What about wrapping it with `Collections.synchronizedList` or using `CopyOnWriteArrayList`? — Sam Marsh, Aug 15 '13 at 14:23
Why wouldn't you use `synchronized`? Do you need to save a few nano-seconds? — Peter Lawrey, Aug 15 '13 at 14:25
@orionll so what? It's not going to be called 1000000000000 _simultaneously._ — Matt Ball, Aug 15 '13 at 14:32
It's amazing that people still think synchronization is somehow slow, and go through extraordinary convoluted designs even when there is absolutely no indication that there's a bottleneck or that it would help even a little bit. — Kayaman, Aug 15 '13 at 14:35
4 threads will call getElementAt simultaneously. I don't want unnecessary synchronizations — ZhekaKozlov, Aug 15 '13 at 14:38
@MattBall: Because `list.get()` isn't thread-safe with respect to `add()`. He needs to rewrite all of his code to use lock-free data structures & immutability. — SLaks, Aug 15 '13 at 16:16
I didn't specify any limitations on changing the code. You are free to completely change data structures. — ZhekaKozlov, Aug 15 '13 at 19:39
The people who mark this question as duplicate point to a completely different question. There is no answer there. — ZhekaKozlov, Aug 15 '13 at 19:42

score 0 · Answer 1 · answered Aug 15 '13 at 14:28

0

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.

answered Aug 15 '13 at 14:28

Andrzej Doyle

102,507
33
189
228

I'm not so sure about using a map instead of a list. If I came across a densely-keyed, int-keyed map, the very first question I'd want to know is: "why the heck didn't the author use a list?" – Matt Ball Aug 15 '13 at 14:31
Since map.putIfAbsent(i, createElement()) is not an atomic operation, it is possible that createElement() will create an extra instance of Element – ZhekaKozlov Aug 15 '13 at 14:43
Also, have you seen how ConcurrentHashMap.size() is implemented? This is an expensive operation – ZhekaKozlov Aug 15 '13 at 14:55
@MattBall I take your point. In practice the suitability will depend on *why* this needs to be dense - as written I see no reason why we couldn't just create each element on demand. And in some cases using list indices might be a minor workaround, they might be e.g. IDs of some objects which could be directly used as map keys. – Andrzej Doyle Aug 15 '13 at 15:20
1

@orionll - If by not atomic you mean that this line will call `createElement` twice, that's not the case. It would be identical to the two lines `Element e = createElement(); map.putIfAbsent(i, e);`. If you mean two threads calling this at once could each create an element (only one of which goes into the map) then yes - that's entirely the point of non-blocking approaches. The only way to avoid this is to make the whole method synchronized, so the second thread waits until the first is done. – Andrzej Doyle Aug 15 '13 at 15:31
And you can avoid the call to size by using `map.containsKey(index)` instead, if that's more appropriate. The answer wasn't intended to be a complete custom solution, merely an illustration of how `putIfAbsent` can be used for non-blocking threadsafe updates. Please do change the surrounding code to suit your circumstances. – Andrzej Doyle Aug 15 '13 at 15:35
@AndrzejDoyle: Calling `containsKey()` will only be safe if nothing is ever removed. – SLaks Aug 15 '13 at 16:17
@SLaks Yeees... That should be a safe assumption for this sort of lazy-init pattern in any case. But if we're talking about full mutability it's *probably* still OK. At the time the method was called, the key was in the map. If it gets removed *later* (even a nanosecond later) then that's what's happens, the `getElementAt` call can't do anything to stop that. – Andrzej Doyle Aug 15 '13 at 16:24

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

1 Answers1