OpenImageIO/oiio — pull request #449 by lgritz (2012-11-02 18:20:54+00:00)
Title: Improved tile cache hashing function

I added some good hashing functions from xxhash and Bob Jenkins to hash.h (implementations for the non-inlined parts in libutil/hashes.cpp). Both are really good hashes, and are BSD and public domain, respectively. The Jenkins one is about 30% faster than xxhash for short keys (I timed with 8-byte keys), but xxhash is fantastically faster (an order of magnitude or more) for really long keys (I tested 4000-byte keys). So it seems like we have room for both in our toolkit, depending on expected key sizes.

I also added a new test to testtex that creates a tile ID for every 64x64 tile of a hypothetical 4k x 4k file, for each of hundreds of files named "00000.tif", "00001.tif", etc. Then it keeps a histogram of the number that would fall into each bin of a hash tables of 4, 8, or 16 bits worth of buckets. A good hash function should end up with the histogram counts as even as possible.

As it turns out, the tile hash I was using was not very good -- in this stress test, it sometimes had wide disparities between buckets with the lowest and highest counts (varying by 2x or more compared to the expected average). By replacing with a call to 'bjfinal', I was able to greatly improve the hash bucket utilization (all hash buckets were within about 10% of the expected average), and it's still pretty fast.

In theory, this should improve hash map performance in the tile cache. In practice, testing on a few production scenes, I'm seeing no significant change in overall performance. But I'd like to commit it, because it's easy to imagine pathological file naming or tile access patterns that would fall into the cases where the old hash function performed poorly. Also, it's probably helpful to have those functions available in libutil for future uses.

I've tested on Linux and OSX. It would be really helpful if somebody using Windows could pull this patch and just make sure it gets a clean compile, before I commit to master.