×Закрыть

Быстрый генератор псевдослучайных чисел на 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. Но тут есть несколько препятствий:

  1. Вызов getcpu занимает ненулевое время, которое может превысить время, необходимое для генерации следующего псевдослучайного числа.
  2. Getcpu может вернуть некорректный номер ядра, если операционная система решит перенести текущий поток на другое ядро во время вызова getcpu. Поэтому локальный генератор для каждого ядра CPU должен быть защищен мьютексом. Это тоже увеличивает время, необходимое на генерацию числа.

Может, есть решение получше? Например, использовать thread local storage для хранения отдельных ГПСЧ на каждый поток. Не выйдет по следующим причинам:

  1. Go не предоставляет доступ к потокам операционной системы. В Go есть только горутины, которые исполняются на потоках операционной системы.
  2. Стандартная библиотека 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 и с такой же масштабируемостью на другом языке программирования. Жду ссылки на эти проекты в комментариях к статье.

LinkedIn

112 комментариев

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.

Сгенерите случайные числа в массив и читайте из него подряд. По проходу массива 1000 раз перегенерите массив.

Это же стандартное решение. Вот только в эмбединге может и не быть места в памяти для подобного массива.

Вот только в эмбединге может и не быть

... гошечки. ^_^

Не учел, что в Го все изобретают велосипеды заново.

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

Скиньте, пожалуйста, ссылку на код. Интересно посмотреть, что такое «функциональный генератор, принимающий сид на вход» и как он масштабируется на многопроцессорных системах.

Да уже выкинул. Берёте ваш же генератор, но не храните его состояние внутри, а передаете как входной параметр в функцию.

а где хранить это состояние при обработке запроса? Вот как выглядит обработчик запроса:

func handler(ctx *fasthttp.RequestHandler) {
    // откуда тут взять oldSeed?
    result, newSeed  := random(oldSeed)
    // куда теперь сохранить newSeed?
}

Одно случайное число на реквест? Да хоть взять адрес переменной ctx xor с каким нить нанотаймом и скормить в качестве сида. Новый сид тогда можно вообще не хранить. Если много, то в обычной локальной переменной. Жаль, id горутины вытащить можно, но сильно не рекомендуется. Завтра гляну ещё исходники пула, а то одолевают смутные сомнения.

Одно случайное число на реквест?
Не одно, а много. Каждое число генерируется при добавлении нового значения (время выполнения запроса либо определенной функции) внутри библиотеки гистограмм.
Если много, то в обычной локальной переменной.
Локальная переменная уничтожается при выходе из функции.
Локальная переменная уничтожается при выходе из функции.

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

Я имел в виду нечто вроде
val (result, newSeed) = random (oldSeed)
Масштабироваться по ядрам будет как банальный sin(x)

Валялькин, хочешь топить за Го. Сделай для него IDE, подобную Матлабу. Либы с частью математики уже есть у Го.
Возможно к либам надо добавить кода, чтобы они могли юзать на выбор MKL, ACML, OpenCL, CUDA, ATLAS.

ну вообще-то есть уже более-менее приличный плагин к IDEA
во всяком случае не в vim’e код писать, и отладчик какой-никакой работает

Есть и LiteIDE, но это не то. Это для того, чтобы чуть более удобно писать на Go, чем в vim.
Речь о другом, о специально заточенной под математику IDE. Вот подобное могло бы привлечь в Го толпы математиков. По сути сейчас в мире есть Матлаб с сильно устаревшим языком и очень удобной IDE и куча других языков получше матлабовского, но не удобных для использования.
Разница в том, что в матлабе я больше думаю, что написать, а в других языках еще и как написать.
По сути, что R, что Питон, что Го — одного поля ягоды.

у R и питона есть нормальные IDE

R-Studio? не согласен, не тянет это на нормальную IDE, во всяком случае в моем понимании
PyCharm? тут согласен, хотя и просто плагин для IDEA вполне себе ничего

лучше, но все равно до нормальной IDE как до Мадрида пешедралом
а для Го есть плагин IDEA
поэтму vim можно смело отправлять на свалку

