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