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.)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.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?
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;
}