[fio.git] / t / genzipf.c

/*
 * Generate/analyze pareto/zipf distributions to better understand
 * what an access pattern would look like.
 *
 * For instance, the following would generate a zipf distribution
 * with theta 1.2, using 262144 (1 GB / 4096) values and split the reporting into
 * 20 buckets:
 *
 *	./t/fio-genzipf -t zipf -i 1.2 -g 1 -b 4096 -o 20
 *
 * Only the distribution type (zipf or pareto) and spread input need
 * to be given, if not given defaults are used.
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <string.h>
#include <unistd.h>

#include "../lib/zipf.h"
#include "../flist.h"
#include "../hash.h"

#define DEF_NR_OUTPUT	20

struct node {
	struct flist_head list;
	unsigned long long val;
	unsigned long hits;
};

static struct flist_head *hash;
static unsigned long hash_bits = 24;
static unsigned long hash_size = 1 << 24;

enum {
	TYPE_NONE = 0,
	TYPE_ZIPF,
	TYPE_PARETO,
};
static const char *dist_types[] = { "None", "Zipf", "Pareto" };

static int dist_type = TYPE_ZIPF;
static unsigned long gb_size = 500;
static unsigned long block_size = 4096;
static unsigned long output_nranges = DEF_NR_OUTPUT;
static double percentage;
static double dist_val;
static int output_csv = 0;

#define DEF_ZIPF_VAL	1.2
#define DEF_PARETO_VAL	0.3

static struct node *hash_lookup(unsigned long long val)
{
	struct flist_head *l = &hash[hash_long(val, hash_bits)];
	struct flist_head *entry;
	struct node *n;

	flist_for_each(entry, l) {
		n = flist_entry(entry, struct node, list);
		if (n->val == val)
			return n;
	}

	return NULL;
}

static struct node *hash_insert(struct node *n, unsigned long long val)
{
	struct flist_head *l = &hash[hash_long(val, hash_bits)];

	n->val = val;
	n->hits = 1;
	flist_add_tail(&n->list, l);
	return n;
}

static void usage(void)
{
	printf("genzipf: test zipf/pareto values for fio input\n");
	printf("\t-h\tThis help screen\n");
	printf("\t-p\tGenerate size of data set that are hit by this percentage\n");
	printf("\t-t\tDistribution type (zipf or pareto)\n");
	printf("\t-i\tDistribution algorithm input (zipf theta or pareto power)\n");
	printf("\t-b\tBlock size of a given range (in bytes)\n");
	printf("\t-g\tSize of data set (in gigabytes)\n");
	printf("\t-o\tNumber of output rows\n");
	printf("\t-c\tOutput ranges in CSV format\n");
}

static int parse_options(int argc, char *argv[])
{
	const char *optstring = "t:g:i:o:b:p:ch";
	int c, dist_val_set = 0;

	while ((c = getopt(argc, argv, optstring)) != -1) {
		switch (c) {
		case 'h':
			usage();
			return 1;
		case 'p':
			percentage = atof(optarg);
			break;
		case 'b':
			block_size = strtoul(optarg, NULL, 10);
			break;
		case 't':
			if (!strncmp(optarg, "zipf", 4))
				dist_type = TYPE_ZIPF;
			else if (!strncmp(optarg, "pareto", 6))
				dist_type = TYPE_PARETO;
			else {
				printf("wrong dist type: %s\n", optarg);
				return 1;
			}
			break;
		case 'g':
			gb_size = strtoul(optarg, NULL, 10);
			break;
		case 'i':
			dist_val = atof(optarg);
			dist_val_set = 1;
			break;
		case 'o':
			output_nranges = strtoul(optarg, NULL, 10);
			break;
		case 'c':
			output_csv = 1;
			break;
		default:
			printf("bad option %c\n", c);
			return 1;
		}
	}

	if (dist_type == TYPE_PARETO) {
		if ((dist_val >= 1.00 || dist_val < 0.00)) {
			printf("pareto input must be > 0.00 and < 1.00\n");
			return 1;
		}
		if (!dist_val_set)
			dist_val = DEF_PARETO_VAL;
	} else if (dist_type == TYPE_ZIPF) {
		if (dist_val == 1.0) {
			printf("zipf input must be different than 1.0\n");
			return 1;
		}
		if (!dist_val_set)
			dist_val = DEF_ZIPF_VAL;
	}

	return 0;
}

struct output_sum {
	double output;
	unsigned int nranges;
};

static int node_cmp(const void *p1, const void *p2)
{
	const struct node *n1 = p1;
	const struct node *n2 = p2;

	return n2->hits - n1->hits;
}

int main(int argc, char *argv[])
{
	unsigned long offset;
	unsigned long i, j, k, nr_vals, cur_vals, interval_step, next_interval, total_vals, nnodes;
	unsigned long long nranges;
	struct output_sum *output_sums;
	struct node *nodes;
	double perc, perc_i;
	struct zipf_state zs;

	if (parse_options(argc, argv))
		return 1;

	if( !output_csv )
		printf("Generating %s distribution with %f input and %lu GB size and %lu block_size.\n", dist_types[dist_type], dist_val, gb_size, block_size);

	nranges = gb_size * 1024 * 1024 * 1024ULL;
	nranges /= block_size;

	if (dist_type == TYPE_ZIPF)
		zipf_init(&zs, nranges, dist_val, 1);
	else
		pareto_init(&zs, nranges, dist_val, 1);

	hash_bits = 0;
	hash_size = nranges;
	while ((hash_size >>= 1) != 0)
		hash_bits++;

	hash_size = 1 << hash_bits;

	hash = malloc(hash_size * sizeof(struct flist_head));
	for (i = 0; i < hash_size; i++)
		INIT_FLIST_HEAD(&hash[i]);

	nodes = malloc(nranges * sizeof(struct node));

	for (i = j = 0; i < nranges; i++) {
		struct node *n;

		if (dist_type == TYPE_ZIPF)
			offset = zipf_next(&zs);
		else
			offset = pareto_next(&zs);

		n = hash_lookup(offset);
		if (n)
			n->hits++;
		else {
			hash_insert(&nodes[j], offset);
			j++;
		}

	}

	qsort(nodes, j, sizeof(struct node), node_cmp);
	nnodes = j;
	nr_vals = nnodes;

	if (output_csv) {
		printf("rank, count\n");
		for (k = 0; k < nnodes; k++) {
			printf("%lu, %lu\n", k, nodes[k].hits);
		}
	} else {
		unsigned long blocks = percentage * nranges / 100;
		double hit_percent_sum = 0;
		unsigned long long hit_sum = 0;
		interval_step = (nr_vals - 1) / output_nranges + 1;
		next_interval = interval_step;
		output_sums = malloc(output_nranges * sizeof(struct output_sum));
		for (i = 0; i < output_nranges; i++) {
			output_sums[i].output = 0.0;
			output_sums[i].nranges = 0;
		}

		j = total_vals = cur_vals = 0;

		for (k = 0; k < nnodes; k++) {
			struct output_sum *os = &output_sums[j];
			struct node *node = &nodes[k];
			cur_vals += node->hits;
			total_vals += node->hits;
			os->nranges += node->hits;
			if (k == (next_interval)  -1 || k == (nnodes - 1)) {
				os->output = (double)(cur_vals) / (double)nranges;
				os->output *= 100.0;
				cur_vals = 0;
				next_interval += interval_step;
				j++;
			}

			if (percentage) {
				if (total_vals >= blocks) {
					double cs = k * block_size / (1024 * 1024);
					char p = 'M';

					if (cs > 1024.0) {
						cs /= 1024.0;
						p = 'G';
					}
					if (cs > 1024.0) {
						cs /= 1024.0;
						p = 'T';
					}

					printf("%.2f%% of hits satisfied in %.3f%cB of cache\n", percentage, cs, p);
					percentage = 0.0;
				}
			}
		}

		perc_i = 100.0 / (double)output_nranges;
		perc = 0.0;

		printf("\n   Rows           Hits %%         No Hits         Size\n");
		printf("--------------------------------------------------------\n");
		for (i = 0; i < output_nranges; i++) {
			struct output_sum *os = &output_sums[i];
			double gb = (double)os->nranges * block_size / 1024.0;
			char p = 'K';

			if (gb > 1024.0) {
				p = 'M';
				gb /= 1024.0;
			}
			if (gb > 1024.0) {
				p = 'G';
				gb /= 1024.0;
			}

			perc += perc_i;
			hit_percent_sum += os->output;
			hit_sum += os->nranges;
			printf("%s %6.2f%%\t%6.2f%%\t\t%8u\t%6.2f%c\n",
			       i ? "|->" : "Top", perc, os->output, os->nranges,
			       gb, p);
		}
		printf("--------------------------------------------------------\n");
		printf("Total\t\t%6.2f%%\t\t%8llu\n", hit_percent_sum, hit_sum);
		free(output_sums);
	}

	free(hash);
	free(nodes);
	return 0;
}
Commit	Line	Data
6ff38856 JA	1	/*
	2	* Generate/analyze pareto/zipf distributions to better understand
	3	* what an access pattern would look like.
	4	*
	5	* For instance, the following would generate a zipf distribution
2c9b3ccd	6	* with theta 1.2, using 262144 (1 GB / 4096) values and split the reporting into
6ff38856 JA	7	* 20 buckets:
6ff38856 JA	8	*
2c9b3ccd	9	* ./t/fio-genzipf -t zipf -i 1.2 -g 1 -b 4096 -o 20
6ff38856	10	*
f880b1f6 JA	11	* Only the distribution type (zipf or pareto) and spread input need
	12	* to be given, if not given defaults are used.
	13	*
6ff38856 JA	14	*/
	15	#include <stdio.h>
	16	#include <stdlib.h>
	17	#include <fcntl.h>
	18	#include <string.h>
