Быстрый генератор псевдослучайных чисел на Go
Продолжаем знакомство с Go. Первая статья должна была заставить читателей начать писать веб-приложения на Go. В этой статье будет показано, как с помощью простых инструментов Go можно создавать высокопроизводительный код под многоядерные системы.
Для чего нужны псевдослучайные числа
Псевдослучайные числа достаточно широко применяются при разработке программ. Наиболее часто их используют в вероятностных алгоритмах. Например, для выборки фиксированного количества случайных значений из бесконечного ряда aka reservoir sampling. Этот матан используется для построения в режиме онлайн гистограмм (aka percentiles) по времени выполнения запроса либо по размеру ответа. Такие данные дают намного больше информации по сравнению со средними значениями и экстремумами при мониторинге и анализе производительности программ.
Псевдослучайные числа в Go
В стандартную поставку Go входит пакет math/rand, который предоставляет функциональность для генерации псевдослучайных чисел. Например, чтобы получить псевдослучайное число от 0 до N-1, достаточно вызвать функцию rand.Intn. Это потокобезопасная функция — ее можно вызывать из нескольких одновременно запущенных потоков. Но есть одна проблема: скорость ее работы не растет при увеличении количества ядер CPU и даже наоборот — падает в несколько раз:
BenchmarkMathRandInt31n 50000000 36.1 ns/op BenchmarkMathRandInt31n-2 30000000 47.3 ns/op BenchmarkMathRandInt31n-4 10000000 125 ns/op
После названия бенчмарка указано количество ядер CPU, на котором был запущен бенчмарк. Третья колонка — время, затраченное на один вызов функции. Видно, что быстрее всего rand.Int31n работает на одном ядре — около 30 млн вызовов в секунду. На четырех ядрах суммарная скорость снижается до 8 млн вызовов в секунду. Это связано с тем, что «под капотом» rand.Int31n используется стандартный мьютекс, который по определению рубит масштабируемость на корню.
Сейчас уже используются сервера с 64 ядрами и более. Как же получить максимальную производительность генератора псевдослучайных чисел на многоядерном сервере? Стандартный ответ
- Вызов getcpu занимает ненулевое время, которое может превысить время, необходимое для генерации следующего псевдослучайного числа.
- Getcpu может вернуть некорректный номер ядра, если операционная система решит перенести текущий поток на другое ядро во время вызова getcpu. Поэтому локальный генератор для каждого ядра CPU должен быть защищен мьютексом. Это тоже увеличивает время, необходимое на генерацию числа.
Может, есть решение получше? Например, использовать thread local storage для хранения отдельных ГПСЧ на каждый поток. Не выйдет по следующим причинам:
- Go не предоставляет доступ к потокам операционной системы. В Go есть только горутины, которые исполняются на потоках операционной системы.
- Стандартная библиотека Go не предоставляет API для управления thread local storage или goroutine local storage.
Есть еще один вариант — сделать массив ГПСЧ, защищенных отдельными мьютексами, и обращаться к ним последовательно через глобальный атомарно инкрементируемый индекс. Вот результаты бенчмарков для такого варианта:
BenchmarkMathRandRNGInt31nArray 100000000 61.6 ns/op BenchmarkMathRandRNGInt31nArray-2 100000000 75.9 ns/op BenchmarkMathRandRNGInt31nArray-4 200000000 44.8 ns/op
Производительность на одном ядре почти в два раза ниже, чем в предыдущем бенчмарке. Это объясняется дополнительными накладными расходами на атомарный инкремент глобального индекса. Зато на четырех ядрах этот вариант опережает предыдущий в 3 раза. Но итоговая производительность бенчмарка на четырех ядрах все равно ниже производительности предыдущего варианта на одном ядре.
Если количество горутин, генерирующих случайные числа, ограничено и постоянно во времени, то можно завести в каждой такой горутине свой ГПСЧ, чтобы получить максимальную производительность и масштабируемость. Но это не всегда возможно. Например, веб-сервер обрабатывает каждый входящий запрос в отдельной горутине. Таким образом, количество горутин зависит от текущей нагрузки на сервер и его сложно контролировать из обработчика запросов.
Существует ли более скоростной и масштабируемый вариант? Да!
Масштабируемый ГПСЧ на sync.Pool
В стандартной библиотеке Go есть классная штука — sync.Pool. Это хранилище повторно используемых объектов, куда можно складывать неприменяемые объекты, чтобы кто-то другой смог их достать и повторно использовать. sync.Pool оптимизирован под использование на многоядерных компьютерах. Что если хранить набор ГПСЧ в sync.Pool, доставая их оттуда для генерации следующего псевдослучайного числа? Смотрим результаты бенчмарков:
BenchmarkUint32n 300000000 29.4 ns/op BenchmarkUint32n-2 300000000 17.4 ns/op BenchmarkUint32n-4 500000000 14.3 ns/op
Как видим, скорость ГПСЧ растет с увеличением количества ядер. На четырех ядрах удается достичь 70 млн вызовов в секунду. Это лучше первого варианта в 8 раз и лучше второго варианта в 3 раза.
Кто-то может подумать, что ради достижения такой производительности пришлось пожертвовать удобством API. Нет, API — простое, как грабли: вызываешь функцию fastrand.Int32n(N) — получаешь псевдослучайное число в диапазоне от 0 до N-1. Данная функция потокобезопасна — ее можно вызывать из параллельно работающих потоков.
Кто-то заподозрит, что пришлось пожертвовать качеством кода в угоду производительности. Вроде код выглядит нормально. Привожу полный исходный код пакета fastrand:
// Package fastrand implements fast pesudorandom number generator
// that should scale well on multi-CPU systems.
//
// Use crypto/rand instead of this package for generating
// cryptographically secure random numbers.
package fastrand
import (
cryptorand "crypto/rand"
"fmt"
"sync"
)
// Uint32 returns pseudorandom uint32.
//
// It is safe calling this function from concurrent goroutines.
func Uint32() uint32 {
v := rngPool.Get()
if v == nil {
v = &RNG{
x: getRandomUint32(),
}
}
r := v.(*RNG)
x := r.Uint32()
rngPool.Put(r)
return x
}
var rngPool sync.Pool
// Uint32n returns pseudorandom uint32 in the range [0..maxN).
//
// It is safe calling this function from concurrent goroutines.
func Uint32n(maxN uint32) uint32 {
x := Uint32()
// See http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
return uint32((uint64(x) * uint64(maxN)) >> 32)
}
// RNG is a pseudorandom number generator.
//
// It is unsafe to call RNG methods from concurrent goroutines.
type RNG struct {
x uint32
}
// Uint32 returns pseudorandom uint32.
//
// It is unsafe to call this method from concurrent goroutines.
func (r *RNG) Uint32() uint32 {
if r.x == 0 {
r.x = getRandomUint32()
}
// See https://en.wikipedia.org/wiki/Xorshift
x := r.x
x ^= x << 13
x ^= x >> 17
x ^= x << 5
r.x = x
return x
}
// Uint32n returns pseudorandom uint32 in the range [0..maxN).
//
// It is unsafe to call this method from concurrent goroutines.
func (r *RNG) Uint32n(maxN uint32) uint32 {
x := r.Uint32()
// See http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
return uint32((uint64(x) * uint64(maxN)) >> 32)
}
func getRandomUint32() uint32 {
var buf [4]byte
_, err := cryptorand.Read(buf[:])
if err != nil {
panic(fmt.Sprintf("BUG: cannot read random number: %s", err))
}
return uint32(buf[3]) | (uint32(buf[2]) << 8) | (uint32(buf[1]) << 16) | (uint32(buf[0]) << 24)
}
Исходники всех бенчмарков, рассмотренных выше, находятся в файле fastrand_timing_test.go. Чтобы запустить эти бенчмарки, достаточно выполнить две команды:
$ go get -u github.com/valyala/fastrand $ go test -bench=. github.com/valyala/fastrand
Первая команда скачает исходники fastrand в папку $GOPATH/src, вторая — запустит все бенчмарки, находящиеся в исходниках fastrand.
По умолчанию бенчмарки запускаются на всех доступных ядрах процессора. Если хотите ограничить количество используемых ядер, то укажите это в переменной окружения GOMAXPROCS. Например, для запуска бенчмарков на одном ядре выполните команду:
$ GOMAXPROCS=1 go test -bench=. github.com/valyala/fastrand
Бенчмарки с тестами на Go писать очень просто. Для этого достаточно прочесть краткую документацию к пакету testing из стандартной библиотеки Go.
Заключение
Разработка быстрых генераторов псевдослучайных чисел может быть простой и интересной. Особенно, если использовать Go :)
Go идеально подходит для создания высокопроизводительного кода под многоядерные компьютеры. В Go минимум бесполезных абстракций и головоломных конструкций. Благодаря этому код на Go легко написать и легко понять. Мы это увидели на наглядном примере. Пакет fastrand успешно используется в наших высоконагруженных сервисах.
Сомневающимся предлагаю написать аналог fastrand с таким же удобным API и с такой же масштабируемостью на другом языке программирования. Жду ссылки на эти проекты в комментариях к статье.
