6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ There are random number generators where you can peel off a branch, in a manner of speaking, for use in parallel threads. This guarantees that these threads all produce independent randomness. It would be a lot more efficient than using atomic operations. For example this one: pcg-random.org \$\endgroup\$ – Cris Luengo Feb 21 '18 at 3:14
  • \$\begingroup\$ Randomic is a cool name though. \$\endgroup\$ – Cris Luengo Feb 21 '18 at 3:14
  • \$\begingroup\$ @CrisLuengo Non-independent randomnes is kind of the point. The inherent non-deterministic nature of shared resources (in this case in the form of an atomic PRNG context) goes well with the idea of randomness. Efficency may well be worse than pcg, but a simple atomic is certainly more convenient than having to set up seperate streams. \$\endgroup\$ – Wingblade Feb 21 '18 at 9:12
3
\$\begingroup\$

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 253 different values in the [1.0...2.0) range and this code only supplies 232 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.

\$\endgroup\$
  • \$\begingroup\$ +1 for "a PRNG with 128 bits of state needs a way to seed it with 128 bits of state." \$\endgroup\$ – Quuxplusone Feb 19 '18 at 18:33
  • \$\begingroup\$ The PRNG used is smallprng, so all your concerns in regards to it should be directed at the author of the algorithm. Based on their testing and my own experience it works really well, though. I have not been able to find an explanation for the magic 20 either, I simply use it because the reference implementation does. \$\endgroup\$ – Wingblade Feb 19 '18 at 18:38
  • \$\begingroup\$ Also, the ranges are inclusive as noted in the accompanying documentation, which was lost when shortening things for the purpose of the question. I've now put them back in. \$\endgroup\$ – Wingblade Feb 19 '18 at 18:41
  • \$\begingroup\$ @Wingblade 1) smallprng is not the issue critiqued here. Its use to generate double is an issue and has a number of short-comings. 2) Changing the code file after answers come in is not good CR etiquette. Recommend rolling it back. This may be useful. 3) "which return a random number in the given range (inclusive)" is not something certainly done by the code as explained in the answer. \$\endgroup\$ – chux Feb 19 '18 at 18:50
  • \$\begingroup\$ @Wingblade Code that fits the presentation width (no horizontal scroll bar) is a good thing - the added comments fail this. With auto formatting, this should be easy to adjust from the original code. \$\endgroup\$ – chux Feb 19 '18 at 18:54
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Good review. Note that #pragma once is not in the C spec. Various compilers define it though. \$\endgroup\$ – chux Feb 19 '18 at 18:43
  • \$\begingroup\$ @chux Yea, I avoid using it for this reason. Like to stay within the standard as much as possible. \$\endgroup\$ – Wingblade Feb 19 '18 at 18:45
  • \$\begingroup\$ A good compiler would warn if there was a conflict with RADEF, at least mine does. Maybe this is different for C++. I've renamed struct randomic to struct randomic_ctx now. Note that in C type names ending in _t are reserved, again probably different in C++. \$\endgroup\$ – Wingblade Feb 20 '18 at 14:23
  • \$\begingroup\$ @Wingblade: The compiler will certainly give an error if the user has already got #define RADEF (radians(0xEF)) or whatever somewhere in another header file. This will be a noisy error, not quiet undefined behavior. But it will still be a build-breaking issue for your user! That's why I advise using a relatively long, "namespaced" name for this (or any) macro. \$\endgroup\$ – Quuxplusone Feb 20 '18 at 18:32
  • \$\begingroup\$ I'm aware that POSIX technically reserves all identifiers ending in _t, but this has never stopped anyone in the history of computer programming from using that convention anyway. ;) If you like the idea of tagging types with a suffix, but have conscientious objections to _t, I might suggest _ty (but not _T — that would be blasphemous!). :) randomic_ctx is better than randomic anyway, because ctx suggests context which is a noun. \$\endgroup\$ – Quuxplusone Feb 20 '18 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.