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

On 01/18/2012 09:23 AM, Daniel P. Berrange wrote: Looks like a good idea, but I have to NAK this version of the patch and ask for a v2. Meanwhile, I wonder if gnulib should adopt the murmurhash3 algorithm (but that's a different story for a different list). I'm not sure if it matters, but you could shorten these two lines to just one: return virHashCodeGen(&name, sizeof(unsigned long), seed); 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. 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. Ouch. This means you only get 31 bits of randomness for virRandom(INT32_MAX). But you _want_ 32 bits of randomness, especially since you are storing _virHashTable.seed as uint32_t. Furthermore, this calculation leaves gaps on platforms where RAND_MAX is only the POSIX-mandated minimum of 32767, or 15 bits (thankfully, at least Linux uses RAND_MAX of INT_MAX for 31 bits). Furthermore, this computation is non-uniform for all but a handful of numbers: if you request a max larger than RAND_MAX, then there are some values you cannot get back; if you request a max smaller than RAND_MAX but which is not a power of 2, then floating point division followed by rounding to integers will cause some numbers to be selected more frequently than others. I also note that all existing clients of virRandom() passed in a power of 2 (your use of virRandom(INT_MAX) was the first instance of someone using less than a power of two; and even then, you really did want a power of 2). Since we want to avoid non-uniform distribution, it makes sense to _require_ that you request a max as a power of 2 (that is, you are requesting a certain quantity of random bits), and proceed to do everything without the use of any floating point math. Technically, it is also possible to write a capped random number generator for any range [0,non-power-of-2), by repeatedly querying the generator for random bits between [0,next-power-of-2) and discarding any queries that fall in the range [cap,power-of-2); but no need to add that complexity if we promise to always request a power-of-2 random bits in the first place. 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). 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. <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. -- Eric Blake eblake(a)redhat.com +1-919-301-3266 Libvirt virtualization library http://libvirt.org