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();

有人知道为什么会出现这种情况吗？

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

- RobinXSI

---

这个问题很快就被关闭了。另一个问题非常不具体，像是“有时候某些东西会变慢”。在这里，人们可能会期望得到更有趣的答案... - Marco13

重新打开了这个问题，因为它寻找的是与所讨论的代码更具体的内容。 - Peter Lawrey

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也会先拉取缓存行的先前值。

另一个问题可能是

为什么不慢20倍？

抓取缓存行的CPU核心可能有两个使用超线程的线程（即两个线程可以本地访问数据），并且该CPU可能在失去缓存行之前循环几次，而另一个需要它的CPU核心正在等待。这意味着20倍的惩罚不会在每次访问或每个循环中发生，但经常发生，从而导致结果变得更慢。

- Peter Lawrey

---

你能提供更多的解释，为什么每次对缓存线的单个写入都必须在下一次计算之前通过 L3 吗？（这是否取决于是否使用 'volatile'？） - JimmyB

@HannoBinder 如果每次访问都通过L3进行，速度会慢20倍甚至更多。volatile并不能真正帮助，因为你不能有一个数组的易失性元素，只能有一个对数组的易失性引用。理论上，JIT可以将循环优化为仅执行最后一次迭代，并且使用易失性可能会防止这种情况发生，但在这种情况下，它也无法消除循环。 - Peter Lawrey

显然，你关于只有引用是易失性的是正确的。但我不确定如果没有volatile，每次访问数组是否仍会产生内存屏障。因此，如果将没有volatile的（单线程）实现与（多线程）带有（不必要的）volatile的实现进行比较，我认为这可能会有所不同。 - JimmyB

我想知道如何强制数据位于不同的缓存行上。JVM规范明确表示(!)它对内存布局没有任何说明(!)。例如使用10个线程和h[10][numCells]（“明显”相距很远）进行快速测试并未显示出任何加速效果。相比之下，保持局部性（如Hanno Binder建议的那样）确实可以使其更快（虽然不像顺序实现那样快——这有许多原因，主要是内存瓶颈，但我不知道如何通过推测缓存来避免或减轻这种情况...）。 - Marco13

@Marco13 在 JVM 中，数组在内存中是连续的，因此如果您使用 int [0] 和 int [16]，它们将相隔 64 字节。问题在于，您需要确保一个块的第一次访问至少在上一个块之后 64 字节。 - Peter Lawrey

Answer 2

虽然不是一个答案，但首先我会尽可能地维护数据访问的局部性：

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;
    }
}

关于为什么局部性很重要的更多解释，请参考例如 为什么对数组性能而言缓存局部性很重要？ 或者 http://en.wikipedia.org/wiki/Locality_of_reference。

基本上就是尽可能地使用已经在缓存中的数据。由于缓存大小有限，如果a[i]已经在缓存中，例如由于先前的读取操作，那么a[i+1]也很有可能在缓存中。至少比a[i+100]的机会高。

此外，从内存连续读取的数据可以通过硬件进行批量处理，并且这是最容易通过预取逻辑进行预测的。

- JimmyB

---

你需要确保数据在不同的缓存行中。即至少相隔64-128个字节。 - Peter Lawrey

我现在进行了相当多的测试，以各种方式切片、分析数据，并以不同的方式将其传递给执行程序服务，在我所有的方法中，与您建议的类似，维护局部性的简单实用解决方案基本上是最快的。 我已经点赞了它，但如果您简要解释局部性的重要性，甚至更正/扩展代码以便复制+粘贴（也许作为MVCE，但至少指出 numberOfCells 实际上应该是 numberOfCellsPerThread），那么它就可以成为一个“真正”的答案。 - Marco13

感谢您抽出时间进行测试。- 我真的忽视了 numberOfCellsPerThread 的问题，感谢您指出。 - JimmyB

现在，我们可以添加一些提示，提醒注意numberOfCells不是numberOfThreads的倍数的情况，这会导致最后几个单元格被跳过计算。但我认为现在的想法已经更加清晰了，这些细节可以留给实现者自行处理。 - Marco13