Fork/Join 快速排序框架比普通快速排序执行时间更长

Question

我把fork/join快速排序和普通快速排序合二为一class然后我计算了执行这两个的时间。奇怪的是 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-complexity 冒泡排序

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

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

Fork/Join 快速排序框架比普通快速排序执行时间更长

Fork/Join framework for quicksort execute longer than normal quicksort

java

fork-join

主要

并发快速排序