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

Dr Heinz M. Kabutz heinz at javaspecialists.eu
Mon Nov 21 18:17:07 EST 2011


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=-
>
>   


More information about the Concurrency-interest mailing list