Для R — это убожетсво.
Для Питона IDE ничего так, но она универсальная, что ее делает неудобной для частного случая.

По сути, что R, что Питон, что Го — одного поля ягоды.

ты уверен?
специализированный язык для матстата, интерпретатор байткода общего назначения и компилятор (это кстати единственное что там вообще есть нормального) с довольно специфической нишей — для тебя примерно одно и то же?

По сравнению с матлабам таки да.

И я тебе скажу основной минус матлаба нынче: это древний, убогий язык и еще более убогий интерпретатор.
Но за счет IDE он до сих пор удобнее всего остального новомодного стада.
У Go и Питона нет нативных векторных типов и операций.
У R убогая IDE.

вывод?
для задач не требующих адской производительности — юзай себе матлаб дальше
а если нужна производительность — бери CUDA/OpenCL и C#/Java для обертки

Именно так. На матлабе придумываю алгоритм, отлаживаю, тестирую.
Если нужно портирую в плюсы с юзанием MKL, ATLAS, OpenCL...

Но, я написал минусы матлаба и они реальные. Сейчас матлаб опять в стадии застоя, как и в прошлый раз, когда начали развиваться SciLab и Octave. Затем mathworks опомнилась и ожила.

Не. И LiteIDE мне больше понравилась, но она универсальная для языка, а не специализированная.

Благодаря этому код на Go легко написать и легко понять.
v := rngPool.Get()
x := r.x

Куда понятнее было бы если бы у переменных были нормальные имена. Если `x` и `r` — еще можно поугадывать зная контекст задачи, то вот `v` почему так называется (сокращение от variable?)
---
Если ваша цель таки привлеч людей в Го, а не просто написать цикл статей «Велосипедный парк Валялкина», то хорошо бы
— чтобы код был читабельным
— пояснить какие гарантии предоставляет sync.Pool? В доке вроде как написано что Гет не обязан ничего оттуда читать
— что такое cryptorand.Read и почему оно используется? Это вроде как ИО, почему бы не взять «текущее время»
— чтобы выводы были выводами (каждое утверждение должно быть доказано в тексте), а не просто набором тезисов в которые вы хотите верить

Куда понятнее было бы если бы у переменных были нормальные имена. Если `x` и `r` — еще можно поугадывать зная контекст задачи, то вот `v` почему так называется (сокращение от variable?)

В go принято использовать короткие названия локальных переменных, если между их объявлением и последним использованием менее пару десятков строчек. Также принято использовать короткие имена для полей структур, если количество этих полей небольшое (в нашем случае у структуры `RNG` только одно поле `x`). Это облегчает чтение кода — вот вы же как-то догадались, что значат `r` и `x`, даже не имея опыта работы с go.

`v` - общепринятое название переменной типа `interface{}` (пустой интерфейс).

— чтобы код был читабельным
Вроде код получился читабельным :) Поднимите руки, кто еще считает код нечитабельным.
— пояснить какие гарантии предоставляет sync.Pool? В доке вроде как написано что Гет не обязан ничего оттуда читать
 В статье приведена ссылка на документацию по sync.Pool. Если вкратце, то содержимое sync.Pool обнуляется в конце каждого цикла garbage collection. Но, т.к. такие циклы обычно происходят реже одного раза в секунду (в некоторых наших сервисах gc происходит раз в минуту), то за это время можно много миллионов раз воспользоваться сохраненными в sync.Pool объектами (в нашем случае — ГПСЧ).
— что такое cryptorand.Read и почему оно используется? Это вроде как ИО, почему бы не взять «текущее время»
crypto/rand содержит функциональность для генерации криптографически стойких случайных чисел. Действительно, тут оно ни к чему, поэтому перевел код на «текущее время». Спасибо за совет.
— чтобы выводы были выводами (каждое утверждение должно быть доказано в тексте), а не просто набором тезисов в которые вы хотите верить
 Не умею писать выводы :( Научите.
Вроде код получился читабельным :) Поднимите руки, кто еще считает код нечитабельным.
`v` - общепринятое название переменной типа `interface{}` (пустой интерфейс).

