Implementing an AtomicByteArray in Java using AtomicIntegerArray

Question

I need an AtomicByteArray for a memory-critical application modeled after Java's AtomicIntegerArray. My implementation wraps four bytes into an integer and uses the AtomicIntegerArray.

The get() implementation is trivial, and the and set() implementations is fairly straightforward. The compareAndSwap() is trickier. My implementation appears below (it works single-threaded just fine).

I'm trying to identify race condition. One potential scenario is that values changed and swapped back between the calls to get() and compareAndSet(), but this seems harmless.

Am I missing anything that could go wrong?

/**
 * Atomically sets the element at position {@code i} to the given
 * updated value if the current value {@code ==} the expected value.
 *
 * @param i the index
 * @param expect the expected value
 * @param update the new value
 * @return true if successful. False return indicates that
 * the actual value was not equal to the expected value.
 */
public boolean compareAndSet(final int i, final byte expected, final byte val) {
    int idx = i >>> 2;
    int shift = (i & 3) << 3;

    while (true) {
        final int num = this.array.get(idx);
        // Check that the read byte is what we expected
        if ((byte)(num >> shift) != expected) {
            return false;
        }
        // If we complete successfully, all is good
        final int num2 = (num & ~(0xff << shift)) | ((val & 0xff) << shift);
        if ((num == num2) || this.array.compareAndSet(idx, num, num2)) {
            return true;
        }
    }
}

Update: I've implemented a basic version of AtomicByteArray that integrates the improvements in the answer below.

I would `i / 4` -> `i >>> 2` and `8 * (i % 4)` -> `(i & 3) << 3` — Peter Lawrey, Jun 13 '14 at 19:46
@JimGarrison I don't know, but am happy to repost there. It's more of a concurrency question than a Java code question. — Shilad Sen, Jun 13 '14 at 19:51
Which is why I asked instead of voting to close off-topic. I'm curious where this type of question belongs. — Jim Garrison, Jun 13 '14 at 19:52

score 1 · Accepted Answer · edited Jun 13 '14 at 20:08

1

You might consider using a mask. This might be quicker/cleaner.

int idx = i >>> 2;
int shift = (i & 3) << 3;
int mask = 0xFF << shift;
int expected2 = (expected & 0xff) << shift;
int val2 = (val & 0xff) << shift;

while (true) {
    final int num = this.array.get(idx);
    // Check that the read byte is what we expected
    if ((num & mask) != expected2) return false;
    // If we complete successfully, all is good
    final int num2 = (num & ~mask) | val2;
    if ((num == num2) || this.array.compareAndSet(idx, num, num2)) {
        return true;
    }
}

You want to do a minimum of work inside the loop so that if there is contention you can try again as quick as possible.

I am not sure the num == num2 helps more than it hurts. I suggest you try it without for comparison.

edited Jun 13 '14 at 20:08

tbodt

16,609
6
58
83

answered Jun 13 '14 at 19:51

Peter Lawrey

525,659
79
751
1,130

1

Thanks! I suggested a few corrections related to signing and byte to int to promotion. To be specific, when you perform bitwise operations on -1 (the 0xff), it is first promoted to the int -1 (0xfffffff). – Shilad Sen Jun 13 '14 at 20:08
1

I implemented a basic version that integrates your suggestions at https://github.com/shilad/wikibrain/blob/master/wikibrain-utils/src/main/java/org/wikibrain/utils/AtomicByteArray.java – Shilad Sen Jun 14 '14 at 03:25

Implementing an AtomicByteArray in Java using AtomicIntegerArray

1 Answers1