java - 为什么这种并行算法比串行算法运行得更慢？

Question

顺序:

void do(List<D> d, final List<C> c) {
for (D datum : d)
    getChampoid(datum, c).tally(datum);

并行:

static final int procs = Runtime.getRuntime().availableProcessors();
static final ExecutorService pool = Executors.newFixedThreadPool(procs);
void do(List<D> d, final List<C> c) {
    List<Future> futures = new ArrayList<>();
    for (final D datum : d)
        futures.add(pool.submit(new Runnable() {

            @Override
            public void run() {
                getChampoid(datum, c).tally(datum);
            }

        }));
    for (Future f : futures)
        try {
            f.get();
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        }

我很困惑，因为对我来说，它们看起来做的是完全相同的事情，并行版本应该更快，但速度慢了一个数量级。有什么想法吗？

仅供引用，d 和 c 都是巨大的列表，其中包含数千到数十万个项目。

Answer 1

the parallel version should just be faster,

这是一个常见的误解。

but it's an order of magnitude slower.

常见结果

Any thoughts?

使用多个线程会产生单线程所没有的开销。开销可能比实际完成的工作高出几个数量级，从而使其速度慢得多。如果完成的工作远大于开销，您可以获得非常好的可扩展性。

例如假设将任务传递给另一个线程大约需要 10 微秒。如果您的任务需要 1 微秒，那么开销可能会影响您的性能。但是，如果任务需要 100 微秒，您就会看到显着的性能改进，并且值得付出开销的代价。

简而言之，没有什么是免费的，尤其是多线程。