为什么我的多线程排序算法不比单线程mergesort快

Question

有一些算法,当一个任务划分并且每个部分并行完成时,其运行时间会显着减少.这些算法之一是合并排序,其中列表被划分为无限小的部分,然后以排序的顺序重新组合.我决定做一个实验来测试我是否可以通过使用多个线程来提高这种速度.我在带有Windows Vista的四核戴尔上运行Java中的以下功能.

一个函数(控件案例)只是递归的:

// x is an array of N elements in random order
public int[] mergeSort(int[] x) {
    if (x.length == 1) 
        return x;

    // Dividing the array in half
    int[] a = new int[x.length/2];
    int[] b = new int[x.length/2+((x.length%2 == 1)?1:0)];
    for(int i = 0; i < x.length/2; i++) 
        a[i] = x[i];
    for(int i = 0; i < x.length/2+((x.length%2 == 1)?1:0); i++) 
        b[i] = x[i+x.length/2];

    // Sending them off to continue being divided
    mergeSort(a);
    mergeSort(b);

    // Recombining the two arrays
    int ia = 0, ib = 0, i = 0;
    while(ia != a.length || ib != b.length) {
        if (ia == a.length) {
            x[i] = b[ib];
            ib++;
        }
        else if (ib == b.length) {
            x[i] = a[ia];
            ia++;
        }
        else if (a[ia] < b[ib]) {
            x[i] = a[ia];
            ia++;
        }
        else {
            x[i] = b[ib];
            ib++;
        }
        i++;
    }

    return x;
}

另一个是扩展线程的类的'run'函数,每次调用时递归创建两个新线程:

public class Merger extends Thread
{
    int[] x;
    boolean finished;

    public Merger(int[] x)
    {
        this.x = x;
    }

    public void run()
    {
        if (x.length == 1) {
            finished = true;
            return;
        }

        // Divide the array in half
        int[] a = new int[x.length/2];
        int[] b = new int[x.length/2+((x.length%2 == 1)?1:0)];
        for(int i = 0; i < x.length/2; i++) 
            a[i] = x[i];
        for(int i = 0; i < x.length/2+((x.length%2 == 1)?1:0); i++) 
            b[i] = x[i+x.length/2];

        // Begin two threads to continue to divide the array
        Merger ma = new Merger(a);
        ma.run();
        Merger mb = new Merger(b);
        mb.run();

        // Wait for the two other threads to finish 
        while(!ma.finished || !mb.finished) ;

        // Recombine the two arrays
        int ia = 0, ib = 0, i = 0;
        while(ia != a.length || ib != b.length) {
            if (ia == a.length) {
                x[i] = b[ib];
                ib++;
            }
            else if (ib == b.length) {
                x[i] = a[ia];
                ia++;
            }
            else if (a[ia] < b[ib]) {
                x[i] = a[ia];
                ia++;
            }
            else {
                x[i] = b[ib];
                ib++;
            }
            i++;
        }

        finished = true;
    }
}

事实证明,不使用多线程的函数实际运行得更快.为什么？操作系统和Java虚拟机是否没有足够有效地"通信"以将不同的线程放在不同的核心上？还是我错过了一些明显的东西？

Answer 1

问题不在于多线程:我在Java中编写了一个正确的多线程QuickSort,它拥有默认的Java排序.我看到一个巨大的数据集正在处理并且只有一个16核机器的核心工作后我这样做了.

你的一个问题(一个巨大的问题)就是你忙着循环:

 // Wait for the two other threads to finish 
 while(!ma.finished || !mb.finished) ;

这是一个巨大的禁忌:它被称为繁忙的循环,你正在破坏性能.

(另一个问题是您的代码不会产生任何新线程,因为它已经向您指出)

您需要使用其他方式进行同步:一个例子是使用a CountDownLatch.

另一件事:分割工作负载时不需要生成两个新线程:只生成一个新线程,并在当前线程中执行另一半.

此外,您可能不希望创建比可用内核更多的线程.

在这里查看我的问题(要求一个好的开源多线程mergesort/quicksort /等等).我正在使用的是专有的,我无法粘贴它.

多线程快速排序或合并排序

我还没有实现Mergesort而是QuickSort,我可以告诉你,没有进行数组复制.

我这样做是:

• 选一个支点
• 根据需要交换价值
• 我们达到了线程限制吗？(取决于核心数量)
  • 是的:在这个帖子中排序第一部分
  • no:生成一个新线程
• 在当前线程中排序第二部分
• 等待第一部分完成,如果尚未完成(使用CountDownLatch).

产生新线程并创建CountDownLatch的代码可能如下所示:

            final CountDownLatch cdl = new CountDownLatch( 1 );
            final Thread t = new Thread( new Runnable() {
                public void run() {
                    quicksort(a, i+1, r );
                    cdl.countDown();
                }
            } };

使用像CountDownLatch这样的同步工具的优点是它非常高效,并且您不会浪费时间来处理低级Java同步特性.

在你的情况下,"拆分"可能看起来像这样(未经测试,它只是给出一个想法):

if ( threads.getAndIncrement() < 4 ) {
    final CountDownLatch innerLatch = new CountDownLatch( 1 );
    final Thread t = new Merger( innerLatch, b );
    t.start();
    mergeSort( a );
    while ( innerLatch.getCount() > 0 ) {
        try {
            innerLatch.await( 1000, TimeUnit.SECONDS );
        } catch ( InterruptedException e ) {
            // Up to you to decide what to do here
        }
    }
} else {
    mergeSort( a );
    mergeSort( b );
}

(每次合并完成后别忘了"倒计时"锁存器)

您可以用可用内核数替换线程数(此处最多4个).您可以使用以下内容(一次,比如在程序开头初始化一些静态变量:核心数量不太可能发生变化[除非您在允许CPU热交换的机器上,如某些Sun系统允许的话]):

Runtime.getRuntime().availableProcessors()