Но в вашем случае `v` имеет тип `*main.RNG` (или что-то в этом роде), в то время как пустой интерфейс — нил. Кстати, а если таких переменных 2 или 3?
---

Если вкратце, то содержимое sync.Pool обнуляется в конце каждого цикла garbage collection.
В доке вроде как написано что Гет не обязан ничего оттуда читать

Get may choose to ignore the pool and treat it as empty
---

Не умею писать выводы :( Научите.

Это будет очень проблематично: онлайн научить человека в 30-35 лет делать выводы из текста, особенно с учетом того что его должны были бы учить этому в ВУЗе (в более благоприятном возрасте).

На джава когда-то была такая же проблема. С

скорость ее работы не растет при увеличении количества ядер CPU

поэтому там теперь есть ThreadLocalRandom. Думаю когда-то и в Го появится :).

Надеюсь, что так и будет. По крайней мере об этом уже задумались

Сомневающимся предлагаю написать аналог fastrand с таким же удобным API и с такой же масштабируемостью на другом языке программирования.

А якщо в цій мові нема проблеми Go зі thread-local random number generator?

Або так (плюси, код не мій, генератор і дестріб’юшн можна обрати інший, якщо хочеться):

int int_rand(const int & min, const int & max) {
    thread_local std::mt19937 generator;
    std::uniform_int_distribution<int> distribution(min,max);
    return distribution(generator);
}

Круто! Кстати, «под капотом» у thread_local из C++ не все так просто — www.akkadia.org/drepper/tls.pdf . Думаю, у rust не проще.

Два момента:
— rust и C++ намного сложнее go;
— на них затруднительно создать сотни тысяч одновременно работающих потоков, чтобы каждый из них обрабатывал отдельное клиентское подключение, которое может потребовать дополнительных обращений по сети.

Кстати, «под капотом» у thread_local из C++ не все так просто — www.akkadia.org/drepper/tls.pdf . Думаю, у rust не проще.

Люблю такі речі. Дякую! Почитаю.

rust и C++ намного сложнее go;

Це холіварне питання. Вони ж не просто так складніше. Ну цей. Матан і т.п. :)

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

Про це хз, ніколи цього не робив.

Про це хз, ніколи цього не робив.

В стандартной поставке c++ и rust нет легковесных потоков подобных goroutines из go. Поэтому приходится работать с обычными потоками операционной системы. А они имеют следующие недостатки по сравнению с goroutines:

1) Размер стэка нельзя изменять после старта потока. Поэтому на каждый поток выделяется слишком много памяти под стэк, чтобы хватило на все случаи (обычно несколько мегабайт и больше). В go размер стека динамически меняется. Поэтому при старте горутины выделяется 2КБ или 4КБ стек, который потом растет по мере необходимости. Выходит, что для ста тысяч потоков под C++ или rust нужно более 100 гигабайт памяти под стэк, а для go — от 200 мегабайт,.

2) Переключение между потоками операционной системы занимает намного больше времени по сравнению с переключеним между goroutines в go. Для переключения потоков ОС нужно выполнить следующие опреации:
— перейти в режим ядра (занимает минимум пару сотен тактов CPU)
— переключить контекст потока — сохранить в памяти полный набор регистров CPU текущего потока, после чего загрузить полный набор регистров CPU нового потока. Также может понадобиться переключение адресного пространства и сброс TLB, если новый поток находится в другом процессе. На все это также уходит пару сотен тактов CPU.
— вернуться обратно в пользовательский режим (еще пару сотен тактов CPU)

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

1) не правда, Линух динамически добавляет блок памяти в стек, если стек превысил текущий размер. Да и превышение стеком блока памяти уже симптом того, что что-то криво.
2) смена контекста горутины повлечет инвалидацию кеша (если, конечно, все горутины не используют одни и те же данные — а тогда нет смысла в нескольких горутинах). Она как раз и приводит к тормозам при переключении контекста.
3) а по какому событию переключаются горутины? само событие/мютекс/сокет не завязано в кернел?

Винда тоже добавляет по странично вплоть до 1Мб помнится

Да и можно ключами компиляции всем этим управлять.

