2 * Generate/analyze pareto/zipf distributions to better understand
3 * what an access pattern would look like.
5 * For instance, the following would generate a zipf distribution
6 * with theta 1.2, using 262144 (1 GB / 4096) values and split the reporting into
9 * ./t/fio-genzipf -t zipf -i 1.2 -g 1 -b 4096 -o 20
11 * Only the distribution type (zipf or pareto) and spread input need
12 * to be given, if not given defaults are used.
21 #include "../lib/zipf.h"
22 #include "../lib/gauss.h"
26 #define DEF_NR_OUTPUT 20
29 struct flist_head list;
30 unsigned long long val;
34 static struct flist_head *hash;
35 static unsigned long hash_bits = 24;
36 static unsigned long hash_size = 1 << 24;
44 static const char *dist_types[] = { "None", "Zipf", "Pareto", "Normal" };
46 static int dist_type = TYPE_ZIPF;
47 static unsigned long gb_size = 500;
48 static unsigned long block_size = 4096;
49 static unsigned long output_nranges = DEF_NR_OUTPUT;
50 static double percentage;
51 static double dist_val;
52 static int output_csv = 0;
54 #define DEF_ZIPF_VAL 1.2
55 #define DEF_PARETO_VAL 0.3
57 static struct node *hash_lookup(unsigned long long val)
59 struct flist_head *l = &hash[hash_long(val, hash_bits)];
60 struct flist_head *entry;
63 flist_for_each(entry, l) {
64 n = flist_entry(entry, struct node, list);
72 static struct node *hash_insert(struct node *n, unsigned long long val)
74 struct flist_head *l = &hash[hash_long(val, hash_bits)];
78 flist_add_tail(&n->list, l);
82 static void usage(void)
84 printf("genzipf: test zipf/pareto values for fio input\n");
85 printf("\t-h\tThis help screen\n");
86 printf("\t-p\tGenerate size of data set that are hit by this percentage\n");
87 printf("\t-t\tDistribution type (zipf, pareto, or normal)\n");
88 printf("\t-i\tDistribution algorithm input (zipf theta, pareto power,\n"
89 "\t\tor normal %% deviation)\n");
90 printf("\t-b\tBlock size of a given range (in bytes)\n");
91 printf("\t-g\tSize of data set (in gigabytes)\n");
92 printf("\t-o\tNumber of output rows\n");
93 printf("\t-c\tOutput ranges in CSV format\n");
96 static int parse_options(int argc, char *argv[])
98 const char *optstring = "t:g:i:o:b:p:ch";
99 int c, dist_val_set = 0;
101 while ((c = getopt(argc, argv, optstring)) != -1) {
107 percentage = atof(optarg);
110 block_size = strtoul(optarg, NULL, 10);
113 if (!strncmp(optarg, "zipf", 4))
114 dist_type = TYPE_ZIPF;
115 else if (!strncmp(optarg, "pareto", 6))
116 dist_type = TYPE_PARETO;
117 else if (!strncmp(optarg, "normal", 6))
118 dist_type = TYPE_NORMAL;
120 printf("wrong dist type: %s\n", optarg);
125 gb_size = strtoul(optarg, NULL, 10);
128 dist_val = atof(optarg);
132 output_nranges = strtoul(optarg, NULL, 10);
138 printf("bad option %c\n", c);
143 if (dist_type == TYPE_PARETO) {
144 if ((dist_val >= 1.00 || dist_val < 0.00)) {
145 printf("pareto input must be > 0.00 and < 1.00\n");
149 dist_val = DEF_PARETO_VAL;
150 } else if (dist_type == TYPE_ZIPF) {
151 if (dist_val == 1.0) {
152 printf("zipf input must be different than 1.0\n");
156 dist_val = DEF_ZIPF_VAL;
164 unsigned int nranges;
167 static int node_cmp(const void *p1, const void *p2)
169 const struct node *n1 = p1;
170 const struct node *n2 = p2;
172 return n2->hits - n1->hits;
175 int main(int argc, char *argv[])
177 unsigned long offset;
178 unsigned long i, j, k, nr_vals, cur_vals, interval_step, next_interval, total_vals, nnodes;
179 unsigned long long nranges;
180 struct output_sum *output_sums;
183 struct zipf_state zs;
184 struct gauss_state gs;
186 if (parse_options(argc, argv))
190 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);
192 nranges = gb_size * 1024 * 1024 * 1024ULL;
193 nranges /= block_size;
195 if (dist_type == TYPE_ZIPF)
196 zipf_init(&zs, nranges, dist_val, 1);
197 else if (dist_type == TYPE_PARETO)
198 pareto_init(&zs, nranges, dist_val, 1);
200 gauss_init(&gs, nranges, dist_val, 1);
204 while ((hash_size >>= 1) != 0)
207 hash_size = 1 << hash_bits;
209 hash = malloc(hash_size * sizeof(struct flist_head));
210 for (i = 0; i < hash_size; i++)
211 INIT_FLIST_HEAD(&hash[i]);
213 nodes = malloc(nranges * sizeof(struct node));
215 for (i = j = 0; i < nranges; i++) {
218 if (dist_type == TYPE_ZIPF)
219 offset = zipf_next(&zs);
220 else if (dist_type == TYPE_PARETO)
221 offset = pareto_next(&zs);
223 offset = gauss_next(&gs);
225 n = hash_lookup(offset);
229 hash_insert(&nodes[j], offset);
235 qsort(nodes, j, sizeof(struct node), node_cmp);
240 printf("rank, count\n");
241 for (k = 0; k < nnodes; k++) {
242 printf("%lu, %lu\n", k, nodes[k].hits);
245 unsigned long blocks = percentage * nranges / 100;
246 double hit_percent_sum = 0;
247 unsigned long long hit_sum = 0;
248 interval_step = (nr_vals - 1) / output_nranges + 1;
249 next_interval = interval_step;
250 output_sums = malloc(output_nranges * sizeof(struct output_sum));
251 for (i = 0; i < output_nranges; i++) {
252 output_sums[i].output = 0.0;
253 output_sums[i].nranges = 0;
256 j = total_vals = cur_vals = 0;
258 for (k = 0; k < nnodes; k++) {
259 struct output_sum *os = &output_sums[j];
260 struct node *node = &nodes[k];
261 cur_vals += node->hits;
262 total_vals += node->hits;
263 os->nranges += node->hits;
264 if (k == (next_interval) -1 || k == (nnodes - 1)) {
265 os->output = (double)(cur_vals) / (double)nranges;
268 next_interval += interval_step;
273 if (total_vals >= blocks) {
274 double cs = k * block_size / (1024 * 1024);
286 printf("%.2f%% of hits satisfied in %.3f%cB of cache\n", percentage, cs, p);
292 perc_i = 100.0 / (double)output_nranges;
295 printf("\n Rows Hits %% No Hits Size\n");
296 printf("--------------------------------------------------------\n");
297 for (i = 0; i < output_nranges; i++) {
298 struct output_sum *os = &output_sums[i];
299 double gb = (double)os->nranges * block_size / 1024.0;
312 hit_percent_sum += os->output;
313 hit_sum += os->nranges;
314 printf("%s %6.2f%%\t%6.2f%%\t\t%8u\t%6.2f%c\n",
315 i ? "|->" : "Top", perc, os->output, os->nranges,
318 printf("--------------------------------------------------------\n");
319 printf("Total\t\t%6.2f%%\t\t%8llu\n", hit_percent_sum, hit_sum);