Changeset dd46fd3

Timestamp:

Nov 30, 2022, 10:36:25 PM (2 years ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

ADT, ast-experimental, master

Children:

5657de9, c8238c0

Parents:

be1d00c

Message:

generalization of PRNG

Files:

• libcfa/src/bits/random.hfa (modified) (6 diffs)
• libcfa/src/concurrency/invoke.h (modified) (2 diffs)
• libcfa/src/concurrency/kernel.cfa (modified) (2 diffs)
• libcfa/src/concurrency/kernel/fwd.hfa (modified) (3 diffs)
• libcfa/src/concurrency/kernel/startup.cfa (modified) (3 diffs)
• libcfa/src/concurrency/thread.cfa (modified) (4 diffs)
• libcfa/src/startup.cfa (modified) (3 diffs)
• libcfa/src/stdlib.cfa (modified) (2 diffs)
• libcfa/src/stdlib.hfa (modified) (3 diffs)
• tests/.expect/nested_function.x64.txt (modified) (1 diff)

libcfa/src/bits/random.hfa

@@ -10 +10 @@
 // Created On       : Fri Jan 14 07:18:11 2022
 // Last Modified By : Peter A. Buhr
-// Last Modified On : Mon Nov 21 17:50:12 2022
-// Update Count     : 15
+// Last Modified On : Wed Nov 30 18:32:25 2022
+// Update Count     : 111
 // 
 
@@ -17 +17 @@
 
 #include <stdint.h>
+
+#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
 #define LEHMER64
+#define XORSHIFT_6_21_7
+//#define XOSHIRO256PP
+//#define XOSHIRO128PP
 #else                                                                                                   // 32-bit architecture
+#define LEHMER64
 #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
+#define PRNG_NAME_64 lehmer64
+#define PRNG_STATE_64_T __uint128_t
 #endif // LEHMER64
 
 #ifdef XORSHIFT_6_21_7
-#define PRNG_NAME xorshift_6_21_7
-#define PRNG_ARG_T uint32_t
+#define PRNG_NAME_32 xorshift_6_21_7
+#define PRNG_STATE_32_T uint32_t
 #endif // XORSHIFT_6_21_7
 
+#ifdef XOSHIRO256PP
+#define PRNG_NAME_64 xoshiro256pp
+#define PRNG_STATE_64_T struct GLUE(PRNG_NAME_64,_t)
+PRNG_STATE_64_T { uint64_t s[4]; };
+#endif // XOSHIRO256PP
+
+#ifdef XOSHIRO128PP
+#define PRNG_NAME_32 xoshiro128pp
+#define PRNG_STATE_32_T struct GLUE(PRNG_NAME_32,_t)
+PRNG_STATE_32_T { uint32_t s[4]; };
+#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)
+
+
 #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
-// (copied), and then compute and store the next random value.
-
-#if defined(__SIZEOF_INT128__)
-//--------------------------------------------------
+// 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
+struct xoshiro128pp_t { uint32_t s[4]; };
+#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));
+        }
+
+        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;
+}
+
+static inline void xoshiro128pp_set_seed( xoshiro128pp_t & state, uint32_t seed ) {
+        state = (xoshiro128pp_t){ {seed, seed, seed, seed} };
+} // xoshiro128pp_set_seed
+
+// 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
+struct xoshiro256pp_t { uint64_t s[4]; };
+#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));
+        }
+
+        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;
+}
+
+static inline void xoshiro256pp_set_seed( xoshiro256pp_t & state,  uint64_t seed ) {
+        state = (xoshiro256pp_t){ {seed, seed, seed, seed} };
+} // xoshiro256pp_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_set_seed
+
+        //--------------------------------------------------
         static inline uint64_t wyhash64( uint64_t & state ) {
                 state += 0x60bee2bee120fc15;
@@ -59 +165 @@
                 return m2;
         }
-#endif
+
+        static inline void wyhash64_set_seed( __uint128_t & state, uint64_t seed ) {
+                state = seed;
+        } // lehmer64_set_seed
+#endif // __SIZEOF_INT128__
 
 //--------------------------------------------------