А что относительно этого:

В стандартной поставке c++ и rust нет легковесных потоков подобных goroutines из go. Поэтому приходится работать с обычными потоками операционной системы.

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

Вот мне в С++ очень интересны «легковесные» потоки. Очень часто есть что распараллелить на много ядер, но мютексы всё съедают.

Про легковесные потоки — коммент прямо под этим.
В бусте есть корутины, но я не пользовался.
Если мютексы все съедают — значит, либо слишком мелкие куски задачи раздются разным потокам, либо она вообще не параллелится нормально.

Да, именно мелкие.
Вот поэтому и спрашиваю. Если бы знал, то не спрашивал.
Хотелось бы услышать мнения о бустовских короутинах, TBB или чем другом или ссылки увидеть.
С большими кусками все просто. Я надеялся, что openmp с мелкими хорош будет, но не надежда не оправдалась или я какие параметры ему не задал.

Мелки куски нельзя параллелить.

(примерно) Требования для симметричного распараллеливания:
1) Непересекающиеся входные и выходные массивы основных данных
2) Примерно одинаковый объем работы на каждый поток
3) Отсутствие зависимостей между данными, обрабатываемыми разными потоками
4) Объем вычислений для каждого потока должен быть существенно большим, чем затраты на возможное переключение контекста

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

Для асимметричного распараллеливания (каждый поток делает свой кусок алгоритма):
1) Алгоритм должен состоять из частей с четко определенными интерфейсами и зависимостями
2) Система должна быть толерантна к увеличению времени обработки пакета данных (вместо обработки одного пакета процессорное время делится между N одновременно обрабатываемыми пакетами)
3) Выделенные в потоки части алгоритма должны иметь примерно одинаковую сложность обработки
4) Надо обратить внимание, как передаются данные между блоками обработки. Варианты: а) предвыделенная структура, в которую каждый блок дописывает свой кусок б) каждый блок выделяет выходной кусок и стирает входной в) циклические буфера (lock-free) между каждыми двумя обработчиками в конвейере.
5) Отпрофайлить и убедиться, что передача данных не тормозит систему. Настроить тип и объем передаваемых данных.

Да всё это понятно и известно. Но... есть несколько ядер и как бы разумно их заюзать и мы упираемся в

4) Объем вычислений для каждого потока должен быть существенно большим, чем затраты на возможное переключение контекста

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

Например, если подолбиться то генетический алгоритм, симуляцию отжига можно написать на GPU очень приличную. Ну ладно, это не тривиальные алгоритмы. Но я могу минимизацию сеточной функции посчитать на GPU простым брутфорсом и забить на градиентные спуски с их итерациями.
Единственный минус в обмене данными с GPU.
Или мои выводы не корректны?

C OpenCL на радеоне только один минус — он завешивает весь линух, если с памятью ошибся или ошибка в счетном ядре.

Можно подумать не про распараллеливание кусков алгоритма расчета, а про использование Actors или Pipes and Filters. В этом случае разные потоки обрабатывают разные шаги алгоритма.

Actors или Pipes and Filters.

Поясни.
И расчета, но маленькие. Понятно, что OpenCL можно заюзать, но не очень хочется лишний раз с ним возиться. Очень замороченно.
Клади кернел в текст, компилируй в коде, фикси, отлаживай отладочной печатью — ну очень не удобно.
А вот IDE с поддержкой OpenCL и компилятором и отладчиком сразу в бинарник для GPU я не нашел.

www.dossier-andreas.net/...​ture/pipe_and_filter.html
суть в последовательном применении алгоритмов, меняющих данные. Например, обработка видео у робота, или скана у распознавалки текста.

en.wikipedia.org/wiki/Actor_model
суть в том, что важные куски системы выделяются в отдельные модули, не имеющие общих данных. Модули кидаются друг с другом неблокирующими сообщениями. Если есть длинные цепочки событий, превращается в ад и стейт машины.

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

