inital commitHEADmaster

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
+
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 <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;
+}
+
diff --git a/rdtsc.S b/rdtsc.S
new file mode 100644
index 0000000..fcac04d
--- /dev/null
+++ b/rdtsc.S
@@ -0,0 +1,13 @@
+global rdtsc
+
+section .text
+rdtsc:
+	mfence
+	lfence
+	rdtsc
+	lfence
+	shl rdx, 32
+	mov edx, eax
+	mov rax, rdx
+	ret
+