Seed and randomness

[artificiel]

Taking the cce8428 occasion of fixing ofRandomShuffle() to revisit seeding and random generators in OF. The concept of randomness and the relationship with seeding is not immediately evident, as one can be under the impression that computers can pick "random numbers" out of thin air while actually, everything is deterministic — it just seems unpredictable to us. Of course with time-based processes, async events, recursivity and real world sensor input, it quickly becomes very hard to predict, but it's still a direct consequence of iterating a math function over itself from a given "seed" starting point.

CLARIFYING THE SEEDING INTERFACE

As of now OF has a function call ofSeedRandom() which does two very different things: (1) called with no arguments, it seeds the random generator with the current time which is generally considered equivalent to a "random" number (so placing the system in an unpredictable state as it does as part as the OF scaffolding in of::priv::initutils()); and (2) called with an argument, it seeds the random generator with the argument value, placing the system in a reproducible state.

The first form is what most people colloquially expect when requesting "random" stuff, and is mostly handled internally by default. This second form is useful to organise a deterministic result in the style of reproducible generative "versions" of artworks à la brün.

Proposal: deprecate ofSeedRandom() (which is not a great name anyway) and introduce:

void ofSetRandomSeed(unsigned int seed)

This removes the no-argument version of ofSeedRandom() as there is no reason to reinitialize the seed to an otherwise unknown value (the behaviour will not differ from simply advancing the random engine). at App init, ofSetRandomSeed() will be called with a proper pseudorandom number, placing the App in unpredictable state by default, which the user can override with a desired seed in setup() (or elsewhere).

CENTRAL ENGINE IMPLEMENTATION AND THREAD SAFETY

Currently in OF the old-school random generators rely on srand(), which is slowly crumbling. In order to benefit from the modern C++ numerical generators OF needs a better random engine. The correct way is to put a std::random_engine into a generator such as std::mt19937, and use that to build distributions as needed (so all the distributions are fed from the same seed, enabling deterministic/reproducible results).

However that is inherently thread-risky as the mt19937 is not thread safe, and while OF/GL is mainly a single thread paradigm, things are evolving and more and more threading is expected, both in user code and library code. So a thread-safe implementation should be favoured, something better than a static pointer in the anonymous namespace.

The usual approach is to use the thread_local keyword, which essentially make statics an instance-per-thread. However this requires different seeds for the different threads (else run the risk of the threads generating the same sequences, probably not what is expected). This makes is hard to support the "deterministically-seeded" design, as you would need to deterministically seed N threads, where N might be unknown to you, and might even not be deterministic due to OS changes or decisions.

A solid barrier is thus required around a single-seed engine. For optimal performance I suggest applying a double-check-lock to a singleton pattern, and construct the singleton in initutils(); and at the same time I suggest adapting a DLCP singleton implementation as ofSingleton and insert it in the OF utils, based on: https://github.com/jimmy-park/singleton/blob/main/include/singleton_dclp.hpp so it can be reused across OF "global monolithic" components with absolute safety and state-of-the-art performance.

BTW the current OF random implementation is not thread-safe:

openFrameworks/libs/openFrameworks/math/ofMath.h

Line 30 in cce8428

/// \warning ofRandom wraps C++'s `rand()` which is not reentrant or thread safe.

GENERATOR INTERFACE