И с видео, звуком реализация обычно сложная получается. Нужно писать кучу кода для параллелизации. Например я могу запустить параллельно несколько кадров в обработку, но мне они нужны последовательно и в итоге я должен всё это согласовать, написать кучу «очередей и блокировок навешать». В итоге код получается навороченным очень.
Да я получу задержу на количество наблюдений (пусть это и целый кадр) — это часто не проблема, но код очень навороченный получается обычно и его отладка тоже.

Вот мне в С++ очень интересны «легковесные» потоки. Очень часто есть что распараллелить на много ядер, но мютексы всё съедают.
Тут go не поможет. Горутины хороши для i/o-bound задач типа микросервисной архитектуры, где каждый входящий запрос может породить несколько запросов по сети на другие микросервисы.

Если же запустить на N-ядерном процессоре 1000*N CPU-bound горутин, то они выполнятся за то же время, что и N потоков для той же задачи.

Если же запустить на N-ядерном процессоре 1000*N CPU-bound горутин, то они выполнятся за то же время, что и N потоков для той же задачи.

Почему-то бенчмарки показывают, что на CPU-bound задачах горутины как раз сливают

Горутины хороши для i/o-bound задач типа микросервисной архитектуры,

Вот подобных постов я и ждал. Это очень полезная инфа.

Линух динамически добавляет блок памяти в стек, если стек превысил текущий размер.
Не путайте виртуальную память с физической. Под стек выделяется виртуальная память. При первом обращении к каждой странице виртуальной памяти выделяется физическая страница памяти. В теории размер виртуальной памяти каждого процесса на 64-битной системе может достигать 2^64 байт, т.е. намного больше объема физической памяти. Но на практике операционная система ограничивает объем виртуальной памяти суммарным размером физической памяти плюс размер файлов подкачки. См. www.kernel.org/...​/vm/overcommit-accounting . Поэтому у вас вряд ли получится запустить миллион одновременных потоков на системе с 10 гигабайтами памяти. Миллион горутин в go — спокойно запустятся.
смена контекста горутины повлечет инвалидацию кеша (если, конечно, все горутины не используют одни и те же данные — а тогда нет смысла в нескольких горутинах). Она как раз и приводит к тормозам при переключении контекста.
Зависит от выполняемых задач. Например, в веб-сервере большинство горутин исполняют один и тот же код над небольшим объемом данных, находящихся в повторно используемой памяти. Таким образом, кэш инструкций будет всегда прогретым, а «теплота» кэша данных будет зависеть от суммарного объема памяти, к которому одновременно обращаются горутины. Также планировщик горутин в go старается минимизировать миграцию горутин между потоками операционной системы, чтобы кэши отдельных ядер процессоров оставались «теплыми».
3) а по какому событию переключаются горутины? само событие/мютекс/сокет не завязано в кернел?
Горутины переключаются во время блокирующих операций. Например, запись/чтение по сети, ожидание заблокированного мьютекса, ожидание чтения/записи сообщений для блокирующей очереди (в go она называется channel).

Мьютексы с channel’ами в go реализованы в пользовательском пространстве, так что у них нет оверхеда на переключение в пространство ядра.

Размер стэка нельзя изменять после старта потока.

google://"split stack"

— перейти в режим ядра (занимает минимум пару сотен тактов CPU)

Если на шлюзах задач x86 — да. На sysenter/sysexit прямой и обратный переход, грубо говоря, один такт. Для других ISA переход тоже дешевле (уровень пары тактов — заменить PSW и SP).
Дополнительно сохраняется/восстанавливается несколько регистров, чтобы освободить оперативный простор, но это нормальные процессоры делают впараллель остальной работе, за счёт out-of-order и переименования регистров.

переключить контекст потока — сохранить в памяти полный набор регистров CPU текущего потока, после чего загрузить полный набор регистров CPU нового потока.

Переключение на «лёгких нитях» требует ровно этого же.

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

Переключаться на нить в другом процессе — это пять. Косяков.

В современных нормальных системах при переключении нитей меняется содержимое регистра TLS (fs на Linux/x86), дёргать страничный механизм не надо вообще.

В контекст горутины входит ограниченный набор регистров CPU.

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

Итого — ни один из описанных аргументов за тонкие нити не верен. Вы просто уникум, коллега. Из анекдота.

