From dc4729e3ef6a9116d7cd30e96e4f5863883e5bd7 Mon Sep 17 00:00:00 2001 From: Jens Axboe Date: Fri, 1 Jul 2022 15:03:39 -0600 Subject: [PATCH] hash: cleanups - Use __hash_u64() for __fill_random_buffer() - Convert rdma to use GOLDEN_RATIO_64 That's the last user of GOLDEN_RATIO_PRIME, which due to bit sparseness isn't really useful for our purposes. Signed-off-by: Jens Axboe --- engines/rdma.c | 2 +- hash.h | 26 -------------------------- lib/rand.c | 2 +- 3 files changed, 2 insertions(+), 28 deletions(-) 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 1df1a7a0..1e669116 100644 --- a/lib/rand.c +++ b/lib/rand.c @@ -103,7 +103,7 @@ void __fill_random_buf(void *buf, unsigned int len, uint64_t seed) for (; b != e; ++b) { *b = seed; - seed *= GOLDEN_RATIO_64; + seed = __hash_u64(seed); } if (fio_unlikely(rest)) -- 2.25.1