libzahl

big integer library
git clone git://git.suckless.org/libzahl
Log | Files | Refs | README | 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 }