Java – why doesn’t this code see any significant performance improvement when using multiple threads on a quad core machine?

I wrote some java code to learn more about the executor framework

Specifically, I wrote code to verify Collatz hypothesis – which means that if you iteratively apply the following function to any integer, you end up with 1:

f(n)=((n％2)== 0)？ n / 2：3 * n 1

Ch is still unproven, and I think it will be a good way to know the executives Each thread is assigned a range of integers to check [l, u]

Specifically, my program needs three parameters - n (I want to check the number of CH), rangesize (the length of the interval that the thread must process), and nthread is the size of the thread pool

My code works well, but when I go from 1 to 4 threads, I see a much lower acceleration - in the order of 30%

My logic is that the calculation is completely CPU limited, and each subtask (checking a fixed size range of CH) takes approximately the same time

What do some people think? Why don't I see a growth rate of 3 to 4 times?

If you can increase the number of threads (along with the machine, JVM and operating system), you can also report your running time

details

Runtime:

Java - d64 - server - CP. Collatz 10000000 4 = > 4 threads, 28412 MS required

Java - d64 - server - CP. Collatz 10000000 1000000 1 = > 1 thread, 38286 MS required

Processor:

Quadcore Intel Q6600,2.4GHZ,4GB. Machine unloading

Java:

Java version "1.6.0_15" Java (TM) se runtime environment (build 1.6.0_15-b03) Java hotspot (TM) 64 bit server virtual machine (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 release. I think the so requirement is too long. The source code 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)" );
  }
}

Solution

Busy waiting can be a problem:

while (!executor.isTerminated() ) { 
}

You can use awaittermination():

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