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  */
  12 #include <stdio.h>
  13 #include <stdlib.h>
  14 #include <fcntl.h>
  15 #include <string.h>
  16
  17 #include "../lib/zipf.h"
  18
  19 static int val_cmp(const void *p1, const void *p2)
  20 {
  21         const unsigned long *v1 = p1;
  22         const unsigned long *v2 = p2;
  23
  24         return *v1 - *v2;
  25 }
  26
  27 int main(int argc, char *argv[])
  28 {
  29         unsigned long nranges, output_nranges;
  30         unsigned long *vals;
  31         unsigned long i, j, nr_vals, cur_vals, max_val, interval, total;
  32         double *output;
  33         struct zipf_state zs;
  34         int use_zipf;
  35         double val;
  36
  37         if (argc < 4) {
  38                 printf("%s: {zipf,pareto} val values [output ranges]\n", argv[0]);
  39                 return 1;
  40         }
  41
  42         if (!strcmp(argv[1], "zipf"))
  43                 use_zipf = 1;
  44         else if (!strcmp(argv[1], "pareto"))
  45                 use_zipf = 0;
  46         else {
  47                 printf("Bad distribution type <%s>\n", argv[1]);
  48                 return 1;
  49         }
  50
  51         val = atof(argv[2]);
  52         nranges = strtoul(argv[3], NULL, 10);
  53         if (argc == 5)
  54                 output_nranges = strtoul(argv[4], NULL, 10);
  55         else
  56                 output_nranges = nranges;
  57
  58         printf("Generating %s distribution with %f input and %lu ranges\n", use_zipf ? "zipf" : "pareto", val, nranges);
  59         getchar();
  60
  61         if (use_zipf)
  62                 zipf_init(&zs, nranges, val);
  63         else
  64                 pareto_init(&zs, nranges, val);
  65
  66         vals = malloc(nranges * sizeof(unsigned long));
  67
  68         total = max_val = nr_vals = 0;
  69         for (i = 0; i < nranges; i++) {
  70                 if (use_zipf)
  71                         vals[nr_vals] = zipf_next(&zs);
  72                 else
  73                         vals[nr_vals] = pareto_next(&zs);
  74
  75                 if (vals[nr_vals] > max_val)
  76                         max_val = vals[nr_vals];
  77                 nr_vals++;
  78         }
  79
  80         qsort(vals, nr_vals, sizeof(unsigned long), val_cmp);
  81
  82         interval = (max_val + output_nranges - 1) / output_nranges;
  83
  84         output = malloc(output_nranges * sizeof(double));
  85
  86         for (i = j = 0, cur_vals = 1; i < nr_vals; i++) {
  87                 if (vals[i] > interval) {
  88                         output[j] = (double) cur_vals / (double) nr_vals;
  89                         output[j] *= 100.0;
  90                         j++;
  91                         total += cur_vals;
  92                         cur_vals = 1;
  93                         interval += (max_val + output_nranges - 1) / output_nranges;
  94                         continue;
  95                 }
  96                 cur_vals++;
  97         }
  98
  99         output[j] = (double) cur_vals / (double) nr_vals;
 100         output[j] *= 100.0;
 101         j++;
 102         total += cur_vals;
 103
 104         for (i = 0; i < j; i++)
 105                 printf("%.2f%%\n", output[i]);
 106
 107         free(output);
 108         free(vals);
 109         return 0;
 110 }