Hi all,

I'm working with threads in java and have some questions about accessing an array concurrently.

The situation: I've an array a[] of doubles, which is "empty" in the beginning. Each double needs to be calculated and takes some amount of work to be calculated. Fortunately, they are independent from each other (the value of a[i] does not depend on the value of a[j]); hence I thought that I could use threads to calculate each a[i]. The idea is, with for example, use two threads, thus the first one calculates the values of a[0]..a[a.length/2], and the second thread calculates the remaining values.

I've implemented this by creating classes that extend Threads and that, when constructed, receive a reference to the array as well as the first and last indices to calculate. To do the calculation the Threads also read some data from other objects (also shared), but do not change any attribute of those other objects.

The question(s): Does it work? I mean: Is there a problem with accessing the same array from two or more threads, even if I'm working with different elements of the array? Do you think it is a good idea to calculate the values like this, or is there a better schema for this? I'm guessing that the situation is fairly common...

Any help on these questions as well as pointers to literature (hopefully on the web, and free) will be truly appreciated.

Regards.

I can't see any problem. Those doubles are at different indexes, so each of the thread works with it's own double. Theoretically it may be possible that both threads could access the array at the same time, but in reality ...

http://java.sun.com/docs/books/tutor...l/concurrency/

Hi -

You answered your own question: if the regions are truly independent, there's no need to lock anything. That's the good news.

However...

Do you really need to use multiple threads here? Remember: if two threads are each doing 1/2 the work ... then it will always take LONGER than if *one* thread did the entire job.

Just a thought .. PSM

Is it also correct on multi-core or hyperthreading enabled machines?

Good point, Alien_Hominid! I should have qualified that statement a bit better:

On a *single-processor* system, the non-threaded version will always complete faster than dividing the same, independent work between multiple threads.

If the system has multiple CPUs (or a single multi-core processor), then you *might* get faster performance ...
... *if* your threading library is smart enough to assign the threads to different CPUs.

Check out these links:

http://www.javaspecialists.eu/archive/Issue135.html

http://mlee888.wordpress.com/2006/03...r-environment/

http://www.javaworld.com/javaworld/j...rocessing.html

You could always use a threadsafe collection instead of an array. The advantage is that you'll never run into an IndexOutOfBoundsException as collections can grow dynamically. However, anything that involves threading also incurs overhead, which may make it less attractive than it seems at first. ArrayLists are faster than Vectors precisely because they are not threadsafe.

I agree with paulsm4. As long as you are certain that each thread will never access the same block based on your logic you should be fine. However, it never hurts to build in a failsafe. A semaphore would help ensure that the same block is never
accessed at the same time.

Hi all,

Thank you all, some really nice posts to read.

paulsm4. I was in the doubt because, even thought these are different indexes, it is still 'the same array'.

Aliem-Hominid, paulsm4. Indeed it 'will be' a multi-core machine. (I'm developing in PIV, and here, as expected, it actually takes longer with more than one thread).

jay73. I thought about using some safe containers, but the truth is the size if fixed and the values are disposable. Then I'm not sure that safe containers would allow to access different indexes in parallel.

terrio. How does the semaphore work? Is it possible to block only one element in the array?

I've done some tests and it *seems* to work for some simpler cases (where I've computed other values, easily checkable).

Just to give you some more background. I'm implementing one of these 'genetic algorithms' where you keep a population of individuals. Each individual has a cercain fitness (a double) and, accordingly to the fitness, they survive/cross, etc and based on this new generations are created, and then the fitness values for the next generation need to be recalculated... Thus, a lot of time is spent computing the fitness for each individual and that is why I'm trying to paralellize the calculation.

Thank you all for your replies!!

Well, a semaphore is a method of restricting access to shared resources. Wiki has a great description.

http://en.wikipedia.org/wiki/Semaphore_(programming)

In your case, there are two ways to approach your semaphore. First, restrict access to the entire array to only one thread at a time, or be more fine grained and restrict access to each individual address in the array to one thread at a time.

The first case is the easiest to implement. In you thread class define a class variable that would be used to indicate when a thread is accessing the array. All threads can then check the value of this class variable to see if the array is available or not. If it is not available, wait until it is.

The second scenario would require a way of tracking which indexes in the array are currently being accessed (another Array possibly). Each thread would then look to see if the address it requires is already being accessed, if so, wait until the address is available.

Hope this helps. There are plenty of examples available as well so a quick google should get you on the right track.

I think you can synchronize access to array.