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

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

Вот алгоритм многопоточности:

    public class ThreadedQuick extends Thread
    {
        final int MAX_THREADS = Runtime.getRuntime().availableProcessors();

        CountDownLatch doneSignal;
        static int num_threads = 1;

        int[] my_array;
        int start, end;

        public ThreadedQuick(CountDownLatch doneSignal, int[] array, int start, int end) {
            this.my_array = array;
            this.start = start;
            this.end = end;
            this.doneSignal = doneSignal;
        }

        public static void reset() {
            num_threads = 1;
        }

        public void run() {
            quicksort(my_array, start, end);
            doneSignal.countDown();
            num_threads--;
        }

        public void quicksort(int[] array, int start, int end) {
            int len = end-start+1;

            if (len <= 1)
                return;

            int pivot_index = medianOfThree(array, start, end);
            int pivotValue = array[pivot_index];

            swap(array, pivot_index, end);

            int storeIndex = start;
            for (int i = start; i < end; i++) {
               if (array[i] <= pivotValue) {
                   swap(array, i, storeIndex);
                   storeIndex++;
               }
            }

            swap(array, storeIndex, end);

            if (num_threads < MAX_THREADS) {
                num_threads++;

                CountDownLatch completionSignal = new CountDownLatch(1);

                new ThreadedQuick(completionSignal, array, start, storeIndex - 1).start();
                quicksort(array, storeIndex + 1, end);

                try {
                    completionSignal.await(1000, TimeUnit.SECONDS);
                } catch(Exception ex) {
                    ex.printStackTrace();
                }
            } else {
                quicksort(array, start, storeIndex - 1);
                quicksort(array, storeIndex + 1, end);
            }
        }
    }

Вот как я начинаю это:

ThreadedQuick.reset();
CountDownLatch completionSignal = new CountDownLatch(1);
new ThreadedQuick(completionSignal, array, 0, array.length-1).start();
try {
    completionSignal.await(1000, TimeUnit.SECONDS);
} catch(Exception ex){
    ex.printStackTrace();
}

Я проверил это с помощью Arrays.sort и аналогичного последовательного алгоритма быстрой сортировки. Вот результаты синхронизации на ноутбуке Intel Duel-Core Dell, в секундах:

Элементы: 500 000, последовательные: 0,068592, резьбовые: 0,046871, Arrays.sort: 0,079677

Элементы: 1 000 000, последовательно: 0,14416, с резьбой: 0,095492, Arrays.sort: 0,167155

Элементы: 2 000 000, последовательно: 0,301666, с резьбой: 0,205719, Arrays.sort: 0,350982

Элементы: 4 000 000, последовательно: 0,623291, с резьбой: 0,424119, Arrays.sort: 0,712698

Элементы: 8 000 000, последовательно: 1,279374, с резьбой: 0,859363, Arrays.sort: 1.487671

Каждое число, приведенное выше, представляет собой среднее время 100 тестов, отбрасывая 3 самых низких и 3 самых высоких случая. Я использовал Random.nextInt (Integer.MAX_VALUE) для генерации массива для каждого теста, который инициализировался один раз каждые 10 тестов с одним и тем же начальным числом. Каждый тест состоял из синхронизации данного алгоритма с System.nanoTime. Я округлил до шести десятичных знаков после усреднения. И, очевидно, я проверил, если каждый видработал.

Как вы можете видеть, в последовательных и многопоточных случаях в каждом наборе тестов скорость увеличивается примерно на 32%. Как я уже говорил выше, разве я не должен ожидать большего?