Prev: adding a new library .jar to your path (netbeans)
Next: Turning off JIT Optimisation
From: markspace on 29 May 2010 16:31
blmblm(a)myrealbox.com wrote:
>
> somewhat related
> point is that limiting the number of threads to the number of
> available processors/cores,


This doesn't work, at least given the algorithms above.

I tried this, long ago, when Java first started tinkering around with
replacing the current merge-sort with a Tim-sort. A multi-threaded
merge- or quicksort seemed like just the thing to beat any single
threaded solution. Alas, it was not to be.

The up shot is that these algorithms here wait() on a child thread. And
if you limit your total threads... then you spawn two sub-threads, they
spawn four sub-tasks... which need threads... which they can't get
because the the two threads are still consumed by waiting.

Trust me, limited thread pools locks up hard.

Having CPU time and having a Thread are two different things. You could
program around this by having the threads NOT wait... they'd need some
sort of completion task... but now you are getting a lot of tasks
running in lots of threads. The overhead is high, and I couldn't get
the overhead down low enough to beat the supplied single-threaded merge
sort.

At some point you to admit that really robust, fast sorting is a hard
enough problem that you don't want to re-invent it, and leave it to the
Java folks to implement. If Jon (the OP) can beat his head against it
and devise a solution, then great. I don't have the time to actually
track down every possible solution and test them all out sufficiently.
From: blmblm on 29 May 2010 17:30
In article <htrtio$lmp$1(a)news.eternal-september.org>,
markspace <nospam(a)nowhere.com> wrote:
> blmblm(a)myrealbox.com wrote:
> >
> > somewhat related
> > point is that limiting the number of threads to the number of
> > available processors/cores,
>
>
> This doesn't work, at least given the algorithms above.
>
> I tried this, long ago, when Java first started tinkering around with
> replacing the current merge-sort with a Tim-sort. A multi-threaded
> merge- or quicksort seemed like just the thing to beat any single
> threaded solution. Alas, it was not to be.
>
> The up shot is that these algorithms here wait() on a child thread. And
> if you limit your total threads... then you spawn two sub-threads, they
> spawn four sub-tasks... which need threads... which they can't get
> because the the two threads are still consumed by waiting.
>
> Trust me, limited thread pools locks up hard.

I must be misunderstanding something ....

I have code for mergesort and quicksort that works as follows ....

The sort method takes an extra argument numThreads saying how many
threads are to be used.

If numThreads is more than 1, the code launches a new thread for
one of the two recursive calls to the method, passing it numThreads/2,
while the original thread first executes the other recursive call
(with numThreads-(numThreads/2)) and then waits for the launched
thread to complete.

If numThreads is not more than 1, the two recursive calls are
executed as they would be in sequential code.

I can't imagine how this could lock up. What am I not getting?

> Having CPU time and having a Thread are two different things. You could
> program around this by having the threads NOT wait... they'd need some
> sort of completion task... but now you are getting a lot of tasks
> running in lots of threads. The overhead is high, and I couldn't get
> the overhead down low enough to beat the supplied single-threaded merge
> sort.
>
> At some point you to admit that really robust, fast sorting is a hard
> enough problem that you don't want to re-invent it, and leave it to the
> Java folks to implement. If Jon (the OP) can beat his head against it
> and devise a solution, then great. I don't have the time to actually
> track down every possible solution and test them all out sufficiently.

Oh sure. But I've had a lot of fun writing different multithreaded
sorts, and I think there's some pedagogical value as well. Not to
mention the fun of then trying to turn my Java solutions into C with
OpenMP .... (The multithreaded parts are actually, in my opinion,
noticeably easier in OpenMP. Anything involving dynamically-allocated
memory, though, is .... "more trouble" is maybe the way to say it.)

--
B. L. Massingill
ObDisclaimer: I don't speak for my employers; they return the favor.
First  |  Prev  | 
Pages: 1 2 3
Prev: adding a new library .jar to your path (netbeans)
Next: Turning off JIT Optimisation