Re: [libvirt] [PATCH] Replace hashing algorithm with murmurhash

On 01/18/2012 09:23 AM, Daniel P. Berrange wrote: > @@ -1636,9 +1637,10 @@ cleanup: > } > > > -static unsigned long virCgroupPidCode(const void *name) > +static int32_t virCgroupPidCode(const void *name, int32_t seed) > { > - return (unsigned long)name; > + unsigned long pid = (unsigned long)name; > + return virHashCodeGen(&pid, sizeof(pid), seed); I'm not sure if it matters, but you could shorten these two lines to just one: return virHashCodeGen(&name, sizeof(unsigned long), seed);

> @@ -101,11 +95,10 @@ static void virHashStrFree(void *name) > VIR_FREE(name); > } > > - > static unsigned long > virHashComputeKey(virHashTablePtr table, const void *name) > { > - unsigned long value = table->keyCode(name); > + uint32_t value = table->keyCode(name, table->seed); > return (value % table->size); If, on a 64-bit machine, table->size ever grows larger than uint32_t, then we've lost some hashing abilities compared to what the old unsigned long hash gave us. Conversely, if table-size ever grows that large, we're burning an awful lot of memory in the first place, and a hash collision at that point is the least of our worries :) I think this is okay, although you may want to consider changing virHashComputeKey to return uint32_t.

> +++ b/src/util/hash.h > @@ -55,12 +55,15 @@ typedef int (*virHashSearcher) (const void *payload, const void *name, > /** > * virHashKeyCode: > * @name: the hash key > + * @seed: random seed > * > - * Compute the hash code corresponding to the key @name > + * Compute the hash code corresponding to the key @name, using > + * @seed to perturb the hashing algorithm > * > * Returns the hash code > */ > -typedef unsigned long (*virHashKeyCode)(const void *name); > +typedef int32_t (*virHashKeyCode)(const void *name, > + int32_t seed); Umm, you used uint32_t in virHashComputeKey, but int32_t here. While I don't _think_ signed values will bite us due to sign-extension in 64-bit operations introducing a bias, I'd rather make this signature: typedef uint32_t (*virHashKeyCode)(const void *name, uint32_t seed); and adjust the callers to comply with unsigned everywhere.

That is, I propose that we ditch virRandom, and instead implement a new function: /* Return an evenly distributed random number between [0,2^nbits), where nbits must be in the range (0,64]. */ uint64_t virRandomBits(int nbits) { int bits_per_iter = count_one_bits(RAND_MAX); uint64_t ret = 0; int32_t bits; /* This algorithm requires that RAND_MAX == 2^n-1 for some n; gnulib's random_r meets this property. */ verify(((RAND_MAX + 1U) & RAND_MAX) == 0); virMutexLock(&randomLock); while (nbits > bits_per_iter) { random_r(&randomData, &bits); ret = (ret << bits_per_iter) | (bits & RAND_MAX); nbits -= bits_per_iter; } random_r(&randomData, &bits); ret = (ret << nbits) | (bits & ((1 << nbits) - 1)); virMutexUnlock(&randomLock); return ret; } where existing calls to virRandom(256) will now be virRandomBits(8), virRandom(1024*1024*1024) will now be virRandomBits(30), and your code would use uint32_t seed = virRandom(32).

> +#include "virhashcode.h" > + > +static uint32_t rotl(uint32_t x, int8_t r) > +{ > + return (x << r) | (x >> (32 - r)); > +} Gnulib provides the bitrotate module, which provides "bitrotate.h" and an implementation of this function that is guaranteed to be as efficient as possible when compiled by gcc (possibly by using compiler-builtins to access raw assembly on architectures that have builtin rotate instructions). I'd suggest using that rather than rolling your own.

> + > +/* slower than original but is endian neutral and handles platforms that > + * do only aligned reads */ > +__attribute__((always_inline)) > +static uint32_t getblock(const uint8_t *p, int i) > +{ > + uint32_t r; > + size_t size = sizeof(uint32_t); > + > + memcpy(&r, &p[i * size], size); > + > + return le32toh(r); <endian.h>, and thus le32toh(), is not yet standardized (although POSIX will be adding it in the future), nor is it currently provided by gnulib. We'd have to get that fixed first.