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.
21 #include "../lib/zipf.h"
25 #define DEF_NR 1000000
26 #define DEF_NR_OUTPUT 23
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;
43 static const char *dist_types[] = { "None", "Zipf", "Pareto" };
45 static int dist_type = TYPE_ZIPF;
46 static unsigned long gb_size = 500;
47 static unsigned long block_size = 4096;
48 static unsigned long output_nranges = DEF_NR_OUTPUT;
49 static double percentage;
50 static double dist_val;
51 static int output_csv = 0;
53 #define DEF_ZIPF_VAL 1.2
54 #define DEF_PARETO_VAL 0.3
56 static struct node *hash_lookup(unsigned long long val)
58 struct flist_head *l = &hash[hash_long(val, hash_bits)];
59 struct flist_head *entry;
62 flist_for_each(entry, l) {
63 n = flist_entry(entry, struct node, list);
71 static struct node *hash_insert(struct node *n, unsigned long long val)
73 struct flist_head *l = &hash[hash_long(val, hash_bits)];
77 flist_add_tail(&n->list, l);
81 static int parse_options(int argc, char *argv[])
83 const char *optstring = "t:g:i:o:b:p:c";
84 int c, dist_val_set = 0;
86 while ((c = getopt(argc, argv, optstring)) != -1) {
89 percentage = atof(optarg);
92 block_size = strtoul(optarg, NULL, 10);
95 if (!strncmp(optarg, "zipf", 4))
96 dist_type = TYPE_ZIPF;
97 else if (!strncmp(optarg, "pareto", 6))
98 dist_type = TYPE_PARETO;
100 printf("wrong dist type: %s\n", optarg);
105 gb_size = strtoul(optarg, NULL, 10);
108 dist_val = atof(optarg);
112 output_nranges = strtoul(optarg, NULL, 10);
118 printf("bad option %c\n", c);
123 if (dist_type == TYPE_PARETO) {
124 if ((dist_val >= 1.00 || dist_val < 0.00)) {
125 printf("pareto input must be > 0.00 and < 1.00\n");
129 dist_val = DEF_PARETO_VAL;
130 } else if (dist_type == TYPE_ZIPF) {
131 if (dist_val == 1.0) {
132 printf("zipf input must be different than 1.0\n");
136 dist_val = DEF_ZIPF_VAL;
144 unsigned int nranges;
147 static int node_cmp(const void *p1, const void *p2)
149 const struct node *n1 = p1;
150 const struct node *n2 = p2;
152 return n2->hits - n1->hits;
155 int main(int argc, char *argv[])
157 unsigned long offset;
158 unsigned long i, j, k, nr_vals, cur_vals, interval, total_vals, nnodes;
159 unsigned long long nranges;
160 struct output_sum *output_sums;
163 struct zipf_state zs;
165 if (parse_options(argc, argv))
169 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);
171 nranges = gb_size * 1024 * 1024 * 1024ULL;
172 nranges /= block_size;
174 if (dist_type == TYPE_ZIPF)
175 zipf_init(&zs, nranges, dist_val, 1);
177 pareto_init(&zs, nranges, dist_val, 1);
181 while ((hash_size >>= 1) != 0)
184 hash_size = 1 << hash_bits;
186 hash = malloc(hash_size * sizeof(struct flist_head));
187 for (i = 0; i < hash_size; i++)
188 INIT_FLIST_HEAD(&hash[i]);
190 nodes = malloc(nranges * sizeof(struct node));
192 for (nr_vals = i = j = 0; i < nranges; i++) {
195 if (dist_type == TYPE_ZIPF)
196 offset = zipf_next(&zs);
198 offset = pareto_next(&zs);
200 n = hash_lookup(offset);
204 hash_insert(&nodes[j], offset);
211 qsort(nodes, j, sizeof(struct node), node_cmp);
216 printf("rank, count\n");
217 for (k = 0; k < nnodes; k++)
218 printf("%lu, %lu\n", k, nodes[k].hits);
220 interval = (nr_vals + output_nranges - 1) / output_nranges;
222 output_sums = malloc(output_nranges * sizeof(struct output_sum));
223 for (i = 0; i < output_nranges; i++) {
224 output_sums[i].output = 0.0;
225 output_sums[i].nranges = 1;
228 total_vals = i = j = cur_vals = 0;
230 for (k = 0; k < nnodes; k++) {
231 struct output_sum *os = &output_sums[j];
232 struct node *node = &nodes[k];
236 (double)(cur_vals + 1) / (double)nranges;
239 cur_vals = node->hits;
241 (nr_vals + output_nranges -
244 cur_vals += node->hits;
245 os->nranges += node->hits;
249 total_vals += node->hits;
252 unsigned long blocks =
253 percentage * nranges / 100;
255 if (total_vals >= blocks) {
257 i * block_size / (1024 * 1024);
269 printf("%.2f%% of hits satisfied in %.3f%cB of cache\n", percentage, cs, p);
275 perc_i = 100.0 / (double)output_nranges;
278 printf("\n Rows Hits No Hits Size\n");
279 printf("--------------------------------------------------------\n");
280 for (i = 0; i < j; i++) {
281 struct output_sum *os = &output_sums[i];
282 double gb = (double)os->nranges * block_size / 1024.0;
295 printf("%s %6.2f%%\t%6.2f%%\t\t%8u\t%6.2f%c\n",
296 i ? "|->" : "Top", perc, os->output, os->nranges,