7

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

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("Most len is " + mostLen + " for " + 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<Future<ValueBean>> list = new ArrayList<Future<ValueBean>>();
    for (int j = 2; j <= 1000000; j++) {
        MyCallable<ValueBean> worker = new MyCallable<ValueBean>();
        worker.setBean(new ValueBean(j, 0));
        Future<ValueBean> f = executor.submit(worker);
        list.add(f);
    }
    System.out.println(System.currentTimeMillis() - currTime);

    int mostLen = 0;
    int mostInt = 0;
    for (Future<ValueBean> 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("Most len is " + mostLen + " for " + mostInt);
}

public class MyCallable<T> implements Callable<ValueBean> {
    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("Most len is " + mostLen + " for " + 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 核机器上的执行速度都比单线程版本快两倍以上。

很明显，必须有一些阈值可以用来确定是否值得引入多线程，我的问题是：

有助于确定给定计算是否足够密集以通过并行运行对其进行优化的基本规则是什么（无需花费精力来实际实现它？）

4

4 回答 4

4

高效实现多线程的关键是确保成本不会太高。没有固定的规则，因为它们在很大程度上取决于您的硬件。

启动和停止线程的成本很高。当然，您已经使用了 executor 服务，这大大降低了这些成本，因为它使用一堆工作线程来执行您的 Runnables。然而，每个 Runnable 仍然会带来一些开销。减少 runnable 的数量并增加每个必须做的工作量将提高性能，但您仍然希望为 executor 服务提供足够的 runnable，以便有效地将它们分布在工作线程上。

您选择为每个起始值创建一个可运行文件，因此您最终创建了 1000000 个可运行文件。如果让每个 Runnable 执行一批比如 1000 个起始值，您可能会得到更好的结果。这意味着您只需要 1000 个可运行文件，从而大大降低了开销。

于 2012-05-22T05:35:10.250 回答
2

“性能增益会大于上下文切换和线程创建的成本吗？”

这是非常依赖于操作系统、语言和硬件的成本；这个问题有一些关于Java成本的讨论，但有一些数字和一些关于如何计算成本的指针。

对于 CPU 密集型工作，您还希望每个 CPU 有一个线程或更少线程。感谢 David Harkness 提供了关于如何计算该数字的线索。

于 2012-05-22T05:24:57.710 回答
2

我认为您没有考虑到另一个组件。当工作单元彼此不依赖时，并行化效果最好。当后面的计算结果依赖于前面的计算结果时，并行运行计算是次优的。在“我需要第一个值来计算第二个值”的意义上，这种依赖性可能很强。在这种情况下，任务是完全串行的，如果不等待早期的计算，就无法计算后面的值。在“如果我有第一个值，我可以更快地计算第二个值”的意义上，也可能存在较弱的依赖性。在这种情况下，并行化的代价是一些工作可能会重复。

这个问题有助于在不使用多线程的情况下进行优化，因为如果您已经掌握了先前的结果，则可以更快地计算一些后面的值。举个例子j == 4。一旦通过内部循环产生i == 2，但您刚刚计算了j == 2两次迭代的结果，如果您保存了 的值，len您可以将其计算为 len(4) = 1 + len(2)。

使用一个数组来存储之前计算的值，len并在方法中稍微调整一下next，您可以以 > 50 倍的速度完成任务。

于 2012-05-22T07:13:54.187 回答
1

估计一个线程在不与其他线程交互（直接或通过公共数据）的情况下可以完成的工作量。如果那件工作可以在 1 微秒或更短的时间内完成，那么开销就太大了，多线程是没有用的。如果是 1 毫秒或更长，多线程应该可以正常工作。如果介于两者之间，则需要进行实验测试。

于 2012-05-22T06:48:48.733 回答