Хуже, когда идут процедуры в параллельной реализации алгоритма быстрой сортировки

Примечание: вопрос" параллельный сегмент Go-lang работает медленнее, чем сегмент серии " касался условий гонки, у этого есть еще одна проблема, так что имхо это не дубликат.

Я пытаюсь найти объяснение следующей ситуации: Запуск параллельного quicksort приводит к значительно более длительному времени выполнения при использовании процедур go.

Бенчмарки следуют за кодом: 

package c9sort

import (
    "time"
)

var runInParllel bool

func Quicksort(nums []int, parallel bool) ([]int, int) {
    started := time.Now()
    ch := make(chan int)
    runInParllel = parallel

    go quicksort(nums, ch)

    sorted := make([]int, len(nums))
    i := 0
    for next := range ch {
        sorted[i] = next
        i++
    }
    return sorted, int(time.Since(started).Nanoseconds() / 1000000)
}

func quicksort(nums []int, ch chan int) {

    // Choose first number as pivot
    pivot := nums[0]

    // Prepare secondary slices
    smallerThanPivot := make([]int, 0)
    largerThanPivot := make([]int, 0)

    // Slice except pivot
    nums = nums[1:]

    // Go over slice and sort
    for _, i := range nums {
        switch {
        case i <= pivot:
            smallerThanPivot = append(smallerThanPivot, i)
        case i > pivot:
            largerThanPivot = append(largerThanPivot, i)
        }
    }

    var ch1 chan int
    var ch2 chan int

    // Now do the same for the two slices
    if len(smallerThanPivot) > 1 {
        ch1 = make(chan int, len(smallerThanPivot))
        if runInParllel {
            go quicksort(smallerThanPivot, ch1)
        } else {
            quicksort(smallerThanPivot, ch1)
        }
    }
    if len(largerThanPivot) > 1 {
        ch2 = make(chan int, len(largerThanPivot))
        if runInParllel {
            go quicksort(largerThanPivot, ch2)
        } else {
            quicksort(largerThanPivot, ch2)
        }
    }

    // Wait until the sorting finishes for the smaller slice
    if len(smallerThanPivot) > 1 {
        for i := range ch1 {
            ch <- i
        }
    } else if len(smallerThanPivot) == 1 {
        ch <- smallerThanPivot[0]
    }
    ch <- pivot

    if len(largerThanPivot) > 1 {
        for i := range ch2 {
            ch <- i
        }
    } else if len(largerThanPivot) == 1 {
        ch <- largerThanPivot[0]
    }

    close(ch)
}

Критерии для случайной перестановки 500000 целых чисел:

Пробежал 100 раз

Не параллельное среднее - 1866мс

Параллельное среднее - 2437 МС

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

Заранее благодарю вас.

2 2
concurrency parallel-processing quicksort goroutine

2 ответа:

Общий ответ заключается в том, что координация между потоками имеет свои издержки, поэтому отправка задачи в другую горутину может ускорить процесс только в том случае, если задача имеет хотя бы определенный размер. Так что не отправляйте одиночные предметы.

Для алгоритма "разделяй и властвуй", такого как quicksort, способы распараллеливания могут быть интересными. Как правило: при рекурсии вы можете запустить задачу "сортировать одну половину массива" в goroutine, если она достаточно большая. Часть "если он достаточно большой" - это то, как вы уменьшаете координацию накладные расходы.

Более подробно, это выглядит так:

  1. Написать непараллельную qsort(data []int)

  2. Измените qsort, чтобы по желанию взять *sync.WaitGroup мы вызовем wg для сигнализации, что это сделано. Добавьте if wg != nil { wg.Done() } Перед каждым из его returns.

  3. Где qsort рекурсии, пусть он проверяет, является ли половина данных, которые он собирается сортировать, большими (скажем, более 500 элементов?), и

    • если он большой, начните другую задачу: wg.Add(1); go qsort(half, wg)
    • Если это не так, сортировка здесь и сейчас: qsort(half, nil)

  4. Оберните qsort , чтобы скрыть параллельный механизм от пользователя: например, сделайте quicksort(data) do wg := new(sync.WaitGroup), сделайте начальный wg.Add(1), вызовите qsort(data, wg) и сделайте wg.Wait(), чтобы дождаться завершения всех фоновых сортировок.

Это не оптимальная стратегия, потому что она продолжает разветвлять новые goroutines даже после того, как есть достаточно задач, чтобы держать ваши ядра занятыми. И есть много настройки, которую можно было бы сделать вокруг просто как Вы передаете некоторые задачи на задний план. Но главное в том, что использование другого потока только для больших подзадач - это способ распараллелить quicksort, не разбив его координационными накладными расходами.

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

Существует также стратегия снизу вверх-сортировка частей, а затем слияние-используемая, например, в этом параллельном пакете сортировки. Однако код слияния на месте, который использует пакет, является сложным.

(и если вы не установили GOMAXPROCS, установите его с чем-то вроде runtime.GOMAXPROCS(runtime.NumCPU()) в main.)

Наконец, посмотрите на пакет сортировки Go. Там много кода, но он довольно ясен, и как только вы его получите, вы сможете проводить свои эксперименты с "реальным", плотным видом реализация.

6

Оказывается, это было очень просто. Поскольку я на новой машине, переменная GOMAXPROCS не была установлена.

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

Using 16 goroutines
Ran 100 times

Non parallel average - 1980
Parallel average - 1133

Установить число ядер: 

Using 8 goroutines
Ran 100 times

Non parallel average - 2004
Parallel average - 1197

Кстати, это довольно последовательно. Среднее значение для удвоенного числа ядер всегда немного лучше.

Эталон для большей коллекции (1000000): 

Using 8 goroutines
Ran 100 times

Non parallel average - 3748
Parallel average - 2265

С двойным: 

Using 16 goroutines
Ran 100 times

Non parallel average - 3817
Parallel average - 2012
2