Golang. Как распараллелить обработку слайса, чтобы получить выигрышь в скорости?
Есть слайс, содержащий большое количество элементов, допустим 100000. Мне необходимо написать функцию, которая умножит каждый элемент данного слайcа на 2. Я хочу, чтобы эта функция работала конкурентно и имела выигрыш в скорости по сравнению с функцией, делающей тоже самое последовательно.
Последовательная функция:
func doubleSlice(s []int) {
for i := range s {
s[i] = s[i] * 2
}
}
Конкурентный вариант:
func concurentDoubleSlice(s []int) {
var wg sync.WaitGroup
for i := range s {
wg.Add(1)
go func(i int) {
defer wg.Done()
s[i] = s[i] * 2
}(i)
}
wg.Wait()
}
Я прочтал, что данный вариант будет замедлять программу из-за большого количество вызываемых горутин и сборщика мусора. Также я прочитал, что данная проблема может быть решена с помощью буферизированного канала, но реализовать его и получить выигрышь в скорости мне не удоалось.
Как я могу ускорить процесс умножения элементов слайса, с помощью конкурентности?
Ответы (2 шт):
Попробуйте разбить массив не на 100000 частей (как это сейчас сделано с точностью до элемента), а две, три или десять:
0 - 9999, 10000 - 19999 и т.д.
и каждую часть обработайте отдельной гороутиной. Достаточно выделить непересекающиеся диапазоны индексов в массиве.
UPD:
package main
import (
"fmt"
"runtime"
"runtime/debug"
"sync"
"time"
)
const size = 100000000
func main() {
for i := 20; i > 0; i-- {
debug.SetGCPercent(-1)
src := make([]int, size)
for idx := range src {
src[idx] = 42
}
fmt.Println("до ", src[:4], src[size-4:])
t1 := time.Now()
multiply2(src, i)
dur := time.Since(t1)
fmt.Println("после ", src[:4], src[size-4:])
fmt.Printf("число гороутин: %d, время: %s\n", i, dur)
fmt.Println()
runtime.GC()
}
}
func multiply2(src []int, workers int) {
if workers <= 0 {
return
}
wg := new(sync.WaitGroup)
last := 0
for i := 0; i < workers; i++ {
idx1 := len(src) / workers * i
idx2 := len(src) / workers * (i + 1)
last = idx2
wg.Add(1)
go func(idx1, idx2 int) {
defer wg.Done()
for idx := idx1; idx < idx2; idx++ {
src[idx] = src[idx] * 2
}
}(idx1, idx2)
}
if last < len(src)-1 {
idx1 := last
idx2 := len(src)
wg.Add(1)
go func(idx1, idx2 int) {
defer wg.Done()
for idx := idx1; idx < idx2; idx++ {
src[idx] = src[idx] * 2
}
}(idx1, idx2)
}
wg.Wait()
}
ИМХО, самый простой способ - разбить слайс на под-слайсы, и обработать их в горутинах.
func doubleSlice(s []uint) {
for i := range s {
s[i] = s[i] * 2
}
}
func sliceWorker[T any](f func([]T), s []T, wg *sync.WaitGroup) {
defer wg.Done()
f(s)
}
func parallelRunner[T any](f func([]T), s []T, n int) {
if n < 2 || len(s) < 2 {
f(s)
return
}
wg := &sync.WaitGroup{}
sliceLen := (len(s))/n + 1
for i := 0; i < len(s); i += sliceLen {
wg.Add(1)
go sliceWorker(f, s[i:min(i+sliceLen, len(s))], wg)
}
wg.Wait()
}
Так как у вас операция над элементами быстрая, то накладные расходы на запуск горутины могут быть больше, чем выигрыш от распараллеливания.
В любом случае, нужно делать замеры. Для этого в Го есть бенчмарки.
const N = 1000000
var reference []uint
func init() {
reference = make([]uint, N)
for i := 0; i < N; i++ {
reference[i] = uint(i % 1000)
}
}
func BenchmarkParallelSlice(b *testing.B) {
for n := 0; n <= 16; n++ {
target := make([]uint, N)
copy(target, reference)
b.Run(
fmt.Sprintf("%02d", n),
func(b *testing.B) {
for i := 0; i < b.N; i++ {
parallelRunner(doubleSlice, target, n)
}
},
)
}
}
Получилось вот что:
Running tool: C:\Software\go\bin\go.exe test -benchmem -run=^$ -bench ^BenchmarkParallelSlice$ example.org/parallel
goos: windows
goarch: amd64
pkg: example.org/parallel
cpu: Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz
BenchmarkParallelSlice/00-8 1222 840182 ns/op 0 B/op 0 allocs/op
BenchmarkParallelSlice/01-8 1588 806857 ns/op 0 B/op 0 allocs/op
BenchmarkParallelSlice/02-8 2023 585552 ns/op 155 B/op 3 allocs/op
BenchmarkParallelSlice/03-8 2658 534651 ns/op 218 B/op 4 allocs/op
BenchmarkParallelSlice/04-8 2504 545334 ns/op 277 B/op 5 allocs/op
BenchmarkParallelSlice/05-8 2671 717660 ns/op 336 B/op 6 allocs/op
BenchmarkParallelSlice/06-8 2676 486645 ns/op 400 B/op 7 allocs/op
BenchmarkParallelSlice/07-8 2502 472972 ns/op 464 B/op 8 allocs/op
BenchmarkParallelSlice/08-8 2868 466620 ns/op 528 B/op 9 allocs/op
BenchmarkParallelSlice/09-8 2736 468633 ns/op 592 B/op 10 allocs/op
BenchmarkParallelSlice/10-8 2364 432166 ns/op 656 B/op 11 allocs/op
BenchmarkParallelSlice/11-8 2710 549252 ns/op 720 B/op 12 allocs/op
BenchmarkParallelSlice/12-8 3033 436206 ns/op 785 B/op 13 allocs/op
BenchmarkParallelSlice/13-8 2348 496906 ns/op 849 B/op 14 allocs/op
BenchmarkParallelSlice/14-8 3018 414058 ns/op 912 B/op 15 allocs/op
BenchmarkParallelSlice/15-8 2677 479136 ns/op 977 B/op 16 allocs/op
BenchmarkParallelSlice/16-8 2883 469376 ns/op 1040 B/op 17 allocs/op
PASS
ok example.org/parallel 25.360sсамый быстрый вариант оказался с 14 горутинами, но это не точно. Увеличение числа горутин не гарантирует улучшение общего времени из-за накладных расходов на запуск горутин. У вас очень быстрая процедура обработки слайса, поэтому даже небольшие задержки в планировщике значительно влияют на результат. Я погонял бенчмарк несколько раз, и более-менее стабильные результаты получены для 2-3 параллельных обработчиков. Для остальных характерны выбросы с большим замедлением.
Здесь нет готовой теории, так как производительность параллельного решения очень сильно зависит от кэша процессора, нагрузки на шину данных и вообще загрузку ядер. Поэтому можно только экспериментально подобрать наилучшие параметры для распараллеливания.