921d17ba	19	#include <unistd.h>
6ff38856 JA	20
6ff38856 JA	21	#include "../lib/zipf.h"
fd6f237d JA	22	#include "../flist.h"
fd6f237d JA	23	#include "../hash.h"
6ff38856	24
2c9b3ccd	25	#define DEF_NR_OUTPUT 20
f880b1f6	26
fd6f237d JA	27	struct node {
fd6f237d JA	28	struct flist_head list;
fd6f237d JA	29	unsigned long long val;
	30	unsigned long hits;
	31	};
	32
	33	static struct flist_head *hash;
	34	static unsigned long hash_bits = 24;
	35	static unsigned long hash_size = 1 << 24;
fd6f237d	36
921d17ba JA	37	enum {
	38	TYPE_NONE = 0,
	39	TYPE_ZIPF,
	40	TYPE_PARETO,
	41	};
	42	static const char *dist_types[] = { "None", "Zipf", "Pareto" };
	43
	44	static int dist_type = TYPE_ZIPF;
	45	static unsigned long gb_size = 500;
444256ea	46	static unsigned long block_size = 4096;
921d17ba	47	static unsigned long output_nranges = DEF_NR_OUTPUT;
444256ea	48	static double percentage;
921d17ba	49	static double dist_val;
355934b7	50	static int output_csv = 0;
921d17ba JA	51
	52	#define DEF_ZIPF_VAL 1.2
	53	#define DEF_PARETO_VAL 0.3
	54
