Why does this code not see any significant performance gain when I use multiple threads on a quadcore machine?

I wrote some Java code to learn more about the Executor framework.

Specifically, I wrote code to verify the Collatz Hypothesis - this says that if you iteratively apply the following function to any integer, you get to 1 eventually:

f(n) = ((n % 2) == 0) ? n/2 : 3*n + 1

CH is still unproven, and I figured it would be a good way to learn about Executor. Each thread is assigned a range [l,u] of integers to check.

Specifically, my program takes 3 arguments - N (the number to which I want to check CH), RANGESIZE (the length of the interval that a thread has to process), and NTHREAD, the size of the threadpool.

My code works fine, but I saw much less speedup that I expected - of the order of 30% when I went from 1 to 4 threads.

My logic was that the computation is completely CPU bound, and each subtask (checking CH for a fixed size range) is takes roughly the same time.

Does anyone have ideas as to why I'm not seeing a 3 to 4x increase in speed?

If you could report your runtimes as you increase the number of thread (along with the machine, JVM and OS) that would also be great.

Specifics

Runtimes:

java -d64 -server -cp . Collatz 10000000 开发者_如何学Go1000000 4 => 4 threads, takes 28412 milliseconds

java -d64 -server -cp . Collatz 10000000 1000000 1 => 1 thread, takes 38286 milliseconds

Processor:

Quadcore Intel Q6600 at 2.4GHZ, 4GB. The machine is unloaded.

Java:

java version "1.6.0_15" Java(TM) SE Runtime Environment (build 1.6.0_15-b03) Java HotSpot(TM) 64-Bit Server VM (build 14.1-b02, mixed mode)

OS:

Linux quad0 2.6.26-2-amd64 #1 SMP Tue Mar 9 22:29:32 UTC 2010 x86_64 GNU/Linux

