Многопоточная быстрая сортировка намного медленнее, чем ожидалось

Question

В основном я потратил несколько часов на поиски лучшего способа реализации как рекурсивной, так и многопоточной быстрой сортировки и сортировки слиянием (этот пост только о быстрой сортировке). Моя цель в этом состоит в том, чтобы взять все логические процессоры на данном компьютере и закрепить их все на максимальной скорости быстрой сортировки.

Я использовал метод рекурсивного разделения своей проблемы при создании потоков, пока либо не будет отсортирован массив, либо я достигну количества процессоров на процессоре, и в этом случае остальная часть проблемы не будет разделена на новыепотоки но остальные выполнены на собственном ядре.

После создания очень элементарного решения, которое могло работать только на моем компьютере, я столкнулся с фреймворком Fork / Join, который я пытался использовать ниже, но я буквально не представлял, как это сделать. То, что я придумал, было медленнее сортировать 10000000 случайных чисел в диапазоне от 0 до 1000, чем его однопоточный аналог, но я все еще считаю его интересным, потому что в его документах говорится, что он способен красть работу из более медленных потоковчто бы это ни значило.

Тогда я только недавно услышал о пулах потоков и первоначальном создании всех моих потоков и их раздаче, потому что создание новых потоков обременительно для системы. Но я никогда не пытался реализовать это. Возможно, мое понимание Fork / Join искажено, и мне было интересно, сможет ли кто-нибудь указать мне правильное направление или сказать, что я делаю неправильно в моей текущей программе.

Ниже вы найдете мою попытку многопоточной быстрой сортировки и однопоточной быстрой сортировки, которую я пытаюсь перевести на свою многопоточную. Любая помощь приветствуется. Cheers!.

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;


public class MultithreadedQuicksort {
    public static void main(String[] args) {
         List<Comparable> nums = new ArrayList<Comparable>();
         Random rand = new Random();
         for (int i=0; i<10000000; i++) {
            nums.add(rand.nextInt(1000));
         }

         long start = System.currentTimeMillis();
         Quicksort quickSort = new Quicksort(nums, 0, nums.size() -1);
         ForkJoinPool pool = new ForkJoinPool();
         pool.invoke(quickSort);
         long end = System.currentTimeMillis();
         System.out.println(end - start);
         System.out.println(nums.size());
    }
}

class Quicksort extends RecursiveAction {
    int first;
    int last;
    private List<Comparable> nums;
    Comparable midValue;
    int midIndex;
    int low;
    int high;

    public Quicksort(List<Comparable> nums){
        this.nums=nums;
        this.low = 0;
        this.high = nums.size() - 1;
    }

    public Quicksort(List<Comparable> nums, int first, int last) {
        this.first = first;
        this.last = last;
        this.nums = nums;
        this.low = first;
        this.high = last;
        this.midIndex = (first + last) / 2;
        this.midValue = nums.get(midIndex);
    }


    @Override
    protected void compute() {
        split();
        if (high > first)
            invokeAll(new Quicksort(nums, first, high));
        if (low < last)
            invokeAll(new Quicksort(nums, low, last));
    }

    public void split() {
        while(low < high) {
            while (nums.get(low).compareTo(midValue) < 0) {
                  low++;
            }
            while (nums.get(high).compareTo(midValue) > 0) {
                  high--;
            }
            if (low <= high) {
                swap(low, high);
                low++;
                high--;
            }
        }
    }

    public void swap(int index1, int index2)
    {
        Comparable temp;
        temp = nums.get(index1);
        nums.set(index1, nums.get(index2));
        nums.set(index2, temp);
    }
}

Однопоточная

public static void quickSort(List<Comparable> nums, int first, int last) {
    int low = first;
    int high = last;
    int midIndex = (first + last) / 2;
    Comparable midValue = nums.get(midIndex);

    while(low < high) {
        while (nums.get(low).compareTo(midValue) < 0) {
              low++;
        }
        while (nums.get(high).compareTo(midValue) > 0) {
              high--;
        }
        if (low <= high) {
            swap(nums, low, high);
            low++;
            high--;
        }
    }
    if (high > first)
           quickSort(nums, first, high);
    if (low < last)
           quickSort(nums, low, last);
    }

Answer 1

