benchmark-func.c - libzahl - big integer library
(HTM) git clone git://git.suckless.org/libzahl
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) README
(DIR) LICENSE
---
benchmark-func.c (9144B)
---
1 #include "util.h"
2
3 #include <limits.h>
4
5
6 #if !defined(USE_MEDIAN) && !defined(USE_MID_7TH_AVERAGE) && !defined(USE_AVERAGE) && !defined(USE_LOWEST)
7 # define USE_MID_7TH_AVERAGE
8 #endif
9
10
11 enum {
12 HIGH_ONLY,
13 HIGH_AND_LOW,
14 HALF,
15 FULL
16 };
17
18 struct function {
19 const char *name;
20 void (*f)(z_t *, z_t *, struct function *);
21 size_t a_start;
22 size_t a_end;
23 size_t a_step;
24 size_t b_start;
25 size_t b_end;
26 size_t b_step;
27 int a_mode;
28 int b_mode;
29 size_t runs;
30 size_t measurements;
31 };
32
33 #define M_MAX 200
34
35
36 static char buf[2000];
37 static z_t temp, temp2;
38 static unsigned long long int measurements[M_MAX];
39
40
41 #if defined(USE_MEDIAN) || defined(USE_MID_7TH_AVERAGE)
42 static int
43 measurementpcmp(const void *ap_, const void *bp_)
44 {
45 const unsigned long long int *ap = ap_, *bp = bp_;
46 return *ap < *bp ? -1 : *ap > *bp;
47 }
48 # if defined(USE_MEDIAN)
49 static unsigned long long int
50 gettime(size_t m)
51 {
52 qsort(measurements, m, sizeof(*measurements), measurementpcmp);
53 if (m & 1)
54 return measurements[m / 2];
55 return (measurements[m / 2] + measurements[m / 2 - 1]) / 2;
56 }
57 # else /* if defined(USE_MID_7TH_AVERAGE) */
58 static unsigned long long int
59 gettime(size_t m)
60 {
61 # define X 2 / 7
62 size_t i = m * X, n = m - m * X;
63 unsigned long long int tot = 0;
64 qsort(measurements, m, sizeof(*measurements), measurementpcmp);
65 for (; i < n; i++)
66 tot += measurements[i];
67 return tot / (n - m * X);
68 # undef X
69 }
70 # endif
71 #elif defined(USE_AVERAGE)
72 static unsigned long long int
73 gettime(size_t m)
74 {
75 unsigned long long int tot = 0;
76 size_t i = m;
77 while (i--)
78 tot += measurements[i];
79 return tot / m;
80 }
81 #else /* if defined(USE_LOWEST) */
82 static unsigned long long int
83 gettime(size_t m)
84 {
85 unsigned long long int best = ULLONG_MAX;
86 size_t i = m;
87 while (i--)
88 if (best > measurements[i])
89 best = measurements[i];
90 return best;
91 }
92 #endif
93
94
95 #define FUNCTION_1D(NAME, INSTRUCTION, PREINSTRUCTION)\
96 static void\
97 NAME(z_t *as, z_t* bs, struct function *f)\
98 {\
99 size_t i, j;\
100 PREINSTRUCTION;\
101 i = f->measurements;\
102 while (i--) {\
103 (void)INSTRUCTION;\
104 (void)INSTRUCTION;\
105 j = f->runs;\
106 TIC;\
107 while (j--) {\
108 (void)INSTRUCTION;\
109 }\
110 TOC;\
111 measurements[i] = TICKS;\
112 }\
113 printf("%llu\n", gettime(f->measurements));\
114 (void) as;\
115 (void) bs;\
116 }
117
118 #define FUNCTION_2D(NAME, INSTRUCTION, PREINSTRUCTION)\
119 static void\
120 NAME(z_t *as, z_t* bs, struct function *f)\
121 {\
122 size_t i, j, k, n = f->a_end - f->a_start + 1;\
123 z_t *a;\
124 zmul(temp, as[n - 1], as[n - 1]);\
125 zadd(temp, temp, temp);\
126 for (i = 0; i < n; i += f->a_step) {\
127 a = as + i;\
128 zset(temp2, *a);\
129 PREINSTRUCTION;\
130 k = f->measurements;\
131 while (k--) {\
132 (void)INSTRUCTION;\
133 (void)INSTRUCTION;\
134 j = f->runs;\
135 TIC;\
136 while (j--) {\
137 (void)INSTRUCTION;\
138 }\
139 TOC;\
140 measurements[k] = TICKS;\
141 }\
142 printf("%llu\n", gettime(f->measurements));\
143 a++;\
144 }\
145 (void) bs;\
146 }
147
148 #if defined(FINE_GRAINED)
149 # define FAST1D() 0, 0, 0, 0, 0, 0, 0, 0, 1000, M_MAX
150 # define FAST2D(P) 1, 4096, 1, 0, 0, 0, P, 0, 1000, M_MAX
151 # define SLOW2D(P) 1, 4096, 1, 0, 0, 0, P, 0, 10, 20
152 #else
153 # define FAST1D() 0, 0, 0, 0, 0, 0, 0, 0, 1000, M_MAX
154 # define FAST2D(P) 1, 4097, 64, 0, 0, 0, P, 0, 1000, M_MAX
155 # define SLOW2D(P) 1, 4097, 64, 0, 0, 0, P, 0, 10, 20
156 #endif
157
158 #define LIST_1D_FUNCTIONS\
159 X(pos_zseti, FAST1D(), zseti(temp, 1000000000LL),)\
160 X(zseti, FAST1D(), zseti(temp, -1000000000LL),)\
161 X(zsetu, FAST1D(), zsetu(temp, 1000000000ULL),)
162
163 #define LIST_2D_FUNCTIONS\
164 X(zset, FAST2D(FULL), zset(temp, *a),)\
165 X(zneg, FAST2D(FULL), zneg(temp, *a),)\
166 X(zabs, FAST2D(FULL), zabs(temp, *a),)\
167 X(self_zneg, FAST2D(FULL), zneg(*a, *a),)\
168 X(self_zabs, FAST2D(FULL), zabs(*a, *a),)\
169 X(zadd_unsigned, FAST2D(FULL), zadd_unsigned(temp, *a, temp2),)\
170 X(zsub_unsigned, FAST2D(FULL), zsub_unsigned(temp, *a, temp2),)\
171 X(zadd, FAST2D(FULL), zadd(temp, *a, temp2),)\
172 X(zsub, FAST2D(FULL), zsub(temp, *a, temp2),)\
173 X(zand, FAST2D(FULL), zand(temp, *a, temp2),)\
174 X(zor, FAST2D(FULL), zor(temp, *a, temp2),)\
175 X(zxor, FAST2D(FULL), zxor(temp, *a, temp2),)\
176 X(znot, FAST2D(FULL), znot(temp, *a),)\
177 X(zeven, FAST2D(FULL), zeven(*a),)\
178 X(zodd, FAST2D(FULL), zodd(*a),)\
179 X(zeven_nonzero, FAST2D(FULL), zeven_nonzero(*a),)\
180 X(zodd_nonzero, FAST2D(FULL), zodd_nonzero(*a),)\
181 X(zzero, FAST2D(FULL), zzero(*a),)\
182 X(zsignum, FAST2D(FULL), zsignum(*a),)\
183 X(zbits, FAST2D(FULL), zbits(*a),)\
184 X(zlsb, FAST2D(HIGH_ONLY), zlsb(*a),)\
185 X(zswap, FAST2D(FULL), zswap(temp, *a),)\
186 X(zcmpmag, FAST2D(FULL), zcmpmag(temp2, *a),)\
187 X(zcmp, FAST2D(FULL), zcmp(temp2, *a),)\
188 X(pos_zcmpi, FAST2D(FULL), zcmpi(*a, 1000000000LL),)\
189 X(zcmpi, FAST2D(FULL), zcmpi(*a, -1000000000LL),)\
190 X(zcmpu, FAST2D(FULL), zcmpu(*a, 1000000000ULL),)\
191 X(sqr_zmul, SLOW2D(FULL), zmul(temp, *a, temp2),)\
192 X(zsqr, SLOW2D(FULL), zsqr(temp, *a),)\
193 X(zstr_length, SLOW2D(FULL), zstr_length(*a, 10),)\
194 X(zstr, SLOW2D(FULL), zstr(*a, buf, sizeof(buf) - 1),)\
195 X(auto_zstr, SLOW2D(FULL), zstr(*a, buf, 0),)\
196 X(zsave, FAST2D(FULL), zsave(*a, buf),)\
197 X(zload, FAST2D(FULL), zload(temp, buf), zsave(*a, buf))\
198 X(zbset_set, FAST2D(FULL), zbset(temp, *a, 2, 1),)\
199 X(zbset_clear, FAST2D(FULL), zbset(temp, *a, 2, 0),)\
200 X(zbset_flip, FAST2D(FULL), zbset(temp, *a, 2, -1),)\
201 X(self_zbset_set, FAST2D(FULL), zbset(temp2, temp2, 2, 1),)\
202 X(self_zbset_clear, FAST2D(FULL), zbset(temp2, temp2, 2, 0),)\
203 X(self_zbset_flip, FAST2D(FULL), zbset(temp2, temp2, 2, -1),)\
204 X(zbtest, FAST2D(FULL), zbtest(*a, 2),)\
205 X(zptest, FAST2D(FULL), zptest(temp, *a, 5),)\
206 X(zsets, FAST2D(FULL), zsets(temp, buf), zstr(*a, buf, sizeof(buf) - 1))\
207 X(zlsh, FAST2D(FULL), zlsh(temp, *a, 1),)\
208 X(zrsh, FAST2D(FULL), zrsh(temp, *a, 1),)\
209 X(ztrunc, FAST2D(FULL), ztrunc(temp, *a, i / 2),)\
210 X(self_ztrunc, FAST2D(FULL), ztrunc(*a, *a, i),)\
211 X(zsplit, FAST2D(FULL), zsplit(temp, temp2, *a, i / 2),)
212
213 /* TODO
214 zgcd
215 zpow
216 zpowu
217 zmodpow
218 zmodpowu
219 zrand
220 zdiv
221 zmod
222 zdivmod
223 zmul
224 zmodmul
225 sqr_zmodmul
226 zmodsqr
227 zdiv
228 zmod
229 zdivmod
230 */
231
232 #define X(FN, A, F1, F2) FUNCTION_1D(bench_##FN, F1, F2)
233 LIST_1D_FUNCTIONS
234 #undef X
235 #define X(FN, A, F1, F2) FUNCTION_2D(bench_##FN, F1, F2)
236 LIST_2D_FUNCTIONS
237 #undef X
238
239 struct function functions[] = {
240 #define X(FN, A, F1, F2) {#FN, bench_##FN, A},
241 LIST_1D_FUNCTIONS
242 LIST_2D_FUNCTIONS
243 #undef X
244 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
245 };
246
247
248 static z_t *
249 create_ints(size_t start, size_t end, int mode)
250 {
251 z_t *array = malloc((++end - start) * sizeof(z_t));
252 z_t *rc = array;
253 ssize_t n;
254 for (; start < end; start++, array++) {
255 zinit(*array);
256 switch (mode) {
257 case HIGH_ONLY:
258 zsetu(temp, 1);
259 zlsh(*array, temp, start - 1);
260 break;
261 case HIGH_AND_LOW:
262 zsetu(temp, 1);
263 zlsh(*array, temp, start - 1);
264 if (start > 1)
265 zadd(*array, *array, temp);
266 break;
267 case HALF:
268 n = (ssize_t)start;
269 zsetu(temp, 1 << (~start & 1));
270 zsetu(*array, 0);
271 for (; n > 0; n -= 2) {
272 zlsh(*array, *array, 2);
273 zadd(*array, *array, temp);
274 }
275 break;
276 case FULL:
277 zsetu(temp, 1);
278 zlsh(*array, temp, start);
279 zsub(*array, *array, temp);
280 break;
281 default:
282 abort();
283 }
284 }
285 return rc;
286 }
287
288 static void
289 destroy_ints(z_t *array, size_t start, size_t end)
290 {
291 z_t *array_ = array;
292 for (; start <= end; start++)
293 zfree(*array++);
294 free(array_);
295 }
296
297 int
298 main(int argc, char *argv[])
299 {
300 static struct function *fs = functions;
301 static z_t *as = 0, *bs = 0;
302 jmp_buf jmp;
303
304 if (argc != 2) {
305 fprintf(stderr, "usage: %s function\n", *argv);
306 return 2;
307 }
308
309 benchmark_init();
310
311 if (setjmp(jmp)) {
312 zperror(argv[0]);
313 return 1;
314 }
315 zsetup(jmp);
316 printf("%s%s\n", BIGINT_LIBRARY, LIBRARY_SUFFIX);
317 zinit(temp);
318 zinit(temp2);
319
320 for (; fs->name && strcmp(fs->name, argv[1]); fs++);
321 if (!fs->name) {
322 fprintf(stderr, "%s: function not recognised: %s\n", *argv, argv[1]);
323 return 2;
324 }
325
326 if (fs->b_end) {
327 as = create_ints(fs->a_start, fs->a_end, fs->a_mode);
328 bs = create_ints(fs->b_start, fs->b_end, fs->b_mode);
329 printf("3\n%zu %zu %zu\n%zu %zu %zu\n",
330 fs->a_start, fs->a_end, fs->a_step,
331 fs->b_start, fs->b_end, fs->b_step);
332 } else if (fs->a_end) {
333 as = create_ints(fs->a_start, fs->a_end, fs->a_mode);
334 printf("2\n%zu %zu %zu\n", fs->a_start, fs->a_end, fs->a_step);
335 } else {
336 printf("1\n");
337 }
338 fs->f(as, bs, fs);
339
340 if (as)
341 destroy_ints(as, fs->a_start, fs->a_end);
342 if (bs)
343 destroy_ints(bs, fs->b_start, fs->b_end);
344
345 zfree(temp);
346 zfree(temp2);
347 zunsetup();
348 return 0;
349 }