1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
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;
}
|
