From 60f60fa1a9b40863cf325cca1447ec36d6108701 Mon Sep 17 00:00:00 2001 From: rebeccadoth Date: Sun, 8 Nov 2026 21:48:41 +0100 Subject: inital commit --- main.c | 239 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 239 insertions(+) create mode 100644 main.c (limited to 'main.c') diff --git a/main.c b/main.c new file mode 100644 index 0000000..a52e77c --- /dev/null +++ b/main.c @@ -0,0 +1,239 @@ +#include + +int max1(int* ints, size_t size) +{ + if (size <= 0) return 0; + if (size == 1) return ints[0]; + + int max = ints[0]; + for (size_t i = 1; i < size; i++) + { + max = max > ints[i] ? max : ints[i]; + } + + return max; +} + +int max2(int input[], size_t length) +{ + if(length < 4) return 0; + + int m1 = input[0]; + int m2 = input[0]; + int m3 = input[0]; + int m4 = input[0]; + length /= 4; + while(length--) + { + if(m1 < input[0]) m1 = input[0]; + if(m2 < input[1]) m2 = input[1]; + if(m3 < input[2]) m3 = input[2]; + if(m4 < input[3]) m4 = input[3]; + + input += 4; + } + int _max1 = m1 < m2 ? m2 : m1; + int _max2 = m3 < m4 ? m4 : m3; + return _max1 < _max2 ? _max2 : _max1; +} + +int max3(int input[], size_t length) +{ + if(length < 4) return 0; + + int m1 = input[0]; + int m2 = input[0]; + int m3 = input[0]; + int m4 = input[0]; + length /= 4; + for(size_t i = 0; i < length; i++) + { + if(m1 < input[0]) m1 = input[0]; + if(m2 < input[1]) m2 = input[1]; + if(m3 < input[2]) m3 = input[2]; + if(m4 < input[3]) m4 = input[3]; + + input += 4; + } + int _max1 = m1 < m2 ? m2 : m1; + int _max2 = m3 < m4 ? m4 : m3; + return _max1 < _max2 ? _max2 : _max1; +} + +int max4(int input[], size_t length) +{ + + if(length < 4) return 0; + size_t olength = length; + + int m1 = input[0]; + int m2 = input[0]; + int m3 = input[0]; + int m4 = input[0]; + length /= 4; + while(length--) + { + if(m1 < input[0]) m1 = input[0]; + if(m2 < input[1]) m2 = input[1]; + if(m3 < input[2]) m3 = input[2]; + if(m4 < input[3]) m4 = input[3]; + + input += 4; + } + int _max1 = m1 < m2 ? m2 : m1; + int _max2 = m3 < m4 ? m4 : m3; + int _max3 = _max1 < _max2 ? _max2 : _max1; + + olength %= 4; + while(olength--) + { + if(_max3 < input[0]) + _max3 = input[0]; + ++input; + } + + return _max3; +} + +// testing stuff below + +#include +#include +#include +#include + +#define SIZE 10000003 +#define TIMES 100 + +/* +#define INITPERF()\ +unsigned int seed = time(NULL);\ +printf("\nseed: %u, %u ints, ran %u times, shortest run time taken\n\n", seed, SIZE, TIMES);\ +srand(seed);\ +int* testarray = calloc(SIZE, sizeof(int));\ +assert(testarray != NULL);\ +unsigned long long start;\ +unsigned long long end;\ +unsigned long long* times = calloc(TIMES, sizeof(unsigned long long)) + +#define PERF(F, NAME)\ +printf("%s: ", NAME);fflush(stdout);\ +for(size_t i=0;i input[0]) m1 = input[0]; + if(m2 > input[1]) m2 = input[1]; + if(m3 > input[2]) m3 = input[2]; + if(m4 > input[3]) m4 = input[3]; + + input += 4; + } + unsigned long long _max1 = m1 < m2 ? m1 : m2; + unsigned long long _max2 = m3 < m4 ? m3 : m4; + return _max1 < _max2 ? _max1 : _max2; +} + +unsigned long long findmaxllu(unsigned long long input[], size_t length) +{ + if(length < 4) return 0; + + unsigned long long m1 = input[0]; + unsigned long long m2 = input[0]; + unsigned long long m3 = input[0]; + unsigned long long m4 = input[0]; + length /= 4; + while(--length) + { + if(m1 < input[0]) m1 = input[0]; + if(m2 < input[1]) m2 = input[1]; + if(m3 < input[2]) m3 = input[2]; + if(m4 < input[3]) m4 = input[3]; + + input += 4; + } + unsigned long long _max1 = m1 < m2 ? m2 : m1; + unsigned long long _max2 = m3 < m4 ? m4 : m3; + return _max1 < _max2 ? _max2 : _max1; +} + +int* testarray; +unsigned long long* times; + +void perf(int (*func)(int[], size_t), char name[]) +{ + printf("%s: ", name); + fflush(stdout); + + for(size_t i = 0; i < SIZE; i++) testarray[i]=rand(); + size_t j; + unsigned long long start, end; + for(j = 0; j < TIMES; j++) + { + repeat: + + start = rdtsc(); // TODO: use rdtscp? + [[maybe_unused]] volatile int _ = func(testarray, SIZE); // volatile unused read so at -O3 the function call doesn't get wished away + end = rdtsc(); + + if(end <= start) goto repeat; // process probably moved cores? idk + // this is the actual cause of the bug that results in random gigantic numbers + // ACTUAL fix TODO: set thread affinity, since otherwise it cannot be guaranteed that 2 separate rdtsc instructions run on the same core and read the same tsc + times[j]=(end - start); + + //printf("%llu: %llu to %llu : %llu\n", j, start, end, times[j]); + } + printf("min: %llu clock cycles, max: %llu clock cycles\n", findminllu(times, TIMES), findmaxllu(times, TIMES)); +} + +int main() +{ + time_t seed = time(NULL); + printf("\nseed: %lld, %u ints, ran %u times, shortest run time taken\n\n", (long long)seed, SIZE, TIMES); + srand((unsigned)seed); + + testarray = calloc(SIZE, sizeof(int)); + assert(testarray != NULL); + + times = calloc(TIMES, sizeof(unsigned long long)); + assert(times != NULL); + + perf(max1, "max1"); + perf(max2, "max2"); + perf(max3, "max3"); + perf(max4, "max4"); + + // sanity check + for(size_t i=0;i