Currently most of the OF random comes from ofRandom, which calls rand() (which depends on srand()) and optionally applies a range. This implies a uniform distribution, which is what most people expect from a "random generator" (thinking about a roll of the dice, or a number on the roulette). However there are many distributions, and I am convinced OF (and the computing/generative arts in general) would gain by having a cleaner, more direct interface to various distributions (and raise questions as early as possible in one's creative journey along the lines of what is (pseudo)randomness and how does it affect my work?). C++11 introduced a lot of distributions, and it would be great to provide a streamlined interface. The cumbersome part is the seeding and engine handling, but since OF handles that centrally, calling a specific distribution can be a one-liner.

NB: I looked around for existing "<random> wrapper libraries", as well as ofxaddons, and nothing is proposing productive solutions in the context of a computing/generative artist's point of view. I also tried to find streamlined patterns to use directly the stdlib distributions in order to facilitate and encourage their use, but it's not practical to reach a on-liner interface and OF is exactly concerned about such efficiency in expressivity.

So I aim for expressivity in the writer’s point of view, as well as “growing” the potential of the form as needed. At the same time, minimizing “invention” and relying on the language and stdlib for as much as possible. In the context of OF, it means streamlining usage by reducing lines of code and localizing on the practical needs.

1. basics (backwards-compatible)

ofRandom(); // random float between -1 and 1 (unsure about this design but let's be backwards-compatible
ofRandom(20); // random float between 0 and 20
ofRandom(10,20); // random float between 10 and 20

these sample a std::uniform_real_distribution based on the discussed mt19937 singleton.

2. distributions

ofRandomUniform(10,20); // same as ofRandom above, no empty arg version
ofRandomNormal(0, 5); // sample of normal dist centered on 0 with stddev of 5
ofRandomPoisson(4); // sample of poisson dist with mean of 4

… etc as much as wanted from https://en.cppreference.com/w/cpp/numeric/random and by maintaining a 1:1 name & argument relationship the docs for the distributions are the C++ ones.

3. output type

ofRandom<int>(10,20); // uses a different C++ uniform_int_distribution for is_integer return types
ofRandomCauchy<double>(-2.0, 0.5); 
ofRandomGamma<glm::vec3> (1,2); // all axis of vector have same parameters

4. refined vector ranges

ofRandom<glm::vec3> ({-20,-10,-1}, {20, 10, 1}); // specific params for each axis
ofRandomNormal<glm::vec2> ({ofGetWidth()/2, ofGetHeight()/2}, {sqrt(ofGetWidth()), sqrt(ofGetHeight()});

In short, OF provides a central random device with auto or specific seed, and harnesses it to generate all the possible distributions, with templated output for the common types (floating, integer, glm::vec).

OTHER UTILITIES

So the starting point for this was to fix ofRandomShuffle() — in this case the implementation moves to std::shuffle, which relies on the mt19937 singleton engine seeded as above. If other OF functions rely on randomness, they should be adapted to feed from the same engine to ensure reproducible results in deterministic seeding scenarios. ofNoise() for example should follow the seed.

Note about immortality: the distributions, as well as things like std::shuffle are compiler implementation-dependent. This means that if you are concerned that your seeded artwork produces deterministic randomness "for ever, everywhere" you should investigate implementing your own distributions (or at least lifting the ones you use out of the compiler/platform libs). As cryptography pushes the parameters of randomness, it is to be expected that mt19937 will eventually be deprecated or "fixed", and ofSetRandomSeed(1984) will suddenly engender a different deterministic result. And of course already today it might also be different on macOS, windows, linux, or across CPUs/architectures, or across compilers vendors or versions.

NAMESPACE?

This might warrant a different discussion but what is the current view on namespaces? Is it a correct time to move these functions into an of:: namespace? or even of::random::/of::rand::? It should be determined if it's a single of:: or if there are submodules; #5641 seems to prefer a single root of:: to make things visually more streamlined (and it satisfies the collision criteria as everything within of:: can be easily controlled).

of::random(10,20);
of::randomUniform(10,20);
of::randomGamma<glm::vec3> (1,2); 

of::random::uniform(10,20);
of::random::gamma<glm::vec3> (1,2); 
of::random::cauchy(-2.0, 0.5); 

of::rand::uniform(10,20);
of::rand::gamma<glm::vec3> (1,2); 
of::rand::cauchy(-2.0, 0.5); 

I dont mind one or the other but now that the vector types are glm:: and the introduction of of::filesystem my take is that any OF component that is worked on should be refactored into of:: — namespaces should now be basic C++ literacy even for absolute beginners.

(of course ofRandom() & al will keep working)

[artificiel]

please check out http://varia.artificiel.org/of/randomexplorer/randomexplorer.html (chrome a bit better);

you can peruse the lib here: https://github.com/artificiel/openFrameworks/blob/ofRandom/libs/openFrameworks/utils/ofRandom.h

and the app here: https://github.com/artificiel/openFrameworks/tree/ofRandom/apps/devApps/random%20explorer/src

NOTES

• the above app is not meant as "example code" but is really a testing ground for the distributions. more "practical" code will be produced as a better "learning" example.

• the lib contains a fair amount of templated boilerplate to transparently support glm::vec2 and 3 (perhaps a template wizard can somehow collapse that, but some distributions are fussy with their parameter types and too much enable_if becomes hard to follow).

• I just noticed ofLaunchURL() is not supported in emscripten so the reference links don't work but they should lead to these kind of pages https://en.cppreference.com/w/cpp/numeric/random/uniform_real_distribution

• on Apple Silicon in release, std::uniform_distribution performance exceeds old rand(). on intel it's about equal. within chrome performance is about 20% of native (but it's still great to share/showcase stuff)

[ofTheo]

Wow, I absolutely love your web example.
That is possibly the nerdiest thing I have seen in ages.

I think as long as we keep the old/existing functions naming and functionality having namespace for more advanced use cases like:
of::random::gamma would be totally fine.

At some point we need to settle on a plan/transition for this so we are consistent. That might need to be a post 0.12 thing, but I like this approach. ( We are going to add of::math::pi etc too )

Would it be possible to get a bugfix PR for just the current ofRandomize issue as minimal as possible that could at least patch the nightlies?

Then a second PR with the above proposed changes? ( just to make it easier to see the changes ).

[artificiel]

yes, i'm not conceptually drawn to web/emscripten as an artistic dissemination platform, but for tests/examples/etc there is great value there.

i'd like to make sure of a few things:

1. in the proposal functions such as ofRandomGamma() are mapped to their of::random:: counterparts so both syntaxes can work in parallel. (at medium-term the ofStuff should be deprecated in favor of of::stuff, but in order to be consistent that requires something like ≥95% of the ofStuff calls to be ready and waiting in of:: under the hood, so most apps can be written with a consistent approach). the templates are sensibly defaulted so ofRandomGamma() will give you a float; ofRandomGamma<glm::vec3>() will give you a vector.

2. to properly fix the shuffle stuff first step is a centralized modern engine to replace srand(). that's the std::mt19937 Engine defined in first part of ofRandom so there needs to be a form of concensus on this approach. it needs to be in core for other things to rely on it. (note that i'm specifically interested in deterministically-seeded works, so the design supports both non-deterministic and deterministic random —it is satisfying to see, for a given seed, the same random sequence generated on a native M1 app and running in chrome on an i7).

   i will move the Engine into it's own file (ofRandomEngine.h vs ofRandomDistributions.h) that will make it easier to comprehend; ofRandomDistributions.h can wait, and the shuffle will be the only thing initially attached to the Engine. Eventually ofRandom impl should move to std::uniform_dist, and ofRandomDistribution introduced. (note that ofRandomDistributions solves a lot of criticism the "modern C++ random" receives, as it's difficult to use without a lot of scaffolding, which OF is in a good position to provide a core component. i give a bunch of references to other approaches that i've studied in order to find the sweet spot for OF usage).

   so: go for this central std::mt19937 Engine approach?

