diff options
| -rw-r--r-- | .gitignore | 6 | ||||
| -rw-r--r-- | Makefile | 47 | ||||
| -rw-r--r-- | main.c | 239 | ||||
| -rw-r--r-- | rdtsc.S | 13 |
4 files changed, 305 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..d6f6423 --- /dev/null +++ b/.gitignore @@ -0,0 +1,6 @@ +max +*.pdb +*.rdi +*.obj +*.exe +.rad-*
\ No newline at end of file diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..450732b --- /dev/null +++ b/Makefile @@ -0,0 +1,47 @@ +CC := clang +WRN := -Wall -Wextra -Wconversion -Wvla -Wformat +ASM := rdtsc +INF := main.c $(ASM).obj +OUT := max +LNK := -lm +DBG := -g -gcodeview -gcolumn-info -fuse-ld=lld -g -Wl,--pdb=$(OUT).pdb + +default: asm com + +com: + $(CC) $(WRN) $(LNK) $(INF) $(DBG) -O0 -o $(OUT) + +asm: + nasm -w+all -f win64 $(ASM).S + +rdi: + $(RAD)/radbin --rdi $(OUT).pdb + +o1: asm + $(CC) $(WRN) $(LNK) $(INF) $(DBG) -o $(OUT) -O1 +o2: asm + $(CC) $(WRN) $(LNK) $(INF) $(DBG) -o $(OUT) -O2 +o3: asm + $(CC) $(WRN) $(LNK) $(INF) $(DBG) -o $(OUT) -O3 +os: asm + $(CC) $(WRN) $(LNK) $(INF) $(DBG) -o $(OUT) -Os +ofast: asm + $(CC) $(WRN) $(LNK) $(INF) $(DBG) -o $(OUT) -Ofast + +test: + make default > /dev/null + ./$(OUT) + make o1 > /dev/null + ./$(OUT) + make o2 > /dev/null + ./$(OUT) + make o3 > /dev/null + ./$(OUT) + make os > /dev/null + ./$(OUT) + make ofast > /dev/null + ./$(OUT) + +clean: + rm -f $(OUT) $(OUT).exe $(OUT).pdb $(OUT).rdi $(ASM).o $(ASM).obj + @@ -0,0 +1,239 @@ +#include <stdlib.h> + +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 <stdio.h> +#include <time.h> +#include <assert.h> +#include <math.h> + +#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<SIZE;i++)testarray[i]=rand();\ +for(size_t j=0;j<TIMES;j++){\ +start=rdtsc();\ +F(testarray,SIZE);\ +end=rdtsc();\ +times[j]=(end - start);}\ +printf("min: %llu clock cycles, max: %llu clock cycles\n", findminllu(times, TIMES), findmaxllu(times, TIMES)) +*/ + +extern unsigned long long rdtsc(); + +unsigned long long findminllu(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 ? 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<SIZE;++i) testarray[i]=rand(); + int m1 = max1(testarray, SIZE); + int m2 = max2(testarray, SIZE); + int m3 = max3(testarray, SIZE); + int m4 = max4(testarray, SIZE); + + free(times); + free(testarray); + assert(m1 == m4); + assert(m1 == m2); + assert(m1 == m3); + + return 0; +} + @@ -0,0 +1,13 @@ +global rdtsc + +section .text +rdtsc: + mfence + lfence + rdtsc + lfence + shl rdx, 32 + mov edx, eax + mov rax, rdx + ret + |