Possible to create AtomicReference that can be swapped atomically?

Question

Is there any way to implement a type of reference whose value can be exchanged with another atomically?

---

In Java we have AtomicReference which can be swapped with a local variable but not with another AtomicReference.

You can do:

AtomicReference r1 = new AtomicReference("hello");
AtomicReference r2 = new AtomicReference("world");

and swap them with a combination of two operations:

r1.set(r2.getAndSet(r1.get()));

But this leaves them in an inconsistent state in between, where both contain "hello". Also even if you could swap them atomically, you still could not read them (as a pair) atomically.

---

What I would like to be able to do is:

PairableAtomicReference r1 = new PairableAtomicReference("hello");
PairableAtomicReference r2 = new PairableAtomicReference("world");
AtomicRefPair rp = new AtomicRefPair(r1, r2);

then

Object[] oldVal, newVal;
do {
    oldVal = rp.get();
    newVal = new Object[] {oldVal[1], oldVal[0]};
} while (! rp.compareAndSet(oldVal, newVal));

to swap the values, and in another thread:

AtomicRefPair otherRP = new AtomicRefPair(r1, r2);
System.out.println(Arrays.toString(otherRP.get()));

and be certain that the output will be either [hello, world] or [world, hello].

Notes:

• r1 and r2 are paired for this operation, but it's possible that another thread will independently pair, say r1 and another r3 (unfortunately that means I cannot use this solution.)
• There will be hundreds of thousands of these references, so a global ReentrantLock would be a major bottleneck.
• rp and otherRP are not necessarily shared between threads, so simply locking them will not work. They could be interned, but the intern pool would need its own synchronization which would be another bottleneck.
• I have only made groups of 2 references here, but the ability to group 3 or more would be a bonus.

Is it possible to implement a lock-free version of AtomicRefPair? I have a hunch that it isn't, but if not then maybe there is an article somewhere that explains why?

---

Related: How do I atomically swap 2 ints in C#?

Graaf

There's an Interner in Guava, which uses ConcurrentHashMap, so the contention could be arbitrary small on average. – Daberath

Answer 1

I don't know if there's a nice solution, but the following ugly one could work:

public final class MyReference<T> extends ReentrantLock implements Comparable<MyReference<T>> {
    public MyReference() {
        id = counter.incrementAndGet();
    }

    public void swap(MyReference<T> other) {
        if (id < other.id) {
            lock();
            other.lock();
        } else {
            other.lock();
            lock();
        }
        final T tmp = value;
        value = other.value;
        other.value = tmp;
        unlock();
        other.unlock();
    }

    public static <T> List<T> consistentGet(List<MyReference<T>> references) {
        final ArrayList<MyReference<T>> sortedReferences = Lists.newArrayList(references);
        Collections.sort(sortedReferences);
        for (val r : sortedReferences) r.lock();
        final List<T> result = Lists.newArrayListWithExpectedSize(sortedReferences.size());
        for (val r : references) result.add(r.value);
        for (val r : sortedReferences) r.unlock();
        return result;
    }

    @Override
    public int compareTo(MyReference<T> o) {
        return id < o.id ? -1 : id > o.id ? 1 : 0;
    }

    private final static AtomicInteger counter = new AtomicInteger();

    private T value;
    private final int id;
}

• Use MyReference instead of AtomicReference.
• It uses a lot of locks, but none of them is global.
• It acquires locks in a fixed order, so it's deadlock-free.
• It compiles using lombok and guava (take it as pseudocode without them).

Daberath

+1. Almost what I wanted to suggest. However op needs "hundreds of thousands of these references". Perhaps it would be better to group them into partitions and associate locks with these partitions, almost the same way how ConcurrentHashMap works. If number of partitions is reasonably large, probability of contention should be low. – Jed

I would not, since ReentrantLock is fairy small as it contains only one reference to an empty Object. So even one million of them costs only 24 MB (assuming 8B per reference and 16B per Object). – Daberath

@maaartinus, where is the reference to lombok? – Graaf

There's for (val r : ...), where val comes from projectlombok.org/features/val.html – Daberath

Why does class MyReference derive from ReentrantLock? Were you trying to save the space on storing a Lock reference within each MyReference instance? – Duester

Sort of. I started by a look at ConcurrentHashMap.Segment. Actually, I don't think that extending ReentrantLock is a good idea here, as MyReference (unlike Segment) is meant to be publicly visible. – Daberath

Answer 2

Have an immutable class holding the pair. That is your atom. Swapping the pair means replacing the atom.

update: your question isn't very clear. but in general, for a concurrent system consisting of multiple variables, one might want

1. take a snapshot of system state. the snapshot doesn't change once taken.
2. atomically update system state by changing multiple variables at once. it may be required that there is no other update between my update an a previous snapshot (which my calculation was based on)

you can model your system directly in snapshots, if it doesn't consume too much resources.

Mortenson

@Graaf - what is wrong with this answer? this is a reasonable (and much less complicated) solution. – Enduring

I was referring to the fact that r1 and r2 may be paired for one operation and r1 and r3 may be paired for another. This could work in principle but it would need a way to dynamically re-group the references. – Graaf

@Graaf - hmm, last time i read through you post, i missed the part about the dynamic grouping. now i understand. – Enduring