Java 顺序执行比并行执行快 4 倍

Question

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

在下面 link 我创建了一个顺序实现： 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

不是真正的答案，但是：首先，我会尽可能保持数据访问的局部性：

final int numberOfCellsPerThread = numberOfCells / numberOfThreads;

public void run() {
    final int start = threadId * numberOfCellsPerThread;
    final int end = start + numberOfCellsPerThread;
    for(int i = start; i < end; 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;
    }
}

有关位置为何重要的更多解释，请参见示例 Why does cache locality matter for array performance? 或 http://en.wikipedia.org/wiki/Locality_of_reference.

基本上就是尽可能使用缓存中已有的数据。由于缓存大小有限，如果 a[i] 已经在缓存中，例如由于先前的读取操作，a[i+1] 也在缓存中的可能性相当高。至少比 a[i+100] 这样的几率要高。

此外，从内存中的顺序读取可能会被硬件优化为突发，并且最容易通过预取逻辑进行预测。

Answer 2

最大的开销是启动和停止线程所花费的时间。如果我将数组的大小从 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 CPUs 也会首先提取缓存行的先前值。

另一个问题可能是

Why isn't this 20x slower?

抢到缓存行的CPU核心可能有两个线程运行超线程（即两个线程可以本地访问数据），CPU可能会绕过在将缓存行丢失到另一个需要它的 CPU 核心之前，循环几次。这意味着 20 倍的惩罚不是针对每次访问或每次循环，但通常足以让您得到更慢的结果。

Java 顺序执行比并行执行快 4 倍

Java sequential implementation is 4 times faster than parallel implementation

java

parallel-processing

multithreading

executorservice

threadpool