How to modify a 2D array from multiple threads without synchronization

Question

How to design a 2D array in java in such a way that it allows multiple threads to modify or insert value at a particular position without using synchronization

Answer 1

Well you cannot do it without synchronization. Only thing you can do is reduce the scope of he lock used. If you don't know yet, read about lock coarsening. ConcurrentHashMap uses it. Idea is that instead of locking the whole array to modifications you just lock a segment of array (e.g: start, middle or end) where the modification would happen. This keeps the array DS open for reads and writes by other threads and no blocking happens unless 2 threads try to mutate the same segment simultaneously.

Answer 2

There are several ways to do it.

Firstly, if you want maximum concurrency as a common library regardless of how many threads are accessing the matrix, and your int[][] is reasonably small, you can do like this.

1. Set up a matrix of AtomicBoolean equals to the dimension of the int[][].
2. While you are trying to update the int matrix, lock that AtomicBoolean first, the use Unsafe.putIntVolatile() to update the value in volatile way, then unluck the AtomicBoolean.

Secondly, if you know the number of threads in advance.

1. Keep a marker object/value as per thread like int; then create an additional int[][] as the marker matrix. Initialize the marker matrix to some dummy value which doesn't equal to any of your thread marker value, e.g. -1.
2. While you are trying to update the int matrix, lock the cell in thr marker matrix by using Unsafe.compareAndSet() first; then update it by Unsafe.putIntVolatile(); and finally unmark the marker matrix by reset the value to -1.

Lastly, if you can tolerate the int[][] isn't really an int matrix in the actual code, what you can do is to use a long[][] matrix, where the first 32 bit is the current number of updates to the value and the last 32 bit is the current value. Then you can easily use Unsafe.compareAndSet() to set this long value as a whole. Note you can circular the upper 32 bit value so you don't have to have a update upper limit == Integer.MAX_VALUE.