P.S. На самом деле аргументы за «лёгкие нити» есть. Но они другие :) Имеет ли смысл их тут расписывать?

Имеет ли смысл их тут расписывать?

ДА!

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

google://"split stack"

-fsplit-stack был специально добавлен в gcc для компиляции программ на go с помощью gccgo. Насколько я знаю, эта опция больше нигде не используется. Документация и реализация gcc.gnu.org/wiki/SplitStacks была создана Ian Lance Taylor’ом — одним из ключевых разработчиков go.

Если на шлюзах задач x86 — да. На sysenter/sysexit прямой и обратный переход, грубо говоря, один такт. Для других ISA переход тоже дешевле (уровень пары тактов — заменить PSW и SP).
Дополнительно сохраняется/восстанавливается несколько регистров, чтобы освободить оперативный простор, но это нормальные процессоры делают впараллель остальной работе, за счёт out-of-order и переименования регистров.

Если бы переключение в режим ядра занимало пару тактов, никто бы не стал заморачиваться с vDSO:


Why does the vDSO exist at all? There are some system calls the
kernel provides that user-space code ends up using frequently, to the
point that such calls can dominate overall performance. This is due
both to the frequency of the call as well as the context-switch
overhead that results from exiting user space and entering the
kernel.
Если бы переключение в режим ядра занимало пару тактов, никто бы не стал заморачиваться с vDSO:

Я ж сказал — на шлюзах задач (до sysenter) это дорогая операция. А ещё есть другие платформы, где цена может быть заметно разной.
vDSO — в целом универсальный механизм. Но даже экономия на лёгком процессе перехода может быть полезной.
Ещё учтите, что vDSO чуть ли не в основном делался для операций взятия таймера для устранения отставания от Windows :)

переключить контекст потока — сохранить в памяти полный набор регистров CPU текущего потока, после чего загрузить полный набор регистров CPU нового потока.

Переключение на «лёгких нитях» требует ровно этого же.

Нет, т.к. рантайм go знает, какие регистры могут использоваться горутинами в заранее заданных местах переключения контекста. Туда входят SP, PC и еще пару платформо-зависимых регистров — см. структуру gobuf.

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

Я сравнивал с «лёгкими нитями», а не с горутинами. Но в последнем случае, если при переключении надо сохранять только «SP, PC и ещё пару платформо-зависимых регистров» — это значит, что все остальные данные уже уложены в память. Цену этой укладки Вы игнорируете — а она сравнима с ценой укладки при внешнем переключении. И хорошо ещё, если эта укладка (и потом возврат) делается только при обнаружении необходимости переключения (а не безусловно).

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

Да. И это нормально, если сама переключаемая программа использует регистровый пул на полную (при хороших компиляторах оно обычно так и есть). А вот тот NIH, который устроили в Go, лишь бы не зависеть от ненавистных GCC/LLVM/etc., заметно проседает по качеству выходного кода.

Но в последнем случае, если при переключении надо сохранять только «SP, PC и ещё пару платформо-зависимых регистров» — это значит, что все остальные данные уже уложены в память. Цену этой укладки Вы игнорируете — а она сравнима с ценой укладки при внешнем переключении.

Цена этой укладки — вызов обычной функции согласно go call convention. Вы же не сохраняете полный набор регистров при вызове функции согласно C call convention.

Вы же не сохраняете полный набор регистров при вызове функции согласно C call convention.

Согласно C calling convention есть
1) callee-saved регистры, которые должны сохраниться при переключении => их сохраняет переключатель;
2) входные/выходные регистры, содержимое которых для вызывающей теряется => если в них что-то было важное, она должна сохранить сама;
3) scratch-регистры, то же самое как (2).

В сумме (1)+(2)+(3) составляют все неслужебные регистры в любой из подобных конвенций.
Поэтому разница только в том, что внешний переключатель сохраняет их одним рывком, а вызов явной функции переключения размазывает это на два этапа.

Переключаться на нить в другом процессе — это пять. Косяков.

