Как ускорить код на Go с помощью закона Амдала

Автор — Владимир Балун

ex-TeamLead в Яндекс
Содержание
При разработке часто возникает вопрос, почему даже при добавлении нескольких ядер CPU код не ускоряется пропорционально их количеству, где в системе возникают «узкие места» и почему оптимизация одного участка кода не всегда дает заметный эффект. Именно здесь помогает закон Амдала.

В этой статье разберем работу закона Амдала простыми словами и на практике. На первый взгляд он может казаться очевидным, пока не начинаешь разбирать, какие ограничения на самом деле стоят за этим эффектом.

1. Закон Амдала в теории

В 1967 году Джин Амдал сформулировал закон, который сегодня считается одним из базовых принципов компьютерной архитектуры.

Закон Амдала:
В случае, когда задача разделяется на несколько частей, суммарное время ее выполнения на параллельной системе не может быть меньше времени выполнения самого медленного фрагмента
Есть важный нюанс в этом объяснении. Даже если другая часть программы может быть ускорена до бесконечности, общее ускорение будет ограничено этой медленной частью.

Даже если у вас есть CPU на 256 ядер, программа не станет работать в 256 раз быстрее. Все ограничивается последовательной частью, которую невозможно распараллелить.

2. Формула закона Амдала

Какое ускорение мы ожидаем, если добавим в компьютер еще одно ядро?

Скорее всего, мы ожидаем ускорение в 2 раза. Однако на практике это невозможно из-за одного ключевого ограничения — доли вычислений, которые остаются последовательными, то есть той части кода, которую нельзя распараллелить. Именно поэтому линейного ускорения в 2 раза не получится.
Для точного расчета этого эффекта используется формула закона Амдала:
Ускорение = 1 / ((1 − P) + (P / S))
где:
  • P — доля вычислений, которую можно ускорить
  • S — ускорение, которое может быть достигнуто в этой части программы
  • (1 − P) — доля вычислений, которые остаются последовательными

Рассмотрим пример в формате задачи

Представим, что 90% программы можно ускорить в 10 раз, например, при помощи добавления новых ядер CPU. Но оставшиеся 10% остаются последовательными и не могут быть ускорены.

Дано:
  • ускорение параллельной части (S): в 10 раз
  • доля параллельной части программы (Р): 90% (0,9)
  • доля последовательной части программы: 10% (0,1)

Теперь оценим максимальное ускорение всей программы с учетом закона Амдала.
По формуле закона Амдала:
Ускорение = 1 / ((1 − P) + (P / S))
Подставим значения:
Ускорение = 1 / ((1 − 0,9) + (0,9 / 10))
Посчитаем:
Ускорение = 1 / (0,1 + 0,09) = 1 / 0,19 ≈ 5,26 раза
Таким образом, даже при добавлении 10 CPU, общее ускорение программы будет ограничено последовательной частью.

Мы разобрали формулу, и теперь давайте перейдем к практике и посмотрим на примере, как можно анализировать отдельные участки кода.

3. Закон Амдала на практике

Напишем функцию на языке программирования Go, которая называется calculate и выполняет некоторое вычисление.
    "testing"
)

// go test -bench=. bench_test.go
// a = 1 / ((1 - P) + (P / S))

func calculate(parallelFactor int) {
    value := 0
    for i := 0; i < 1000000; i++ {
        value += i
    }

    wg := sync.WaitGroup{}
    wg.Add(parallelFactor)
    for i := 0; i < parallelFactor; i++ {
        go func() {
            defer wg.Done()

            localValue := 0
            for j := 0; j < 1000000/parallelFactor; j++ {
                localValue += j
            }
        }()
    }

    wg.Wait()
}
Внутри она последовательно прогоняет цикл на миллионы итераций, выполняя операции синхронно.

Далее запускается определенное количество горутин. Здесь вступает в работу параметр — параллельный фактор, который определяет, как распределяется нагрузка.

Если параллельный фактор равен 2, то миллион операций делится пополам, и каждая горутина получает по 500 тысяч итераций.

