Index: libcfa/src/bits/random.hfa =================================================================== --- libcfa/src/bits/random.hfa (revision 1553a5552a430f9af78a97c35d5fc3629d0910c2) +++ libcfa/src/bits/random.hfa (revision 29702ad1e351b5bb998c5b18e96a209401abf2b4) @@ -10,6 +10,6 @@ // Created On : Fri Jan 14 07:18:11 2022 // Last Modified By : Peter A. Buhr -// Last Modified On : Fri Jan 14 07:18:58 2022 -// Update Count : 1 +// Last Modified On : Mon Nov 21 17:50:12 2022 +// Update Count : 15 // @@ -17,4 +17,24 @@ #include + +// Set default PRNG for architecture size. +#ifdef __x86_64__ // 64-bit architecture +#define LEHMER64 +#else // 32-bit architecture +#define XORSHIFT_6_21_7 +#endif // __x86_64__ + +// C/CFA PRNG name and random-state. +#ifdef LEHMER64 +#define PRNG_NAME lehmer64 +#define PRNG_ARG_T __uint128_t +#endif // LEHMER64 + +#ifdef XORSHIFT_6_21_7 +#define PRNG_NAME xorshift_6_21_7 +#define PRNG_ARG_T uint32_t +#endif // XORSHIFT_6_21_7 + +#ifdef __cforall // don't include in C code (invoke.h) // Pipelined to allow out-of-order overlap with reduced dependencies. Critically, the current random state is returned @@ -61,6 +81,6 @@ //-------------------------------------------------- typedef struct { - uint32_t a, b, c, d; - uint32_t counter; + uint32_t a, b, c, d; + uint32_t counter; } xorwow__state_t; @@ -116,2 +136,4 @@ #undef C #undef D + +#endif // __cforall Index: libcfa/src/concurrency/invoke.h =================================================================== --- libcfa/src/concurrency/invoke.h (revision 1553a5552a430f9af78a97c35d5fc3629d0910c2) +++ libcfa/src/concurrency/invoke.h (revision 29702ad1e351b5bb998c5b18e96a209401abf2b4) @@ -10,6 +10,6 @@ // Created On : Tue Jan 17 12:27:26 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Sun Jan 9 19:06:45 2022 -// Update Count : 48 +// Last Modified On : Mon Nov 21 17:40:24 2022 +// Update Count : 55 // @@ -17,4 +17,5 @@ #include "bits/defs.hfa" #include "bits/locks.hfa" +#include "bits/random.hfa" #include "kernel/fwd.hfa" @@ -222,5 +223,5 @@ struct processor * last_proc; - uint32_t random_state; // fast random numbers + PRNG_ARG_T random_state; // fast random numbers #if defined( __CFA_WITH_VERIFY__ ) Index: libcfa/src/concurrency/kernel/fwd.hfa =================================================================== --- libcfa/src/concurrency/kernel/fwd.hfa (revision 1553a5552a430f9af78a97c35d5fc3629d0910c2) +++ libcfa/src/concurrency/kernel/fwd.hfa (revision 29702ad1e351b5bb998c5b18e96a209401abf2b4) @@ -120,5 +120,5 @@ // Yield: yield N times - static inline void yield( unsigned times ) { + static inline void yield( size_t times ) { for( times ) { yield(); Index: libcfa/src/concurrency/kernel/startup.cfa =================================================================== --- libcfa/src/concurrency/kernel/startup.cfa (revision 1553a5552a430f9af78a97c35d5fc3629d0910c2) +++ libcfa/src/concurrency/kernel/startup.cfa (revision 29702ad1e351b5bb998c5b18e96a209401abf2b4) @@ -39,4 +39,5 @@ #include "limits.hfa" #include "math.hfa" +#include "bits/random.hfa" // prng #define CFA_PROCESSOR_USE_MMAP 0 @@ -107,5 +108,6 @@ extern void __wake_proc(processor *); extern int cfa_main_returned; // from interpose.cfa -uint32_t __global_random_prime = 4_294_967_291u, __global_random_mask = false; +PRNG_ARG_T __global_random_prime = 4_294_967_291u; +bool __global_random_mask = false; //----------------------------------------------------------------------------- Index: libcfa/src/concurrency/thread.cfa =================================================================== --- libcfa/src/concurrency/thread.cfa (revision 1553a5552a430f9af78a97c35d5fc3629d0910c2) +++ libcfa/src/concurrency/thread.cfa (revision 29702ad1e351b5bb998c5b18e96a209401abf2b4) @@ -10,6 +10,6 @@ // Created On : Tue Jan 17 12:27:26 2017 // Last Modified By : Peter A. Buhr -// Last Modified On : Sat Feb 12 15:24:18 2022 -// Update Count : 66 +// Last Modified On : Sun Nov 20 17:17:50 2022 +// Update Count : 80 // @@ -26,5 +26,6 @@ #include "invoke.h" -extern uint32_t __global_random_seed, __global_random_prime, __global_random_mask; +extern PRNG_ARG_T __global_random_seed, __global_random_prime; +extern bool __global_random_mask; #pragma GCC visibility push(default) @@ -225,17 +226,16 @@ //----------------------------------------------------------------------------- -#define GENERATOR LCG - -void set_seed( uint32_t seed ) { - uint32_t & state = active_thread()->random_state; + +void set_seed( uint64_t seed ) { + PRNG_ARG_T & state = active_thread()->random_state; state = __global_random_seed = seed; - GENERATOR( state ); + (void)PRNG_NAME( state ); // prime PRNG __global_random_prime = state; __global_random_mask = true; } // set_seed -uint32_t prng( void ) { // [0,UINT_MAX] - uint32_t & state = active_thread()->random_state; - return GENERATOR( state ); +uint64_t prng( void ) { // [0,UINT_MAX] + PRNG_ARG_T & state = active_thread()->random_state; + return PRNG_NAME( state ); } // prng Index: libcfa/src/concurrency/thread.hfa =================================================================== --- libcfa/src/concurrency/thread.hfa (revision 1553a5552a430f9af78a97c35d5fc3629d0910c2) +++ libcfa/src/concurrency/thread.hfa (revision 29702ad1e351b5bb998c5b18e96a209401abf2b4) @@ -10,6 +10,6 @@ // Created On : Tue Jan 17 12:27:26 2017 // Last Modified By : Peter A. Buhr -// Last Modified On : Fri Feb 11 16:34:07 2022 -// Update Count : 20 +// Last Modified On : Sat Nov 19 16:41:27 2022 +// Update Count : 30 // @@ -23,4 +23,5 @@ #include "monitor.hfa" #include "exception.hfa" +#include "bits/random.hfa" //----------------------------------------------------------------------------- @@ -142,11 +143,11 @@ // prng static inline { - uint32_t prng( thread$ & th ) __attribute__(( warn_unused_result )) { return LCG( th.random_state ); } // [0,UINT_MAX] - uint32_t prng( thread$ & th, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( th ) % u; } // [0,u) - uint32_t prng( thread$ & th, uint32_t l, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( th, u - l + 1 ) + l; } // [l,u] + uint64_t prng( thread$ & th ) __attribute__(( warn_unused_result )) { return PRNG_NAME( th.random_state ); } // [0,UINT_MAX] + uint64_t prng( thread$ & th, uint64_t u ) __attribute__(( warn_unused_result )) { return prng( th ) % u; } // [0,u) + uint64_t prng( thread$ & th, uint64_t l, uint64_t u ) __attribute__(( warn_unused_result )) { return prng( th, u - l + 1 ) + l; } // [l,u] forall( T & | is_thread(T) ) { - uint32_t prng( T & th ) __attribute__(( warn_unused_result )) { return prng( (thread &)th ); } // [0,UINT_MAX] - uint32_t prng( T & th, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( th ) % u; } // [0,u) - uint32_t prng( T & th, uint32_t l, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( th, u - l + 1 ) + l; } // [l,u] + uint64_t prng( T & th ) __attribute__(( warn_unused_result )) { return prng( (thread &)th ); } // [0,UINT_MAX] + uint64_t prng( T & th, uint64_t u ) __attribute__(( warn_unused_result )) { return prng( th ) % u; } // [0,u) + uint64_t prng( T & th, uint64_t l, uint64_t u ) __attribute__(( warn_unused_result )) { return prng( th, u - l + 1 ) + l; } // [l,u] } // distribution } // distribution Index: libcfa/src/startup.cfa =================================================================== --- libcfa/src/startup.cfa (revision 1553a5552a430f9af78a97c35d5fc3629d0910c2) +++ libcfa/src/startup.cfa (revision 29702ad1e351b5bb998c5b18e96a209401abf2b4) @@ -10,6 +10,6 @@ // Created On : Tue Jul 24 16:21:57 2018 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Oct 6 13:51:57 2022 -// Update Count : 57 +// Last Modified On : Sun Nov 20 21:26:40 2022 +// Update Count : 59 // @@ -18,8 +18,9 @@ #include // getenv #include "bits/defs.hfa" // rdtscl +#include "bits/random.hfa" // rdtscl #include "startup.hfa" -extern uint32_t __global_random_seed; // sequential/concurrent -extern uint32_t __global_random_state; // sequential +extern PRNG_ARG_T __global_random_seed; // sequential/concurrent +extern PRNG_ARG_T __global_random_state; // sequential extern "C" { Index: libcfa/src/stdlib.cfa =================================================================== --- libcfa/src/stdlib.cfa (revision 1553a5552a430f9af78a97c35d5fc3629d0910c2) +++ libcfa/src/stdlib.cfa (revision 29702ad1e351b5bb998c5b18e96a209401abf2b4) @@ -10,6 +10,6 @@ // Created On : Thu Jan 28 17:10:29 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Aug 25 22:41:14 2022 -// Update Count : 604 +// Last Modified On : Sat Nov 19 16:42:26 2022 +// Update Count : 612 // @@ -225,15 +225,11 @@ //--------------------------------------- -#define GENERATOR LCG - // would be cool to make hidden but it's needed for libcfathread -__attribute__((visibility("default"))) uint32_t __global_random_seed; // sequential/concurrent -__attribute__((visibility("hidden"))) uint32_t __global_random_state; // sequential only - -void set_seed( PRNG & prng, uint32_t seed_ ) with( prng ) { state = seed = seed_; GENERATOR( state ); } // set seed - -void set_seed( uint32_t seed ) { __global_random_state = __global_random_seed = seed; GENERATOR( __global_random_state ); } -uint32_t get_seed() { return __global_random_seed; } -uint32_t prng( void ) { return GENERATOR( __global_random_state ); } // [0,UINT_MAX] +__attribute__((visibility("default"))) PRNG_ARG_T __global_random_seed; // sequential/concurrent +__attribute__((visibility("hidden"))) PRNG_ARG_T __global_random_state; // sequential only + +void set_seed( uint64_t seed ) { __global_random_state = __global_random_seed = seed; PRNG_NAME( __global_random_state ); } +uint64_t get_seed() { return __global_random_seed; } +uint64_t prng( void ) { return PRNG_NAME( __global_random_state ); } // [0,UINT_MAX] //--------------------------------------- Index: libcfa/src/stdlib.hfa =================================================================== --- libcfa/src/stdlib.hfa (revision 1553a5552a430f9af78a97c35d5fc3629d0910c2) +++ libcfa/src/stdlib.hfa (revision 29702ad1e351b5bb998c5b18e96a209401abf2b4) @@ -10,6 +10,6 @@ // Created On : Thu Jan 28 17:12:35 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Aug 25 18:07:06 2022 -// Update Count : 645 +// Last Modified On : Sun Nov 20 17:12:37 2022 +// Update Count : 730 // @@ -404,19 +404,47 @@ // calls( sprng ); -struct PRNG { +trait basic_prng( PRNG &, S, R ) { + void set_seed( PRNG & prng, S seed ); // set seed + S get_seed( PRNG & prng ); // get seed + R prng( PRNG & prng ); + void ?{}( PRNG & prng ); // random seed + void ?{}( PRNG & prng, S seed ); // fixed seed +}; // basic_prng + +static inline forall( PRNG &, S, R | basic_prng( PRNG, S, R ) | { R ?%?( R, R ); } ) { + R prng( PRNG & prng, R u ) { return prng( prng ) % u; } // [0,u) +} +static inline forall( PRNG &, S, R | basic_prng( PRNG, S, R ) | { R ?+?( R, R ); R ?-?( R, R ); R ?%?( R, R ); void ?{}( R &, one_t ); } ) { + R prng( PRNG & prng, R l, R u ) { return prng( prng, u - l + (R){1} ) + l; } // [l,u] +} + +struct PRNG32 { uint32_t callcnt; // call count uint32_t seed; // current seed - uint32_t state; // random state + PRNG_ARG_T state; // random state }; // PRNG -void set_seed( PRNG & prng, uint32_t seed_ ); -static inline { - void ?{}( PRNG & prng ) with( prng ) { callcnt = 0; set_seed( prng, rdtscl() ); } // random seed - void ?{}( PRNG & prng, uint32_t seed ) with( prng ) { callcnt = 0; set_seed( prng, seed ); } // fixed seed - uint32_t get_seed( PRNG & prng ) __attribute__(( warn_unused_result )) with( prng ) { return seed; } // get seed - uint32_t prng( PRNG & prng ) __attribute__(( warn_unused_result )) with( prng ) { callcnt += 1; return LCG( state ); } // [0,UINT_MAX] - uint32_t prng( PRNG & prng, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( prng ) % u; } // [0,u) - uint32_t prng( PRNG & prng, uint32_t l, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( prng, u - l + 1 ) + l; } // [l,u] - uint32_t calls( PRNG & prng ) __attribute__(( warn_unused_result )) with( prng ) { return callcnt; } +static inline { + void set_seed( PRNG32 & prng, uint32_t seed_ ) with( prng ) { state = seed = seed_; PRNG_NAME( state ); } // set seed + uint32_t get_seed( PRNG32 & prng ) __attribute__(( warn_unused_result )) with( prng ) { return seed; } // get seed + uint32_t prng( PRNG32 & prng ) __attribute__(( warn_unused_result )) with( prng ) { callcnt += 1; return PRNG_NAME( state ); } // [0,UINT_MAX] + uint32_t calls( PRNG32 & prng ) __attribute__(( warn_unused_result )) with( prng ) { return callcnt; } + void ?{}( PRNG32 & prng ) with( prng ) { callcnt = 0; set_seed( prng, rdtscl() ); } // random seed + void ?{}( PRNG32 & prng, uint32_t seed ) with( prng ) { callcnt = 0; set_seed( prng, seed ); } // fixed seed +} // distribution + +struct PRNG64 { + uint64_t callcnt; // call count + uint64_t seed; // current seed + PRNG_ARG_T state; // random state +}; // PRNG + +static inline { + void set_seed( PRNG64 & prng, uint64_t seed_ ) with( prng ) { state = seed = seed_; PRNG_NAME( state ); } // set seed + uint64_t get_seed( PRNG64 & prng ) __attribute__(( warn_unused_result )) with( prng ) { return seed; } // get seed + uint64_t prng( PRNG64 & prng ) __attribute__(( warn_unused_result )) with( prng ) { callcnt += 1; return PRNG_NAME( state ); } // [0,UINT_MAX] + uint64_t calls( PRNG64 & prng ) __attribute__(( warn_unused_result )) with( prng ) { return callcnt; } + void ?{}( PRNG64 & prng ) with( prng ) { callcnt = 0; set_seed( prng, rdtscl() ); } // random seed + void ?{}( PRNG64 & prng, uint64_t seed ) with( prng ) { callcnt = 0; set_seed( prng, seed ); } // fixed seed } // distribution @@ -435,10 +463,11 @@ // prng( 5, 21 ); -void set_seed( uint32_t seed_ ) OPTIONAL_THREAD; -uint32_t get_seed() __attribute__(( warn_unused_result )); -uint32_t prng( void ) __attribute__(( warn_unused_result )) OPTIONAL_THREAD; // [0,UINT_MAX] -static inline { - uint32_t prng( uint32_t u ) __attribute__(( warn_unused_result )) { return prng() % u; } // [0,u) - uint32_t prng( uint32_t l, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( u - l + 1 ) + l; } // [l,u] +// Harmonize with concurrency/thread.hfa. +void set_seed( uint64_t seed_ ) OPTIONAL_THREAD; +uint64_t get_seed() __attribute__(( warn_unused_result )); +uint64_t prng( void ) __attribute__(( warn_unused_result )) OPTIONAL_THREAD; // [0,UINT_MAX] +static inline { + uint64_t prng( uint64_t u ) __attribute__(( warn_unused_result )) { return prng() % u; } // [0,u) + uint64_t prng( uint64_t l, uint64_t u ) __attribute__(( warn_unused_result )) { return prng( u - l + 1 ) + l; } // [l,u] } // distribution