Code: (I can't get the code to post, I think it's too long for SO requirements, the source is available on Google Docs

import java.math.BigInteger;
import java.util.Date;
import java.util.List;
import java.util.ArrayList;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

class MyRunnable implements Runnable {
  public int lower;
  public int upper;

  MyRunnable(int lower, int upper) {
    this.lower = lower;
    this.upper = upper;
  }

  @Override
  public void run() {
    for (int i = lower ; i <= upper; i++ ) {
      Collatz.check(i);
    }
    System.out.println("(" + lower + "," + upper + ")" );
  }
}


public class Collatz {

  public static boolean check( BigInteger X ) {
    if (X.equals( BigInteger.ONE ) ) {
      return true;
    } else if ( X.getLowestSetBit() == 1 ) { 
      // odd
      BigInteger Y = (new BigInteger("3")).multiply(X).add(BigInteger.ONE);
      return check(Y);
    } else {
      BigInteger Z = X.shiftRight(1); // fast divide by 2
      return check(Z);
    }
  }

  public static boolean check( int x ) {
    BigInteger X = new BigInteger( new Integer(x).toString() );
    return check(X);
  }

  static int N = 10000000;
  static int RANGESIZE = 1000000;
  static int NTHREADS = 4;

  static void parseArgs( String [] args ) {

    if ( args.length >= 1 ) {
      N = Integer.parseInt(args[0]);
    }
    if ( args.length >= 2 ) {
      RANGESIZE = Integer.parseInt(args[1]);
    }
    if ( args.length >= 3 ) {
      NTHREADS = Integer.parseInt(args[2]);
    }
  }

  public static void maintest(String [] args ) {
    System.out.println("check(1): " + check(1));
    System.out.println("check(3): " + check(3));
    System.out.println("check(8): " + check(8));
    parseArgs(args);
  }

  public static void main(String [] args) {
    long lDateTime = new Date().getTime();
    parseArgs( args );
    List<Thread> threads = new ArrayList<Thread>();
    ExecutorService executor = Executors.newFixedThreadPool( NTHREADS );
    for( int i = 0 ; i < (N/RANGESIZE); i++) {
      Runnable worker = new MyRunnable( i*RANGESIZE+1, (i+1)*RANGESIZE );
      executor.execute( worker );
    }
    executor.shutdown();
    while (!executor.isTerminated() ) {
    }
    System.out.println("Finished all threads");
    long fDateTime = new Date().getTime();
    System.out.println("time in milliseconds for checking to " + N + " is " + 
                            (fDateTime - lDateTime )  + 
                            " (" + N/(fDateTime - lDateTime ) + " per ms)" );
  }
}

Busy waiting can be a problem:

while (!executor.isTerminated() ) { 
} 

You can use awaitTermination() instead:

while (!executor.awaitTermination(1, TimeUnit.SECONDS)) {}

You are using BigInteger. It consumes a lot of register space. What you most likely have on the compiler level is register spilling that makes your process memory-bound.

Also note that when you are timing your results you are not taking into account extra time taken by the JVM to allocate threads and work with the thread pool.

You could also have memory conflicts when you are using constant Strings. All strings are stored in a shared string pool and so it may become a bottleneck, unless java is really clever about it.

Overall, I wouldn't advise using Java for this kind of stuff. Using pthreads would be a better way to go for you.

As @axtavt answered, busy waiting can be a problem. You should fix that first, as it is part of the answer, but not all of it. It won't appear to help in your case (on Q6600), because it seems to be bottlenecked at 2 cores for some reason, so another is available for the busy loop and so there is no apparent slowdown, but on my Core i5 it speeds up the 4-thread version noticeably.

I suspect that in the case of the Q6600 your particular app is limited by the amount of shared cache available or something else specific to the architecture of that CPU. The Q6600 has two 4MB L2 caches, which means CPUs are sharing them, and no L3 cache. On my core i5, each CPU has a dedicated L2 cache (256K, then there is a larger 8MB shared L3 cache. 256K more per-CPU cache might make a difference... otherwise something else architecture wise does.

Here is a comparison of a Q6600 running your Collatz.java, and a Core i5 750.

On my work PC, which is also a Q6600 @ 2.4GHz like yours, but with 6GB RAM, Windows 7 64-bit, and JDK 1.6.0_21* (64-bit), here are some basic results:

• 10000000 500000 1 (avg of three runs): 36982 ms
• 10000000 500000 4 (avg of three runs): 21252 ms

Faster, certainly - but not completing in quarter of the time like you would expect, or even half... (though it is roughly just a bit more than half, more on that in a moment). Note in my case I halved the size of the work units, and have a default max heap of 1500m.

At home on my Core i5 750 (4 cores no hyperthreading), 4GB RAM, Windows 7 64-bit, jdk 1.6.0_22 (64-bit):

• 10000000 500000 1 (avg of 3 runs) 32677 ms
• 10000000 500000 4 (avg of 3 runs) 8825 ms
• 10000000 500000 4 (avg of 3 runs) 11475 ms (without the busy wait fix, for reference)

the 4 threads version takes 27% of the time the 1 thread version takes when the busy-wait loop is removed. Much better. Clearly the code can make efficient use of 4 cores...

• NOTE: Java 1.6.0_18 and later have modified default heap settings - so my default heap size is almost 1500m on my work PC, and around 1000m on my home PC.

You may want to increase your default heap, just in case garbage collection is happening and slowing your 4 threaded version down a bit. It might help, it might not.

At least in your example, there's a chance your larger work unit size is skewing your results slightly...halving it may help you get closer to at least 2x the speed since 4 threads will be kept busy for a longer portion of the time. I don't think the Q6600 will do much better at this particular task...whether it is cache or some other inherent architecture thing.

In all cases, I am simply running "java Collatz 10000000 500000 X", where x = # of threads indicated.

The only changes I made to your java file were to make one of the println's into a print, so there were less linebreaks for my runs with 500000 per work unit so I could see more results in my console at once, and I ditched the busy wait loop, which matters on the i5 750 but didn't make a difference on the Q6600.

You can should try using the submit function and then watching the Future's that are returning checking them to see if the thread has finished.

Terminate doesn't return until there is a shutdown.

Future submit(Runnable task) Submits a Runnable task for execution and returns a Future representing that task.

isTerminated() Returns true if all tasks have completed following shut down.

Try this...

public static void main(String[] args) {
    long lDateTime = new Date().getTime();
    parseArgs(args);
    List<Thread> threads = new ArrayList<Thread>();
    List<Future> futures = new ArrayList<Future>();

    ExecutorService executor = Executors.newFixedThreadPool(NTHREADS);
    for (int i = 0; i < (N / RANGESIZE); i++) {
        Runnable worker = new MyRunnable(i * RANGESIZE + 1, (i + 1) * RANGESIZE);
        futures.add(executor.submit(worker));
    }
    boolean done = false;
    while (!done) {
        for(Future future : futures) {
            done = true;
            if( !future.isDone() ) {
                done = false;
                break;
            }
        }
        try {
            Thread.sleep(100);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    System.out.println("Finished all threads");
    long fDateTime = new Date().getTime();
    System.out.println("time in milliseconds for checking to " + N + " is " +
            (fDateTime - lDateTime) +
            " (" + N / (fDateTime - lDateTime) + " per ms)");
    System.exit(0);
}