Java顺序实现比并行实现快4倍

Question

我创建了一个非常简单的场景，其中我发现了一个我无法理解的非常奇怪的行为。

在以下链接下，我创建了一个顺序实现: http://ideone.com/B8JYeA基本上有几个固定大小的大数组。该算法遍历它们并更改值。

for(int i = 0; i < numberOfCells; i++) {
    h0[i] =  h0[i] + 1;
    h1[i] =  h1[i] + 1;
    h2[i] =  h2[i] + 1;
    h3[i] =  h3[i] + 1;
    h4[i] =  h4[i] + 1;
}

如果我在我的工作站上运行它大约需要 5 秒。

我在并行版本中实现了相同的功能。 8 个线程同时运行它。代码应该是线程安全的，线程之间没有依赖关系。

但代码在我的工作站上运行速度仍然慢了大约 4 倍: http://ideone.com/yfwVmr

final int numberOfThreads = Runtime.getRuntime().availableProcessors();

ExecutorService exec = Executors.newFixedThreadPool(numberOfThreads);

for(int thread = 0; thread < numberOfThreads; thread++) {
    final int threadId = thread;
    exec.submit(new Runnable() {
        @Override
        public void run() {
            for(int i = threadId; i < numberOfCells; i += numberOfThreads) {
                h0[i] =  h0[i] + 1;
                h1[i] =  h1[i] + 1;
                h2[i] =  h2[i] + 1;
                h3[i] =  h3[i] + 1;
                h4[i] =  h4[i] + 1;
            }
        }
    });
}

exec.shutdown();

有人知道为什么会这样吗？

编辑:这个问题与其他问题不同，原因可能是缓存问题。我该如何解决这个缓存问题？

Answer 1

最大的开销是启动和停止线程所花费的时间。如果我将数组的大小从 10000 减少到 10，则需要大约相同的时间。

如果保留线程池，并为每个线程分配工作以写入本地数据集，那么在我的 6 核机器上速度会提高 4 倍。

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.*;


public class ParallelImplementationOptimised {
    static final int numberOfThreads = Runtime.getRuntime().availableProcessors();
    final ExecutorService exec = Executors.newFixedThreadPool(numberOfThreads);

    private int numberOfCells;

    public ParallelImplementationOptimised(int numberOfCells) {
        this.numberOfCells = numberOfCells;
    }

    public void update() throws ExecutionException, InterruptedException {

        List<Future<?>> futures = new ArrayList<>();
        for(int thread = 0; thread < numberOfThreads; thread++) {
            final int threadId = thread;
            futures.add(exec.submit(new Runnable() {
                @Override
                public void run() {
                    int num = numberOfCells / numberOfThreads;
                    double[] h0 = new double[num],
                            h1 = new double[num],
                            h2 = new double[num],
                            h3 = new double[num],
                            h4 = new double[num],
                            h5 = new double[num],
                            h6 = new double[num],
                            h7 = new double[num],
                            h8 = new double[num],
                            h9 = new double[num];
                    for (int i = 0; i < num; i++) {
                        h0[i] = h0[i] + 1;
                        h1[i] = h1[i] + 1;
                        h2[i] = h2[i] + 1;
                        h3[i] = h3[i] + 1;
                        h4[i] = h4[i] + 1;
                        h5[i] = h5[i] + 1;
                        h6[i] = h6[i] + 1;
                        h7[i] = h7[i] + 1;
                        h8[i] = h8[i] + 1;
                        h9[i] = h9[i] + 1;
                    }
                }
            }));
        }
        for (Future<?> future : futures) {
            future.get();
        }
    }

    public static void main(String[] args) throws ExecutionException, InterruptedException {

        ParallelImplementationOptimised si = new ParallelImplementationOptimised(10);

        long start = System.currentTimeMillis();

        for (int i = 0; i < 10000; i++) {
            if(i % 1000 == 0) {
                System.out.println(i);
            }
            si.update();
        }

        long stop = System.currentTimeMillis();
        System.out.println("Time: " + (stop - start));
        si.exec.shutdown();
    }

}

SequentialImplementation 3.3 秒。ParallelImplementationOptimised 0.8 秒。

---

您似乎在同一缓存行上写入相同的数据。这意味着数据必须通过 L3 缓存未命中传递，这比访问 L1 缓存花费的时间长 20 倍。我建议您尝试完全分开的数据结构，它们至少相隔 128 个字节，以确保您没有触及相同的缓存行。

注意:即使您打算完全覆盖整个缓存行，x64 CPU 也会首先提取缓存行的先前值。

另一个问题可能是

Why isn't this 20x slower?

获取缓存行的 CPU 核心可能有两个线程以超线程运行(即两个线程可以访问本地数据)，并且该 CPU 可能会在将缓存行丢失给另一个之前绕过循环几次要求它的CPU核心。这意味着 20 倍的惩罚并非针对每次访问或每次循环，但通常足以让您获得更慢的结果。