commit 1436ee4e42cc0d327a92f5fd25552f6f6d14d686
parent a7bb3bc812f7dffc67a448be3fe6538bddaaf6c1
Author: NunoSempere <nuno.sempere@protonmail.com>
Date: Sat, 3 Jun 2023 10:50:06 -0600
compare using a struct instead of a pointer, reorg
Diffstat:
11 files changed, 106 insertions(+), 42 deletions(-)
diff --git a/C/README.md b/C/README.md
@@ -12,7 +12,7 @@ This repository contains a few implementations of a simple botec (back-of-the-en
- [ ] Add CUDA?
- [x] Added results of perf. `rand_r` seems like a big chunk of it, but I'm hesitant to use lower-quality random numbers
- [x] used xorshift instead
- - [ ] Use xorshift with a struct instead of a pointer? idk, could be faster for some reason?
+ - [-] Use xorshift with a struct instead of a pointer? idk, could be faster for some reason? => Tested, it takes the same time.
- [x] Update repository with correct timing
- [x] Use better profiling approach to capture timing with 1M samples.
- [x] See if program can be reworded so as to use multithreading effectively, e.g., so that you see speed gains proportional to the number of threads used
diff --git a/C/samples.c b/C/samples.c
@@ -84,6 +84,8 @@ uint32_t xorshift32(uint32_t* seed)
// Algorithm "xor" from p. 4 of Marsaglia, "Xorshift RNGs"
// See <https://stackoverflow.com/questions/53886131/how-does-xorshift32-works>
// https://en.wikipedia.org/wiki/Xorshift
+ // Also some drama: <https://www.pcg-random.org/posts/on-vignas-pcg-critique.html>, <https://prng.di.unimi.it/>
+
uint32_t x = *seed;
x ^= x << 13;
x ^= x >> 17;
diff --git a/C/scratchpad/makefile b/C/scratchpad/makefile
@@ -1,2 +0,0 @@
-build:
- gcc xorshift.c -o xorshift
diff --git a/C/scratchpad/xorshift b/C/scratchpad/xorshift
Binary files differ.
diff --git a/C/scratchpad/xorshift.c b/C/scratchpad/xorshift.c
@@ -1,39 +0,0 @@
-#include <stdint.h>
-#include <stdio.h>
-#include <stdlib.h>
-
-uint32_t xorshift32(uint32_t* state)
-{
- /* Algorithm "xor" from p. 4 of Marsaglia, "Xorshift RNGs" */
- uint32_t x = *state;
- x ^= x << 13;
- x ^= x >> 17;
- x ^= x << 5;
- return *state = x;
-}
-
-float rand_xorshift32(uint32_t* state){
- return (float) xorshift32(state) / (float) UINT32_MAX;
-}
-
-int main(){
- uint32_t** states = malloc(4 * sizeof(uint32_t*));
- for(int i=0; i<4;i++){
- states[i] = malloc(sizeof(uint32_t));
- *states[i] = i + 1;
- }
-
- for(int i=0; i<100; i++){
- printf("%u\n", xorshift32(states[0]));
- printf("%f\n", rand_xorshift32(states[1]));
- }
- for(int i=0; i<4;i++){
- free(states[i]);
- }
- free(states);
-
- return 0;
-}
-
-// See <https://stackoverflow.com/questions/53886131/how-does-xorshift32-works>
-// https://en.wikipedia.org/wiki/Xorshift
diff --git a/C/xorshift-scratchpad/makefile b/C/xorshift-scratchpad/makefile
@@ -0,0 +1,15 @@
+build:
+ gcc xorshift-pointer.c -o out/xorshift-pointer
+ gcc xorshift-struct.c -o out/xorshift-struct
+
+run-pointer:
+ ./out/xorshift-pointer
+
+run-struct:
+ ./out/xorshift-struct
+
+time-pointer:
+ /bin/time -f "Time: %es" ./out/xorshift-pointer && echo
+
+time-struct:
+ /bin/time -f "Time: %es" ./out/xorshift-struct && echo
diff --git a/C/xorshift-scratchpad/notes.md b/C/xorshift-scratchpad/notes.md
@@ -0,0 +1 @@
+Using a pointer or a struct turns out to be pretty equivalent in terms of speed. I don't think there are gains to be found here, but I find the pointer implementation clearer.
diff --git a/C/xorshift-scratchpad/out/xorshift-pointer b/C/xorshift-scratchpad/out/xorshift-pointer
Binary files differ.
diff --git a/C/xorshift-scratchpad/out/xorshift-struct b/C/xorshift-scratchpad/out/xorshift-struct
Binary files differ.
diff --git a/C/xorshift-scratchpad/xorshift-pointer.c b/C/xorshift-scratchpad/xorshift-pointer.c
@@ -0,0 +1,41 @@
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+uint32_t xorshift32(uint32_t* state)
+{
+ /* Algorithm "xor" from p. 4 of Marsaglia, "Xorshift RNGs" */
+ uint32_t x = *state;
+ x ^= x << 13;
+ x ^= x >> 17;
+ x ^= x << 5;
+ return *state = x;
+}
+
+float rand_xorshift32(uint32_t* state){
+ return (float) xorshift32(state) / (float) UINT32_MAX;
+}
+
+int main(){
+ uint32_t** states = malloc(4 * sizeof(uint32_t*));
+ for(int i=0; i<4;i++){
+ states[i] = malloc(sizeof(uint32_t));
+ *states[i] = (uint32_t) i + 1;
+ }
+ for(int i=0; i<1000000000;i++){
+ uint32_t x = xorshift32(states[0]);
+ float y = rand_xorshift32(states[1]);
+ // printf("%u\n", x);
+ // printf("%f\n", y);
+ }
+
+ for(int i=0; i<4;i++){
+ free(states[i]);
+ }
+ free(states);
+
+ return 0;
+}
+
+// See <https://stackoverflow.com/questions/53886131/how-does-xorshift32-works>
+// https://en.wikipedia.org/wiki/Xorshift
diff --git a/C/xorshift-scratchpad/xorshift-struct.c b/C/xorshift-scratchpad/xorshift-struct.c
@@ -0,0 +1,46 @@
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+struct xorshift32_state {
+ uint32_t a;
+};
+
+uint32_t xorshift32(struct xorshift32_state *state)
+{
+ /* Algorithm "xor" from p. 4 of Marsaglia, "Xorshift RNGs" */
+ uint32_t x = state->a;
+ x ^= x << 13;
+ x ^= x >> 17;
+ x ^= x << 5;
+ return state->a = x;
+}
+
+float rand_xorshift32(struct xorshift32_state *state){
+ return (float) xorshift32(state) / (float) UINT32_MAX;
+}
+
+
+int main(){
+ struct xorshift32_state** states = malloc(sizeof(struct xorshift32_state*) * 4);
+ for(int i=0; i<4;i++){
+ states[i] = malloc(sizeof(struct xorshift32_state));
+ states[i]->a = (uint32_t) i + 1;
+ }
+
+ for(int i=0; i<1000000000; i++){
+ uint32_t x = xorshift32(states[0]);
+ float y = rand_xorshift32(states[1]);
+ // printf("%u\n", x);
+ // printf("%f\n", y);
+ }
+
+ for(int i=0; i<4;i++){
+ free(states[i]);
+ }
+ free(states);
+
+
+ return 0;
+}
+