Дано: операционная система работает на одноядерном процессоре и выполняет два процесса в пользовательском пространстве.
Вопрос1: как операционная система переключает потоки между этими процессами?
Вопрос2: нужно ли сбрасывать кэш TLB при переключении между потоками разных процессов?

В современных нормальных системах при переключении нитей меняется содержимое регистра TLS (fs на Linux/x86), дёргать страничный механизм не надо вообще.

Этот бред даже комментировать не хочется :)

Дано: операционная система работает на одноядерном процессоре и выполняет два процесса в пользовательском пространстве.

Дано: контекстом сравнения была работа в одном процессе и последствия этого. А не Ваш уход в сторону, когда горутины вдруг начинаете сравнивать с переключениями в _разных_ процессах. Поэтому и такая моя реакция.

Этот бред даже комментировать не хочется :)

Бред у Вас. Повторяю: речь о нитях одного процесса — такое описание и сравнение корректно. Если же Вы вдруг переключились на сравнение со случаем разных процессов — сами с собой и разгребайте последствия такого виляния. Без меня.

Другая задача: работают два процесса. В одном — один поток, во втором либо один поток с тысячей горутин, либо тысяча потоков. В каком случае будет меньше переключений контекста между потоками разных процессов при прочих равных условиях на двухъядерном процессоре?

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

P.S. На самом деле аргументы за «лёгкие нити» есть. Но они другие :) Имеет ли смысл их тут расписывать?

Да, хотелось бы узнать настоящие аргументы за «легкие нити».

Спавнится количество потоков, равное количеству ядер; данные клиентских подключений заносятся в контейнер (может быть глобальным или TLS); потоки обрабатывают то, что приходит на сокеты через что-то вроде poll/select/epoll (надо смотреть, как люди делают), подтягивая данные из контейнера по дескриптору сокета в качестве ключа. Получаем Actors без спавна сотни тысяч потоков (которые в любом случае не могут одновременно работать в системе с 16 ядрами).
Вероятно, подобное можно навесить и на nginx.

В go достаточно запустить сотни тысяч потоков с простым и понятным линейным кодом внутри, который может выполнять обращения по сети. Не нужно никаких epoll’ов, TLS’ов, контейнеров, actors и state machines.

И это крутая фича Go.

Плохо, что нету метода на манер python’а, где на nix используется «/dev/urandom», а на win «RtlGenRandom()».

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

Спасибо! Невнимательно читал пакет..

А вообще вопрос, можно ли горутины поднять поверх CUDA ядер?

кхм...
это все равно что теплое и мягкое сравнивать

Почему теплое и мягое? горутины все рано бегают на ядрах ЦПУ, а тут вопрос заставить их бегать поверх ГПУ ядер, ясно что юание должно отличатся почти полностью скорее всего, вопрос чисто о возможностях

горутины все рано бегают на ядрах ЦПУ, а тут вопрос заставить их бегать поверх ГПУ

почитай внимательно чем отличаются ядра gpu от cpu
как там коммуникации происходят
и почему в CUDA и OpenCL используется голый C

В теории можно. Но в них нельзя будет исполнять произвольный код — только специально заточенный под CUDA.

Можно, но кернелы все одна на С придется написать с ограничениями CUDA или OpenCL.

потоки для генерация рандома?... какойто странный и непонянтый для меня мир.... при всем желании не могу ответить на вопрос — зачем?

Выбор источника рекламы для отдачи юзеру.

там паралелить надо не рандом, а всю логику связанную с розыгрышом, да и вообще там рандом далеко не самое узкое место

А кто сказал, что у них эта «вся логика» есть? :)

розыгрыш рекламы на одних рандомах — как-то несерьезно, conversion rate будет сильно низкий

В начале статьи написано, зачем. Жаль, что некоторые не умеют внимательно читать...

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

Количество ядер может быть полезно, если ты на каждой случайной величиной проводишь некий одинаковый набор операций и тут очень поможет много ядер СPU или GPU, но надо не забывать о скорости передачи данных в ГПУ и назад, чтобы в юзании оного был смысл.

если ты на каждой случайной величиной проводишь некий одинаковый набор операций и тут очень поможет много ядер