fd6f237d JA	55	static struct node *hash_lookup(unsigned long long val)
	56	{
	57	struct flist_head *l = &hash[hash_long(val, hash_bits)];
	58	struct flist_head *entry;
	59	struct node *n;
	60
	61	flist_for_each(entry, l) {
	62	n = flist_entry(entry, struct node, list);
	63	if (n->val == val)
	64	return n;
	65	}
	66
	67	return NULL;
	68	}
	69
24baa4c7	70	static struct node hash_insert(struct node n, unsigned long long val)
fd6f237d JA	71	{
fd6f237d JA	72	struct flist_head *l = &hash[hash_long(val, hash_bits)];
fd6f237d JA	73
	74	n->val = val;
	75	n->hits = 1;
	76	flist_add_tail(&n->list, l);
24baa4c7	77	return n;
6ff38856 JA	78	}
6ff38856 JA	79
4e98a450 JA	80	static void usage(void)
	81	{
	82	printf("genzipf: test zipf/pareto values for fio input\n");
	83	printf("\t-h\tThis help screen\n");
	84	printf("\t-p\tGenerate size of data set that are hit by this percentage\n");
	85	printf("\t-t\tDistribution type (zipf or pareto)\n");
	86	printf("\t-i\tDistribution algorithm input (zipf theta or pareto power)\n");
	87	printf("\t-b\tBlock size of a given range (in bytes)\n");
	88	printf("\t-g\tSize of data set (in gigabytes)\n");
2c9b3ccd	89	printf("\t-o\tNumber of output rows\n");
4e98a450 JA	90	printf("\t-c\tOutput ranges in CSV format\n");
	91	}
	92
