Простой атомной псевдо-генератор случайных чисел


Мне нравится использовать один глобальный ГПСЧ в моих программах (аналог в JavaScript Math.random), потому что он упрощает вещи и непредсказуемый характер глобальной подходит для ПГСЧ. Недавно я начал использовать многопоточность больше, так что я адаптировал свой глобальный ГПСЧ, сделав его атомной.

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

В первую очередь я ищу подтверждение того, что он на самом деле является атомарным. Обратите внимание, что struct randomic не совпадает randomicпоследний состоит из _Atomic struct randomic. Конечно не лучший нейминг никогда.

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

//include only once
#ifndef RANDOMIC_H
#define RANDOMIC_H

//process configuration
#ifdef RANDOMIC_STATIC
    #define RANDOMIC_IMPLEMENTATION
    #define RADEF static
#else //RANDOMIC_EXTERN
    #define RADEF extern
#endif

//includes
#include <stdatomic.h>
#include <stdint.h>

//types
typedef _Atomic struct randomic {
    uint32_t a, b, c, d;
} randomic;

//function declarations
RADEF void randomicSeed(randomic*, uint32_t);
RADEF float randomicFloat(randomic*, float, float);
RADEF double randomicDouble(randomic*, double, double);
RADEF uint32_t randomicNext(randomic*);

//implementation section
#ifdef RANDOMIC_IMPLEMENTATION

//function declarations
static struct randomic randomicInternal(struct randomic);

//public functions
RADEF void randomicSeed (randomic* rdic, uint32_t seed) {
    struct randomic ctx;
    ctx.a = 0xf1ea5eed;
    ctx.b = ctx.c = ctx.d = seed;
    for (int i = 0; i < 20; i++)
        ctx = randomicInternal(ctx);
    atomic_store(rdic, ctx);
}
RADEF float randomicFloat (randomic* rdic, float a, float b) {
    return a + (b-a)*((float)randomicNext(rdic)/(float)UINT32_MAX);
}
RADEF double randomicDouble (randomic* rdic, double a, double b) {
    return a + (b-a)*((double)randomicNext(rdic)/(double)UINT32_MAX);
}
RADEF uint32_t randomicNext (randomic* rdic) {
    struct randomic ctx = atomic_load(rdic), ntx;
    while (!atomic_compare_exchange_weak(rdic, &ctx, (ntx = randomicInternal(ctx))));
    return ntx.d;
}

//internal functions
static struct randomic randomicInternal (struct randomic ctx) {
    uint32_t e = ctx.a - ((ctx.b << 27)|(ctx.b >> 5));
    ctx.a = ctx.b ^ ((ctx.c << 17)|(ctx.c >> 15));
    ctx.b = ctx.c + ctx.d;
    ctx.c = ctx.d + e;
    ctx.d = e + ctx.a;
    return ctx;
}

#endif //RANDOMIC_IMPLEMENTATION
#endif //RANDOMIC_H


133
6
задан 19 февраля 2018 в 04:02 Источник Поделиться
Комментарии
2 ответа


В первую очередь я ищу подтверждение того, что он на самом деле является атомарным.

Да, похоже, атомной.


Другие вопросы

Диапазон и точность

randomicDouble() требуется больше функциональных объяснений по поводу дальности и точности. Похоже, попытка о линейном распределении между [a...b] (b включена).

Диапазон [a...b) (b основе) является довольно распространенным. Так, детализируя цель кодирование-это важно.

Код не обеспечивает полную точность случайных чисел. Простой пример: randomicDouble(1.0, 2.0) как правило, имеет около 253 различные значения в [1.0...2.0) диапазон и этот код только для питания 232 различных значения.

С randomicDouble()возможно, иногда 2 звонка randomicNext() нужны.

Чтобы обеспечить линейное распределение с randomicDouble(1.0, 4.0) сложнее, учитывая изменения в абсолютной точности между [1.0...2.0) и [2.0...4.0). randomicDouble(0.0, 1.0) даже выполнить.

Инициализация

