PRNG
Source Files
└───liblfds711
├───inc
│ └───liblfds711
│ lfds711_prng.h
└───src
└───lfds711_prng
lfds711_prng_init.c
lfds711_prng_internal.h
Defines
#define LFDS711_PRNG_SEED
Opaque Structures
struct lfds711_prng_state; struct lfds711_prng_st_state;
Macros
#define LFDS711_PRNG_GENERATE( prng_state, random_value ) #define LFDS711_PRNG_ST_GENERATE( prng_st_state, random_value ) #define LFDS711_PRNG_MIXING_FUNCTION( random_value )
Prototypes
void lfds711_prng_init_valid_on_current_logical_core( struct lfds711_prng_state *ps, lfds711_pal_uint_t seed ); void lfds711_prng_st_init( struct lfds711_prng_st_state *psts, lfds711_pal_uint_t seed );
Overview
This API implements a PRNG (Psuedo Random Number Generator) in both a lock-free and single-threaded version.
The implementation performs no allocations. The user is responsible for all allocations (and deallocations), where these allocations are passed into the API functions, which then use them. As such, allocations can be on the stack, on the heap, or as can sometimes be the the case in embedded systems, allocated with fixed addresses at compile time from a fixed global store. Allocations can also be shared memory, but in this case, the virtual addresses used must be the same in all processes.
The lock-free version is an unusual beast as it has almost no use cases, for, as in all things, the single-threaded version, especially as the number of threads increases, massively out-performs the lock-free version. As such, and given how easy it usually is to provide for a per-thread PRNG state, it is almost always the case a single-threaded PRNG will be used. The only really conceivable use cases are in unusual situations, such as callbacks coming from unmodifable third party code, where per-thread state cannot easily be maintained, or where performance is not a concern. In these situations, the convenience of a single, global, lock-free PRNG which by being lock-free can be safely accessed by all threads might mean it is the right choice.
The lock-free version is lfds711_prng, the single-threaded version is lfds711_prng_st. The states are identical internally, but are not interchangable in the eyes of the compiler due to being different types, and are not interchangable in the eyes of the processor, because there is no code to perform the necessary magic to make a single-threaded state work properly on multiple cores (as such, different cores can at the same time see different values for the single-threaded PRNG).
General usage for the lock-free variant is that the user calls lfds711_prng_init_valid_on_current_logical_core to initialize a struct lfds711_prng_state, and then calls the macro LFDS711_PRNG_GENERATE to both step the PRNG and obtain a random value.
(See the section below, on lock-free specific behaviour, for an explanation of the unusual init function name.)
General usage for the single-threaded variant is that the user calls lfds711_prng_st_init to initialize a struct lfds711_prng_st_state, and then calls the macro LFDS711_PRNG_ST_GENERATE to both step the PRNG and obtain a random value.
In both cases, a seed value is required for the PRNG. Where liblfds targets a bare C compiler, the Standard Library is not available and so the usual stand-in, time(), is not available. For convenience, the define LFDS711_PRNG_SEED is provided. This contains a random value taken from an on-line real random number generator (based on atmospheric noise). This define is 32 bits long on 32 bit platforms and 64 bits long on 64 bit platforms.
In addition to the LFDS711_PRNG_GENERATE macro, a second macro, LFDS711_PRNG_MIXING_FUNCTION, is provided. This is a convenience function to help address a particular situation which can arise with PRNG use. It can be that a number of threads exist, each of which has its own single-threaded PRNG. These single-threaded PRNGs however all need seed values when they are initialized. It is not viable to pass them all the same seed, as each thread will then be using exactly the same sequence of random numbers. A seeming solution to this is to create a single PRNG, and use that to generate values which are used to seed the per-thread PRNGs. This however fails if the PRNG in use is the same in all cases, as each PRNG is a sequence of numbers, and calling generate on a PRNG provides the next number in the sequence; so creating one instance of a PRNG and then pulling off say the next hundred numbers for one hundred per-thread PRNGs simply means that each thread is simply one step further down the list of the same numbers - i.e. the threads are going to produce identical numbers, just offset by one per thread.
An actual solution to this is to create a single master PRNG to produce seed values (just as before) but now passing each number provided through a mixing function (basically a hash function) so that it becomes very different to its original value, i.e. jumps to some entirely new offset into the sequence of numbers produced by the PRNG. This is the purpose of LFDS711_PRNG_MIXING_FUNCTION.
The mixing function used should be completely different in character to that used in the per-thread PRNGs to prevent and overall correlations in the numbers generated. Unfortunately, currently, it is not so - it is the same mixing function. However, the PRNG in use has to stages, where the mixing stage is the second stage, and so it still functions correctly; it's just not as nice as it could be. Sorting this out is on the to-do list.
The state structures are both public, present in the lfds711_prng.h header file, so that users can embed them in their own structures (and where necessary pass them to sizeof). Expected use is that user structures which are to use PRNGs contain within themselves a struct lfds711_prng_state. This approach permits zero run-time allocation of store and also permits the caller full control over the location of allocations.
Lock-free Specific Behaviour
The state initialization function, lfds711_freelist_prng_valid_on_current_logical_core, as the same suggests, initializes the state structure but that initialization is only valid on the current logical core. For the initialization to be valid on other logical cores (i.e. other threads where they are running on other logical cores) those other threads need to call the long-windedly named macro LFDS711_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE, which will do that which its name suggests.
License
The PRNG algorithm is known as "SplitMix64" and the design comes from Sebastiano Vigna's PRNG Shootout] web-site, where it is licensed under v1.0 of the Creative Commons 0 (zero) license, which can be found here. This is a "full grant and public domain" license. The algorithm on the site is single-threaded. Dr. Vigna provided essential design insight and advice during the design of the lock-free version, and provided email consent to it being used in liblfds under the liblfds licensing terms ("there is no license, but if you really want one, pick which-ever you want").
Example
#include <stdio.h>
#include "liblfds711.h"
int main()
{
int unsigned
loop;
lfds711_pal_uint_t
random_value;
struct lfds711_prng_state
ps;
lfds711_prng_init_valid_on_current_logical_core( &ps, LFDS711_PRNG_SEED );
// TRD : ten psuedo-random numbers
for( loop = 0 ; loop < 10 ; loop++ )
{
LFDS711_PRNG_GENERATE( &ps, random_value );
printf( "random_value = %llu\n", (int long long unsigned) random_value );
}
return( EXIT_SUCCESS );
}