921d17ba JA	93	static int parse_options(int argc, char *argv[])
921d17ba JA	94	{
4e98a450	95	const char *optstring = "t:g:i:o:b:p:ch";
921d17ba JA	96	int c, dist_val_set = 0;
	97
	98	while ((c = getopt(argc, argv, optstring)) != -1) {
	99	switch (c) {
4e98a450 JA	100	case 'h':
	101	usage();
	102	return 1;
444256ea JA	103	case 'p':
	104	percentage = atof(optarg);
	105	break;
	106	case 'b':
	107	block_size = strtoul(optarg, NULL, 10);
	108	break;
921d17ba JA	109	case 't':
	110	if (!strncmp(optarg, "zipf", 4))
	111	dist_type = TYPE_ZIPF;
	112	else if (!strncmp(optarg, "pareto", 6))
	113	dist_type = TYPE_PARETO;
	114	else {
	115	printf("wrong dist type: %s\n", optarg);
	116	return 1;
	117	}
	118	break;
	119	case 'g':
	120	gb_size = strtoul(optarg, NULL, 10);
	121	break;
	122	case 'i':
	123	dist_val = atof(optarg);
	124	dist_val_set = 1;
	125	break;
921d17ba JA	126	case 'o':
	127	output_nranges = strtoul(optarg, NULL, 10);
	128	break;
355934b7 VKF	129	case 'c':
	130	output_csv = 1;
	131	break;
921d17ba JA	132	default:
	133	printf("bad option %c\n", c);
	134	return 1;
	135	}
	136	}
	137
	138	if (dist_type == TYPE_PARETO) {
	139	if ((dist_val >= 1.00 \|\| dist_val < 0.00)) {
	140	printf("pareto input must be > 0.00 and < 1.00\n");
	141	return 1;
	142	}
	143	if (!dist_val_set)
	144	dist_val = DEF_PARETO_VAL;
	145	} else if (dist_type == TYPE_ZIPF) {
	146	if (dist_val == 1.0) {
	147	printf("zipf input must be different than 1.0\n");
	148	return 1;
	149	}
	150	if (!dist_val_set)
	151	dist_val = DEF_ZIPF_VAL;
	152	}
	153
	154	return 0;
	155	}
	156
444256ea JA	157	struct output_sum {
	158	double output;
	159	unsigned int nranges;
	160	};
	161
24baa4c7 JA	162	static int node_cmp(const void p1, const void p2)
	163	{
	164	const struct node *n1 = p1;
	165	const struct node *n2 = p2;
	166
	167	return n2->hits - n1->hits;
	168	}
	169
