[concurrency-interest] A beginner question (on fork-and-join)

David Harrigan dharrigan at gmail.com
Mon Nov 21 18:20:32 EST 2011


Hi Everyone,

I would like to thank everyone for their generous and kind answers to
my question. I'll try out the few suggestions offered so far and see
the results I get. This is most fun! :-)

Thanks again!.

-=david=-

On 21 November 2011 23:17, Dr Heinz M. Kabutz <heinz at javaspecialists.eu> wrote:
> Hi David,
>
> you are lucky that you have such a good machine to test on - I have an older
> MBP with an Intel Core 2 Duo which has 2 cores, it performs MUCH worse using
> the parallel search algorithm than the sequential one.
>
> Each of your tasks is too small.  You are basically just doing a search
> through a list that is at most 100 elements long.  If you give each thread
> more work, you will manage to get the parallel to be faster than the
> sequential.
>
> The biggest bottleneck in your test is context switching.  You can see that
> if you look at the task manager, most of the time is spent in system time.
>
> Personally, I have yet to find a really compelling example that shows how
> the parallel recursive algorithm improves performance.  I'm sure there must
> be some out there, such as some forms of sorting.  In your case, I would
> much rather use the CompletionService to get the answer back as soon as it
> is available.  In other words, something like this:
>
>  protected void doInParallel(final List<First> firsts) {
>   ExecutorService pool = Executors.newFixedThreadPool(
>       Runtime.getRuntime().availableProcessors()
>   );
>   CompletionService<Boolean> service = new
> ExecutorCompletionService<>(pool);
>   int submittedJobs = 0;
>   for (final First first : firsts) {
>     service.submit(new Callable<Boolean>() {
>       public Boolean call() throws Exception {
>         for (Second second : first.getSeconds()) {
>           final List<Third> thirds = second.getThirds();
>           for (Third third : thirds) {
>             if (third.getValue() == Main.NUMBER) {
>               return true;
>             }
>           }
>         }
>         return false;
>       }
>     });
>     submittedJobs++;
>   }
>   for (int i = 0; i < submittedJobs; i++) {
>     try {
>       if (service.take().get()) break;
>     } catch (Exception e) {
>       e.printStackTrace();
>     }
>   }
>   pool.shutdown();
>   return;
>  }
>
>
> I reduced the number of Thirds and also the call count, and got the
> following results on a dual-processor machine:
>
> Generating some data...done!
> Sequential
> Simon Stopwatch: total 14.7 s, counter 500, max 126 ms, min 25.3 ms, mean
> 29.3 ms [sequential INHERIT]
> Parallel
> Simon Stopwatch: total 15.0 s, counter 500, max 72.0 ms, min 25.6 ms, mean
> 29.9 ms [parallel INHERIT]
>
> On your machine you should see significant performance gains in the parallel
> vs sequential version.
>
> Regards
>
> Heinz
> --
> Dr Heinz M. Kabutz (PhD CompSci)
> Author of "The Java(tm) Specialists' Newsletter"
> Sun Java Champion
> IEEE Certified Software Development Professional
> http://www.javaspecialists.eu
> Tel: +30 69 72 850 460
> Skype: kabutz
>
>
> On 11/21/11 11:15 PM, David Harrigan wrote:
>>
>> Hi Everyone,
>>
>> I'm learning about the fork and join framework in JDK7 and to test it
>> out I wrote a little program that tries to find a number at the end of
>> a list with 50,000 elements.
>> What puzzles me is when I run the "find" in a sequential fashion, it
>> returns faster than if I use a fork-and-join implementation. I'm
>> running each "find" 5000 times
>> so as to "warm" up the JVM. I've got a timing listed below:
>>
>> Generating some data...done!
>> Sequential
>> Simon Stopwatch: total 1015 s, counter 5000, max 292 ms, min 195 ms,
>> mean 203 ms [sequential INHERIT]
>> Parallel
>> Simon Stopwatch: total 1352 s, counter 5000, max 4.70 s, min 243 ms,
>> mean 270 ms [parallel INHERIT]
>>
>> (some runtime information)
>>
>> openjdk version "1.7.0-ea"
>> OpenJDK Runtime Environment (build 1.7.0-ea-b215)
>> OpenJDK 64-Bit Server VM (build 21.0-b17, mixed mode)
>>
>> 2.66Mhz Intel Core i7 with 8GB RAM (256KB L2 cache per core (4 cores)
>> and 4MB L3 cache) running on a MBP (Lion 10.7.2)
>>
>> Forgive my ignorance but this type of programming is still quite new
>> to me and I'm obviously doing something wrong, but I don't know what.
>> My suspicion is
>> something to do with spinning up and down threads and the overhead
>> that entails. I've posted the src here http://pastebin.com/p96R24R0.
>>
>> My sincere apologies if this list is not appropriate for this posting,
>> if so I would welcome a pointer on where I can find more information
>> to help me understand
>> better the behaviour of my program when using F&J.
>>
>> I thought that by using F&J I would be able to find the answer quicker
>> than doing the searching sequentially, perhaps I've choosen a wrong
>> initial problem to
>> test this out (something that is suited to a sequential search and not
>> a parallel search?)
>>
>> Thank you all in advance.
>>
>> -=david=-
>>
>>



-- 
I prefer encrypted and signed messages. KeyID: B20A22F9
Fingerprint: 110A F423 3647 54E2 880F ADAD 1C52 85BF B20A 22F9

"It is not usually until you've built and used a version of the
program that you understand the issues well enough to get the design
right." - Rob Pike, Brian Kernighan.

No trees were harmed in the sending of this message, however, a number
of electrons were inconvenienced.



More information about the Concurrency-interest mailing list