LinuxQuestions.org
Help answer threads with 0 replies.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 11-29-2007, 09:53 AM   #1
enemorales
Member
 
Registered: Jul 2004
Location: Santiago, Chile
Distribution: Ubuntu
Posts: 410

Rep: Reputation: 30
Accessing a java array concurrently


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.
 
Old 11-29-2007, 02:52 PM   #2
Alien_Hominid
Senior Member
 
Registered: Oct 2005
Location: Lithuania
Distribution: Hybrid
Posts: 2,247

Rep: Reputation: 53
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/

Last edited by Alien_Hominid; 11-29-2007 at 02:53 PM.
 
Old 11-29-2007, 05:11 PM   #3
paulsm4
Guru
 
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Blog Entries: 1

Rep: Reputation: Disabled
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
 
Old 11-29-2007, 11:45 PM   #4
Alien_Hominid
Senior Member
 
Registered: Oct 2005
Location: Lithuania
Distribution: Hybrid
Posts: 2,247

Rep: Reputation: 53
Quote:
Originally Posted by paulsm4 View Post
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?
 
Old 11-30-2007, 01:42 AM   #5
paulsm4
Guru
 
Registered: Mar 2004
Distribution: SusE 8.2
Posts: 5,863
Blog Entries: 1

Rep: Reputation: Disabled
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
 
Old 11-30-2007, 05:47 AM   #6
jay73
Guru
 
Registered: Nov 2006
Location: Belgium
Distribution: Ubuntu 11.04, Debian testing
Posts: 5,019

Rep: Reputation: 130Reputation: 130
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.
 
Old 11-30-2007, 06:12 AM   #7
terrio
LQ Newbie
 
Registered: Jan 2007
Location: Halifax, NS
Distribution: Linux Mint 11
Posts: 29

Rep: Reputation: 15
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.
 
Old 11-30-2007, 08:11 AM   #8
enemorales
Member
 
Registered: Jul 2004
Location: Santiago, Chile
Distribution: Ubuntu
Posts: 410

Original Poster
Rep: Reputation: 30
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!!

Last edited by enemorales; 11-30-2007 at 08:14 AM. Reason: typo
 
Old 11-30-2007, 10:59 AM   #9
terrio
LQ Newbie
 
Registered: Jan 2007
Location: Halifax, NS
Distribution: Linux Mint 11
Posts: 29

Rep: Reputation: 15
Quote:
terrio. How does the semaphore work? Is it possible to block only one element in the array?
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.
 
Old 11-30-2007, 11:24 AM   #10
Alien_Hominid
Senior Member
 
Registered: Oct 2005
Location: Lithuania
Distribution: Hybrid
Posts: 2,247

Rep: Reputation: 53
I think you can synchronize access to array.
 
  


Reply

Tags
java, threads


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Accessing perl array rjcrews Programming 5 11-08-2006 07:16 PM
Bash Scripting - Accessing Array Indices Jus144tice Programming 6 10-22-2006 09:20 PM
Help accessing data on NTFS raid array Qwindelzorf Linux - Hardware 2 01-15-2005 02:34 PM
Java help (accessing array elemonts from another class or method) Tru_Messiah Programming 6 05-14-2004 09:20 AM
PHP: accessing unnamed array mrtwice Programming 8 04-28-2004 11:14 AM


All times are GMT -5. The time now is 01:54 AM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration