Prev: add authorization header (user/password) before sendRedirect
Next: catch native crash
From: Roedy Green on 8 Dec 2009 20:53
On Sat, 5 Dec 2009 09:19:40 -0800 (PST), neuneudr(a)yahoo.fr wrote,
quoted or indirectly quoted someone who said :

>To me you can't simply spawn thread and pass them
>a reference to an [] and indexes and tell it "go ahead,
>swap and re-arrange the [] as you like" and hope that
>changes are going to be visible. Java makes no such
>guarantees right!?

I think the trick is the different threads, because of the way
Quicksort works, never touch the same parts of the array. Thus there
is no need for synchronisation.

--
Roedy Green Canadian Mind Products
http://mindprod.com
The future has already happened, it just isn�t evenly distributed.
~ William Gibson (born: 1948-03-17 age: 61)
From: Roedy Green on 8 Dec 2009 20:55
On Sat, 5 Dec 2009 09:28:20 -0800 (PST), neuneudr(a)yahoo.fr wrote,
quoted or indirectly quoted someone who said :

>
>Is the synchronization on the mutex at the end of each
>sort enough to guarantee that changes made to the array
>are indeed visible? (and hence guaranteed to work seen
>that due to quicksort's nature we're sure each thread
>is working on a different part of the array)?

you could instrument the code in your Comparator too see if any other
threads would interfere.
--
Roedy Green Canadian Mind Products
http://mindprod.com
The future has already happened, it just isn�t evenly distributed.
~ William Gibson (born: 1948-03-17 age: 61)
From: Kevin McMurtrie on 9 Dec 2009 04:09
In article
<a27534d9-2925-4ee6-83f0-3bbde23e83ea(a)1g2000vbm.googlegroups.com>,
neuneudr(a)yahoo.fr wrote:

> Hi all,
>
> On Oreilly's website there's a column about implementing
> multi-threaded algoriths, with an example of quicksort in Java.
>
> I'm scratching my head on someting...
>
> May Column: Multi-threaded Algorithm Implementations
>
> http://broadcast.oreilly.com/2009/06/may-column-multithreaded-algor.html
>
> I read the column and thought "that ain't working", then downloaded
> the code.
>
> Here's the array to be sorted:
>
> /** Elements to be sorted. */
> @SuppressWarnings("unchecked")
> final Comparable[] ar;
>
> So it's a regular array.
>
> I fail to see what guarantees are made in the sorting code
> that swaps made by spawned threads are visible to someone
> who would be observing the [].
>
> Say we have 8,7,6,5,4,3,2,1 and the code makes the swaps
> in the array and as now 4,3,2,1,8,7,6,5 and asks to two threads
> to take care respectively of the 4,3,2,1 part and the 8,7,6,5 part.
>
> I agree that the spawned threads are going to see correctly what
> they should. But what guarantee are there that an observer will
> indeed see the array sorted at the end?
>
> To me to work the code needs to be changed, the following
> doesn't seem correct:
>
> final Comparable[] ar;
>
> I'd replace it with:
>
> final AtomicReferenceArray<Comparable> ar;
>
> To me you can't simply spawn thread and pass them
> a reference to an [] and indexes and tell it "go ahead,
> swap and re-arrange the [] as you like" and hope that
> changes are going to be visible. Java makes no such
> guarantees right!?
>
> While a AtomiceReferenceArray it's guaranteed to work,
> but it incurs a performance hit compare to the [] version.
>
> But then I guess I don't understand anything about the Java
> memory model nor about the code posted (there a tiny code.zip
> file, once you keep only the .java files related to quicksort
> it's tiny).
>
> Thoughts?

The synchronized block syncs up everything - local caches in the
compiled code of the current thread and CPU caches. However, not having
a synchronized block doesn't mean that everything is running
independently at full speed. Some CPUs do automatic syncing of memory
blocks in their internal caches at great cost to performance. You don't
want multiple cores working on adjacent memory.


George T. Heineman's implementation in his blog is suspect. If he
really is using a spin lock on a long task he needs to be booted out of
the O'Reilly community. I don't have his full source code so I'll use
another example.

To modify this code:
http://www.cs.princeton.edu/introcs/42sort/QuickSort.java.html

First, delete the two static counter variables used for debugging. They
can not perform well with multiple threads.

Second, modify the nested quicksort to put the left sub-sort on a thread
if there are many values and not too much threaded recursion. The right
sub-sort will be calculated by the current thread. Make sure the left
thread finishes before leaving the method.

That's the basics of it. It doesn't run a whole lot faster in this
simple case because it's mostly memory-bound. Real-world cases with
complex comparison methods should perform much better.

public static void quicksort(double[] a)
{
shuffle(a); // to guard against worst-case
quicksort(a, 0, a.length - 1, 0);
}

static void quicksort(final double[] a,
final int left,
final int right,
final int tdepth)
{
if (right <= left)
return;
final int i = partition(a, left, right);

if ((tdepth < 4) && ((i - left) > 1000))
{
final Thread t = new Thread()
{
public void run()
{
quicksort(a, left, i - 1, tdepth + 1);
}
};
t.start();
quicksort(a, i + 1, right, tdepth + 1);

try
{
t.join();
}
catch (InterruptedException e)
{
throw new RuntimeException("Cancelled", e);
}
} else
{
quicksort(a, left, i - 1, tdepth);
quicksort(a, i + 1, right, tdepth);
}
}
--
I won't see Goolge Groups replies because I must filter them as spam
From: markspace on 9 Dec 2009 12:09
Kevin McMurtrie wrote:

> George T. Heineman's implementation in his blog is suspect.


To say the least.

> If he
> really is using a spin lock on a long task he needs to be booted out of
> the O'Reilly community.


Well, it might be that he wants to add an extra thread, so he can
include some task switching with his testing. But I agree he really
ought to explain himself here, it looks hokey as all heck.


> I don't have his full source code so I'll use
> another example.

This is the other problem. I notice at least two errors in the code he
does provide.

1. He claims that his testing uses a maximum R (the ratio) of 51 yet his
code has MAX_R set to 21.

2. He uses Comparable as a raw type. It's just so 1.4.
First  |  Prev  | 
Pages: 1 2 3
Prev: add authorization header (user/password) before sendRedirect
Next: catch native crash