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

Question

Существуют определенные алгоритмы, время выполнения которых может значительно уменьшиться, если разделить задачу и выполнить каждую часть параллельно. Один из этих алгоритмов - сортировка слиянием, где список делится на бесконечно малые части, а затем рекомбинирует в отсортированном порядке. Я решил провести эксперимент, чтобы проверить, могу ли я увеличить скорость такого рода, используя несколько потоков. Я выполняю следующие функции в 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;
}

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

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

Answer 1

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

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

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

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

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

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

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

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

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

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

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

Что я делаю, это:

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

Answer 2

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

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

Answer 3

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

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

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

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

---

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

Answer 4

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