Java - synchronize individual elements in primitive array

Question

so I have an array of a lot of ints, and I am writing single bits to it everywhere to store information. Like so:

public class myclass
{
    int[] bitArray;

    //methods

    public myclass()
    {
        bitArray = new int[200000000]; //200 million ints
    }

    public void flagBit(int arrayIndex, bitIndex)
    {
        /** 10000000 00000000 00000000 00000000 >>> bitIndex */    
        bitArray[arrayIndex] |= (0x80000000 >>> bitIndex);
    }
}

Now, as you can see, that's a lot of data. So efficiency is imperative.

Anyway, I want multiple threads to be (safely) writing data to this array at once. Unfortunately in Java, you can't do the following:

public void flagBit(int arrayIndex, bitIndex)
{
    /** 10000000 00000000 00000000 00000000 >>> bitIndex */

    synchronized (bitArray[arrayIndex]) //wrong!!! must synchronize to object!
    {
        bitArray[arrayIndex] |= (0x80000000 >>> bitIndex);
    }
}

So, I was wondering what the most efficient or best way to do this is? I'm aware of AtomicIntegerArray, but I believe that I can be more efficient than that. I've made an attempt at coming up with a solution and this is what I got (I haven't tested it yet though, is it valid?)

public class myclass
{
    int[] bitArray;
    SYNC[] indexSync;

    //inner class(es)

    private static final class SYNC
    {
        private static final boolean sync = false;
    }

    //methods

    public myclass()
    {
        bitArray = new int[200000000]; //200 million ints

        indexSync = new SYNC[bitArray.length];
    }

    public void flagBit(int arrayIndex, bitIndex)
    {
        /** 10000000 00000000 00000000 00000000 >>> bitIndex */    

        synchronized (indexSync[arrayIndex])
        {
            bitArray[arrayIndex] |= (0x80000000 >>> bitIndex);
        }
    }
}

So, is there a more efficient way to do that than the way I've posted? Does the way I posted even work? Would my way be very efficient? Thanks~

AtomicIntegerArray would be much more efficient than what you propose. In fact, I believe it would perform quite well. Did you test it? Go and have a try. — ciamej
– ciamej, Commented Jul 31, 2014 at 23:10
You will run into a database design challenge here. Whether to lock tables, pages or rows. Good luck. — Kayaman
– Kayaman, Commented Jul 31, 2014 at 23:12
An array with size 200M doesn't found efficient. You can't polish biological waste. — Bohemian
– Bohemian ♦, Commented Jul 31, 2014 at 23:13

Bradley Kaiser · Accepted Answer · 2014-08-01 00:46:56Z

1

You should probably just use AtomicIntegerArray. It seems like it does exactly what you need and is well tested code written by experts. You should test its performance before discounting it.

If you really don't want to use AtomicIntegerArray, you don't really need the SYNC class, you could just use Boolean objects. Also, if you are going to make an entire second array of SYNC objects, it might be worth it to make your first array Integers instead of ints.

answered Aug 1, 2014 at 0:46

Bradley Kaiser

7744 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Voo Over a year ago

@Ricky Considering that the only way to actually implement this stuff using that class was introduced with 1.8, linking the 1.7 documentation won't do much good ;)

Ricky Mutschlechner Over a year ago

docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/…

Voo · Accepted Answer · 2014-08-01 02:05:38Z

Fascinating, they updated the AtomicIntegerArray class with Java 8 to actually add functionality that allows you to implement this using it - and no, you really can't do that more efficient than it.

As a matter of fact it's way more efficient than what you're doing since it avoids locking as a whole. For people stuck with Java 7 or before - or people who just want to understand how this works, here is a simplified version that I actually wrote before checking the new Javadocs.

At least educational still. This is a very basic compare and swap loop in Java. Quite useful in many situations, although it seems with the update to AtomicIntegerArray (and presumably the other classes as well) this may not longer be that necessary or useful for people interested in getting the best performance out of their code. Still it's quite simple once you get the boilerplate code out of the way.

private static final Unsafe unsafe = getUnsafe();
private static final long arrayBase = getArrayBase();
private static final long arrayScale = getArrayScale();

private static Unsafe getUnsafe() {
    try {
        Field theUnsafe = Unsafe.class.getDeclaredField("theUnsafe");
        theUnsafe.setAccessible(true);
        return (Unsafe) theUnsafe.get(null);
    } catch (NoSuchFieldException | IllegalAccessException e) {
        throw new RuntimeException(e);
    }
}

private static long getArrayBase() {
    return unsafe.arrayBaseOffset(int[].class);
}

private static long getArrayScale() {
    return unsafe.arrayIndexScale(int[].class);
}

private final int[] array = new int[1000];

public void flagBit(int arrayIndex, int bitIndex) {
    // offset of array[arrayIndex] from start of array. In practice you'd want to compute the log2 
    // of arrayScale and just do a shift.
    long offset = arrayBase + arrayIndex * arrayScale;
    int oldValue, newValue;
    do {
        // Read array[arrayIndex] volatile, we need the memory ordering guarantee
        oldValue = unsafe.getIntVolatile(array, offset);
        // Compute new value we want
        newValue = oldValue | (0x80000000 >>> bitIndex);
        // If the field wasn't updated, update it with newValue and return true, otherwise
        // return false and we retry.
    } while (!unsafe.compareAndSwapInt(array, offset, oldValue, newValue));
}

Stanislav Levental · Accepted Answer · 2014-08-01 00:44:53Z

0

You can set bit without any synchronization reads/writes of int arrays are atomic, unless you do read-modify-write operations.

answered Aug 1, 2014 at 0:44

Stanislav Levental

2,2561 gold badge15 silver badges29 bronze badges

1 Comment

Voo Over a year ago

Now you'd just have to figure out how to set a bit without doing a read-modify-write operation...

Collectives™ on Stack Overflow

Java - synchronize individual elements in primitive array

3 Answers 3

2 Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related