The following changes since commit 660879102e32a0ed3d3225afaebcc0d46625a4a6: Merge branch 'master' of https://github.com/bvanassche/fio (2022-06-23 08:20:22 -0600) are available in the Git repository at: git://git.kernel.dk/fio.git master for you to fetch changes up to dc4729e3ef6a9116d7cd30e96e4f5863883e5bd7: hash: cleanups (2022-07-01 15:03:39 -0600) ---------------------------------------------------------------- Georg Sauthoff (1): Simplify and optimize __fill_random_buf Jens Axboe (3): Merge branch 'fill-random-smaller' of https://github.com/gsauthof/fio lib/rand: improve __fill_random_buf() hash: cleanups engines/rdma.c | 2 +- hash.h | 26 -------------------------- lib/rand.c | 30 +++++++++--------------------- 3 files changed, 10 insertions(+), 48 deletions(-) --- Diff of recent changes: diff --git a/engines/rdma.c b/engines/rdma.c index e3bb2567..fcb41068 100644 --- a/engines/rdma.c +++ b/engines/rdma.c @@ -1389,7 +1389,7 @@ static int fio_rdmaio_setup(struct thread_data *td) rd = malloc(sizeof(*rd)); memset(rd, 0, sizeof(*rd)); - init_rand_seed(&rd->rand_state, (unsigned int) GOLDEN_RATIO_PRIME, 0); + init_rand_seed(&rd->rand_state, (unsigned int) GOLDEN_RATIO_64, 0); td->io_ops_data = rd; } diff --git a/hash.h b/hash.h index f7596a56..51f0706e 100644 --- a/hash.h +++ b/hash.h @@ -9,32 +9,6 @@ (C) 2002 William Lee Irwin III, IBM */ /* - * Knuth recommends primes in approximately golden ratio to the maximum - * integer representable by a machine word for multiplicative hashing. - * Chuck Lever verified the effectiveness of this technique: - * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf - * - * These primes are chosen to be bit-sparse, that is operations on - * them can use shifts and additions instead of multiplications for - * machines where multiplications are slow. - */ - -#if BITS_PER_LONG == 32 -/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */ -#define GOLDEN_RATIO_PRIME 0x9e370001UL -#elif BITS_PER_LONG == 64 -/* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */ -#define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL -#else -#error Define GOLDEN_RATIO_PRIME for your wordsize. -#endif - -/* - * The above primes are actively bad for hashing, since they are - * too sparse. The 32-bit one is mostly ok, the 64-bit one causes - * real problems. Besides, the "prime" part is pointless for the - * multiplicative hash. - * * Although a random odd number will do, it turns out that the golden * ratio phi = (sqrt(5)-1)/2, or its negative, has particularly nice * properties. diff --git a/lib/rand.c b/lib/rand.c index 6e893e80..1e669116 100644 --- a/lib/rand.c +++ b/lib/rand.c @@ -97,29 +97,17 @@ void init_rand_seed(struct frand_state *state, uint64_t seed, bool use64) void __fill_random_buf(void *buf, unsigned int len, uint64_t seed) { - void *ptr = buf; + uint64_t *b = buf; + uint64_t *e = b + len / sizeof(*b); + unsigned int rest = len % sizeof(*b); - while (len) { - int this_len; - - if (len >= sizeof(int64_t)) { - *((int64_t *) ptr) = seed; - this_len = sizeof(int64_t); - } else if (len >= sizeof(int32_t)) { - *((int32_t *) ptr) = seed; - this_len = sizeof(int32_t); - } else if (len >= sizeof(int16_t)) { - *((int16_t *) ptr) = seed; - this_len = sizeof(int16_t); - } else { - *((int8_t *) ptr) = seed; - this_len = sizeof(int8_t); - } - ptr += this_len; - len -= this_len; - seed *= GOLDEN_RATIO_PRIME; - seed >>= 3; + for (; b != e; ++b) { + *b = seed; + seed = __hash_u64(seed); } + + if (fio_unlikely(rest)) + __builtin_memcpy(e, &seed, rest); } uint64_t fill_random_buf(struct frand_state *fs, void *buf,