Этот код моделирует ситуацию, в которой примерно половина вычислений (50%) вообще не поддается параллелизации, а вторая половина (50%) может выполняться параллельно и ускоряться в зависимости от заданного параметра.
run benchmark | debug benchmark
func BenchmarkCalculation(b *testing.B) {
    parallelFactor := 1
    runtime.GOMAXPROCS(parallelFactor)
    for i := 0; i < b.N; i++ {
        calculate(parallelFactor)
    }
}
Далее был написан бенчмарк и установлен параметр runtime.GOMAXPROCS, равный единице. Для тех, кто не знаком с Go, можно условно считать, что код выполняется на одном ядре. Запускается бенчмарк и анализируется результат. Время выполнения операции составляет 1 008 571 ns/op.
BenchmarkCalculation-8 | 1176 | 1008571 ns/op
testing: BenchmarkCalculation-8 left GOMAXPROCS set to 1
Затем добавляется второе ядро, и ожидается, что код будет выполняться в 2 раза быстрее.
run benchmark | debug benchmark
func BenchmarkCalculation(b *testing.B) {
    parallelFactor := 2
    runtime.GOMAXPROCS(parallelFactor)
    for i := 0; i < b.N; i++ {
        calculate(parallelFactor)
    }
}
Запускаем бенчмарк на двух ядрах и смотрим результат — 734 809 ns/op.
BenchmarkCalculation-8 | 1629 | 734809 ns/op
testing: BenchmarkCalculation-8 left GOMAXPROCS set to 2
Как видно из результатов бенчмарка (1 008 571 ns/op на одном ядре и 734 809 ns/op на двух ядрах), ускорения в 2 раза не произошло. Поэтому давайте разберёмся, какое ускорение было достигнуто на практике.
Используем формулу закона Амдала и подставляем значения.

Дано:
  • ускорение параллельной части (S) = 2
  • доля параллельной части (P) = 0,5
  • доля последовательной части = 0,5
Формула закона Амдала:
a = 1 / ((1 − P) + (P / S))
Подставим значения в формулу:
a = 1 / ((1 − 0,5) + (0,5 / 2)) = 1 / (0,5 + 0,25) = 1 / 0,75 ≈ 1,33
Таким образом, при добавлении дополнительного ядра CPU общее ускорение программы составляет примерно 1,33 раза.

И теперь проверяем, действительно ли этот результат по формуле совпадает с реальным ускорением. Используем значения времени выполнения из двух запусков бенчмарка, приведенных выше:
  • 1 008 571 ns/op — результат на одном ядре
  • 734 809 ns/op — результат на двух ядрах.

Если разделить первое значение на второе, мы получаем ускорение примерно 1,33 раза:
1 008 571 / 734 809 = 1,33
Получается приблизительно то же самое ускорение в 1,33 раза — результаты совпадают, а значит, формула закона Амдала приблизительно верно оценивает реальные возможности ускорения.

4. Вывод

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

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

Еще больше тонкостей golang

Если хочется изучить все подводные камни быстро, структурированно и на практике, приходи на наш курс по внутреннему устройству Golang
Курс «Глубокий Go»
balun.courses
Подойдёт, если хочешь детально разобраться в работе строк, срезов, словарей и других особенностях языка Go
Начать можно бесплатно: в качестве тест-драйва открыли тебе два урока. Можешь протестировать и понять, подходит ли тебе
Особенности аллоцирования объектов
Выравнивание структур данных
Еще погрузиться в Golang можно на курсе «Concurrency в Go» — там мы изучаем многопоточное программирование, практикуемся на реальных задачах, с которыми сталкивались IT-компании, и разрабатываем In-memory key-value базу данных с асинхронной репликацией
Курс «Concurrency в Go»
balun.courses
Поможет углубиться в тему работы с горутинами, каналами, примитивами синхронизации и другими особенностями Concurrency в golang
А если хочешь сменить работу, можно потренироваться на mock-собеседованиях. Это поможет чувствовать себя увереннее и заранее найти свои слабые места, на которых можно споткнуться на реальном собесе
Подготовка к собеседованию по Go
it-interview.io
Сервис mock-собеседований, в котором можно потренироваться с senior’ами из российских BigTech-компаний. Есть бесплатный бот для подготовки

Другие статьи