多线程编程不是预期的结果

Question

我遇到了多线程 java 程序的问题。该程序由具有多线程的整数数组的拆分和组成，而不是切片的总和。问题是计算时间不会随着线程数的增加而减少（我知道线程数是有限的，计算时间比更少的线程慢）。我希望在限制线程数之前看到执行时间的减少（并行执行的好处）。我在运行方法中使用变量 fake 来制造时间 "readable"。

public class MainClass {

private final int MAX_THREAD = 8;
private final int ARRAY_SIZE = 1000000;

private  int[] array;
private SimpleThread[] threads;
private int numThread = 1;
private int[] sum;
private int start = 0;
private int totalSum = 0;
long begin, end;
int fake;


MainClass() {
    fillArray();

    for(int i = 0; i < MAX_THREAD; i++) {
        threads = new SimpleThread[numThread];
        sum = new int[numThread];

        begin = (long) System.currentTimeMillis();

        for(int j = 0 ; j < numThread; j++) {
            threads[j] = new SimpleThread(start, ARRAY_SIZE/numThread, j);
            threads[j].start();
            start+= ARRAY_SIZE/numThread;
        }



        for(int k = 0; k < numThread; k++) {
            try {
                threads[k].join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }


        end = (long) System.currentTimeMillis();


        for(int g = 0; g < numThread; g++) {
            totalSum+=sum[g];
        }


        System.out.printf("Result with %d thread-- Sum = %d Time = %d\n", numThread, totalSum, end-begin);
        numThread++;
        start = 0;
        totalSum = 0;
    }

}


public static void main(String args[]) {
    new MainClass();
}


private void fillArray() {
    array = new int[ARRAY_SIZE];
    for(int i = 0; i < ARRAY_SIZE; i++) 
        array[i] = 1;
}


private class SimpleThread extends Thread{
    int start;
    int size;
    int index;

    public SimpleThread(int start, int size, int sumIndex) {
        this.start = start;
        this.size = size;
        this.index = sumIndex;
    }

    public void run() {
        for(int i = start; i < start+size; i++) 
            sum[index]+=array[i];

        for(long i = 0; i < 1000000000; i++) {
            fake++;
        }
    }
}

Unexpected Result Screenshot

Answer 1

启动线程很繁重，您只会在不竞争相同资源的大型进程上看到它的好处（none 此处适用）。

Answer 2

为什么有时求和不对？

因为 ARRAY_SIZE/numThread 可能有小数部分（例如 1000000/3=333333.3333333333），它会向下舍入，所以 start 变量会丢失一些，因此总和可能小于 1000000，具体取决于除数的值。

为什么随着线程数的增加，耗时也在增加？

因为在每个线程的运行函数中你这样做：

for(long i = 0; i < 1000000000; i++) {
    fake++;
}

我不明白你的问题:

I use the variable fake in run method to make time "readable".

这是什么意思。但是每个线程都需要将您的 fake 变量递增 1000000000 次。

Answer 3

作为一般规则，如果每个线程执行的 "work" 小于使用线程的开销，您将不会从多线程中获得加速。

开销之一是启动新线程的成本。这高得惊人。每次启动线程时，JVM 都需要执行系统调用来分配线程堆栈内存段和 "red zone" 内存段，并初始化它们。（默认线程堆栈大小通常为 500KB 或 1MB。）然后有进一步的系统调用来创建本机线程并对其进行调度。

在此示例中，您有 1,000,000 个元素要求和，您将此工作分配给 N 个线程。随着 N 的增加，每个线程执行的工作量减少。

不难看出，求和1,000,000个元素所花费的时间将少于启动4个线程所需的时间......仅根据内存读写操作计算。然后你需要考虑到子线程是由父线程一次创建一个。

如果您进行完整的分析，很明显，添加更多线程实际上会减慢计算速度 即使您有足够的内核来运行所有线程并行。您的基准测试似乎表明 ¹ 那一点大约是 2 个线程。

顺便说一下，还有第二个原因，为什么您可能无法像这样的基准测试那样获得预期的加速。每个线程在做的"work"，基本上就是在扫描一个大数组。读写数组会产生对内存系统的请求。理想情况下，这些请求将由（快速）片上内存缓存来满足。但是，如果您尝试读取/写入大于内存缓存的数组，那么这些请求中的许多/大部分都会变成（缓慢的）主内存请求。更糟糕的是，如果您有 N 个内核都在执行此操作，那么您会发现主内存请求的数量太多，内存系统无法跟上....并且线程速度变慢。

最重要的是，多线程不会自动使应用程序更快，如果您使用错误的方法，它肯定不会。

在你的例子中：

与创建和启动线程的开销相比，每个线程的工作量太小，并且
如果可以"factor out"线程创建开销

^{1 - 我不明白 "fake" 计算的意义。它可能会使基准测试无效，尽管 JIT 编译器可能会对其进行优化。}

Answer 4

附带说明一下，对于您要尝试执行的操作，有 Fork/Join-Framework。它允许您轻松地递归地拆分任务，并实现一个算法来自动分配您的工作量。

有一个guide available here；它的示例与您的情况非常相似，归结为 RecursiveTask 如下：

class Adder extends RecursiveTask<Integer>
{
    private int[] toAdd;
    private int from;
    private int to;

    /** Add the numbers in the given array */
    public Adder(int[] toAdd)
    {
        this(toAdd, 0, toAdd.length);
    }

    /** Add the numbers in the given array between the given indices;
        internal constructor to split work */
    private Adder(int[] toAdd, int fromIndex, int upToIndex)
    {
        this.toAdd = toAdd;
        this.from = fromIndex;
        this.to = upToIndex;
    }

    /** This is the work method */
    @Override
    protected Integer compute()
    {
        int amount = to - from;
        int result = 0;
        if (amount < 500)
        {
            // base case: add ints and return the result
            for (int i = from; i < to; i++)
            {
                result += toAdd[i];
            }
        }
        else
        {
            // array too large: split it into two parts and distribute the actual adding
            int newEndIndex = from + (amount / 2);
            Collection<Adder> invokeAll = invokeAll(Arrays.asList(
                    new Adder(toAdd, from, newEndIndex),
                    new Adder(toAdd, newEndIndex, to)));
            for (Adder a : invokeAll)
            {
                result += a.invoke();
            }
        }
        return result;
    }
}

实际上运行这个，你可以使用

RecursiveTask adder = new Adder(fillArray(ARRAY_LENGTH));
int result = ForkJoinPool.commonPool().invoke(adder);

多线程编程不是预期的结果

Not expected result with multithread programming

java

multithreading

parallelism-amdahl