Simple atomic pseudo-random number generation

Question

I like to use a single global PRNG in my c programs (similar to Javascript's Math.random) because it simplifies things and the unpredictable nature of a global is quite fitting for a PRNG. I recently started using multithreading more so I adapted my global PRNG by making it atomic.

Besides the obvious, it is meant to be atomic in such a way that two threads requesting a pseudo-random number simultaneously won't get the same number in the sequence of pseudo-random numbers. Using a CAS-loop seems to be the only way of accomplishing this, if there is a better way do let me know.

Primarily I'm looking for confirmation that it actually is atomic. Note that struct randomic isn't the same as randomic, the latter is a typedef of _Atomic struct randomic. Admittedly not the best naming ever.

The real magic happens in randomicNext but the whole thing is pretty small so I've included all of it. It can also be found on 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

Answer 1

Primarily I'm looking for confirmation that it actually is atomic.

Yes, it appears atomic.

---

Other issues

Range and precision

randomicDouble() needs more functional explanation about range and precision. It seems to attempt an about linear distribution between [a...b] (b included).

A range of [a...b) (b excluded) is quite common. So detailing the coding goal is important.

The code fails to provide a full precision random number. Simple example: randomicDouble(1.0, 2.0) typically has about 2⁵³ different values in the [1.0...2.0) range and this code only supplies 2³² different values.

With randomicDouble(), perhaps sometimes 2 calls to randomicNext() are needed.

To provide a linear distribution with randomicDouble(1.0, 4.0) is trickier given the change in absolute precision between [1.0...2.0) and [2.0...4.0). randomicDouble(0.0, 1.0) is even tricker.

Initialization

Code passes in only a 32-bit initialization whereas the state is 128-bit. I'd expect at least a 64-bit initialization if not a full 128-bit one.

---

Mnior

20 is a magic number in for (int i = 0; i < 20; i++) and deserves explanation.

Answer 2

Looks simple enough. You've got some nice little idioms for dealing with C's version of "header-only libraries" here. I'm mostly a C++ programmer, so I'm not 100% sure — C still doesn't have a way to say "this function is defined inline in a header"? it's still got the two-level inline/extern inline system going on, which is why you have to use static if you want the header-only version of this library?

---

The macro RADEF leaks out of this header file, which is unfortunate because it has a very short and possibly contended name. If the user has their own RADEF macro, your header will break for no obvious reason. recommend renaming it to RANDOMIC_STORAGE_CLASS, and #undefing it at the end of the header file.

---

Consider using #pragma once. I tell everyone this. ;) Your ifndef-guard looks correct as written (as long as you trust the user not to have their own definition of RANDOMIC_H somewhere).

---

Please, please, please, do not make randomic and struct randomic mean different types! Not only is this gratuitously confusing to the reader, it is also a huge pitfall for the writer, because if the writer accidentally leaves off the noise word struct in a single place, they get a bug. And finally, it means that this code won't port cleanly to C++, because in C++, struct X and X must be the same type, by definition.

And yes, this code is almost entirely C++, albeit non-idiomatic. You'd just have to wrap your uses of _Atomic in a macro:

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

Anyway, if you don't want people touching your struct randomic type at all, a common convention is to name it struct randomic_s (by analogy with typedef ... randomic_t). And if you do foresee people wanting to use both types, the best names are probably randomic_t and atomic_randomic_t, or just struct randomic and struct atomic_randomic.

(That's right — I would avoid baking C's _Atomic into your exported typedef! I would create a new struct atomic_randomic { _Atomic struct randomic r_; } for export. This allows you to change the implementation details of struct atomic_randomic, such as whether it uses C or C++ or non-standard atomics, or whether it uses a mutex, without bothering the user too much.)

---

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;
}

This code is needlessly compact and hard-to-read. I would write it out like this:

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;
}

I would also consider renaming randomicInternal to randomicStep, since that's what it's doing. Sure it is "internal", but what it actually does is "single-step the PRNG function", and that's more important to understanding the code.

---

With this function expanded out, it's easier (but still not super easy) to see that the atomic_compare_exchange_weak here is trying to do an atomic CMPXCHG on objects of type struct randomic, i.e., 16-byte quantities. Check the assembly code (e.g. by compiling with -S); is your compiler actually generating a CMPXCHG16 instruction, or is it (more likely IMO) generating a call to a library routine which will use a mutex internally?

To get CMPXCHG16 codegen with Clang and GCC right now, I think you need to be either compiling with some -march= flag that I don't know, or explicitly enabling -mcx16.