| | 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" |
| | 12 | #include "../hash.h" |
| | 13 | |
| | 14 | #define ZIPF_MAX_GEN 10000000UL |
| | 15 | |
| | 16 | static void zipf_update(struct zipf_state *zs) |
| | 17 | { |
| | 18 | unsigned long to_gen; |
| | 19 | unsigned int i; |
| | 20 | |
| | 21 | /* |
| | 22 | * It can become very costly to generate long sequences. Just cap it at |
| | 23 | * 10M max, that should be doable in 1-2s on even slow machines. |
| | 24 | * Precision will take a slight hit, but nothing major. |
| | 25 | */ |
| | 26 | to_gen = min(zs->nranges, (uint64_t) ZIPF_MAX_GEN); |
| | 27 | |
| | 28 | for (i = 0; i < to_gen; i++) |
| | 29 | zs->zetan += pow(1.0 / (double) (i + 1), zs->theta); |
| | 30 | } |
| | 31 | |
| | 32 | static void shared_rand_init(struct zipf_state *zs, unsigned long nranges, |
| | 33 | unsigned int seed) |
| | 34 | { |
| | 35 | memset(zs, 0, sizeof(*zs)); |
| | 36 | zs->nranges = nranges; |
| | 37 | |
| | 38 | init_rand_seed(&zs->rand, seed, 0); |
| | 39 | zs->rand_off = __rand(&zs->rand); |
| | 40 | } |
| | 41 | |
| | 42 | void zipf_init(struct zipf_state *zs, unsigned long nranges, double theta, |
| | 43 | unsigned int seed) |
| | 44 | { |
| | 45 | shared_rand_init(zs, nranges, seed); |
| | 46 | |
| | 47 | zs->theta = theta; |
| | 48 | zs->zeta2 = pow(1.0, zs->theta) + pow(0.5, zs->theta); |
| | 49 | |
| | 50 | zipf_update(zs); |
| | 51 | } |
| | 52 | |
| | 53 | unsigned long long zipf_next(struct zipf_state *zs) |
| | 54 | { |
| | 55 | double alpha, eta, rand_uni, rand_z; |
| | 56 | unsigned long long n = zs->nranges; |
| | 57 | unsigned long long val; |
| | 58 | |
| | 59 | alpha = 1.0 / (1.0 - zs->theta); |
| | 60 | eta = (1.0 - pow(2.0 / n, 1.0 - zs->theta)) / (1.0 - zs->zeta2 / zs->zetan); |
| | 61 | |
| | 62 | rand_uni = (double) __rand(&zs->rand) / (double) FRAND32_MAX; |
| | 63 | rand_z = rand_uni * zs->zetan; |
| | 64 | |
| | 65 | if (rand_z < 1.0) |
| | 66 | val = 1; |
| | 67 | else if (rand_z < (1.0 + pow(0.5, zs->theta))) |
| | 68 | val = 2; |
| | 69 | else |
| | 70 | val = 1 + (unsigned long long)(n * pow(eta*rand_uni - eta + 1.0, alpha)); |
| | 71 | |
| | 72 | val--; |
| | 73 | |
| | 74 | if (!zs->disable_hash) |
| | 75 | val = __hash_u64(val); |
| | 76 | |
| | 77 | return (val + zs->rand_off) % zs->nranges; |
| | 78 | } |
| | 79 | |
| | 80 | void pareto_init(struct zipf_state *zs, unsigned long nranges, double h, |
| | 81 | unsigned int seed) |
| | 82 | { |
| | 83 | shared_rand_init(zs, nranges, seed); |
| | 84 | zs->pareto_pow = log(h) / log(1.0 - h); |
| | 85 | } |
| | 86 | |
| | 87 | unsigned long long pareto_next(struct zipf_state *zs) |
| | 88 | { |
| | 89 | double rand = (double) __rand(&zs->rand) / (double) FRAND32_MAX; |
| | 90 | unsigned long long n; |
| | 91 | |
| | 92 | n = (zs->nranges - 1) * pow(rand, zs->pareto_pow); |
| | 93 | |
| | 94 | if (!zs->disable_hash) |
| | 95 | n = __hash_u64(n); |
| | 96 | |
| | 97 | return (n + zs->rand_off) % zs->nranges; |
| | 98 | } |
| | 99 | |
| | 100 | void zipf_disable_hash(struct zipf_state *zs) |
| | 101 | { |
| | 102 | zs->disable_hash = true; |
| | 103 | } |
projects / fio.git / blame_incremental