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