Почему мой многопоточный алгоритм сортировки не быстрее, чем моя единственная потоковая сортировка с объединением

Существуют определенные алгоритмы, время выполнения которых может уменьшиться значительно, когда каждый делит задачу и получает каждую часть, сделанную параллельно. Один из этих алгоритмов является сортировкой слиянием, где список разделен на бесконечно мало меньшие части и затем повторно объединен в отсортированном порядке. Я решил сделать эксперимент, чтобы протестировать, мог ли я я увеличивать скорость этого вида при помощи нескольких потоков. Я выполняю следующие функции в Java на Четырехъядерном Dell с Windows Vista.

Одна функция (случай управления) является просто рекурсивной:

// 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;
}

Другой находится в функции 'выполнения' класса, который расширяет поток и рекурсивно создает два новых потока каждый раз, когда это называют:

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 не "связываются" достаточно эффективно для размещения различных потоков в различные ядра? Или я пропускаю что-то очевидное?

5
задан Raedwald 1 February 2016 в 08:09
поделиться

4 ответа

Проблема не в многопоточности: я правильно написал многопоточный QuickSort на Java, и он владеет сортировка Java по умолчанию. Я сделал это после того, как стал свидетелем процесса обработки гигантского набора данных, и у меня было только одно ядро ​​16-ядерной машины.

Одна из ваших проблем (огромная) заключается в том, что вы заняты зацикливанием:

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

Это ОГРОМНОЕ нет-нет: это называется зацикливанием занятости, и вы разрушаете перфомансы.

(Другая проблема заключается в том, что ваш код не порождает никаких новых потоков, как вам уже указывалось)

Вам нужно использовать другой способ синхронизации: примером может быть использование CountDownLatch .

Еще один момент: при разделении рабочей нагрузки нет необходимости создавать два новых потока: порождать только один новый поток и делать вторую половину в текущем потоке.

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

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

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

Я не реализовал сортировку слиянием, но QuickSort, и я могу вам сказать, что копирование массивов не происходит.

Что я делаю:

  • выбираю опорные
  • значения обмена по мере необходимости
  • достигли ли мы ограничения потока? (в зависимости от количества ядер)
    • да: отсортировать первую часть в этом потоке
    • нет: создать новый поток
  • отсортировать вторую часть в текущем потоке
  • дождаться завершения первой части, если это еще не сделано (с помощью 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) на количество доступных ядер. Вы можете использовать следующее (один раз, скажем, для инициализации некоторой статической переменной в начале вашей программы: количество ядер вряд ли изменится [если вы не находитесь на машине, допускающей горячую замену ЦП, как это позволяют некоторые системы Sun]):

Runtime.getRuntime().availableProcessors()
12
ответ дан 18 December 2019 в 10:42
поделиться

Сколько элементов в массиве нужно отсортировать? Если элементов слишком мало, время синхронизации и переключения ЦП будет больше времени, которое вы сэкономите для разделения задания на параллельную работу

0
ответ дан 18 December 2019 в 10:42
поделиться

Как говорили другие; Этот код не будет работать, потому что он не запускает новые потоки. Вам нужно вызвать метод start () вместо метода run () для создания новых потоков. Он также имеет ошибки параллелизма: проверки готовой переменной не являются потокобезопасными.

Параллельное программирование может быть довольно сложным, если вы не понимаете основ. Вы можете прочитать книгу Брайана Гетца Параллелизм в Java на практике . В нем объясняются основы и объясняются конструкции (такие как Latch и т. Д.), Упрощающие создание параллельных программ.

3
ответ дан 18 December 2019 в 10:42
поделиться

Накладные расходы на синхронизацию могут быть сравнительно большими и помешать многим оптимизациям.

Кроме того, вы создаете слишком много потоков.

Другой - в функции «run» класса, который расширяет поток, и рекурсивно создает два новых потока каждый раз, когда он вызывается .

Было бы лучше с фиксированным количеством потоков, предположительно 4 на четырехъядерном процессоре. Это может быть реализовано с помощью пула потоков ( учебник ), и шаблон будет «мешком задач». Но, возможно, еще лучше изначально разделить задачу на четыре одинаково больших задачи и выполнить «однопоточную» сортировку по этим задачам. Тогда это будет намного лучше использовать кеши.


Вместо того, чтобы иметь «цикл занятости», ожидающий завершения потоков (кража циклов процессора), вам следует взглянуть на Thread.join () .

1
ответ дан 18 December 2019 в 10:42
поделиться
Другие вопросы по тегам:

Похожие вопросы: