[5910fc0] | 1 | // -*- Mode: C -*- |
---|
| 2 | // |
---|
| 3 | // Cforall Version 1.0.0 Copyright (C) 2021 University of Waterloo |
---|
| 4 | // |
---|
| 5 | // PRNG.c -- |
---|
| 6 | // |
---|
| 7 | // Author : Peter A. Buhr |
---|
| 8 | // Created On : Wed Dec 29 09:38:12 2021 |
---|
| 9 | // Last Modified By : Peter A. Buhr |
---|
[8a2f7f1] | 10 | // Last Modified On : Sat Apr 15 16:44:31 2023 |
---|
| 11 | // Update Count : 419 |
---|
[5910fc0] | 12 | // |
---|
| 13 | |
---|
| 14 | #include <fstream.hfa> // sout |
---|
| 15 | #include <stdlib.hfa> // PRNG |
---|
| 16 | #include <clock.hfa> |
---|
| 17 | #include <limits.hfa> // MAX |
---|
| 18 | #include <math.hfa> // sqrt |
---|
| 19 | #include <malloc.h> // malloc_stats |
---|
| 20 | #include <locale.h> // setlocale |
---|
[8a2f7f1] | 21 | #include <thread.hfa> |
---|
[470618c0] | 22 | #include <mutex_stmt.hfa> |
---|
[5910fc0] | 23 | |
---|
[8a2f7f1] | 24 | #define xstr(s) str(s) |
---|
| 25 | #define str(s) #s |
---|
| 26 | |
---|
| 27 | #if defined( __x86_64__ ) || defined( __aarch64__ ) // 64-bit architecture |
---|
[d2ad151] | 28 | #define PRNG PRNG64 |
---|
| 29 | #else // 32-bit architecture |
---|
| 30 | #define PRNG PRNG32 |
---|
| 31 | #endif // __x86_64__ |
---|
| 32 | |
---|
[8a2f7f1] | 33 | //#define TIME |
---|
| 34 | |
---|
[5910fc0] | 35 | #ifdef TIME // use -O2 -nodebug |
---|
| 36 | #define STARTTIME start = timeHiRes() |
---|
| 37 | #define ENDTIME( extra ) sout | wd(0,1, (timeHiRes() - start)`ms / 1000.) | extra "seconds" |
---|
| 38 | enum { BUCKETS = 100_000, TRIALS = 1_000_000_000 }; |
---|
| 39 | #else |
---|
| 40 | #define STARTTIME |
---|
| 41 | #define ENDTIME( extra ) |
---|
| 42 | enum { BUCKETS = 100_000, TRIALS = 100_000_000 }; |
---|
| 43 | #endif // TIME |
---|
| 44 | |
---|
[8a2f7f1] | 45 | static void avgstd( size_t trials, size_t buckets[] ) { |
---|
| 46 | size_t min = MAX, max = 0; |
---|
[5910fc0] | 47 | double sum = 0.0, diff; |
---|
| 48 | for ( i; BUCKETS ) { |
---|
| 49 | if ( buckets[i] < min ) min = buckets[i]; |
---|
| 50 | if ( buckets[i] > max ) max = buckets[i]; |
---|
| 51 | sum += buckets[i]; |
---|
| 52 | } // for |
---|
| 53 | |
---|
| 54 | double avg = sum / BUCKETS; // average |
---|
| 55 | sum = 0.0; |
---|
| 56 | for ( i; BUCKETS ) { // sum squared differences from average |
---|
| 57 | diff = buckets[i] - avg; |
---|
| 58 | sum += diff * diff; |
---|
| 59 | } // for |
---|
| 60 | double std = sqrt( sum / BUCKETS ); |
---|
[8a2f7f1] | 61 | mutex( sout ) sout | "trials" | trials | "buckets" | BUCKETS |
---|
[470618c0] | 62 | | "min" | min | "max" | max |
---|
| 63 | | "avg" | wd(0,1, avg) | "std" | wd(0,1, std) | "rstd" | wd(0,1, (avg == 0 ? 0.0 : std / avg * 100)) | "%"; |
---|
[5910fc0] | 64 | } // avgstd |
---|
| 65 | |
---|
| 66 | |
---|
[ae7a085c] | 67 | size_t seed = 1009; |
---|
[5910fc0] | 68 | |
---|
| 69 | thread T1 {}; |
---|
| 70 | void main( T1 & ) { |
---|
[8a2f7f1] | 71 | size_t * buckets = calloc( BUCKETS ); // too big for task stack |
---|
| 72 | for ( TRIALS / 50 ) { |
---|
[5910fc0] | 73 | buckets[rand() % BUCKETS] += 1; // concurrent |
---|
| 74 | } // for |
---|
[8a2f7f1] | 75 | avgstd( TRIALS / 50, buckets ); |
---|
[5910fc0] | 76 | free( buckets ); |
---|
| 77 | } // main |
---|
| 78 | |
---|
| 79 | thread T2 {}; |
---|
| 80 | void main( T2 & ) { |
---|
| 81 | PRNG prng; |
---|
| 82 | if ( seed != 0 ) set_seed( prng, seed ); |
---|
[8a2f7f1] | 83 | size_t * buckets = calloc( BUCKETS ); // too big for task stack |
---|
[5910fc0] | 84 | for ( TRIALS ) { |
---|
| 85 | buckets[prng( prng ) % BUCKETS] += 1; // concurrent |
---|
| 86 | } // for |
---|
[8a2f7f1] | 87 | avgstd( TRIALS, buckets ); |
---|
[5910fc0] | 88 | free( buckets ); |
---|
| 89 | } // main |
---|
| 90 | |
---|
| 91 | thread T3 {}; |
---|
| 92 | void main( T3 & th ) { |
---|
[8a2f7f1] | 93 | size_t * buckets = calloc( BUCKETS ); // too big for task stack |
---|
| 94 | for ( TRIALS / 5 ) { |
---|
[5910fc0] | 95 | buckets[prng() % BUCKETS] += 1; // concurrent |
---|
| 96 | } // for |
---|
[8a2f7f1] | 97 | avgstd( TRIALS / 5, buckets ); |
---|
[5910fc0] | 98 | free( buckets ); |
---|
| 99 | } // main |
---|
| 100 | |
---|
| 101 | thread T4 {}; |
---|
| 102 | void main( T4 & th ) { |
---|
[8a2f7f1] | 103 | size_t * buckets = calloc( BUCKETS ); // too big for task stack |
---|
[5910fc0] | 104 | for ( TRIALS ) { |
---|
[8a2f7f1] | 105 | buckets[prng( th ) % BUCKETS] += 1; // concurrent |
---|
[5910fc0] | 106 | } // for |
---|
[8a2f7f1] | 107 | avgstd( TRIALS, buckets ); |
---|
[5910fc0] | 108 | free( buckets ); |
---|
| 109 | } // main |
---|
| 110 | |
---|
| 111 | // Compiler bug requires hiding declaration of th from the bucket access, otherwise the compiler thinks th is aliased |
---|
| 112 | // and continually reloads it from memory, which doubles the cost. |
---|
| 113 | static void dummy( thread$ & th ) __attribute__(( noinline )); |
---|
| 114 | static void dummy( thread$ & th ) { |
---|
[8a2f7f1] | 115 | size_t * buckets = (size_t *)calloc( BUCKETS, sizeof(size_t) ); // too big for task stack |
---|
| 116 | for ( size_t i = 0; i < TRIALS; i += 1 ) { |
---|
[5910fc0] | 117 | buckets[prng( th ) % BUCKETS] += 1; // sequential |
---|
| 118 | } // for |
---|
[8a2f7f1] | 119 | avgstd( TRIALS, buckets ); |
---|
[5910fc0] | 120 | free( buckets ); |
---|
| 121 | } // dummy |
---|
| 122 | |
---|
[ae7a085c] | 123 | |
---|
[5910fc0] | 124 | int main() { |
---|
| 125 | // causes leaked storage message |
---|
[ae7a085c] | 126 | // setlocale( LC_NUMERIC, getenv( "LANG" ) ); // print digit separator |
---|
| 127 | // locale_t loc = newlocale( LC_NUMERIC_MASK, getenv( "LANG" ), (locale_t)0p ); |
---|
| 128 | // if ( loc == (locale_t)0p ) abort( "newlocale" ); |
---|
| 129 | // uselocale( loc ); |
---|
[5910fc0] | 130 | |
---|
| 131 | enum { TASKS = 4 }; |
---|
| 132 | Time start; |
---|
[8a2f7f1] | 133 | |
---|
[5910fc0] | 134 | #ifdef TIME // too slow for test and generates non-repeatable results |
---|
| 135 | #if 1 |
---|
[8a2f7f1] | 136 | sout | "glib rand" | nl | nl; |
---|
| 137 | |
---|
| 138 | size_t rseed; |
---|
[5910fc0] | 139 | if ( seed != 0 ) rseed = seed; |
---|
| 140 | else rseed = rdtscl(); |
---|
| 141 | srand( rseed ); |
---|
| 142 | |
---|
| 143 | sout | sepDisable; |
---|
[8a2f7f1] | 144 | sout | nl | wd(26, "rand()" ) | wd(12, "rand(5)") | wd(12, "rand(0,5)" ); |
---|
[5910fc0] | 145 | for ( 20 ) { |
---|
[ae7a085c] | 146 | sout | wd(26, rand()) | nonl; |
---|
| 147 | sout | wd(12, rand() % 5) | nonl; |
---|
| 148 | sout | wd(12, rand() % (5 - 0 + 1) + 0); |
---|
[5910fc0] | 149 | } // for |
---|
| 150 | sout | sepEnable; |
---|
| 151 | sout | "seed" | rseed; |
---|
| 152 | |
---|
| 153 | sout | nl | "Sequential"; |
---|
| 154 | STARTTIME; |
---|
| 155 | { |
---|
[8a2f7f1] | 156 | size_t * buckets = calloc( BUCKETS ); // too big for task stack |
---|
| 157 | for ( i; TRIALS / 5 ) { |
---|
[5910fc0] | 158 | buckets[rand() % BUCKETS] += 1; // sequential |
---|
| 159 | } // for |
---|
[8a2f7f1] | 160 | avgstd( TRIALS / 5, buckets ); |
---|
[5910fc0] | 161 | free( buckets ); |
---|
| 162 | } |
---|
[8a2f7f1] | 163 | ENDTIME( " x 5 " ); |
---|
[5910fc0] | 164 | |
---|
| 165 | sout | nl | "Concurrent"; |
---|
| 166 | STARTTIME; |
---|
| 167 | { |
---|
| 168 | processor p[TASKS - 1]; // already 1 processor |
---|
| 169 | { |
---|
| 170 | T1 t[TASKS]; |
---|
| 171 | } // wait for threads to complete |
---|
| 172 | } |
---|
[8a2f7f1] | 173 | ENDTIME( " x 50 " ); |
---|
[5910fc0] | 174 | #endif // 0 |
---|
| 175 | #endif // TIME |
---|
[8a2f7f1] | 176 | |
---|
| 177 | sout | nl | "CFA " xstr(PRNG_NAME); |
---|
| 178 | |
---|
[5910fc0] | 179 | #if 1 |
---|
| 180 | PRNG prng; |
---|
[d2ad151] | 181 | |
---|
[5910fc0] | 182 | if ( seed != 0 ) set_seed( prng, seed ); |
---|
| 183 | |
---|
| 184 | sout | sepDisable; |
---|
[ae7a085c] | 185 | sout | nl | wd(26, "PRNG()" ) | wd(12, "PRNG(5)") | wd(12, "PRNG(0,5)" ); |
---|
[5910fc0] | 186 | for ( 20 ) { |
---|
[ae7a085c] | 187 | sout | wd(26, prng( prng )) | nonl; // cascading => side-effect functions called in arbitary order |
---|
| 188 | sout | wd(12, prng( prng, 5 )) | nonl; |
---|
| 189 | sout | wd(12, prng( prng, 0, 5 )); |
---|
[5910fc0] | 190 | } // for |
---|
| 191 | sout | sepEnable; |
---|
| 192 | sout | "seed" | get_seed( prng ); |
---|
| 193 | |
---|
| 194 | sout | nl | "Sequential"; |
---|
| 195 | STARTTIME; |
---|
| 196 | { |
---|
[8a2f7f1] | 197 | size_t * buckets = calloc( BUCKETS ); // too big for task stack |
---|
[5910fc0] | 198 | for ( TRIALS ) { |
---|
| 199 | buckets[prng( prng ) % BUCKETS] += 1; // sequential |
---|
| 200 | } // for |
---|
[8a2f7f1] | 201 | avgstd( TRIALS, buckets ); |
---|
[5910fc0] | 202 | free( buckets ); |
---|
| 203 | } |
---|
| 204 | ENDTIME(); |
---|
| 205 | |
---|
| 206 | sout | nl | "Concurrent"; |
---|
| 207 | STARTTIME; |
---|
| 208 | { |
---|
| 209 | processor p[TASKS - 1]; // already 1 processor |
---|
| 210 | { |
---|
| 211 | T2 t[TASKS]; |
---|
| 212 | } // wait for threads to complete |
---|
| 213 | } |
---|
| 214 | ENDTIME(); |
---|
| 215 | #endif // 0 |
---|
| 216 | #if 1 |
---|
| 217 | if ( seed != 0 ) set_seed( seed ); |
---|
| 218 | |
---|
| 219 | sout | sepDisable; |
---|
[ae7a085c] | 220 | sout | nl | wd(26, "prng()" ) | wd(12, "prng(5)") | wd(12, "prng(0,5)" ); |
---|
[5910fc0] | 221 | for ( 20 ) { |
---|
[ae7a085c] | 222 | sout | wd(26, prng()) | nonl; // cascading => side-effect functions called in arbitary order |
---|
| 223 | sout | wd(12, prng( 5 )) | nonl; |
---|
| 224 | sout | wd(12, prng( 0, 5 )); |
---|
[5910fc0] | 225 | } // for |
---|
| 226 | sout | sepEnable; |
---|
| 227 | sout | "seed" | get_seed( prng ); |
---|
| 228 | |
---|
| 229 | sout | nl | "Sequential"; |
---|
| 230 | STARTTIME; |
---|
| 231 | { |
---|
[8a2f7f1] | 232 | size_t * buckets = calloc( BUCKETS ); // too big for task stack |
---|
| 233 | for ( TRIALS / 5 ) { |
---|
[5910fc0] | 234 | buckets[prng() % BUCKETS] += 1; |
---|
| 235 | } // for |
---|
[8a2f7f1] | 236 | avgstd( TRIALS / 5, buckets ); |
---|
[5910fc0] | 237 | free( buckets ); |
---|
| 238 | } |
---|
[8a2f7f1] | 239 | ENDTIME( " x 5 " ); |
---|
[5910fc0] | 240 | |
---|
| 241 | sout | nl | "Concurrent"; |
---|
| 242 | STARTTIME; |
---|
| 243 | { |
---|
| 244 | processor p[TASKS - 1]; // already 1 processor |
---|
| 245 | { |
---|
| 246 | T3 t[TASKS]; |
---|
| 247 | } // wait for threads to complete |
---|
| 248 | } |
---|
[8a2f7f1] | 249 | ENDTIME( " x 5 " ); |
---|
[5910fc0] | 250 | #endif // 0 |
---|
| 251 | #if 1 |
---|
| 252 | if ( seed != 0 ) set_seed( seed ); |
---|
| 253 | thread$ & th = *active_thread(); |
---|
| 254 | |
---|
| 255 | sout | sepDisable; |
---|
[ae7a085c] | 256 | sout | nl | wd(26, "prng(t)" ) | wd(12, "prng(t,5)") | wd(12, "prng(t,0,5)" ); |
---|
[5910fc0] | 257 | for ( 20 ) { |
---|
[ae7a085c] | 258 | sout | wd(26, prng( th )) | nonl; // cascading => side-effect functions called in arbitary order |
---|
| 259 | sout | wd(12, prng( th, 5 )) | nonl; |
---|
| 260 | sout | wd(12, prng( th, 0, 5 )); |
---|
[5910fc0] | 261 | } // for |
---|
| 262 | sout | sepEnable; |
---|
| 263 | sout | "seed" | get_seed( prng ); |
---|
| 264 | |
---|
| 265 | sout | nl | "Sequential"; |
---|
| 266 | STARTTIME; |
---|
| 267 | { |
---|
| 268 | dummy( th ); |
---|
| 269 | } |
---|
| 270 | ENDTIME(); |
---|
| 271 | |
---|
| 272 | sout | nl | "Concurrent"; |
---|
| 273 | STARTTIME; |
---|
| 274 | { |
---|
| 275 | processor p[TASKS - 1]; // already 1 processor |
---|
| 276 | { |
---|
| 277 | T4 t[TASKS]; |
---|
| 278 | } // wait for threads to complete |
---|
| 279 | } |
---|
| 280 | ENDTIME(); |
---|
| 281 | #endif // 0 |
---|
| 282 | // malloc_stats(); |
---|
[ae7a085c] | 283 | // freelocale( loc ); |
---|
[5910fc0] | 284 | } // main |
---|
| 285 | |
---|
| 286 | |
---|
| 287 | // Local Variables: // |
---|
| 288 | // compile-command: "cfa -DTIME -O2 -nodebug PRNG.cfa" // |
---|
| 289 | // End: // |
---|