java - 用于快速排序的 Fork/Join 框架比普通快速排序执行时间更长

Question

我在一个类中编写了 fork/join 快速排序和普通快速排序，然后我计算了两者的执行时间。奇怪的是 fork/join 的工作时间比普通的快速排序要长。问题是为什么？

主要

public class Main
{
public static void main(String[] args)
{
    Random generator = new Random();
    List<Integer> list = new ArrayList<>(50000);

    for(int i = 0; i < 50000; i ++)
    {
        list.add(generator.nextInt(500200));
    }


   List<Integer> list2 = new ArrayList<>(list);





    ConcurrentQuickSort<Integer> sort = new ConcurrentQuickSort<>(list,0,list.size() - 1);
    long startTime = System.currentTimeMillis();
    ForkJoinPool pool = new ForkJoinPool();
    pool.invoke(sort);
    pool.shutdown();
    pool.awaitTermination(10,TimeUnit.SECONDS);
    long endTime = System.currentTimeMillis();
    long ConcurrentTime = (endTime - startTime);


    startTime = System.currentTimeMillis();
    ConcurrentQuickSort<Integer> sort2 = new ConcurrentQuickSort<>(list2,0,list.size() - 1);
    sort2.doSort(0,list2.size() - 1);
    endTime = System.currentTimeMillis();
    long sequentialTime = (endTime - startTime);


    System.out.println(ConcurrentTime);
    System.out.println(sequentialTime);
    System.out.println(sort2.isCorrect(list));

   }
}

并发快速排序

public class ConcurrentQuickSort<T extends Comparable<T> > extends RecursiveAction
{
    private List<T> list;
    private int size;
    private int begin;
    private int end;


public ConcurrentQuickSort(List<T> list,int begin,int end)
{
    this.list = list;
    this.size = this.list.size();
    this.begin = begin;
    this.end = end;

}


private int partition(int begin, int end)
{

    T x = list.get(begin);
    int i = begin;
    int j = end;

    while(true)
    {
        while(list.get(j).compareTo(x) > 0)
        {
            j--;
        }

        while(list.get(i).compareTo(x) < 0)
        {
            i++;
        }

        if(i < j)
        {
            swap(i,j);
            i++;
            j--;

        }
        else
            return j;
    }
}

public void doSort(int begin, int end)
{
    int q;
    if(begin < end)
     {
        q = partition(begin,end);

         doSort(begin,q);
         doSort(q + 1,end);
    }
}

public void doSort()
{

}

public void sort()
{
    doSort(0,list.size() - 1);
}

private void swap(int first, int second)
{
    T temp = list.get(first);
    list.set(first,list.get(second));
    list.set(second,temp);
}

@Override
protected void compute()
{

    int q;
    if(begin < end)
    {

        q = partition(begin,end);
        List<ConcurrentQuickSort<T>> subtasks = splitWork(q);
        for(ConcurrentQuickSort<T> t : subtasks)
        {
            t.fork();
        }


    }
}

private List<ConcurrentQuickSort<T>> splitWork(int q)
{
    List<ConcurrentQuickSort<T>> subtasks = new ArrayList<>();
    subtasks.add(new ConcurrentQuickSort<>(this.list,begin,q));
    subtasks.add(new ConcurrentQuickSort<>(this.list,q +1,end));
    return subtasks;
}

public boolean isCorrect(List<T> other)
{
   return list.equals(other);
}
 }

普通快速排序的执行时间约为 20 毫秒，而 fork/join 则需要 80 毫秒。为什么？

Answer 1

对于足够小的数据集:

• 在不同线程之间同步数据的成本将超过并行性的好处
• 多个线程将在彼此非常接近的内存范围上工作，这些内存范围将被缓存在每个核心的 L1 缓存中，这意味着缓存的使用效率较低(相同的数据在访问时会多次从内存中获取)实际上在另一个核心的缓存中)
• 冒泡排序实际上会优于快速排序，因为即使 O(n^2) > O(n log n)，递归调用的成本也会超过冒泡排序额外的 O 复杂度

如果您实现较低的阈值，在并发和非并发快速排序之间以及快速排序和冒泡排序之间切换，您可能能够计算出不同 cpu 缓存的行大小和算法。

RecursiveAction 的 javadoc显示阈值设置为 1000 的合并排序的实现。