java 中的多线程矩阵加法比单线程版本花费的时间更长

Question

在 Java 和运行中处理并发问题，解决这个相当普遍的多线程问题。我有一段代码（如下），它只需要两个矩阵 m1 和 m2，并将 m1[i][j] 和 m2[i][j] 的总和写入 result[i][j].

for(int i = 0; i < numCols ; i++) {
            for(int j = 0 ; j < numRows ; j++) {
                int finalI = i;
                int finalJ = j;
                executorService.execute(
                        new Runnable() {
                            @Override
                            public void run()  {
                                    ArrayList<Integer> v1 = m1.get(finalI);
                                    Integer m1Val = v1.get(finalJ);
                                    ArrayList<Integer> v2 = m2.get(finalI);
                                    Integer m2Val = v2.get(finalJ);
                                    result.get(finalI).add(finalJ,  m1Val + m2Val);
                            }
                        }
                );
            }
        }

数组的类型为 ArrayLists<ArrayList<Integer>>，其中每个嵌套 ArrayList 描述一列。它们的尺寸为 numRows x numCols。我测量了这个操作的时间来总结一对运行domly 生成的大小为 10000 x 10000 的矩阵，发现单线程版本花了我 123 秒和多线程（6 核英特尔上的 11 个线程i7) 版本花了我大约 300 秒。

我在这种情况下选择使用 ArrayList，因为它们允许不安全的并发访问，即我可以同时修改 ArrayList 的不同部分。但是，这并没有提供我预期的任何额外加速。我对为什么看不到加速的猜测是因为以下原因：

内存总线堵塞，因此无法处理多个 reads/writes RAM 由线程完成，因此内存速度成为瓶颈。
这个操作我用了Executors.newFixedThreadPool。每次从 RAM 读取后，L1 缓存都会更新以提高数据访问速度。但是，此缓存无效，因为在给定处理器上的线程上执行的下一个任务可能需要内存中不同位置的数据，这些数据可能不会缓存在 L1 或 L2 级别，从而增加时间。

这些猜测有道理吗？我可能没有看到任何其他解释？

Answer 1

您有 2 个主要问题：

您正在为作为矩阵加法的一部分执行的每个加法安排一个可运行的。创建 Runnable、将其放入线程安全队列（由线程池内部使用）并让工作线程轮询该队列以获取任务会产生巨大的开销。
您正在为矩阵 (ArrayLists<ArrayList<Integer>>) 使用非常低效的数据结构，数据局部性差，访问单个项目的开销很大。

1 和 2 都会导致许多额外的 CPU 周期被完全浪费；它们还导致数据局部性差，导致超过必要的缓存未命中。

此外，您得到的结果不正确，因为您使用的是非线程安全的数据结构（“在本例中为 ArrayList，因为它们允许不安全的并发访问”）来收集结果；如果它没有为每个结果预填充 Integer 值，那么随着列表的扩展和覆盖早期数据，您将丢失数据。

一种有效的方法是：

在线程池中放置与 CPU 内核一样多的线程。给每个线程一个矩阵的一部分，让每个 Runnable 对整个部分执行加法。这意味着，如果您有 8 个核心和 8 个工作线程，那么每个线程将处理一个 Runnable，并且该 Runnable 在矩阵的 12.5% 上执行加法。
为您的数据结构使用 int[][]，或者更好的是，使用 int[] 并对 row * width + col 的索引进行您自己的计算。这提供了更好的数据局部性，并且不进行任何自动装箱和拆箱，从而也提高了速度。使用 int[] 特别适合添加矩阵，因为您可以将矩阵视为数组 - 您不需要知道行和列，只需 result[i] = m1[i] + m2[i];

java 中的多线程矩阵加法比单线程版本花费的时间更长

Multithreaded matrix addition taking longer than single threaded version in java

java

multithreading

concurrency

executorservice