@@ -68 +178 @@
         state ^= state << 17;
         return ret;
+}
+
+static inline void xorshift_13_7_17_set_seed( uint64_t & state, uint32_t seed ) {
+        state = seed;
 }
 
@@ -79 +193 @@
 } // xorshift_6_21_7
 
+static inline void xorshift_6_21_7_set_seed( uint32_t & state, uint32_t seed ) {
+        state = seed;
+}
+
 //--------------------------------------------------
 typedef struct {
@@ -105 +223 @@
 }
 
-//--------------------------------------------------
-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
-
+// Used in __tls_rand_fwd
 //--------------------------------------------------
 #define M  (1_l64u << 48_l64u)

libcfa/src/concurrency/invoke.h

@@ -10 +10 @@
 // Created On       : Tue Jan 17 12:27:26 2016
 // Last Modified By : Peter A. Buhr
-// Last Modified On : Mon Nov 21 17:40:24 2022
-// Update Count     : 55
+// Last Modified On : Tue Nov 29 20:42:21 2022
+// Update Count     : 56
 //
 
@@ -223 +223 @@
                 struct processor * last_proc;
 
-                PRNG_ARG_T random_state;                                                // fast random numbers
+                PRNG_STATE_T random_state;                                              // fast random numbers
 
                 #if defined( __CFA_WITH_VERIFY__ )

libcfa/src/concurrency/kernel.cfa

@@ -10 +10 @@
 // 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 +151 @@
         // 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();

libcfa/src/concurrency/kernel/fwd.hfa

@@ -46 +46 @@
                         } 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 +54 @@
 
                         struct __stats_t        * volatile this_stats;
-
 
                         #ifdef __CFA_WITH_VERIFY__
@@ -76 +72 @@
                 #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 );
                 }
 

libcfa/src/concurrency/kernel/startup.cfa

@@ -108 +108 @@
 extern void __wake_proc(processor *);
 extern int cfa_main_returned;                                                   // from interpose.cfa
-PRNG_ARG_T __global_random_prime = 4_294_967_291u;
+size_t __global_random_prime = 4_294_967_291u;
 bool __global_random_mask = false;
 
@@ -135 +135 @@
 // 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
 };
@@ -521 +521 @@
         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;

libcfa/src/concurrency/thread.cfa

@@ -10 +10 @@
 // Created On       : Tue Jan 17 12:27:26 2017
 // Last Modified By : Peter A. Buhr
-// Last Modified On : Tue Nov 22 22:18:37 2022
-// Update Count     : 81
+// Last Modified On : Wed Nov 30 18:14:07 2022
+// Update Count     : 95
 //
 
@@ -26 +26 @@
 #include "invoke.h"
 
-extern PRNG_ARG_T __global_random_seed, __global_random_prime;
+extern size_t __global_random_seed;
+extern size_t __global_random_prime;
 extern bool __global_random_mask;
 
@@ -53 +54 @@
         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;
@@ -228 +229 @@
 
 void set_seed( size_t seed ) {
-        PRNG_ARG_T & state = active_thread()->random_state;
-        state = __global_random_seed = seed;
+        PRNG_STATE_T & state = active_thread()->random_state;
+        __global_random_seed = seed;
+        PRNG_SET_SEED( state, seed );
         (void)PRNG_NAME( state );                                                       // prime PRNG
-        __global_random_prime = state;
+        __global_random_prime = seed;
         __global_random_mask = true;
 } // set_seed
 
 size_t prng( void ) {                                                                   // [0,UINT_MAX]
-        PRNG_ARG_T & state = active_thread()->random_state;
+        PRNG_STATE_T( & state ) = active_thread()->random_state;
         return PRNG_NAME( state );
 } // prng

libcfa/src/startup.cfa

@@ -10 +10 @@
 // Created On       : Tue Jul 24 16:21:57 2018
 // Last Modified By : Peter A. Buhr
