Index: doc/user/user.tex =================================================================== --- doc/user/user.tex (revision 1eec0b03255eb72d14cb9fc93b46b77f5007129f) +++ doc/user/user.tex (revision 5cefa433745f174ac307ad32f414eb2fef7476a2) @@ -11,6 +11,6 @@ %% Created On : Wed Apr 6 14:53:29 2016 %% Last Modified By : Peter A. Buhr -%% Last Modified On : Sat Feb 12 17:04:03 2022 -%% Update Count : 5376 +%% Last Modified On : Mon Feb 14 17:20:39 2022 +%% Update Count : 5382 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -8223,6 +8223,6 @@ Random numbers are values generated independently, i.e., new values do not depend on previous values (independent trials), \eg lottery numbers, shuffled cards, dice roll, coin flip. While a primary goal of programming is computing values that are \emph{not} random, random values are useful in simulation, cryptography, games, etc. -A random-number generator is an algorithm computing independent values. -If the algorithm uses deterministic computation (predictable sequence of values), it generates \emph{pseudo} random numbers versus \emph{true} random numbers. +A random-number generator is an algorithm that computes independent values. +If the algorithm uses deterministic computation (a predictable sequence of values), it generates \emph{pseudo} random numbers versus \emph{true} random numbers. All \newterm{pseudo random-number generators} (\newterm{PRNG}) involve some technique to scramble bits of a value, \eg multiplicative recurrence: @@ -8249,8 +8249,8 @@ Finally, a PRNG usually generates a range of large values, \eg ©[0, UINT_MAX]©, which are scaled using the modulus operator, \eg ©prng() % 5© produces random values in the range 0--4. -\CFA provides a sequential and concurrent PRNGs. +\CFA provides a sequential PRNG type only accessible by a single thread (not thread-safe) and a set of global and companion thread PRNG functions accessible by multiple threads without contention. \begin{itemize} \item -For sequential programs, like coroutining, the PRNG is used to randomize behaviour or values during execution, \eg in games, a character makes a random move or an object takes on a random value. +The ©PRNG© type is for sequential programs, like coroutining: \begin{cfa} struct PRNG { ... }; $\C[3.75in]{// opaque type}$ @@ -8264,6 +8264,7 @@ uint32_t calls( PRNG & prng ); $\C{// number of calls}\CRT$ \end{cfa} -Sequential execution is repeatable given the same starting seeds for all ©PRNG©s. -In this scenario, it is useful to have multiple ©PRNG©, \eg one per player or object so a type is provided to generate multiple instances. +A ©PRNG© object is used to randomize behaviour or values during execution, \eg in games, a character makes a random move or an object takes on a random value. +In this scenario, it is useful to have multiple ©PRNG© objects, \eg one per player or object. +However, sequential execution is still repeatable given the same starting seeds for all ©PRNG©s. \VRef[Figure]{f:SequentialPRNG} shows an example that creates two sequential ©PRNG©s, sets both to the same seed (1009), and illustrates the three forms for generating random values, where both ©PRNG©s generate the same sequence of values. @@ -8307,5 +8308,4 @@ \end{tabular} \end{cquote} -\vspace{-10pt} \caption{Sequential PRNG} \label{f:SequentialPRNG} @@ -8313,16 +8313,5 @@ \item -For concurrent programs, it is important the PRNG is thread-safe and not a point of contention. -A PRNG in concurrent programs is often used to randomize execution in short-running programs, \eg ©yield( prng() % 5 )©. - -Because concurrent execution is non-deterministic, seeding the concurrent PRNG is less important, as repeatable execution is impossible. -Hence, there is one system-wide PRNG (global seed) but each \CFA thread has its own non-contended PRNG state. -If the global seed is set, threads start with this seed, until it is reset and than threads start with the reset seed. -Hence, these threads generate the same sequence of random numbers from their specific starting seed. -If the global seed is \emph{not} set, threads start with a random seed, until the global seed is set. -Hence, these threads generate different sequences of random numbers. -If each thread needs its own seed, use a sequential ©PRNG© in each thread. - -There are two versions of the PRNG functions to manipulate the thread-local PRNG-state, which are differentiated by performance. +The PRNG global and companion thread functions are for concurrent programming, such as randomizing execution in short-running programs, \eg ©yield( prng() % 5 )©. \begin{cfa} void set_seed( uint32_t seed ); $\C[3.75in]{// set global seed}$ @@ -8337,6 +8326,15 @@ uint32_t prng( $thread\LstStringStyle{\textdollar}$ & th, uint32_t l, uint32_t u ); $\C{// [l,u]}\CRT$ \end{cfa} -The slower ©prng© functions call ©active_thread© internally to access the thread-local PRNG-state, while the faster ©prng© functions are passed a pointer to the active thread. -If the thread pointer is known, \eg in a thread ©main©, eliminating the call to ©active_thread© significantly reduces the cost for accessing the thread's PRNG state. +The only difference between the two sets of ©prng© routines is performance. + +Because concurrent execution is non-deterministic, seeding the concurrent PRNG is less important, as repeatable execution is impossible. +Hence, there is one system-wide PRNG (global seed) but each \CFA thread has its own non-contended PRNG state. +If the global seed is set, threads start with this seed, until it is reset and then threads start with the reset seed. +Hence, these threads generate the same sequence of random numbers from their specific starting seed. +If the global seed is \emph{not} set, threads start with a random seed, until the global seed is set. +Hence, these threads generate different sequences of random numbers. +If each thread needs its own seed, use a sequential ©PRNG© in each thread. +The slower ©prng© functions \emph{without} a thread argument call ©active_thread© internally to indirectly access the current thread's PRNG state, while the faster ©prng© functions \emph{with} a thread argument directly access the thread through the thread parameter. +If a thread pointer is available, \eg in thread main, eliminating the call to ©active_thread© significantly reduces the cost of accessing the thread's PRNG state. \VRef[Figure]{f:ConcurrentPRNG} shows an example using the slower/faster concurrent PRNG in the program main and a thread.