java - 在java中使用多线程添加整数2D数组元素比顺序添加慢

Question

因此，我正在 Java 中练习多线程，并尝试使用 4 个线程按顺序添加随机生成的 2D 整数数组的元素。我测量了代码的性能，由于某种原因，顺序部分比多线程快得多。以下是顺序相加的代码:

public class ArraySum2DNonMT {

private int[][] arrayToSum;
private int totalSum;

public ArraySum2DNonMT(int[][] arr){
    this.arrayToSum = arr;
    this.setTotalSum(0);
}

public void runSequential(){
    for(int i = 0; i < arrayToSum[0].length; i++){
        for(int j = 0; j < arrayToSum.length; j++){
            setTotalSum(getTotalSum() + arrayToSum[j][i]);
        }
    }
}

public int getTotalSum() {
    return totalSum;
}

public void setTotalSum(int totalSum) {
    this.totalSum = totalSum;
}

}

这是多线程版本的代码:

package multiThreaded;

/**
* 
* @author Sahil Gupta
* 
* This class takes in a 2D integer array and adds it's contents. This
* addition will be concurrent between several threads which will divide
* the work of the array based on the threadID assigned to thread by the
* programmer. Assume that the passed in 2D array to the constructor is a 
* matrix with each array in the main array having same length.
*/

public class ArraySum2D implements Runnable{

private int[][] arrayToSum;
private int threadID;
private int totalSum;

public ArraySum2D(int[][] arr, int threadID){
    this.arrayToSum = arr;
    this.threadID = threadID;
    this.setTotalSum(0);
}

@Override
public void run() {
    int arrayCol = arrayToSum[0].length;
    int arrayRow = arrayToSum.length;
    int colStart = (int)((threadID%2) * (arrayCol/2));
    int rowStart = (int)((int)(threadID/2) * (arrayRow/2));
    int colEnd = colStart + (int)(arrayCol/2);
    int rowEnd = rowStart + (int)(arrayRow/2);

    for(int i = colStart; i < colEnd; i++){
        for(int j = rowStart; j < rowEnd; j++){
            setTotalSum(getTotalSum() + arrayToSum[j][i]);
        }
    }
}

public int getTotalSum() {
    return totalSum;
}

public void setTotalSum(int totalSum) {
    this.totalSum = totalSum;
}

}

主要内容如下:

package controller;

import java.util.Random;

import multiThreaded.ArraySum2D;
import sequentialNonMT.ArraySum2DNonMT;

public class ControllerMain {

private final static int cols = 20;
private final static int rows = 10;
private static volatile int[][] arrayToAdd = new int[rows][cols];
private static Random rand = new Random();
private static ArraySum2D a0, a1, a2, a3;

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

    for(int j = 0; j < rows; j++){
        for(int i = 0; i < cols; i++){
            arrayToAdd[j][i] = rand.nextInt(100);
        }
    }

    ArraySum2DNonMT a = new ArraySum2DNonMT(arrayToAdd);

    long startTimeSequential = System.nanoTime();
    a.runSequential();
    long estimatedTimeSequential = System.nanoTime() - startTimeSequential;

    System.out.println("The total sum calculated by sequential program is: " + a.getTotalSum());
    System.out.println("The total time taken by sequential program is: " + estimatedTimeSequential);

    a0 = new ArraySum2D(arrayToAdd, 0);
    a1 = new ArraySum2D(arrayToAdd, 1);
    a2 = new ArraySum2D(arrayToAdd, 2);
    a3 = new ArraySum2D(arrayToAdd, 3);
    Thread t0 = new Thread(a0);
    Thread t1 = new Thread(a1);
    Thread t2 = new Thread(a2);
    Thread t3 = new Thread(a3);

    long startTimeMultiThreaded = System.nanoTime();
    t0.start();
    t1.start();
    t2.start();
    t3.start();

    t0.join();
    t1.join();
    t2.join();
    t3.join();
    int Sum = addThreadSum();
    long estimatedTimeMultiThreaded = System.nanoTime() - startTimeMultiThreaded;

    System.out.println("The total sum calculated by multi threaded program is: " + Sum);
    System.out.println("The total time taken by multi threaded program is: " + estimatedTimeMultiThreaded);
}

private static int addThreadSum(){
    return a0.getTotalSum() + a1.getTotalSum() + a2.getTotalSum() + a3.getTotalSum();
}

}

我当前得到的输出显示运行时的显着差异(此处以纳秒为单位测量)。这是我得到的:

The total sum calculated by sequential program is: 10109 
The total time taken by sequential program is: 46000
The total sum calculated by multi threaded program is: 10109
The total time taken by multi threaded program is: 641000

顺序代码的速度大约快 13 倍。您能帮我指出我可能做得不正确吗？我有双核 i7 haswell、MacBook Air。我不确定为什么要花更长的时间，但我想到的一些想法可能会导致这种情况:错误共享、太多并行/线程(双核为 4)、缓存一致性协议(protocol)可能不利于我，我缺少/不知道其他一些基本的多线程内容。

请帮助我确定具体原因以及使多线程运行速度比顺序运行更快的方法。非常感谢您对我的帮助!

编辑:有关处理器及其缓存的更多信息: 处理器名称:英特尔酷睿 i7 处理器速度:1.7 GHz 处理器数量:1 核心总数:2 L2 缓存(每个核心):256 KB L3 缓存:4 MB

根据英特尔的数据表，我认为最多可以有 4 个线程。

附注这是我第一篇提出问题的帖子，但我已经使用这个网站来消除疑虑有一段时间了。请原谅我所犯的任何错误。

Answer 1

有一个sizable amount of overhead建立线程时。也就是说，如果您的示例数据集太小，则旋转和拆除线程所花费的时间将大于代码的实际运行时间性能。

让我们主观地看一下。您有一个仅包含 200 个元素的数组。您的方法的运行时间为 O(nm)，其中 n 是行大小，m 是列大小。

坦白说，我认为唯一不会能够以这种方式快速处理 200 个元素的机器是我的旧 Pentium III 机器。即使那样，也不会那么那么遥远。

我有一个相对强大的 i7-4770K，它可以运行 4 个核心，每个核心有两个线程。如果我用这些较低的数字运行你的程序，我会得到大约相同的结果。

但是...如果我将界限设置得大一点怎么办？令n = 2**m*，并令n = 9000。

不要关注金额。整数溢出完全破坏了我们从中获得的任何值(value)。

The total sum calculated by sequential program is: -570429863
The total time taken by sequential program is: 3369190200
The total sum calculated by multi threaded program is: -570429863
The total time taken by multi threaded program is: 934624554

线程版本的运行时间为 27%，速度提高了约 3.6 倍。或者通俗地说，3.36 秒 vs. 934 毫秒。这是巨大。

线程并没有改变算法的性能 - 它在 O(nm) 下仍然非常低效 - 但它确实改变了运行时常数，虽然不完全改变，但接近 1/4 的时间。我能够从中获得优势的唯一原因是我通过它推送的数据大小。否则，线程就不值得了。