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 }