3. this entails a small modification in initutils() to construct the Engine, but more importantly this raises the question of the ofSingleton proposal. the opinions vary on the requiredness of the singleton approach but in this case i find myself drawn to it because beyond guaranteeing a single instance, explicitly constructed; it includes thread-safety, in a very succint implementation. it's CRTP so any class can be wrapped into a singleton shell, and provide a unique ressource in a thread-safe manner from anywhere. BUT it means introducing the concept in OF core... the implementation can always evolve, it's really about the concept. (Note that i am open to alternative approaches to the Singleton in giving access to a central ressource, but it is important that it is done in a thread-safe manner (which is arguably a problem independent to the singleton, but i find the implementation/usage very easy and safe));

   so: go for ofSingleton? and if not, what?

4. the Singleton impl relies on C++17 (and doing it below C++17 entails a performance penalty on the DLCP locking stuff, which is what makes it thread-safe at near-no-cost), and (like for my std::optional problem) the armv6 gcc6 tests are failing on it... it works on armv6 with a modern gcc; it's really the github armv6 OF test that's stuck in 2018 with partial C++17 support. it's possible to ignore but a bit sad to see the failures.

[ofTheo]

@artificiel I'd love a solution for the short term that doesn't require the singleton but essentially mimics the prior ofRandomize functionality. ( ie: a hotfix that doesn't use OF's seed, and behaves 1:1 as random_shuffle did in terms of seeding ).

