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

Question

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 1000000 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)" );
  }
}

Answer 1

Busy waiting can be a problem:

while (!executor.isTerminated() ) { 
} 

You can use awaitTermination() instead:

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

Answer 2

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.