-// Last Modified On : Sun Nov 20 21:26:40 2022
-// Update Count     : 59
+// Last Modified On : Wed Nov 30 18:14:06 2022
+// Update Count     : 68
 //
 
@@ -21 +21 @@
 #include "startup.hfa"
 
-extern PRNG_ARG_T __global_random_seed;                                 // sequential/concurrent
-extern PRNG_ARG_T __global_random_state;                                // sequential
+extern size_t __global_random_seed;                                             // sequential/concurrent
+extern PRNG_STATE_T __global_random_state;                              // sequential
 
 extern "C" {
@@ -69 +69 @@
         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();

libcfa/src/stdlib.cfa

@@ -10 +10 @@
 // Created On       : Thu Jan 28 17:10:29 2016
 // Last Modified By : Peter A. Buhr
-// Last Modified On : Tue Nov 22 22:18:36 2022
-// Update Count     : 613
+// Last Modified On : Wed Nov 30 18:14:05 2022
+// Update Count     : 622
 //
 
@@ -226 +226 @@
 
 // would be cool to make hidden but it's needed for libcfathread
-__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( size_t seed ) { __global_random_state = __global_random_seed = seed; PRNG_NAME( __global_random_state ); }
+__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 ); PRNG_NAME( __global_random_state ); }
 size_t get_seed() { return __global_random_seed; }
 size_t prng( void ) { return PRNG_NAME( __global_random_state ); } // [0,UINT_MAX]

libcfa/src/stdlib.hfa

@@ -10 +10 @@
 // Created On       : Thu Jan 28 17:12:35 2016
 // Last Modified By : Peter A. Buhr
-// Last Modified On : Tue Nov 22 22:48:59 2022
-// Update Count     : 736
+// Last Modified On : Wed Nov 30 18:18:26 2022
+// Update Count     : 760
 //
 
@@ -422 +422 @@
         uint32_t callcnt;                                                                       // call count
         uint32_t seed;                                                                          // current seed
-        PRNG_ARG_T state;                                                                       // random state
+        PRNG_STATE_32_T state;                                                          // random state
 }; // PRNG
 
 static inline {
-        void set_seed( PRNG32 & prng, uint32_t seed_ ) with( prng ) { state = seed = seed_; PRNG_NAME( state ); } // set seed
+        void set_seed( PRNG32 & prng, uint32_t seed_ ) with( prng ) { seed = seed_; PRNG_SET_SEED_32( state, seed ); PRNG_NAME_32( 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 prng( PRNG32 & prng ) __attribute__(( warn_unused_result )) with( prng ) { callcnt += 1; return PRNG_NAME_32( state ); } // [0,UINT_MAX]
         uint32_t prng( PRNG32 & prng, size_t u ) __attribute__(( warn_unused_result )) { return prng( prng ) % u; } // [0,u)
         uint32_t prng( PRNG32 & prng, size_t l, size_t u ) __attribute__(( warn_unused_result )) { return prng( prng, u - l + 1 ) + l; } // [l,u]
@@ -439 +439 @@
         uint64_t callcnt;                                                                       // call count
         uint64_t seed;                                                                          // current seed
-        PRNG_ARG_T state;                                                                       // random state
+        PRNG_STATE_64_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
+        void set_seed( PRNG64 & prng, uint64_t seed_ ) with( prng ) { seed = seed_; PRNG_SET_SEED_64( state, seed ); PRNG_NAME_64( 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 prng( PRNG64 & prng ) __attribute__(( warn_unused_result )) with( prng ) { callcnt += 1; return PRNG_NAME_64( state ); } // [0,UINT_MAX]
         uint64_t prng( PRNG64 & prng, size_t u ) __attribute__(( warn_unused_result )) { return prng( prng ) % u; } // [0,u)
         uint64_t prng( PRNG64 & prng, size_t l, size_t u ) __attribute__(( warn_unused_result )) { return prng( prng, u - l + 1 ) + l; } // [l,u]

tests/.expect/nested_function.x64.txt

@@ -1 @@
-total 80
+total 75