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 25 #define DEF_NR 1000000 26 #define DEF_NR_OUTPUT 23 27 28 struct node { 29 struct flist_head list; 30 unsigned long long val; 31 unsigned long hits; 32 }; 33 34 static struct flist_head *hash; 35 static unsigned long hash_bits = 24; 36 static unsigned long hash_size = 1 << 24; 37 38 enum { 39 TYPE_NONE = 0, 40 TYPE_ZIPF, 41 TYPE_PARETO, 42 }; 43 static const char *dist_types[] = { "None", "Zipf", "Pareto" }; 44 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; 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 void usage(void) 82 { 83 printf("genzipf: test zipf/pareto values for fio input\n"); 84 printf("\t-h\tThis help screen\n"); 85 printf("\t-p\tGenerate size of data set that are hit by this percentage\n"); 86 printf("\t-t\tDistribution type (zipf or pareto)\n"); 87 printf("\t-i\tDistribution algorithm input (zipf theta or pareto power)\n"); 88 printf("\t-b\tBlock size of a given range (in bytes)\n"); 89 printf("\t-g\tSize of data set (in gigabytes)\n"); 90 printf("\t-o\tNumber of output columns\n"); 91 printf("\t-c\tOutput ranges in CSV format\n"); 92 } 93 94 static int parse_options(int argc, char *argv[]) 95 { 96 const char *optstring = "t:g:i:o:b:p:ch"; 97 int c, dist_val_set = 0; 98 99 while ((c = getopt(argc, argv, optstring)) != -1) { 100 switch (c) { 101 case 'h': 102 usage(); 103 return 1; 104 case 'p': 105 percentage = atof(optarg); 106 break; 107 case 'b': 108 block_size = strtoul(optarg, NULL, 10); 109 break; 110 case 't': 111 if (!strncmp(optarg, "zipf", 4)) 112 dist_type = TYPE_ZIPF; 113 else if (!strncmp(optarg, "pareto", 6)) 114 dist_type = TYPE_PARETO; 115 else { 116 printf("wrong dist type: %s\n", optarg); 117 return 1; 118 } 119 break; 120 case 'g': 121 gb_size = strtoul(optarg, NULL, 10); 122 break; 123 case 'i': 124 dist_val = atof(optarg); 125 dist_val_set = 1; 126 break; 127 case 'o': 128 output_nranges = strtoul(optarg, NULL, 10); 129 break; 130 case 'c': 131 output_csv = 1; 132 break; 133 default: 134 printf("bad option %c\n", c); 135 return 1; 136 } 137 } 138 139 if (dist_type == TYPE_PARETO) { 140 if ((dist_val >= 1.00 || dist_val < 0.00)) { 141 printf("pareto input must be > 0.00 and < 1.00\n"); 142 return 1; 143 } 144 if (!dist_val_set) 145 dist_val = DEF_PARETO_VAL; 146 } else if (dist_type == TYPE_ZIPF) { 147 if (dist_val == 1.0) { 148 printf("zipf input must be different than 1.0\n"); 149 return 1; 150 } 151 if (!dist_val_set) 152 dist_val = DEF_ZIPF_VAL; 153 } 154 155 return 0; 156 } 157 158 struct output_sum { 159 double output; 160 unsigned int nranges; 161 }; 162 163 static int node_cmp(const void *p1, const void *p2) 164 { 165 const struct node *n1 = p1; 166 const struct node *n2 = p2; 167 168 return n2->hits - n1->hits; 169 } 170 171 int main(int argc, char *argv[]) 172 { 173 unsigned long offset; 174 unsigned long i, j, k, nr_vals, cur_vals, interval, total_vals, nnodes; 175 unsigned long long nranges; 176 struct output_sum *output_sums; 177 struct node *nodes; 178 double perc, perc_i; 179 struct zipf_state zs; 180 181 if (parse_options(argc, argv)) 182 return 1; 183 184 if( !output_csv ) 185 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); 186 187 nranges = gb_size * 1024 * 1024 * 1024ULL; 188 nranges /= block_size; 189 190 if (dist_type == TYPE_ZIPF) 191 zipf_init(&zs, nranges, dist_val, 1); 192 else 193 pareto_init(&zs, nranges, dist_val, 1); 194 195 hash_bits = 0; 196 hash_size = nranges; 197 while ((hash_size >>= 1) != 0) 198 hash_bits++; 199 200 hash_size = 1 << hash_bits; 201 202 hash = malloc(hash_size * sizeof(struct flist_head)); 203 for (i = 0; i < hash_size; i++) 204 INIT_FLIST_HEAD(&hash[i]); 205 206 nodes = malloc(nranges * sizeof(struct node)); 207 208 for (nr_vals = i = j = 0; i < nranges; i++) { 209 struct node *n; 210 211 if (dist_type == TYPE_ZIPF) 212 offset = zipf_next(&zs); 213 else 214 offset = pareto_next(&zs); 215 216 n = hash_lookup(offset); 217 if (n) 218 n->hits++; 219 else { 220 hash_insert(&nodes[j], offset); 221 j++; 222 } 223 224 nr_vals++; 225 } 226 227 qsort(nodes, j, sizeof(struct node), node_cmp); 228 nnodes = j; 229 nr_vals = nnodes; 230 231 if (output_csv) { 232 printf("rank, count\n"); 233 for (k = 0; k < nnodes; k++) 234 printf("%lu, %lu\n", k, nodes[k].hits); 235 } else { 236 interval = (nr_vals + output_nranges - 1) / output_nranges; 237 238 output_sums = malloc(output_nranges * sizeof(struct output_sum)); 239 for (i = 0; i < output_nranges; i++) { 240 output_sums[i].output = 0.0; 241 output_sums[i].nranges = 1; 242 } 243 244 total_vals = i = j = cur_vals = 0; 245 246 for (k = 0; k < nnodes; k++) { 247 struct output_sum *os = &output_sums[j]; 248 struct node *node = &nodes[k]; 249 250 if (i >= interval) { 251 os->output = 252 (double)(cur_vals + 1) / (double)nranges; 253 os->output *= 100.0; 254 j++; 255 cur_vals = node->hits; 256 interval += 257 (nr_vals + output_nranges - 258 1) / output_nranges; 259 } else { 260 cur_vals += node->hits; 261 os->nranges += node->hits; 262 } 263 264 i++; 265 total_vals += node->hits; 266 267 if (percentage) { 268 unsigned long blocks = 269 percentage * nranges / 100; 270 271 if (total_vals >= blocks) { 272 double cs = 273 i * block_size / (1024 * 1024); 274 char p = 'M'; 275 276 if (cs > 1024.0) { 277 cs /= 1024.0; 278 p = 'G'; 279 } 280 if (cs > 1024.0) { 281 cs /= 1024.0; 282 p = 'T'; 283 } 284 285 printf("%.2f%% of hits satisfied in %.3f%cB of cache\n", percentage, cs, p); 286 percentage = 0.0; 287 } 288 } 289 } 290 291 perc_i = 100.0 / (double)output_nranges; 292 perc = 0.0; 293 294 printf("\n Rows Hits No Hits Size\n"); 295 printf("--------------------------------------------------------\n"); 296 for (i = 0; i < j; i++) { 297 struct output_sum *os = &output_sums[i]; 298 double gb = (double)os->nranges * block_size / 1024.0; 299 char p = 'K'; 300 301 if (gb > 1024.0) { 302 p = 'M'; 303 gb /= 1024.0; 304 } 305 if (gb > 1024.0) { 306 p = 'G'; 307 gb /= 1024.0; 308 } 309 310 perc += perc_i; 311 printf("%s %6.2f%%\t%6.2f%%\t\t%8u\t%6.2f%c\n", 312 i ? "|->" : "Top", perc, os->output, os->nranges, 313 gb, p); 314 } 315 316 free(output_sums); 317 } 318 319 free(hash); 320 free(nodes); 321 return 0; 322 } 323
