t/genzipf.c

   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
   6  * with theta 1.2, using 100,000 values and split the reporting into
   7  * 20 buckets:
   8  *
   9  *      t/genzipf zipf 1.2 100000 20
  10  *
  11  * Only the distribution type (zipf or pareto) and spread input need
  12  * to be given, if not given defaults are used.
  13  *
  14  */
  15 #include <stdio.h>
  16 #include <stdlib.h>
  17 #include <fcntl.h>
  18 #include <string.h>
  19
  20 #include "../lib/zipf.h"
  21 #include "../flist.h"
  22 #include "../hash.h"
  23 #include "../rbtree.h"
  24
  25 #define DEF_NR          1000000
  26 #define DEF_NR_OUTPUT   23
  27
  28 struct node {
  29         struct flist_head list;
  30         struct rb_node rb;
  31         unsigned long long val;
  32         unsigned long hits;
  33 };
  34
  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;
  39
  40 static struct node *hash_lookup(unsigned long long val)
  41 {
  42         struct flist_head *l = &hash[hash_long(val, hash_bits)];
  43         struct flist_head *entry;
  44         struct node *n;
  45
  46         flist_for_each(entry, l) {
  47                 n = flist_entry(entry, struct node, list);
  48                 if (n->val == val)
  49                         return n;
  50         }
  51
  52         return NULL;
  53 }
  54
  55 static void hash_insert(unsigned long long val)
  56 {
  57         struct flist_head *l = &hash[hash_long(val, hash_bits)];
  58         struct node *n = malloc(sizeof(*n));
  59
  60         n->val = val;
  61         n->hits = 1;
  62         flist_add_tail(&n->list, l);
  63 }
  64
  65 static void rb_insert(struct node *n)
  66 {
  67         struct rb_node **p, *parent;
  68
  69         memset(&n->rb, 0, sizeof(n->rb));
  70         p = &rb.rb_node;
  71         parent = NULL;
  72         while (*p) {
  73                 struct node *__n;
  74
  75                 parent = *p;
  76                 __n = rb_entry(parent, struct node, rb);
  77                 if (n->hits > __n->hits)
  78                         p = &(*p)->rb_left;
  79                 else
  80                         p = &(*p)->rb_right;
  81         }
  82
  83         rb_link_node(&n->rb, parent, p);
  84         rb_insert_color(&n->rb, &rb);
  85 }
  86
  87 static unsigned long rb_add(struct flist_head *list)
  88 {
  89         struct flist_head *entry;
  90         unsigned long ret = 0;
  91         struct node *n;
  92
  93         flist_for_each(entry, list) {
  94                 n = flist_entry(entry, struct node, list);
  95
  96                 rb_insert(n);
  97                 ret++;
  98         }
  99
 100         return ret;
 101 }
 102
 103 static unsigned long rb_gen(void)
 104 {
 105         unsigned long ret = 0;
 106         unsigned int i;
 107
 108         for (i = 0; i < hash_size; i++)
 109                 ret += rb_add(&hash[i]);
 110
 111         return ret;
 112 }
 113
 114 int main(int argc, char *argv[])
 115 {
 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;
 121         struct rb_node *n;
 122         int use_zipf;
 123         double val;
 124
 125         if (argc < 3) {
 126                 printf("%s: {zipf,pareto} val values [output ranges]\n", argv[0]);
 127                 return 1;
 128         }
 129
 130         if (!strcmp(argv[1], "zipf"))
 131                 use_zipf = 1;
 132         else if (!strcmp(argv[1], "pareto"))
 133                 use_zipf = 0;
 134         else {
 135                 printf("Bad distribution type <%s>\n", argv[1]);
 136                 return 1;
 137         }
 138
 139         val = atof(argv[2]);
 140         if ((val >= 1.00 || val < 0.00) && !use_zipf) {
 141                 printf("pareto input must be > 0.00 and < 1.00\n");
 142                 return 1;
 143         }
 144         if (val == 1.0 && use_zipf) {
 145                 printf("zipf input must be different than 1.0\n");
 146                 return 1;
 147         }
 148
 149         nranges = DEF_NR;
 150         output_nranges = DEF_NR_OUTPUT;
 151
 152         if (argc >= 4)
 153                 nranges = strtoul(argv[3], NULL, 10);
 154         if (argc >= 5)
 155                 output_nranges = strtoul(argv[4], NULL, 10);
 156
 157         printf("Generating %s distribution with %f input and %lu ranges.\n", use_zipf ? "zipf" : "pareto", val, nranges);
 158
 159         if (use_zipf)
 160                 zipf_init(&zs, nranges, val, 1);
 161         else
 162                 pareto_init(&zs, nranges, val, 1);
 163
 164         hash_bits = 0;
 165         hash_size = nranges;
 166         while ((hash_size >>= 1) != 0)
 167                 hash_bits++;
 168
 169         hash_size = 1 << hash_bits;
 170
 171         hash = malloc(hash_size * sizeof(struct flist_head));
 172         for (i = 0; i < hash_size; i++)
 173                 INIT_FLIST_HEAD(&hash[i]);
 174
 175         for (nr_vals = 0, i = 0; i < nranges; i++) {
 176                 struct node *n;
 177
 178                 if (use_zipf)
 179                         offset = zipf_next(&zs);
 180                 else
 181                         offset = pareto_next(&zs);
 182
 183                 n = hash_lookup(offset);
 184                 if (n)
 185                         n->hits++;
 186                 else
 187                         hash_insert(offset);
 188
 189                 nr_vals++;
 190         }
 191
 192         nr_vals = rb_gen();
 193
 194         interval = (nr_vals + output_nranges - 1) / output_nranges;
 195
 196         output = malloc(output_nranges * sizeof(double));
 197
 198         i = j = cur_vals = 0;
 199
 200         n = rb_first(&rb);
 201         while (n) {
 202                 struct node *node = rb_entry(n, struct node, rb);
 203
 204                 if (i >= interval) {
 205                         output[j] = (double) (cur_vals + 1) / (double) nranges;
 206                         output[j] *= 100.0;
 207                         j++;
 208                         cur_vals = node->hits;
 209                         interval += (nr_vals + output_nranges - 1) / output_nranges;
 210                 } else
 211                         cur_vals += node->hits;
 212
 213                 n = rb_next(n);
 214                 i++;
 215         }
 216
 217         perc_i = 100.0 / (double) output_nranges;
 218         perc = 0.0;
 219         for (i = 0; i < j; i++) {
 220                 perc += perc_i;
 221                 printf("%s %6.2f%%:\t%6.2f%% of hits\n", i ? "|->" : "Top", perc, output[i]);
 222         }
 223
 224         free(output);
 225         free(hash);
 226         return 0;
 227 }