Prev: add authorization header (user/password) before sendRedirect
Next: catch native crash
From: neuneudr on 5 Dec 2009 18:48
On Dec 5, 8:31 pm, Peter Duniho <NpOeStPe...(a)NnOwSlPiAnMk.com> wrote:
....
> The top-level waits on the volatile variable "helpersWorking", and since
> that variable is volatile and is modified only after the worker threads
> complete their effort and decrement the variable to 0. The use of
> "volatile" preserves ordering of the operations, ensuring the main
> thread does not return until all of the sorting has in fact been completed.

OK, I think I understand it better now...

Leaving the minor issue and the bigger performance issue aside,
then because the call to quicksort I'd make is blocking:

public void qsort (final int left, final int right) {
...
(wait on helpersWorking) [blocking here on volatile]
}

Then, because that call is blocking on that volatile, I'm
guaranteed to have the correct, sorted, array at the end
(because I'm calling it from a thread that is synchronizing
on the volatile).

Well, I may be wrong in my understanding, but that's how
I understand it now :)

Time to get out my copy of Java Concurrency In Practice,
read on CountdownLatch, and modify the example.

From the example code, apparently on thread is not just lost
monitoring the volatile variable: it's lost *busy looping* on
the variable:

while (helpersWorking > 0) { }

Sadly I only have a two-cores machine here so can't make
a lot of test but I'll still try to modify it.

Thanks a lot and don't hesitate to correct any further
misunderstanding I'm making here!



From: neuneudr on 5 Dec 2009 18:51
On Dec 5, 7:04 pm, markspace <nos...(a)nowhere.com> wrote:
> neune...(a)yahoo.fr wrote:
> > 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'm scratching my head also. Did you download the source code? I don't
> see at least one whole package of his. His package:
>
> algs.model.array
>
> just seems to be missing. It's not in the bin directory either. Broken
> code, not tested. Hmm, maybe his book isn't great too.

There's a "code.zip" included in the article. Various classes from
the package are in there (including tests/benchmarks) but maybe not
the pivot selection method.

Anyway just for testing a pivot picking lo+hi/2 is probably
sufficient.

As Peter Duniho wrote, there's one thread 'lost' monitoring the
volatile and I think it's lost busy-looping doing that, which
seems bad but not hard to fix.


From: Peter Duniho on 5 Dec 2009 19:08
neuneudr(a)yahoo.fr wrote:
> [...]
> public void qsort (final int left, final int right) {
> ...
> (wait on helpersWorking) [blocking here on volatile]
> }
>
> Then, because that call is blocking on that volatile, I'm
> guaranteed to have the correct, sorted, array at the end
> (because I'm calling it from a thread that is synchronizing
> on the volatile).
>
> Well, I may be wrong in my understanding, but that's how
> I understand it now :)

Yes, you seem to have understood my reply correctly. The read in the
main thread of the volatile variable orders the other memory reads the
main thread might make of the sorted array such that those reads are
guaranteed to take place after the writes the worker threads make.

Basically, the volatile variable creates a sort of "checkpoint" that
prevents writes from being reordered later than the write to the
variable, and reads from being reorder prior to the read from the
variable. This puts all the writes before the access of the variable
and all the reads after it.

> Time to get out my copy of Java Concurrency In Practice,
> read on CountdownLatch, and modify the example.
>
> From the example code, apparently on thread is not just lost
> monitoring the volatile variable: it's lost *busy looping* on
> the variable:
>
> while (helpersWorking > 0) { }

Right. That's my point. The mere fact that there's a thread not doing
work isn't really a problem. It's the fact that even though it's doing
no work, it's still requiring a lot of CPU time because it hasn't
stopped executing.

> Sadly I only have a two-cores machine here so can't make
> a lot of test but I'll still try to modify it.

Even with two cores, you should be able to measure the effects. If you
limit the worker thread count to 2, for example, you'll find (or should,
anyway) that the sort is only about 25% faster than not using any
threading at all (i.e. a single blocking call to sort that returns when
it's done), because you've got three threads all competing for the CPU
(two worker threads spawned by the main thread, and then the main thread
having returned from creating the worker threads, running the busy wait
until the other threads finish).

This compares to the theoretical "perfectly scaling" 50% you'd see if
there was zero thread overhead and the work is dividing perfectly.
You'll never see the full 50% reduction in time cost because of the
overhead that's necessarily there, but with a good implementation, you
should be able to get much closer to a 50% improvement than 25%.

Conversely, if you raise the thread count to something much larger, 10
or 20 for example, then that busy wait won't have as much effect, and
you should see _some_ improvement over a non-threading sort (but because
of the threads > CPU cores issue and the busy wait, the improvement will
also not be a doubling, and will also not be as good as it could be).

Actually, having only two cores, it should be easier to see the
inefficiencies in this particular implementation, because CPU contention
is easier to create and has a greater effect.

> Thanks a lot and don't hesitate to correct any further
> misunderstanding I'm making here!

No, you seem to have it. :) Besides, you've heard of the "Java
Concurrency..." book, which is a good sign. The fact that you intend to
review its contents is even better. You've got a big head start over a
lot of other people trying to write concurrent Java code. :)

Pete
From: markspace on 5 Dec 2009 19:58
neuneudr(a)yahoo.fr wrote:

> There's a "code.zip" included in the article. Various classes from
> the package are in there (including tests/benchmarks) but maybe not
> the pivot selection method.


Yes, code.zip is what I have. Unzipped it, popped it into NetBeans, got
all sorts of silly red underlining saying "package does not exist."

Oh well, I was trying to do it the easy way. I can roll my own if I
have to.

Note that there seems to be even more multi-threading stuff going into
Java 7, so you might want to hold off on that home brew all sining, all
dancing multi-threading code library:

<http://blogs.sun.com/mr/entry/closures>
From: Mike Amling on 8 Dec 2009 12:40
neuneudr(a)yahoo.fr wrote:
> re all,
>
> adding to my own question... At the end of each spawned thread,
> we can see this:
>
> new Thread () {
> public void run () {
> // invoke single-thread qsort
> qsortN (left, pivotIndex - 1);
> synchronized(helpRequestedMutex) {
> helpersWorking--;
> }
> }
> }.start();
>
> Is the synchronization on the mutex at the end of each
> sort enough to guarantee that changes made to the array
> are indeed visible?

Yes. When the code leaves the synchronized(){}, all changes made by
the running Thread get flushed to RAM, where they will become visible to
other Threads no later than when those other Threads enter a
synchronized(){}.

--Mike Amling
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: add authorization header (user/password) before sendRedirect
Next: catch native crash