Я не очень хорошо знаю java, поэтому приведенный ниже пример кода может быть неудобным использованием runnable для нескольких потоков. В этом примере кода используется 8 потоков, qsortmt () выполняет разбиение и запускает два экземпляра qsort0 (). Каждый экземпляр qsort0 () выполняет разбиение и вызывает два экземпляра qsort1 (). Каждый экземпляр qsort1 () выполняет разбиение и вызывает два экземпляра qsort2 (). Каждый экземпляр qsort2 () вызывает qsort (). Для 16 миллионов целых чисел, используемых в этом примере, 8-поточная сортировка занимает около 1 секунды, в то время как непоточная сортировка занимает около 1,6 секунды, что не является значительной экономией. Частично проблема заключается в том, что шаги раздела выполняются перед тем, как запускать потоки для работы с подразделами.

Переключение на собственные потоки C ++ и Windows, 8 потокам заняло около 0,632 секунды, а без потоков - около 1,352 секунды. Переключение на сортировку слиянием, разбиение массива на 8 частей, сортировка каждой части, а затем объединение 8 частей заняло около 0,40 секунды, а однопоточность - около 1,45 секунды.

package x;
import java.util.Random;

public class x {

    class qsort0 implements Runnable
    {
        int[] a;
        int lo;
        int hi;

        private qsort0(int[] a, int lo, int hi)
        {
            this.a = a;
            this.lo = lo;
            this.hi = hi;
        }
        @Override
        public void run()
        {
            if(this.lo >= this.hi)
                return;
            int pi = partition(this.a, this.lo, this.hi);
            Thread lt = new Thread(new qsort1(a, this.lo, pi));
            Thread rt = new Thread(new qsort1(a, pi+1, this.hi));
            lt.start();
            rt.start();
            try {lt.join();} catch (InterruptedException ex){}
            try {rt.join();} catch (InterruptedException ex){}
        }
    }

    class qsort1 implements Runnable
    {
        int[] a;
        int lo;
        int hi;

        private qsort1(int[] a, int lo, int hi)
        {
            this.a = a;
            this.lo = lo;
            this.hi = hi;
        }
        @Override
        public void run()
        {
            if(this.lo >= this.hi)
                return;
            int pi = partition(this.a, this.lo, this.hi);
            Thread lt = new Thread(new qsort2(a, this.lo, pi));
            Thread rt = new Thread(new qsort2(a, pi+1, this.hi));
            lt.start();
            rt.start();
            try {lt.join();} catch (InterruptedException ex){}
            try {rt.join();} catch (InterruptedException ex){}
        }
    }

    class qsort2 implements Runnable
    {
        int[] a;
        int lo;
        int hi;
        private qsort2(int[] a, int lo, int hi)
        {
            this.a = a;
            this.lo = lo;
            this.hi = hi;
        }
        @Override
        public void run() {
            if(this.lo >= this.hi)
                return;
            qsort(this.a, this.lo, this.hi);
        }
    }

    // quicksort multi-threaded
    @SuppressWarnings("empty-statement")
    public static void qsortmt(int[] a, int lo, int hi)
    {
        if(lo >= hi)
            return;
        int pi = partition(a, lo, hi);
        Thread lt = new Thread(new x().new qsort0(a, lo, pi));
        Thread rt = new Thread(new x().new qsort0(a, pi+1, hi));
        lt.start();
        rt.start();
        try {lt.join();} catch (InterruptedException ex){}
        try {rt.join();} catch (InterruptedException ex){}
    }

    @SuppressWarnings("empty-statement")
    public static int partition(int []a, int lo, int hi)
    {
        int  md = lo+(hi-lo)/2;
        int  ll = lo-1;
        int  hh = hi+1;
        int t;
        int p = a[md];
        while(true){
            while(a[++ll] < p);
            while(a[--hh] > p);
            if(ll >= hh)
                break;
            t     = a[ll];
            a[ll] = a[hh];
            a[hh] = t;
        }
        return hh;
    }

    @SuppressWarnings("empty-statement")
    public static void qsort(int[] a, int lo, int hi)
    {
        while(lo < hi){
            int ll = partition(a, lo, hi);
            int hh = ll+1;
            // recurse on smaller part, loop on larger part
            if((ll - lo) <= (hi - hh)){
                qsort(a, lo, ll);
                lo = hh;
            } else {
                qsort(a, hh, hi);
                hi = ll;
            }
        }
    }

    public static void main(String[] args)
    {
        int[] a = new int[16*1024*1024];
        Random r = new Random(0);
        for(int i = 0; i < a.length; i++)
            a[i] = r.nextInt();
        long bgn, end;
        bgn = System.currentTimeMillis();
        qsortmt(a, 0, a.length-1);
        end = System.currentTimeMillis();
        for(int i = 1; i < a.length; i++){
            if(a[i-1] > a[i]){
                System.out.println("failed");
                break;
            }
        }
        System.out.println("milliseconds " + (end-bgn));
    }
}