6ff38856 JA	170	int main(int argc, char *argv[])
6ff38856 JA	171	{
fd6f237d	172	unsigned long offset;
2c9b3ccd	173	unsigned long i, j, k, nr_vals, cur_vals, interval_step, next_interval, total_vals, nnodes;
444256ea JA	174	unsigned long long nranges;
444256ea JA	175	struct output_sum *output_sums;
24baa4c7	176	struct node *nodes;
444256ea	177	double perc, perc_i;
6ff38856	178	struct zipf_state zs;
6ff38856	179
921d17ba	180	if (parse_options(argc, argv))
6ff38856	181	return 1;
6ff38856	182
355934b7 VKF	183	if( !output_csv )
355934b7 VKF	184	printf("Generating %s distribution with %f input and %lu GB size and %lu block_size.\n", dist_types[dist_type], dist_val, gb_size, block_size);
444256ea JA	185
	186	nranges = gb_size * 1024 * 1024 * 1024ULL;
	187	nranges /= block_size;
f880b1f6	188
921d17ba JA	189	if (dist_type == TYPE_ZIPF)
921d17ba JA	190	zipf_init(&zs, nranges, dist_val, 1);
6ff38856	191	else
921d17ba	192	pareto_init(&zs, nranges, dist_val, 1);
6ff38856	193
c71224e7 JA	194	hash_bits = 0;
	195	hash_size = nranges;
	196	while ((hash_size >>= 1) != 0)
	197	hash_bits++;
	198
	199	hash_size = 1 << hash_bits;
	200
fd6f237d JA	201	hash = malloc(hash_size * sizeof(struct flist_head));
	202	for (i = 0; i < hash_size; i++)
	203	INIT_FLIST_HEAD(&hash[i]);
	204
24baa4c7 JA	205	nodes = malloc(nranges * sizeof(struct node));
24baa4c7 JA	206
2c9b3ccd	207	for (i = j = 0; i < nranges; i++) {
fd6f237d	208	struct node *n;
6ff38856	209
921d17ba	210	if (dist_type == TYPE_ZIPF)
fd6f237d	211	offset = zipf_next(&zs);
6ff38856	212	else
fd6f237d JA	213	offset = pareto_next(&zs);
	214
	215	n = hash_lookup(offset);
	216	if (n)
	217	n->hits++;
24baa4c7 JA	218	else {
	219	hash_insert(&nodes[j], offset);
	220	j++;
	221	}
6ff38856	222
6ff38856 JA	223	}
6ff38856 JA	224
24baa4c7 JA	225	qsort(nodes, j, sizeof(struct node), node_cmp);
	226	nnodes = j;
	227	nr_vals = nnodes;
6ff38856	228
355934b7 VKF	229	if (output_csv) {
355934b7 VKF	230	printf("rank, count\n");
2c9b3ccd	231	for (k = 0; k < nnodes; k++) {
355934b7	232	printf("%lu, %lu\n", k, nodes[k].hits);
2c9b3ccd	233	}
355934b7	234	} else {
2c9b3ccd FB	235	unsigned long blocks = percentage * nranges / 100;
	236	double hit_percent_sum = 0;
	237	unsigned long long hit_sum = 0;
	238	interval_step = (nr_vals - 1) / output_nranges + 1;
	239	next_interval = interval_step;
355934b7 VKF	240	output_sums = malloc(output_nranges * sizeof(struct output_sum));
	241	for (i = 0; i < output_nranges; i++) {
	242	output_sums[i].output = 0.0;
2c9b3ccd	243	output_sums[i].nranges = 0;
444256ea	244	}
6ff38856	245
2c9b3ccd	246	j = total_vals = cur_vals = 0;
355934b7 VKF	247
	248	for (k = 0; k < nnodes; k++) {
	249	struct output_sum *os = &output_sums[j];
	250	struct node *node = &nodes[k];
2c9b3ccd FB	251	cur_vals += node->hits;
	252	total_vals += node->hits;
	253	os->nranges += node->hits;
	254	if (k == (next_interval) -1 \|\| k == (nnodes - 1)) {
	255	os->output = (double)(cur_vals) / (double)nranges;
355934b7	256	os->output *= 100.0;
2c9b3ccd FB	257	cur_vals = 0;
2c9b3ccd FB	258	next_interval += interval_step;
355934b7	259	j++;
355934b7	260	}
444256ea	261
355934b7	262	if (percentage) {
355934b7	263	if (total_vals >= blocks) {
2c9b3ccd	264	double cs = k * block_size / (1024 * 1024);
355934b7 VKF	265	char p = 'M';
	266
	267	if (cs > 1024.0) {
	268	cs /= 1024.0;
	269	p = 'G';
	270	}
	271	if (cs > 1024.0) {
	272	cs /= 1024.0;
	273	p = 'T';
	274	}
	275
	276	printf("%.2f%% of hits satisfied in %.3f%cB of cache\n", percentage, cs, p);
	277	percentage = 0.0;
444256ea	278	}
444256ea JA	279	}
444256ea JA	280	}
6ff38856	281
355934b7 VKF	282	perc_i = 100.0 / (double)output_nranges;
355934b7 VKF	283	perc = 0.0;
921d17ba	284
2c9b3ccd	285	printf("\n Rows Hits %% No Hits Size\n");
355934b7	286	printf("--------------------------------------------------------\n");
2c9b3ccd	287	for (i = 0; i < output_nranges; i++) {
355934b7 VKF	288	struct output_sum *os = &output_sums[i];
	289	double gb = (double)os->nranges * block_size / 1024.0;
	290	char p = 'K';
921d17ba	291
355934b7 VKF	292	if (gb > 1024.0) {
	293	p = 'M';
	294	gb /= 1024.0;
	295	}
	296	if (gb > 1024.0) {
	297	p = 'G';
	298	gb /= 1024.0;
	299	}
	300
	301	perc += perc_i;
2c9b3ccd FB	302	hit_percent_sum += os->output;
2c9b3ccd FB	303	hit_sum += os->nranges;
355934b7 VKF	304	printf("%s %6.2f%%\t%6.2f%%\t\t%8u\t%6.2f%c\n",
	305	i ? "\|->" : "Top", perc, os->output, os->nranges,
	306	gb, p);
921d17ba	307	}
2c9b3ccd FB	308	printf("--------------------------------------------------------\n");
2c9b3ccd FB	309	printf("Total\t\t%6.2f%%\t\t%8llu\n", hit_percent_sum, hit_sum);
355934b7	310	free(output_sums);
f880b1f6	311	}
6ff38856	312
fd6f237d	313	free(hash);
355934b7	314	free(nodes);
6ff38856 JA	315	return 0;
6ff38856 JA	316	}