Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Shuffling array in multiple threads

I have an array of size N. I want to shuffle its elements in 2 threads (or more). Each thread should work with it's own part of the array.

Lets say, the first thread shuffles elements from 0 to K, and the second thread shuffles elements from K to N (where 0 < K < N). So, it can look like this:

//try-catch stuff is ommited
static void shuffle(int[] array) {
   Thread t1 = new ShufflingThread(array, 0, array.length / 2);
   Thread t2 = new ShufflingThread(array, array.length / 2, array.length);
   t1.start();
   t2.start();
   t1.join();
   t2.join();
}

public static void main(String[] args) {
   int array = generateBigSortedArray();
   shuffle(array);
}

Are there any guaranties from JVM that I will see changes in the array from the main method after such shuffling?

How should I implement ShufflingThread (or, how should I run it, maybe within a synchronized block or whatever else) in order to get such guaranties?

like image 808
Roman Avatar asked Jan 19 '11 13:01

Roman


1 Answers

The join() calls are sufficient to ensure memory coherency: when t1.join() returns, the main thread "sees" whatever operations thread t1 did on the array.

Also, Java guarantees that there is no word-tearing on arrays: distinct threads may use distinct elements of the same array without needing synchronization.

like image 139
Thomas Pornin Avatar answered Oct 01 '22 00:10

Thomas Pornin