Commit | Line | Data |
---|---|---|
e25839d4 JA |
1 | #include <math.h> |
2 | #include <string.h> | |
3 | #include <inttypes.h> | |
4 | #include <stdio.h> | |
5 | #include <unistd.h> | |
6 | #include <sys/types.h> | |
7 | #include <fcntl.h> | |
8 | #include "ieee754.h" | |
9 | #include "../log.h" | |
10 | #include "zipf.h" | |
11 | #include "../minmax.h" | |
ed1860cd | 12 | #include "../hash.h" |
e25839d4 | 13 | |
4c9060e3 | 14 | #define ZIPF_MAX_GEN 10000000 |
e25839d4 JA |
15 | |
16 | static void zipf_update(struct zipf_state *zs) | |
17 | { | |
4c9060e3 | 18 | unsigned long to_gen; |
e25839d4 JA |
19 | unsigned int i; |
20 | ||
21 | log_info("fio: generating zetan for theta=%f, ranges=%lu\n", zs->theta, zs->nranges); | |
22 | ||
4c9060e3 JA |
23 | /* |
24 | * It can become very costly to generate long sequences. Just cap it at | |
25 | * 10M max, that should be doable in 1-2s on even slow machines. Precision | |
26 | * will take a slight hit, but nothing major. | |
27 | */ | |
28 | to_gen = min(zs->nranges, ZIPF_MAX_GEN); | |
e25839d4 | 29 | |
4c9060e3 JA |
30 | for (i = 0; i < to_gen; i++) |
31 | zs->zetan += pow(1.0 / (double) (i + 1), zs->theta); | |
e25839d4 JA |
32 | } |
33 | ||
2316296a JA |
34 | static void shared_rand_init(struct zipf_state *zs, unsigned long nranges, |
35 | unsigned int seed) | |
b2b0b753 JA |
36 | { |
37 | memset(zs, 0, sizeof(*zs)); | |
38 | zs->nranges = nranges; | |
39 | ||
2316296a | 40 | init_rand_seed(&zs->rand, seed); |
b2b0b753 JA |
41 | zs->rand_off = __rand(&zs->rand); |
42 | } | |
43 | ||
2316296a JA |
44 | void zipf_init(struct zipf_state *zs, unsigned long nranges, double theta, |
45 | unsigned int seed) | |
e25839d4 | 46 | { |
2316296a | 47 | shared_rand_init(zs, nranges, seed); |
e25839d4 | 48 | |
e25839d4 | 49 | zs->theta = theta; |
1442ba18 | 50 | zs->zeta2 = pow(1.0, zs->theta) + pow(0.5, zs->theta); |
e25839d4 | 51 | |
4c9060e3 | 52 | zipf_update(zs); |
e25839d4 JA |
53 | } |
54 | ||
55 | unsigned long long zipf_next(struct zipf_state *zs) | |
56 | { | |
e25839d4 JA |
57 | double alpha, eta, rand_uni, rand_z; |
58 | unsigned long long n = zs->nranges; | |
59 | unsigned long long val; | |
60 | ||
61 | alpha = 1.0 / (1.0 - zs->theta); | |
62 | eta = (1.0 - pow(2.0 / n, 1.0 - zs->theta)) / (1.0 - zs->zeta2 / zs->zetan); | |
63 | ||
64 | rand_uni = (double) __rand(&zs->rand) / (double) FRAND_MAX; | |
65 | rand_z = rand_uni * zs->zetan; | |
66 | ||
67 | if (rand_z < 1.0) | |
68 | val = 1; | |
69 | else if (rand_z < (1.0 + pow(0.5, zs->theta))) | |
70 | val = 2; | |
71 | else | |
72 | val = 1 + (unsigned long long)(n * pow(eta*rand_uni - eta + 1.0, alpha)); | |
73 | ||
b2b0b753 | 74 | return (__hash_long(val - 1) + zs->rand_off) % zs->nranges; |
e25839d4 | 75 | } |
925fee33 | 76 | |
2316296a JA |
77 | void pareto_init(struct zipf_state *zs, unsigned long nranges, double h, |
78 | unsigned int seed) | |
925fee33 | 79 | { |
2316296a | 80 | shared_rand_init(zs, nranges, seed); |
925fee33 | 81 | zs->pareto_pow = log(h) / log(1.0 - h); |
925fee33 JA |
82 | } |
83 | ||
84 | unsigned long long pareto_next(struct zipf_state *zs) | |
85 | { | |
86 | double rand = (double) __rand(&zs->rand) / (double) FRAND_MAX; | |
87 | unsigned long long n = zs->nranges - 1; | |
88 | ||
b2b0b753 | 89 | return (__hash_long(n * pow(rand, zs->pareto_pow)) + zs->rand_off) % zs->nranges; |
925fee33 | 90 | } |