Код проходит только 32-бит инициализации, в то время как государство составляет 128-бит. Я бы ожидать, по крайней мере, 64-бит инициализации, если не полный 128-битный.


Mnior

20 это магическое число в for (int i = 0; i < 20; i++) и заслуживает объяснения.

3
ответ дан 19 февраля 2018 в 06:02 Источник Поделиться

Выглядит достаточно просто. У вас есть несколько идиом для работы с версия с "только заголовков библиотеки" здесь. Я в основном на C++ программист, так что я не уверен на 100% — С до сих пор не имеют возможность сказать "эта функция определена inline в заголовке"? это еще два уровня inline/extern inline системы происходит, который является, почему вы должны использовать static Если вы хотите заголовке-только версия этой библиотеки?


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


Рассмотрим использование #pragma once. Я говорю все это. ;) Ваш ifndef-охранник выглядит правильно как написано (как долго, как Вы доверяете пользователей не иметь свое собственное определение RANDOMIC_H где-то).


Пожалуйста, пожалуйста, пожалуйста, не делайте randomic и struct randomic значит, разные типы! Это не только безвозмездно в заблуждение читателя, это еще и огромная ошибка для писателя, потому что если писатель случайно избегает шума слова struct в одном месте, они получают ошибку. И, наконец, это означает, что этот код не Порт чисто на C++, что в C++, struct X и X должны быть того же типа, по определению.

И да, этот код почти целиком на C++, хотя и не-идиоматические. Вы просто должны обернуть свои использования _Atomic в макросе:

#ifdef __cplusplus
#define RANDOMIC_ATOMIC(T) std::atomic<T>
#else
#define RANDOMIC_ATOMIC(T) _Atomic T
#endif

В любом случае, если вы не хотите, чтобы люди трогают ваши struct randomic вообще, общее правило-имя его struct randomic_s (по аналогии с typedef ... randomic_t). И если вы не предвижу людей, желающих использовать оба типа, Лучшие имена, вероятно, randomic_t и atomic_randomic_tили просто struct randomic и struct atomic_randomic.

(Это верно — я бы избегала выпечки с _Atomic в экспортированных оператор typedef! Я бы создал новый struct atomic_randomic { _Atomic struct randomic r_; } на экспорт. Это позволяет изменить детали реализации struct atomic_randomic, например, используется ли C или C++ или нестандартные Атомикс, или же он использует мьютекс, не беспокоя пользователя слишком много.)


RADEF uint32_t randomicNext (randomic* rdic) {
struct randomic ctx = atomic_load(rdic), ntx;
while (!atomic_compare_exchange_weak(rdic, &ctx, (ntx = randomicInternal(ctx))));
return ntx.d;
}

Этот код напрасно компактный и трудно читаемые. Я бы написал это так:

RANDOMIC_STORAGE_CLASS uint32_t randomicNext(randomic *rdic) {
struct randomic ctx = atomic_load(rdic);
struct randomic ntx;
do {
ntx = randomicInternal(ctx);
} while (!atomic_compare_exchange_weak(rdic, &ctx, ntx));
return ntx.d;
}

Я бы также рассмотреть вопрос о переименовании randomicInternal для randomicStepС того, что он делает. Уверен, что это является "внутренним", но что это на самом деле не является "один-шаг ППНГ функция", и что более важно для понимания код.


С помощью этой функции расширены, это легче (но все равно не очень легко), чтобы увидеть, что atomic_compare_exchange_weak вот пытаюсь сделать атомную CMPXCHG на объекты типа struct randomic, т. е. 16-байтовых величин. Проверить код сборки (например, путем составления с -S); ваш компилятор на самом деле генерирует CMPXCHG16 инструкция, или (что более вероятно ИМО) генерирующих вызов библиотечной функции, которая будет использовать мьютекс внутри?

Чтобы получить CMPXCHG16 что codegen с Clang и gcc сейчас, я думаю, вы должны быть либо компиляция с некоторыми -march= флаг, который я не знаю, или явно разрешить -mcx16.

3
ответ дан 19 февраля 2018 в 06:02 Источник Поделиться