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 GiB / 4096) values and split the
7 * reporting into 20 buckets:
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.
20 #include "../lib/zipf.h"
21 #include "../lib/gauss.h"
25 #define DEF_NR_OUTPUT 20
28 struct flist_head list;
29 unsigned long long val;
33 static struct flist_head *hash;
34 static unsigned long hash_bits = 24;
35 static unsigned long hash_size = 1 << 24;
43 static const char *dist_types[] = { "None", "Zipf", "Pareto", "Normal" };
50 static int dist_type = TYPE_ZIPF;
51 static unsigned long gib_size = 500;
52 static unsigned long block_size = 4096;
53 static unsigned long output_nranges = DEF_NR_OUTPUT;
54 static double percentage;
55 static double dist_val;
56 static int output_type = OUTPUT_NORMAL;
58 #define DEF_ZIPF_VAL 1.2
59 #define DEF_PARETO_VAL 0.3
61 static unsigned int hashv(unsigned long long val)
63 return jhash(&val, sizeof(val), 0) & (hash_size - 1);
66 static struct node *hash_lookup(unsigned long long val)
68 struct flist_head *l = &hash[hashv(val)];
69 struct flist_head *entry;
72 flist_for_each(entry, l) {
73 n = flist_entry(entry, struct node, list);
81 static void hash_insert(struct node *n, unsigned long long val)
83 struct flist_head *l = &hash[hashv(val)];
87 flist_add_tail(&n->list, l);
90 static void usage(void)
92 printf("genzipf: test zipf/pareto values for fio input\n");
93 printf("\t-h\tThis help screen\n");
94 printf("\t-p\tGenerate size of data set that are hit by this percentage\n");
95 printf("\t-t\tDistribution type (zipf, pareto, or normal)\n");
96 printf("\t-i\tDistribution algorithm input (zipf theta, pareto power,\n"
97 "\t\tor normal %% deviation)\n");
98 printf("\t-b\tBlock size of a given range (in bytes)\n");
99 printf("\t-g\tSize of data set (in gigabytes)\n");
100 printf("\t-o\tNumber of output rows\n");
101 printf("\t-c\tOutput ranges in CSV format\n");
104 static int parse_options(int argc, char *argv[])
106 const char *optstring = "t:g:i:o:b:p:ch";
107 int c, dist_val_set = 0;
109 while ((c = getopt(argc, argv, optstring)) != -1) {
115 percentage = atof(optarg);
118 block_size = strtoul(optarg, NULL, 10);
121 if (!strncmp(optarg, "zipf", 4))
122 dist_type = TYPE_ZIPF;
123 else if (!strncmp(optarg, "pareto", 6))
124 dist_type = TYPE_PARETO;
125 else if (!strncmp(optarg, "normal", 6))
126 dist_type = TYPE_NORMAL;
128 printf("wrong dist type: %s\n", optarg);
133 gib_size = strtoul(optarg, NULL, 10);
136 dist_val = atof(optarg);
140 output_nranges = strtoul(optarg, NULL, 10);
143 output_type = OUTPUT_CSV;
146 printf("bad option %c\n", c);
151 if (dist_type == TYPE_PARETO) {
152 if ((dist_val >= 1.00 || dist_val < 0.00)) {
153 printf("pareto input must be > 0.00 and < 1.00\n");
157 dist_val = DEF_PARETO_VAL;
158 } else if (dist_type == TYPE_ZIPF) {
159 if (dist_val == 1.0) {
160 printf("zipf input must be different than 1.0\n");
164 dist_val = DEF_ZIPF_VAL;
172 unsigned int nranges;
175 static int node_cmp(const void *p1, const void *p2)
177 const struct node *n1 = p1;
178 const struct node *n2 = p2;
180 return n2->hits - n1->hits;
183 static void output_csv(struct node *nodes, unsigned long nnodes)
187 printf("rank, count\n");
188 for (i = 0; i < nnodes; i++)
189 printf("%lu, %lu\n", i, nodes[i].hits);
192 static void output_normal(struct node *nodes, unsigned long nnodes,
193 unsigned long nranges)
195 unsigned long i, j, cur_vals, interval_step, next_interval, total_vals;
196 unsigned long blocks = percentage * nnodes / 100;
197 double hit_percent_sum = 0;
198 unsigned long long hit_sum = 0;
200 struct output_sum *output_sums;
202 interval_step = (nnodes - 1) / output_nranges + 1;
203 next_interval = interval_step;
204 output_sums = malloc(output_nranges * sizeof(struct output_sum));
206 for (i = 0; i < output_nranges; i++) {
207 output_sums[i].output = 0.0;
208 output_sums[i].nranges = 0;
211 j = total_vals = cur_vals = 0;
213 for (i = 0; i < nnodes; i++) {
214 struct output_sum *os = &output_sums[j];
215 struct node *node = &nodes[i];
216 cur_vals += node->hits;
217 total_vals += node->hits;
218 os->nranges += node->hits;
219 if (i == (next_interval) -1 || i == nnodes - 1) {
220 os->output = (double) cur_vals / (double) nranges;
223 next_interval += interval_step;
228 if (total_vals >= blocks) {
229 double cs = (double) i * block_size / (1024.0 * 1024.0);
241 printf("%.2f%% of hits satisfied in %.3f%cB of cache\n", percentage, cs, p);
247 perc_i = 100.0 / (double)output_nranges;
250 printf("\n Rows Hits %% Sum %% # Hits Size\n");
251 printf("-----------------------------------------------------------------------\n");
252 for (i = 0; i < output_nranges; i++) {
253 struct output_sum *os = &output_sums[i];
254 double gb = (double)os->nranges * block_size / 1024.0;
267 hit_percent_sum += os->output;
268 hit_sum += os->nranges;
269 printf("%s %6.2f%%\t%6.2f%%\t\t%6.2f%%\t\t%8u\t%6.2f%c\n",
270 i ? "|->" : "Top", perc, os->output, hit_percent_sum,
274 printf("-----------------------------------------------------------------------\n");
275 printf("Total\t\t\t\t\t\t%8llu\n", hit_sum);
279 int main(int argc, char *argv[])
281 unsigned long offset;
282 unsigned long long nranges;
283 unsigned long nnodes;
285 struct zipf_state zs;
286 struct gauss_state gs;
289 if (parse_options(argc, argv))
292 if (output_type != OUTPUT_CSV)
293 printf("Generating %s distribution with %f input and %lu GiB size and %lu block_size.\n",
294 dist_types[dist_type], dist_val, gib_size, block_size);
296 nranges = gib_size * 1024 * 1024 * 1024ULL;
297 nranges /= block_size;
299 if (dist_type == TYPE_ZIPF)
300 zipf_init(&zs, nranges, dist_val, -1, 1);
301 else if (dist_type == TYPE_PARETO)
302 pareto_init(&zs, nranges, dist_val, -1, 1);
304 gauss_init(&gs, nranges, dist_val, -1, 1);
308 while ((hash_size >>= 1) != 0)
311 hash_size = 1 << hash_bits;
313 hash = calloc(hash_size, sizeof(struct flist_head));
314 for (i = 0; i < hash_size; i++)
315 INIT_FLIST_HEAD(&hash[i]);
317 nodes = malloc(nranges * sizeof(struct node));
319 for (i = j = 0; i < nranges; i++) {
322 if (dist_type == TYPE_ZIPF)
323 offset = zipf_next(&zs);
324 else if (dist_type == TYPE_PARETO)
325 offset = pareto_next(&zs);
327 offset = gauss_next(&gs);
329 n = hash_lookup(offset);
333 hash_insert(&nodes[j], offset);
338 qsort(nodes, j, sizeof(struct node), node_cmp);
341 if (output_type == OUTPUT_CSV)
342 output_csv(nodes, nnodes);
344 output_normal(nodes, nnodes, nranges);