вот именно! сам рандом обычно не та операция которую надо паралелить, а вот то что следует за ним, с очень высокой вероятностью — надо, а так какаято высосаная из пальца проблема, по крайне мере она мне так видится

Вообще качественный рандом, пригодный даже для шифрования самому сделать сейчас 3 копейки.
По USB подключаешь шумящую хрень и считываешь с нее. Все накладные — это быстро с USB считать число.

Быстро с USB не бывает. Наверняка оно через кернел с переключением контекста.

Что значит быстро?

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

Не «даже для шифрования», а «только для шифрования». Из-за невозможности сохранить состояние и повторить.

Все накладные — это быстро с USB считать число.

«Быстро» и «ждать миллисекундной границы», в контексте темы, мало совместимы. Значит — придётся кэшировать.

а еще в упор не пониманию как может колво ядер влиять на рандом, ведь рандом должен быть чистой функцией
ГПСЧ никак не может быть чистой функцией, т.к. у него есть внутреннее состояние, изменяющееся при каждом вызове функции. ГПСЧ — это конечный автомат.

Автомат преобразовывается в функцию, Nvidia в cuRandom так и сделала

Забавно про нет бесполезных абстрацкий, и этого нет, поэтому мы изобретем велосипед.

Если велосипед получается простым, понятным и производительным, то зачем усложнять код тормозными и бесполезными абстракциями?

Потому что загромождается костылями.

Где костыли? Вижу только велосипед :) Наборот, костыли свойственны коду, построенному на абстракциях. Их городят, чтобы обойти искусственные (иногда бессмысленные) ограничения абстракций.

Опять ты невовремя опубликовал, все оппоненты заняты вторым яндекс-срачем))

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

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

А что там обсуждать? Когда ты выбираешь генератор случайных чисел у тебя уже есть набор требований к нему.
Для сферического случая в вакууме оптимального генератора не существует.

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

У меня тоже, я больше прикладной. Но в шифровании они нужны на ограниченном железе.
Но есть еще требование по стохастичности. Для монтекарлы и подобного мне и обычного rand хватало выше крыши. Для awgn тоже.

ну у аффтора это зачем-то используется в

наших высоконагруженных сервисах.

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

Приведенный в статье ГПСЧ используется в библиотеке метрик и гистограмм, которые затем собираются в prometheus для мониторинга наших сервисов и построения различных графиков в grafana.
Эта библиотека используется во всех сервисах, написанных у нас на go — сервисы рекламы, сбор и обработка статы, realtime счетчики по бизнес-данным, сервисы кэширования и т.д.

Кстати, prometheus и grafana также написаны на go :) Еще один повод бросить мучаться со scala, java, c#, nodejs и перейти на go.

Описанный в статье ГПСЧ не годится для шифрования, т.к. генерируемые им значения легко предсказать. Об этом явно написано в описании fastrand — см. комментарий в начале приведенных исходников.
Для шифрования нужно использовать специальный пакет из стандартной поставки go — crypto/rand .

В начале статьи написано, что это используется для построения различных гистограмм в реальном времени. Например, по времени обработки запроса, коих у нас приходит до 300К в секунду на один сервер. Для обработки каждого запроса вызывается куча функций, в т.ч. и rpc, производительность которых тоже желательно мониторить в realtime. Отсюда получаются миллионы вызовов ГПСЧ, которые вылазят в топ профиля по использованию CPU. Так что приходится заморачиваться вместо использования стандартного ГПСЧ.

В начале статьи написано

да, там есть раздел, в котором только общие фразы, без конкретики
типа вот можно юзать для того и того
а вот это уже конкретика, которую стоило добавить в этот раздел

Приведенный в статье ГПСЧ используется в библиотеке метрик и гистограмм, которые затем собираются в prometheus для мониторинга наших сервисов и построения различных графиков в grafana.
Эта библиотека используется во всех сервисах, написанных у нас на go — сервисы рекламы, сбор и обработка статы, realtime счетчики по бизнес-данным, сервисы кэширования и т.д.

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

Та що ж ти так математику не любиш :)

Подписаться на комментарии