Швидкий генератор псевдовипадкових чисел на 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 ядрами і більше . Як отримати максимальну продуктивність генератора псевдовипадкових чисел на багатоядерний сервері? Стандартний відповідь C-програміста — «використовувати локальні ДПРЧ для кожного ядра CPU». Номер ядра, на якому виконується поточний потік, можна дізнатися за допомогою функції getcpu . Але тут є кілька перешкод:

Виклик 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 і з такою ж масштабованістю на іншій мові програмування. Чекаю посилання на ці проекти в коментарях до статті.

Опубліковано: 30/05/17 @ 07:00
Розділ Різне

SEO Блог