是否有任何“阈值”可以证明多线程计算的合理性？

基本上，今天我需要优化这段代码。它试图找到由某个函数为前一百万个起始数字产生的最长序列：

public static void main(String[] args) {
    int mostLen = 0;
    int mostInt = 0;
    long currTime = System.currentTimeMillis();
    for(int j=2; j<=1000000; j++) {
        long i = j;
        int len = 0;
        while((i=next(i)) != 1) {
            len++;
        }
        if(len > mostLen) {
            mostLen = len;
            mostInt = j;
        }
    }
    System.out.println(System.currentTimeMillis() - currTime);
    System.out.println("最长序列长度为 " + mostLen + " 对应的数字为 " + mostInt);
}
static long next(long i) {
    if(i%2==0) {
        return i/2;
    } else {
        return i*3+1;
    }
}

我的错误在于尝试引入多线程：

void doSearch() throws ExecutionException, InterruptedException {
    final int numProc = Runtime.getRuntime().availableProcessors();
    System.out.println("numProc = " + numProc);
    ExecutorService executor = Executors.newFixedThreadPool(numProc);
    long currTime = System.currentTimeMillis();
    List> list = new ArrayList>();
    for (int j = 2; j <= 1000000; j++) {
        MyCallable worker = new MyCallable();
        worker.setBean(new ValueBean(j, 0));
        Future f = executor.submit(worker);
        list.add(f);
    }
    System.out.println(System.currentTimeMillis() - currTime);
    int mostLen = 0;
    int mostInt = 0;
    for (Future f : list) {
        final int len = f.get().getLen();
        if (len > mostLen) {
            mostLen = len;
            mostInt = f.get().getNum();
        }
    }
    executor.shutdown();
    System.out.println(System.currentTimeMillis() - currTime);
    System.out.println("最长序列长度为 " + mostLen + " 对应的数字为 " + mostInt);
}
public class MyCallable implements Callable {
    public ValueBean bean;
    public void setBean(ValueBean bean) {
        this.bean = bean;
    }
    public ValueBean call() throws Exception {
        long i = bean.getNum();
        int len = 0;
        while ((i = next(i)) != 1) {
            len++;
        }
        return new ValueBean(bean.getNum(), len);
    }
}
public class ValueBean {
    int num;
    int len;
    public ValueBean(int num, int len) {
        this.num = num;
        this.len = len;
    }
    public int getNum() {
        return num;
    }
    public int getLen() {
        return len;
    }
}
long next(long i) {
    if (i % 2 == 0) {
        return i / 2;
    } else {
        return i * 3 + 1;
    }
}

不幸的是，多线程版本在4个处理器（核心）上的运行速度比单线程版本慢了5倍。

然后我尝试了一种更简单的方法：

static int mostLen = 0;
static int mostInt = 0;
synchronized static void updateIfMore(int len, int intgr) {
    if (len > mostLen) {
        mostLen = len;
        mostInt = intgr;
    }
}
public static void main(String[] args) throws InterruptedException {
    long currTime = System.currentTimeMillis();
    final int numProc = Runtime.getRuntime().availableProcessors();
    System.out.println("numProc = " + numProc);
    ExecutorService executor = Executors.newFixedThreadPool(numProc);
    for (int i = 2; i <= 1000000; i++) {
        final int j = i;
        executor.execute(new Runnable() {
            public void run() {
                long l = j;
                int len = 0;
                while ((l = next(l)) != 1) {
                    len++;
                }
                updateIfMore(len, j);
            }
        });
    }
    executor.shutdown();
    executor.awaitTermination(30, TimeUnit.SECONDS);
    System.out.println(System.currentTimeMillis() - currTime);
    System.out.println("最长序列长度为 " + mostLen + " 对应的数字为 " + mostInt);
}
static long next(long i) {
    if (i % 2 == 0) {
        return i / 2;
    } else {
        return i * 3 + 1;
    }
}

它运行速度快得多，但仍然比单线程方法慢。

我希望这不是因为我搞砸了多线程的方式，而是因为这个特定的计算/算法不适合并行计算。如果我通过将方法next替换为更加处理器密集型的计算来改变计算方式：

long next(long i) {
    Random r = new Random();
    for(int j=0; j<10; j++) {
        r.nextLong();
    }
    if (i % 2 == 0) {
        return i / 2;
    } else {
        return i * 3 + 1;
    }
}

两个多线程版本在4核机器上的执行速度开始超过单线程版本的两倍以上。

因此，显然必须有一个阈值可以用来确定是否值得引入多线程进行优化（而不需要花费精力去实现它）。

我的问题是：

有哪些基本规则可以帮助决定给定的计算是否足够密集，以便通过并行计算进行优化？