Athen
journeyman
Reged: 06/05/07
Posts: 79
Loc: San Francisco, CA
|
|
Brain wrote:
the article is just wrong.
A missed an opportunity about the real value of multicore machines and java.
that is most certainly to sort big arrays faster.
|
Kirill_Grouchnikov
stranger
Reged: 10/01/07
Posts: 3
|
|
Brian,
What is so wrong in using the available computing power to speed up an inherently parallelizable task? If you have two tasks, then you can run them on two processors. If you have one task and you can perform it faster by splitting it between available cores, why not do it?
Thanks
Kirill
|
Andrey
Unregistered
|
|
Hello Kiril.
I have a few questions here.
1) What is the point of creating two additional threads? Why two? why not four? or just one since you already have the main thread (that initiate sorting).
2) Have you considered memory overhead?
Merge sort has one significant drawback - it is recursive and therefore it involves additional memory overhead for recursion stack. It make it inappropriate for sorting BIG arrays. You had rather use Heapsort [1]. Your way of scaling aggravate the situation as each thread has its own stack. If you had found a way of scaling of Heapsort it whoud have been VERY cool.
3) Is there any guaranty that your threads will be scheduled on different cores? What if the they will be executed by the same core while the other will be executing something else? (I suppose there will be a lot of threads if you will follow the same way of scaling programs).
I think we must avoid sharing objects between threads. Idealy conncurent systems should share nothing between executing units. Something we have in Erlang [2]
[1] http://en.wikipedia.org/wiki/Heapsort
[2] http://www.ibm.com/developerworks/java/library/j-cb04186.html
|
Kirill_Grouchnikov
stranger
Reged: 10/01/07
Posts: 3
|
|
Andrey,
1. As mentioned in the article, this is a simple implementation that doesn't take advantage of all the available cores / processors. In addition, there is indeed no need for two new threads, and as shown in the comments on my blog [1], you can create one additional thread and split the work between the current thread and the new thread.
2. You're right.
3. Here i rely on the JVM to schedule the sub threads on available cores. When i run this code on my dual core laptop, i see that both cores are at 100% which indicates that the worker threads are scheduled correctly. When i run the usual Arrays.sort sorting, only one core is at 100% and another is at 10-15%.
This specific algorithm doesn't require that data is not shared between the threads, since each one is working on its own slice. For more complicated algorithms, you'll pay the penalty of guarding the data. In addition, if the subtasks need to communicate, you'll pay for that as well.
Thanks for the comments.
Kirill
[1] http://www.pushing-pixels.org/?p=142
|
Previous
Index
Next
Threaded
Edit
Reply
Quote
