Index: libcfa/src/bits/random.hfa =================================================================== --- libcfa/src/bits/random.hfa (revision 7d9598d809dda423890eb3996cfe6e61bc3b543b) +++ libcfa/src/bits/random.hfa (revision 2dcd80a064f6154cf7aad118ffd2a53fa127cab5) @@ -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 : Sun Dec 11 18:43:58 2022 +// Update Count : 171 // @@ -18,26 +18,204 @@ #include -// Pipelined to allow out-of-order overlap with reduced dependencies. Critically, the current random state is returned -// (copied), and then compute and store the next random value. - -#if defined(__SIZEOF_INT128__) -//-------------------------------------------------- +#define GLUE2( x, y ) x##y +#define GLUE( x, y ) GLUE2( x, y ) + +// Set default PRNG for architecture size. +#ifdef __x86_64__ // 64-bit architecture + // 64-bit generators + #define LEHMER64 + //#define XORSHIFT_12_25_27 + //#define XOSHIRO256PP + //#define KISS_64 + + // 32-bit generators + #define XORSHIFT_6_21_7 + //#define XOSHIRO128PP +#else // 32-bit architecture + // 64-bit generators + #define XORSHIFT_13_7_17 + + // 32-bit generators + #define XORSHIFT_6_21_7 +#endif // __x86_64__ + +// Define C/CFA PRNG name and random-state. + +// SKULLDUGGERY: typedefs name struct and typedef with the same name to deal with CFA typedef numbering problem. + +#ifdef XOSHIRO256PP +#define PRNG_NAME_64 xoshiro256pp +#define PRNG_STATE_64_T GLUE(PRNG_NAME_64,_t) +typedef struct PRNG_STATE_64_T { uint64_t s[4]; } PRNG_STATE_64_T; +#endif // XOSHIRO256PP + +#ifdef XOSHIRO128PP +#define PRNG_NAME_32 xoshiro128pp +#define PRNG_STATE_32_T GLUE(PRNG_NAME_32,_t) +typedef struct PRNG_STATE_32_T { uint32_t s[4]; } PRNG_STATE_32_T; +#endif // XOSHIRO128PP + +#ifdef LEHMER64 +#define PRNG_NAME_64 lehmer64 +#define PRNG_STATE_64_T __uint128_t +#endif // LEHMER64 + +#ifdef WYHASH64 +#define PRNG_NAME_64 wyhash64 +#define PRNG_STATE_64_T uint64_t +#endif // LEHMER64 + +#ifdef XORSHIFT_13_7_17 +#define PRNG_NAME_64 xorshift_13_7_17 +#define PRNG_STATE_64_T uint64_t +#endif // XORSHIFT_13_7_17 + +#ifdef XORSHIFT_6_21_7 +#define PRNG_NAME_32 xorshift_6_21_7 +#define PRNG_STATE_32_T uint32_t +#endif // XORSHIFT_6_21_7 + +#ifdef XORSHIFT_12_25_27 +#define PRNG_NAME_64 xorshift_12_25_27 +#define PRNG_STATE_64_T uint64_t +#endif // XORSHIFT_12_25_27 + +#ifdef KISS_64 +#define PRNG_NAME_64 kiss_64 +#define PRNG_STATE_64_T GLUE(PRNG_NAME_64,_t) +typedef struct PRNG_STATE_64_T { uint64_t z, w, jsr, jcong; } PRNG_STATE_64_T; +#endif // KISS_^64 + +#ifdef XORWOW +#define PRNG_NAME_32 xorwow +#define PRNG_STATE_32_T GLUE(PRNG_NAME_32,_t) +typedef struct PRNG_STATE_32_T { uint32_t a, b, c, d, counter; } PRNG_STATE_32_T; +#endif // XOSHIRO128PP + +#define PRNG_SET_SEED_64 GLUE(PRNG_NAME_64,_set_seed) +#define PRNG_SET_SEED_32 GLUE(PRNG_NAME_32,_set_seed) + + +// Default PRNG used by runtime. +#ifdef __x86_64__ // 64-bit architecture +#define PRNG_NAME PRNG_NAME_64 +#define PRNG_STATE_T PRNG_STATE_64_T +#else // 32-bit architecture +#define PRNG_NAME PRNG_NAME_32 +#define PRNG_STATE_T PRNG_STATE_32_T +#endif // __x86_64__ + +#define PRNG_SET_SEED GLUE(PRNG_NAME,_set_seed) + + +// ALL PRNG ALGORITHMS ARE OPTIMIZED SO THAT THE PRNG LOGIC CAN HAPPEN IN PARALLEL WITH THE USE OF THE RESULT. +// Therefore, the set_seed routine primes the PRNG by calling it with the state so the seed is not return as the +// first random value. + +#ifdef __cforall // don't include in C code (invoke.h) + +// https://prng.di.unimi.it/xoshiro256starstar.c +// +// This is xoshiro256++ 1.0, one of our all-purpose, rock-solid generators. It has excellent (sub-ns) speed, a state +// (256 bits) that is large enough for any parallel application, and it passes all tests we are aware of. +// +// For generating just floating-point numbers, xoshiro256+ is even faster. +// +// The state must be seeded so that it is not everywhere zero. If you have a 64-bit seed, we suggest to seed a +// splitmix64 generator and use its output to fill s. + +#ifndef XOSHIRO256PP +typedef struct xoshiro256pp_t { uint64_t s[4]; } xoshiro256pp_t; +#endif // ! XOSHIRO256PP + +static inline uint64_t xoshiro256pp( xoshiro256pp_t & rs ) with(rs) { + inline uint64_t rotl(const uint64_t x, int k) { + return (x << k) | (x >> (64 - k)); + } // rotl + + const uint64_t result = rotl( s[0] + s[3], 23 ) + s[0]; + const uint64_t t = s[1] << 17; + + s[2] ^= s[0]; + s[3] ^= s[1]; + s[1] ^= s[2]; + s[0] ^= s[3]; + s[2] ^= t; + s[3] = rotl( s[3], 45 ); + return result; +} // xoshiro256pp + +static inline void xoshiro256pp_set_seed( xoshiro256pp_t & state, uint64_t seed ) { + state = (xoshiro256pp_t){ {seed, seed, seed, seed} }; + xoshiro256pp( state ); +} // xoshiro256pp_set_seed + +// https://prng.di.unimi.it/xoshiro128plusplus.c +// +// This is xoshiro128++ 1.0, one of our 32-bit all-purpose, rock-solid generators. It has excellent speed, a state size +// (128 bits) that is large enough for mild parallelism, and it passes all tests we are aware of. +// +// For generating just single-precision (i.e., 32-bit) floating-point numbers, xoshiro128+ is even faster. +// +// The state must be seeded so that it is not everywhere zero. + +#ifndef XOSHIRO128PP +typedef struct xoshiro128pp_t { uint32_t s[4]; } xoshiro128pp_t; +#endif // ! XOSHIRO128PP + +static inline uint32_t xoshiro128pp( xoshiro128pp_t & rs ) with(rs) { + inline uint32_t rotl( const uint32_t x, int k ) { + return (x << k) | (x >> (32 - k)); + } // rotl + + const uint32_t result = rotl( s[0] + s[3], 7 ) + s[0]; + const uint32_t t = s[1] << 9; + + s[2] ^= s[0]; + s[3] ^= s[1]; + s[1] ^= s[2]; + s[0] ^= s[3]; + s[2] ^= t; + s[3] = rotl( s[3], 11 ); + return result; +} // xoshiro128pp + +static inline void xoshiro128pp_set_seed( xoshiro128pp_t & state, uint32_t seed ) { + state = (xoshiro128pp_t){ {seed, seed, seed, seed} }; + xoshiro128pp( state ); // prime +} // xoshiro128pp_set_seed + +#ifdef __SIZEOF_INT128__ + // Pipelined to allow out-of-order overlap with reduced dependencies. Critically, the current random state is + // returned (copied), and then compute and store the next random value. + //-------------------------------------------------- static inline uint64_t lehmer64( __uint128_t & state ) { __uint128_t ret = state; state *= 0xda942042e4dd58b5; return ret >> 64; - } - -//-------------------------------------------------- + } // lehmer64 + + static inline void lehmer64_set_seed( __uint128_t & state, uint64_t seed ) { + state = seed; + lehmer64( state ); + } // lehmer64_set_seed + + //-------------------------------------------------- static inline uint64_t wyhash64( uint64_t & state ) { - state += 0x60bee2bee120fc15; + uint64_t ret = state; + state += 0x_60be_e2be_e120_fc15; __uint128_t tmp; - tmp = (__uint128_t) state * 0xa3b195354a39b70d; + tmp = (__uint128_t) ret * 0x_a3b1_9535_4a39_b70d; uint64_t m1 = (tmp >> 64) ^ tmp; - tmp = (__uint128_t)m1 * 0x1b03738712fad5c9; + tmp = (__uint128_t)m1 * 0x_1b03_7387_12fa_d5c9; uint64_t m2 = (tmp >> 64) ^ tmp; return m2; - } -#endif + } // wyhash64 + + static inline void wyhash64_set_seed( uint64_t & state, uint64_t seed ) { + state = seed; + wyhash64( state ); // prime + } // wyhash64_set_seed +#endif // __SIZEOF_INT128__ //-------------------------------------------------- @@ -48,7 +226,16 @@ state ^= state << 17; return ret; -} - -//-------------------------------------------------- +} // xorshift_13_7_17 + +static inline void xorshift_13_7_17_set_seed( uint64_t & state, uint64_t seed ) { + state = seed; + xorshift_13_7_17( state ); // prime +} // xorshift_13_7_17_set_seed + +//-------------------------------------------------- +// Marsaglia shift-XOR PRNG with thread-local state +// Period is 4G-1 +// 0 is absorbing and must be avoided +// Low-order bits are not particularly random static inline uint32_t xorshift_6_21_7( uint32_t & state ) { uint32_t ret = state; @@ -59,38 +246,77 @@ } // xorshift_6_21_7 -//-------------------------------------------------- -typedef struct { - uint32_t a, b, c, d; - uint32_t counter; -} xorwow__state_t; - -// The state array must be initialized to not be all zero in the first four words. -static inline uint32_t xorwow( xorwow__state_t & state ) { +static inline void xorshift_6_21_7_set_seed( uint32_t & state, uint32_t seed ) { + state = seed; + xorshift_6_21_7( state ); // prime +} // xorshift_6_21_7_set_seed + +//-------------------------------------------------- +// The state must be seeded with a nonzero value. +static inline uint64_t xorshift_12_25_27( uint64_t & state ) { + uint64_t ret = state; + state ^= state >> 12; + state ^= state << 25; + state ^= state >> 27; + return ret * 0x_2545_F491_4F6C_DD1D; +} // xorshift_12_25_27 + +static inline void xorshift_12_25_27_set_seed( uint64_t & state, uint64_t seed ) { + state = seed; + xorshift_12_25_27( state ); // prime +} // xorshift_12_25_27_set_seed + +//-------------------------------------------------- +// The state must be seeded with a nonzero value. +#ifndef KISS_64 +typedef struct kiss_64_t { uint64_t z, w, jsr, jcong; } kiss_64_t; +#endif // ! KISS_64 + +static inline uint64_t kiss_64( kiss_64_t & state ) with(state) { + kiss_64_t ret = state; + z = 36969 * (z & 65535) + (z >> 16); + w = 18000 * (w & 65535) + (w >> 16); + jsr ^= (jsr << 17); + jsr ^= (jsr << 13); + jsr ^= (jsr << 5); + jcong = 69069 * jcong + 1234567; + return (((ret.z << 16) + ret.w) ^ ret.jcong) + ret.jsr; +} // kiss_64 + +static inline void kiss_64_set_seed( kiss_64_t & state, uint64_t seed ) with(state) { + z = 1; w = 1; jsr = 4; jcong = seed; + kiss_64( state ); // prime +} // kiss_64_set_seed + +//-------------------------------------------------- +// The state array must be initialized to non-zero in the first four words. +#ifndef XORWOW +typedef struct xorwow_t { uint32_t a, b, c, d, counter; } xorwow_t; +#endif // ! XORWOW + +static inline uint32_t xorwow( xorwow_t & state ) with(state) { // Algorithm "xorwow" from p. 5 of Marsaglia, "Xorshift RNGs". - uint32_t ret = state.a + state.counter; - uint32_t t = state.d; - - uint32_t const s = state.a; - state.d = state.c; - state.c = state.b; - state.b = s; + uint32_t ret = a + counter; + uint32_t t = d; + + uint32_t const s = a; + d = c; + c = b; + b = s; t ^= t >> 2; t ^= t << 1; t ^= s ^ (s << 4); - state.a = t; - - state.counter += 362437; + a = t; + counter += 362437; return ret; -} - -//-------------------------------------------------- -static inline uint32_t LCG( uint32_t & state ) { // linear congruential generator - uint32_t ret = state; - state = 36969 * (state & 65535) + (state >> 16); // 36969 is NOT prime! No not change it! - return ret; -} // LCG - -//-------------------------------------------------- +} // xorwow + +static inline void xorwow_set_seed( xorwow_t & state, uint32_t seed ) { + state = (xorwow_t){ seed, seed, seed, seed, 0 }; + xorwow( state ); // prime +} // xorwow_set_seed + +//-------------------------------------------------- +// Used in __tls_rand_fwd #define M (1_l64u << 48_l64u) #define A (25214903917_l64u) @@ -103,5 +329,5 @@ state = (A * state + C) & (M - 1); return state >> D; -} +} // LCGBI_fwd static inline uint32_t LCGBI_bck( uint64_t & state ) { @@ -109,5 +335,5 @@ state = AI * (state - C) & (M - 1); return r; -} +} // LCGBI_bck #undef M @@ -116,2 +342,4 @@ #undef C #undef D + +#endif // __cforall Index: libcfa/src/concurrency/invoke.h =================================================================== --- libcfa/src/concurrency/invoke.h (revision 7d9598d809dda423890eb3996cfe6e61bc3b543b) +++ libcfa/src/concurrency/invoke.h (revision 2dcd80a064f6154cf7aad118ffd2a53fa127cab5) @@ -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 : Tue Nov 29 20:42:21 2022 +// Update Count : 56 // @@ -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_STATE_T random_state; // fast random numbers #if defined( __CFA_WITH_VERIFY__ ) Index: libcfa/src/concurrency/kernel.cfa =================================================================== --- libcfa/src/concurrency/kernel.cfa (revision 7d9598d809dda423890eb3996cfe6e61bc3b543b) +++ libcfa/src/concurrency/kernel.cfa (revision 2dcd80a064f6154cf7aad118ffd2a53fa127cab5) @@ -10,6 +10,6 @@ // Created On : Tue Jan 17 12:27:26 2017 // Last Modified By : Peter A. Buhr -// Last Modified On : Mon Aug 31 07:08:20 2020 -// Update Count : 71 +// Last Modified On : Wed Nov 30 18:14:08 2022 +// Update Count : 76 // @@ -151,5 +151,5 @@ // Because of a bug, we couldn't initialized the seed on construction // Do it here - __cfaabi_tls.rand_seed ^= rdtscl(); + PRNG_SET_SEED( __cfaabi_tls.random_state, rdtscl() ); __cfaabi_tls.ready_rng.fwd_seed = 25214903917_l64u * (rdtscl() ^ (uintptr_t)&runner); __tls_rand_advance_bck(); Index: libcfa/src/concurrency/kernel/fwd.hfa =================================================================== --- libcfa/src/concurrency/kernel/fwd.hfa (revision 7d9598d809dda423890eb3996cfe6e61bc3b543b) +++ libcfa/src/concurrency/kernel/fwd.hfa (revision 2dcd80a064f6154cf7aad118ffd2a53fa127cab5) @@ -46,9 +46,6 @@ } preemption_state; - #if defined(__SIZEOF_INT128__) - __uint128_t rand_seed; - #else - uint64_t rand_seed; - #endif + PRNG_STATE_T random_state; + struct { uint64_t fwd_seed; @@ -57,5 +54,4 @@ struct __stats_t * volatile this_stats; - #ifdef __CFA_WITH_VERIFY__ @@ -76,11 +72,12 @@ #define publicTLS_get( member ) ((typeof(__cfaabi_tls.member))__cfatls_get( __builtin_offsetof(KernelThreadData, member) )) - static inline uint64_t __tls_rand() { - return - #if defined(__SIZEOF_INT128__) - lehmer64( kernelTLS().rand_seed ); - #else - xorshift_13_7_17( kernelTLS().rand_seed ); - #endif + static inline + #ifdef __x86_64__ // 64-bit architecture + uint64_t + #else // 32-bit architecture + uint32_t + #endif // __x86_64__ + __tls_rand() { + return PRNG_NAME( kernelTLS().random_state ); } @@ -120,5 +117,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 7d9598d809dda423890eb3996cfe6e61bc3b543b) +++ libcfa/src/concurrency/kernel/startup.cfa (revision 2dcd80a064f6154cf7aad118ffd2a53fa127cab5) @@ -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; +size_t __global_random_prime = 4_294_967_291u; +bool __global_random_mask = false; //----------------------------------------------------------------------------- @@ -133,14 +135,14 @@ // Global state __thread struct KernelThreadData __cfaabi_tls __attribute__ ((tls_model ( "initial-exec" ))) @= { - NULL, // cannot use 0p - NULL, - false, - { 1, false, false }, - 0, - { 0, 0 }, - NULL, + .this_thread : NULL, // cannot use 0p + .this_processor : NULL, + .sched_lock : false, + .preemption_state : { .disable_count : 1, .enabled : false, .in_progress : false }, + // random_state uninitialized + .ready_rng : { .fwd_seed : 0, .bck_seed : 0 }, + .this_stats : NULL, #ifdef __CFA_WITH_VERIFY__ - false, - 0, + .in_sched_lock : false, + .sched_id : 0, #endif }; @@ -513,7 +515,11 @@ rdy_link.next = 0p; rdy_link.ts = MAX; + user_link.next = 0p; + user_link.prev = 0p; + cltr_link.next = 0p; + cltr_link.prev = 0p; preferred = ready_queue_new_preferred(); last_proc = 0p; - random_state = __global_random_mask ? __global_random_prime : __global_random_prime ^ rdtscl(); + PRNG_SET_SEED( random_state, __global_random_mask ? __global_random_prime : __global_random_prime ^ rdtscl() ); #if defined( __CFA_WITH_VERIFY__ ) executing = 0p; Index: libcfa/src/concurrency/stats.cfa =================================================================== --- libcfa/src/concurrency/stats.cfa (revision 7d9598d809dda423890eb3996cfe6e61bc3b543b) +++ libcfa/src/concurrency/stats.cfa (revision 2dcd80a064f6154cf7aad118ffd2a53fa127cab5) @@ -48,5 +48,7 @@ stats->io.submit.eagr = 0; stats->io.submit.nblk = 0; + stats->io.submit.extr = 0; stats->io.flush.external = 0; + stats->io.flush.signal = 0; stats->io.flush.dirty = 0; stats->io.flush.full = 0; @@ -120,5 +122,7 @@ tally_one( &cltr->io.submit.eagr , &proc->io.submit.eagr ); tally_one( &cltr->io.submit.nblk , &proc->io.submit.nblk ); + tally_one( &cltr->io.submit.extr , &proc->io.submit.extr ); tally_one( &cltr->io.flush.external , &proc->io.flush.external ); + tally_one( &cltr->io.flush.signal , &proc->io.flush.signal ); tally_one( &cltr->io.flush.dirty , &proc->io.flush.dirty ); tally_one( &cltr->io.flush.full , &proc->io.flush.full ); @@ -199,5 +203,5 @@ if(io.alloc.slow) { double avgfasts = (100.0 * (double)io.submit.fast) / total_submits; - sstr | "fast," | eng3(io.submit.slow) | "slow (" | ws(3, 3, avgfasts) | "%)" | nonl; + sstr | "fast," | eng3(io.submit.slow) | "slow (" | ws(3, 3, avgfasts) | "%)," | eng3(io.submit.extr) | "external" | nonl; } sstr | " - eager" | eng3(io.submit.eagr) | nonl; @@ -217,5 +221,5 @@ | " - cmp " | eng3(io.calls.locked) | "locked, " | eng3(io.calls.helped) | "helped" | " - " | eng3(io.calls.errors.busy) | " EBUSY"; - sstr | " - sub: " | eng3(io.flush.full) | "full, " | eng3(io.flush.dirty) | "drty, " | eng3(io.flush.idle) | "idle, " | eng3(io.flush.eager) | "eagr, " | eng3(io.flush.external) | "ext"; + sstr | " - sub: " | eng3(io.flush.full) | "full, " | eng3(io.flush.dirty) | "drty, " | eng3(io.flush.idle) | "idle, " | eng3(io.flush.eager) | "eagr, " | eng3(io.flush.external) | '/' | eng3(io.flush.signal) | "ext"; sstr | "- ops blk: " | " sk rd: " | eng3(io.ops.sockread) | "epll: " | eng3(io.ops.epllread) Index: libcfa/src/concurrency/stats.hfa =================================================================== --- libcfa/src/concurrency/stats.hfa (revision 7d9598d809dda423890eb3996cfe6e61bc3b543b) +++ libcfa/src/concurrency/stats.hfa (revision 2dcd80a064f6154cf7aad118ffd2a53fa127cab5) @@ -94,7 +94,9 @@ volatile uint64_t eagr; volatile uint64_t nblk; + volatile uint64_t extr; } submit; struct { volatile uint64_t external; + volatile uint64_t signal; volatile uint64_t dirty; volatile uint64_t full; Index: libcfa/src/concurrency/thread.cfa =================================================================== --- libcfa/src/concurrency/thread.cfa (revision 7d9598d809dda423890eb3996cfe6e61bc3b543b) +++ libcfa/src/concurrency/thread.cfa (revision 2dcd80a064f6154cf7aad118ffd2a53fa127cab5) @@ -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 Dec 11 20:56:54 2022 +// Update Count : 102 // @@ -26,5 +26,7 @@ #include "invoke.h" -extern uint32_t __global_random_seed, __global_random_prime, __global_random_mask; +extern size_t __global_random_seed; +extern size_t __global_random_prime; +extern bool __global_random_mask; #pragma GCC visibility push(default) @@ -46,7 +48,11 @@ rdy_link.next = 0p; rdy_link.ts = MAX; + user_link.next = 0p; + user_link.prev = 0p; + cltr_link.next = 0p; + cltr_link.prev = 0p; preferred = ready_queue_new_preferred(); last_proc = 0p; - random_state = __global_random_mask ? __global_random_prime : __global_random_prime ^ rdtscl(); + PRNG_SET_SEED( random_state, __global_random_mask ? __global_random_prime : __global_random_prime ^ rdtscl() ); #if defined( __CFA_WITH_VERIFY__ ) executing = 0p; @@ -176,10 +182,7 @@ //----------------------------------------------------------------------------- bool migrate( thread$ * thrd, struct cluster & cl ) { - monitor$ * tmon = get_monitor(thrd); monitor$ * __monitors[] = { tmon }; monitor_guard_t __guard = { __monitors, 1 }; - - { // if nothing needs to be done, return false @@ -221,17 +224,15 @@ //----------------------------------------------------------------------------- -#define GENERATOR LCG - -void set_seed( uint32_t seed ) { - uint32_t & state = active_thread()->random_state; - state = __global_random_seed = seed; - GENERATOR( state ); - __global_random_prime = state; + +void set_seed( size_t seed ) { + PRNG_STATE_T & state = active_thread()->random_state; + PRNG_SET_SEED( state, seed ); + __global_random_seed = seed; + __global_random_prime = seed; __global_random_mask = true; } // set_seed -uint32_t prng( void ) { // [0,UINT_MAX] - uint32_t & state = active_thread()->random_state; - return GENERATOR( state ); +size_t prng( void ) { // [0,UINT_MAX] + return PRNG_NAME( active_thread()->random_state ); } // prng Index: libcfa/src/concurrency/thread.hfa =================================================================== --- libcfa/src/concurrency/thread.hfa (revision 7d9598d809dda423890eb3996cfe6e61bc3b543b) +++ libcfa/src/concurrency/thread.hfa (revision 2dcd80a064f6154cf7aad118ffd2a53fa127cab5) @@ -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 : Tue Nov 22 22:18:34 2022 +// Update Count : 35 // @@ -23,4 +23,5 @@ #include "monitor.hfa" #include "exception.hfa" +#include "bits/random.hfa" //----------------------------------------------------------------------------- @@ -141,12 +142,13 @@ //---------- // prng +void set_seed( size_t seed ); 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] + size_t prng( thread$ & th ) __attribute__(( warn_unused_result )) { return PRNG_NAME( th.random_state ); } // [0,UINT_MAX] + size_t prng( thread$ & th, size_t u ) __attribute__(( warn_unused_result )) { return prng( th ) % u; } // [0,u) + size_t prng( thread$ & th, size_t l, size_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] + size_t prng( T & th ) __attribute__(( warn_unused_result )) { return prng( (thread &)th ); } // [0,UINT_MAX] + size_t prng( T & th, size_t u ) __attribute__(( warn_unused_result )) { return prng( th ) % u; } // [0,u) + size_t prng( T & th, size_t l, size_t u ) __attribute__(( warn_unused_result )) { return prng( th, u - l + 1 ) + l; } // [l,u] } // distribution } // distribution Index: libcfa/src/exception.h =================================================================== --- libcfa/src/exception.h (revision 7d9598d809dda423890eb3996cfe6e61bc3b543b) +++ libcfa/src/exception.h (revision 2dcd80a064f6154cf7aad118ffd2a53fa127cab5) @@ -143,5 +143,5 @@ } -forall(exceptT &, virtualT & | is_exception(exceptT, virtualT)) +forall(exceptT &, virtualT & | is_termination_exception(exceptT, virtualT)) static inline void defaultResumptionHandler(exceptT & except) { throw except; Index: libcfa/src/startup.cfa =================================================================== --- libcfa/src/startup.cfa (revision 7d9598d809dda423890eb3996cfe6e61bc3b543b) +++ libcfa/src/startup.cfa (revision 2dcd80a064f6154cf7aad118ffd2a53fa127cab5) @@ -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 : Mon Dec 5 11:41:58 2022 +// Update Count : 73 // @@ -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 size_t __global_random_seed; // sequential/concurrent +extern PRNG_STATE_T __global_random_state; // sequential extern "C" { @@ -68,5 +69,7 @@ void __cfaabi_core_startup( void ) __attribute__(( constructor( STARTUP_PRIORITY_CORE ) )); void __cfaabi_core_startup( void ) { - __global_random_state = __global_random_seed = rdtscl(); + __global_random_seed = rdtscl(); + PRNG_SET_SEED( __global_random_state, __global_random_seed ); + __cfaabi_interpose_startup(); __cfaabi_device_startup(); Index: libcfa/src/stdlib.cfa =================================================================== --- libcfa/src/stdlib.cfa (revision 7d9598d809dda423890eb3996cfe6e61bc3b543b) +++ libcfa/src/stdlib.cfa (revision 2dcd80a064f6154cf7aad118ffd2a53fa127cab5) @@ -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 : Fri Dec 9 15:11:30 2022 +// Update Count : 631 // @@ -225,15 +225,15 @@ //--------------------------------------- -#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"))) size_t __global_random_seed; // sequential/concurrent +__attribute__((visibility("hidden"))) PRNG_STATE_T __global_random_state; // sequential only + +void set_seed( size_t seed ) { + __global_random_seed = seed; + PRNG_SET_SEED( __global_random_state, seed ); +} // set_seed + +size_t get_seed() { return __global_random_seed; } +size_t prng( void ) { return PRNG_NAME( __global_random_state ); } // [0,UINT_MAX] //--------------------------------------- Index: libcfa/src/stdlib.hfa =================================================================== --- libcfa/src/stdlib.hfa (revision 7d9598d809dda423890eb3996cfe6e61bc3b543b) +++ libcfa/src/stdlib.hfa (revision 2dcd80a064f6154cf7aad118ffd2a53fa127cab5) @@ -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 Dec 11 18:25:53 2022 +// Update Count : 765 // @@ -404,19 +404,51 @@ // calls( sprng ); -struct PRNG { +trait basic_prng( PRNG &, R ) { + void set_seed( PRNG & prng, R seed ); // set seed + R get_seed( PRNG & prng ); // get seed + R prng( PRNG & prng ); + void ?{}( PRNG & prng ); // random seed + void ?{}( PRNG & prng, R seed ); // fixed seed +}; // basic_prng + +static inline forall( PRNG &, R | basic_prng( PRNG, R ) | { R ?%?( R, R ); } ) { + R prng( PRNG & prng, R u ) { return prng( prng ) % u; } // [0,u) +} +static inline forall( PRNG &, R | basic_prng( PRNG, 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_STATE_32_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 ) { seed = seed_; PRNG_SET_SEED_32( state, seed ); } + uint32_t get_seed( PRNG32 & prng ) __attribute__(( warn_unused_result )) with( prng ) { return seed; } + uint32_t prng( PRNG32 & prng ) __attribute__(( warn_unused_result )) with( prng ) { callcnt += 1; return PRNG_NAME_32( state ); } // [0,UINT_MAX] + uint32_t prng( PRNG32 & prng, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( prng ) % u; } // [0,u) + uint32_t prng( PRNG32 & prng, uint32_t l, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( prng, u - l + 1 ) + l; } // [l,u] + 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_STATE_64_T state; // random state +}; // PRNG + +static inline { + void set_seed( PRNG64 & prng, uint64_t seed_ ) with( prng ) { seed = seed_; PRNG_SET_SEED_64( state, seed ); } + uint64_t get_seed( PRNG64 & prng ) __attribute__(( warn_unused_result )) with( prng ) { return seed; } + uint64_t prng( PRNG64 & prng ) __attribute__(( warn_unused_result )) with( prng ) { callcnt += 1; return PRNG_NAME_64( state ); } // [0,UINT_MAX] + uint64_t prng( PRNG64 & prng, uint64_t u ) __attribute__(( warn_unused_result )) { return prng( prng ) % u; } // [0,u) + uint64_t prng( PRNG64 & prng, uint64_t l, uint64_t u ) __attribute__(( warn_unused_result )) { return prng( prng, u - l + 1 ) + l; } // [l,u] + 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 +467,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( size_t seed_ ) OPTIONAL_THREAD; // set global seed +size_t get_seed() __attribute__(( warn_unused_result )); // get global seed +size_t prng( void ) __attribute__(( warn_unused_result )) OPTIONAL_THREAD; // [0,UINT_MAX] +static inline { + size_t prng( size_t u ) __attribute__(( warn_unused_result )) { return prng() % u; } // [0,u) + size_t prng( size_t l, size_t u ) __attribute__(( warn_unused_result )) { return prng( u - l + 1 ) + l; } // [l,u] } // distribution