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 100,000 values and split the reporting into
9 * t/genzipf zipf 1.2 100000 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"
23 #include "../rbtree.h"
25 #define DEF_NR 1000000
26 #define DEF_NR_OUTPUT 23
29 struct flist_head list;
31 unsigned long long val;
35 static struct flist_head *hash;
36 static unsigned long hash_bits = 24;
37 static unsigned long hash_size = 1 << 24;
38 static struct rb_root rb;
40 static struct node *hash_lookup(unsigned long long val)
42 struct flist_head *l = &hash[hash_long(val, hash_bits)];
43 struct flist_head *entry;
46 flist_for_each(entry, l) {
47 n = flist_entry(entry, struct node, list);
55 static void hash_insert(unsigned long long val)
57 struct flist_head *l = &hash[hash_long(val, hash_bits)];
58 struct node *n = malloc(sizeof(*n));
62 flist_add_tail(&n->list, l);
65 static void rb_insert(struct node *n)
67 struct rb_node **p, *parent;
69 memset(&n->rb, 0, sizeof(n->rb));
76 __n = rb_entry(parent, struct node, rb);
77 if (n->hits > __n->hits)
83 rb_link_node(&n->rb, parent, p);
84 rb_insert_color(&n->rb, &rb);
87 static unsigned long rb_add(struct flist_head *list)
89 struct flist_head *entry;
90 unsigned long ret = 0;
93 flist_for_each(entry, list) {
94 n = flist_entry(entry, struct node, list);
103 static unsigned long rb_gen(void)
105 unsigned long ret = 0;
108 for (i = 0; i < hash_size; i++)
109 ret += rb_add(&hash[i]);
114 int main(int argc, char *argv[])
116 unsigned long nranges, output_nranges;
117 unsigned long offset;
118 unsigned long i, j, nr_vals, cur_vals, interval;
119 double *output, perc, perc_i;
120 struct zipf_state zs;
126 printf("%s: {zipf,pareto} val values [output ranges]\n", argv[0]);
130 if (!strcmp(argv[1], "zipf"))
132 else if (!strcmp(argv[1], "pareto"))
135 printf("Bad distribution type <%s>\n", argv[1]);
142 output_nranges = DEF_NR_OUTPUT;
145 nranges = strtoul(argv[3], NULL, 10);
147 output_nranges = strtoul(argv[4], NULL, 10);
149 printf("Generating %s distribution with %f input and %lu ranges.\n", use_zipf ? "zipf" : "pareto", val, nranges);
152 zipf_init(&zs, nranges, val);
154 pareto_init(&zs, nranges, val);
156 hash = malloc(hash_size * sizeof(struct flist_head));
157 for (i = 0; i < hash_size; i++)
158 INIT_FLIST_HEAD(&hash[i]);
160 for (nr_vals = 0, i = 0; i < nranges; i++) {
164 offset = zipf_next(&zs);
166 offset = pareto_next(&zs);
168 n = hash_lookup(offset);
179 interval = nr_vals / output_nranges;
181 output = malloc(output_nranges * sizeof(double));
183 i = j = cur_vals = 0;
187 struct node *node = rb_entry(n, struct node, rb);
190 output[j] = (double) (cur_vals + 1) / (double) nranges;
193 cur_vals = node->hits;
194 interval += nr_vals / output_nranges;
196 cur_vals += node->hits;
202 perc_i = 100.0 / (double) output_nranges;
204 for (i = 0; i < j; i++) {
206 printf("Top %6.2f%%:\t%6.2f%% of hits\n", perc, output[i]);