More of an emergency patch to just effectively restore what was working before.

I can also take a stab at that.

For 2 and 4 - I think yes and yes and would like to see as a PR which could be either merged pre or post 0.12.0
Either way I think a < C++17 fallback would be good if only to pass the tests, but also in cases where this might be the only thing that breaks for non C++17 compilers.

[artificiel]

well std::shuffle requires an engine, which requires seeding, and you do not want to seed an engine at each call, so you need to have one that's hanging around somewhere... and then you may (or may not) worry about it being thread safe. as far as an emergency patch (without taking deterministic seeding into account), the crux of the matter is to have somewhere static:

	std::random_device rd_{ }; // provides a source of randomness
	std::seed_seq seq_{ rd_(), rd_(), rd_(), rd_() }; // seq of 4 is considered pretty-good for non-cryptographic needs
	std::mt19937 g_{ seq_ }; // seed an engine with the seq

and from there have a way of globally accessing g_. each call to g_() provides a value and advances the generator.

it's basically what the Engine class in the ofRandom proposal does, with the support of ofSingleton to protect access. (as mentioned above I'll split the code in 2 files and the ofRandomEngine file will be about 15 lines). ofRandomized is fixed like this: https://github.com/artificiel/openFrameworks/blob/5afb1a100b7ae5978a4b7c670043ce6ac7afd703/libs/openFrameworks/utils/ofUtils.h#L230C8-L238

note that introducing the singleton in itself will not affect anything else (there is no user-facing interface for it to document/support); it's more a matter of philosophy.

and to be clear re armv6, the tests are not failing because the code is "special", but because the compiler has partial C++17 support (in any case we are tied to C++17 with std::filesystem, for which we happen to be lucky the ancient armv6 gcc6 supports correctly).

[ofTheo]

yeah totally get it. was trying a simpler implementation and found I needed most of the things above.
I think it would be nice too if ofSeedRandom(int val) did affect the the std::mt19937 generator to be predicable.

happy if you want to do the fix as you see fit in terms of using singleton etc, we will need to get the CI for arm working for C++17 anyway.

Thanks for all your thoughts on this!

[artificiel]

good idea to "parallelize" the seeding of srand() with the std::mt19937 — so initially it does not disrupt the user-facing functions. so I will clean up the Engine part, and apply the minimal changes to initutils() to get shuffle working within randomize. these changes will be implementation-only. I will however deprecate ofRandomize() towards ofShuffle() as randomize is the wrong name for the function.

once that's confirmed stable, the next step will be to introduce the distributions and replace all calls to rand()/srand(), and provide both ofRandomStuff and of::random::stuff user interfaces -- and we'll be able to remove https://github.com/artificiel/openFrameworks/blob/5afb1a100b7ae5978a4b7c670043ce6ac7afd703/libs/openFrameworks/math/ofMath.h#L11-L13

I'll be able to do that within the next few days.

[ofTheo]

Awesome - thanks @artificiel !
Please don't deprecate ofRandomize though. Let's wait on ofShuffle until we get a chance to review all the naming changes ( post 0.12.0 ).