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 #include <unistd.h>
  20
  21 #include "../lib/zipf.h"
  22 #include "../flist.h"
  23 #include "../hash.h"
  24 #include "../rbtree.h"
  25
  26 #define DEF_NR          1000000
  27 #define DEF_NR_OUTPUT   23
  28
  29 struct node {
  30         struct flist_head list;
  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
  39 enum {
  40         TYPE_NONE = 0,
  41         TYPE_ZIPF,
  42         TYPE_PARETO,
  43 };
  44 static const char *dist_types[] = { "None", "Zipf", "Pareto" };
  45
  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
  53 #define DEF_ZIPF_VAL    1.2
  54 #define DEF_PARETO_VAL  0.3
  55
  56 static struct node *hash_lookup(unsigned long long val)
  57 {
  58         struct flist_head *l = &hash[hash_long(val, hash_bits)];
  59         struct flist_head *entry;
  60         struct node *n;
  61
  62         flist_for_each(entry, l) {
  63                 n = flist_entry(entry, struct node, list);
  64                 if (n->val == val)
  65                         return n;
  66         }
  67
  68         return NULL;
  69 }
  70
  71 static struct node *hash_insert(struct node *n, unsigned long long val)
  72 {
  73         struct flist_head *l = &hash[hash_long(val, hash_bits)];
  74
  75         n->val = val;
  76         n->hits = 1;
  77         flist_add_tail(&n->list, l);
  78         return n;
  79 }
  80
  81 static int parse_options(int argc, char *argv[])
  82 {
  83         const char *optstring = "t:g:i:o:b:p:";
  84         int c, dist_val_set = 0;
  85
  86         while ((c = getopt(argc, argv, optstring)) != -1) {
  87                 switch (c) {
  88                 case 'p':
  89                         percentage = atof(optarg);
  90                         break;
  91                 case 'b':
  92                         block_size = strtoul(optarg, NULL, 10);
  93                         break;
  94                 case 't':
  95                         if (!strncmp(optarg, "zipf", 4))
  96                                 dist_type = TYPE_ZIPF;
  97                         else if (!strncmp(optarg, "pareto", 6))
  98                                 dist_type = TYPE_PARETO;
  99                         else {
 100                                 printf("wrong dist type: %s\n", optarg);
 101                                 return 1;
 102                         }
 103                         break;
 104                 case 'g':
 105                         gb_size = strtoul(optarg, NULL, 10);
 106                         break;
 107                 case 'i':
 108                         dist_val = atof(optarg);
 109                         dist_val_set = 1;
 110                         break;
 111                 case 'o':
 112                         output_nranges = strtoul(optarg, NULL, 10);
 113                         break;
 114                 default:
 115                         printf("bad option %c\n", c);
 116                         return 1;
 117                 }
 118         }
 119
 120         if (dist_type == TYPE_PARETO) {
 121                 if ((dist_val >= 1.00 || dist_val < 0.00)) {
 122                         printf("pareto input must be > 0.00 and < 1.00\n");
 123                         return 1;
 124                 }
 125                 if (!dist_val_set)
 126                         dist_val = DEF_PARETO_VAL;
 127         } else if (dist_type == TYPE_ZIPF) {
 128                 if (dist_val == 1.0) {
 129                         printf("zipf input must be different than 1.0\n");
 130                         return 1;
 131                 }
 132                 if (!dist_val_set)
 133                         dist_val = DEF_ZIPF_VAL;
 134         }
 135
 136         return 0;
 137 }
 138
 139 struct output_sum {
 140         double output;
 141         unsigned int nranges;
 142 };
 143
 144 static int node_cmp(const void *p1, const void *p2)
 145 {
 146         const struct node *n1 = p1;
 147         const struct node *n2 = p2;
 148
 149         return n2->hits - n1->hits;
 150 }
 151
 152 int main(int argc, char *argv[])
 153 {
 154         unsigned long offset;
 155         unsigned long i, j, k, nr_vals, cur_vals, interval, total_vals, nnodes;
 156         unsigned long long nranges;
 157         struct output_sum *output_sums;
 158         struct node *nodes;
 159         double perc, perc_i;
 160         struct zipf_state zs;
 161
 162         if (parse_options(argc, argv))
 163                 return 1;
 164
 165         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);
 166
 167         nranges = gb_size * 1024 * 1024 * 1024ULL;
 168         nranges /= block_size;
 169
 170         if (dist_type == TYPE_ZIPF)
 171                 zipf_init(&zs, nranges, dist_val, 1);
 172         else
 173                 pareto_init(&zs, nranges, dist_val, 1);
 174
 175         hash_bits = 0;
 176         hash_size = nranges;
 177         while ((hash_size >>= 1) != 0)
 178                 hash_bits++;
 179
 180         hash_size = 1 << hash_bits;
 181
 182         hash = malloc(hash_size * sizeof(struct flist_head));
 183         for (i = 0; i < hash_size; i++)
 184                 INIT_FLIST_HEAD(&hash[i]);
 185
 186         nodes = malloc(nranges * sizeof(struct node));
 187
 188         for (nr_vals = i = j = 0; i < nranges; i++) {
 189                 struct node *n;
 190
 191                 if (dist_type == TYPE_ZIPF)
 192                         offset = zipf_next(&zs);
 193                 else
 194                         offset = pareto_next(&zs);
 195
 196                 n = hash_lookup(offset);
 197                 if (n)
 198                         n->hits++;
 199                 else {
 200                         hash_insert(&nodes[j], offset);
 201                         j++;
 202                 }
 203
 204                 nr_vals++;
 205         }
 206
 207         qsort(nodes, j, sizeof(struct node), node_cmp);
 208         nnodes = j;
 209         nr_vals = nnodes;
 210
 211         interval = (nr_vals + output_nranges - 1) / output_nranges;
 212
 213         output_sums = malloc(output_nranges * sizeof(struct output_sum));
 214         for (i = 0; i < output_nranges; i++) {
 215                 output_sums[i].output = 0.0;
 216                 output_sums[i].nranges = 1;
 217         }
 218
 219         total_vals = i = j = cur_vals = 0;
 220
 221         for (k = 0; k < nnodes; k++) {
 222                 struct output_sum *os = &output_sums[j];
 223                 struct node *node = &nodes[k];
 224
 225                 if (i >= interval) {
 226                         os->output = (double) (cur_vals + 1) / (double) nranges;
 227                         os->output *= 100.0;
 228                         j++;
 229                         cur_vals = node->hits;
 230                         interval += (nr_vals + output_nranges - 1) / output_nranges;
 231                 } else {
 232                         cur_vals += node->hits;
 233                         os->nranges += node->hits;
 234                 }
 235
 236                 i++;
 237                 total_vals += node->hits;
 238
 239                 if (percentage) {
 240                         unsigned long blocks = percentage * nranges / 100;
 241
 242                         if (total_vals >= blocks) {
 243                                 double cs = i * block_size / (1024 * 1024);
 244                                 char p = 'M';
 245
 246                                 if (cs > 1024.0) {
 247                                         cs /= 1024.0;
 248                                         p = 'G';
 249                                 }
 250                                 if (cs > 1024.0) {
 251                                         cs /= 1024.0;
 252                                         p = 'T';
 253                                 }
 254
 255                                 printf("%.2f%% of hits satisfied in %.3f%cB of cache\n", percentage, cs, p);
 256                                 percentage = 0.0;
 257                         }
 258                 }
 259         }
 260
 261         perc_i = 100.0 / (double) output_nranges;
 262         perc = 0.0;
 263
 264         printf("\n   Rows           Hits           No Hits         Size\n");
 265         printf("--------------------------------------------------------\n");
 266         for (i = 0; i < j; i++) {
 267                 struct output_sum *os = &output_sums[i];
 268                 double gb = (double) os->nranges * block_size / 1024.0;
 269                 char p = 'K';
 270
 271                 if (gb > 1024.0) {
 272                         p = 'M';
 273                         gb /= 1024.0;
 274                 }
 275                 if (gb > 1024.0) {
 276                         p = 'G';
 277                         gb /= 1024.0;
 278                 }
 279
 280                 perc += perc_i;
 281                 printf("%s %6.2f%%\t%6.2f%%\t\t%8u\t%6.2f%c\n", i ? "|->" : "Top", perc, os->output, os->nranges, gb, p);
 282         }
 283
 284         free(output_sums);
 285         free(hash);
 286         return 0;
 287 }