Messages in this thread | | | Date | Wed, 7 Apr 1999 17:39:47 -0400 (EDT) | From | Chuck Lever <> | Subject | more on hash functions |
| |
i've set up a 2.2.5 kernel with some test hash functions to see what kind of improvement is available with hash tweaking. i tweaked the page hash function by changing PAGE_HASH_BITS to 13 (haven't tried +offset yet), and replaced the buffer hash function with one of my own devising.
these tests were run on a dual 200Mhz PPro with 128M RAM and 2 10M/s SCSI drivers. i've seen similar results on my 233Mhz K6 and a P-II laptop. i will also test on a half-gig machine.
after some intensive memory and file activity (no swapping, though), the page hash looks like this:
Apr 7 16:55:27 pillbox kernel: Total pages in hash: 9664 total buckets: 8192 Apr 7 16:55:27 pillbox kernel: hash table histogram: Apr 7 16:55:27 pillbox kernel: size: 0 buckets: 2521 pages: 0 Apr 7 16:55:27 pillbox kernel: size: 1 buckets: 2976 pages: 2976 Apr 7 16:55:27 pillbox kernel: size: 2 buckets: 1732 pages: 3464 Apr 7 16:55:27 pillbox kernel: size: 3 buckets: 691 pages: 2073 Apr 7 16:55:27 pillbox kernel: size: 4 buckets: 215 pages: 860 Apr 7 16:55:27 pillbox kernel: size: 5 buckets: 51 pages: 255 Apr 7 16:55:27 pillbox kernel: size: 6 buckets: 6 pages: 36 Apr 7 16:55:27 pillbox kernel: size: 7 buckets: 0 pages: 0 Apr 7 16:55:27 pillbox kernel: size: 8 buckets: 0 pages: 0 Apr 7 16:55:27 pillbox kernel: size: 9 buckets: 0 pages: 0 Apr 7 16:55:27 pillbox kernel: size: 10 buckets: 0 pages: 0 Apr 7 16:55:27 pillbox kernel: size: 11 buckets: 0 pages: 0 Apr 7 16:55:27 pillbox kernel: size: 12 buckets: 0 pages: 0 Apr 7 16:55:27 pillbox kernel: size: 13 buckets: 0 pages: 0 Apr 7 16:55:27 pillbox kernel: size: 14 buckets: 0 pages: 0 Apr 7 16:55:27 pillbox kernel: size: 15 buckets: 0 pages: 0 Apr 7 16:55:27 pillbox kernel: size:>15 buckets: 0 pages: 0 Apr 7 16:55:27 pillbox kernel: Max bucket size: 6 Apr 7 16:55:27 pillbox kernel: Total lookups: 4568709 pages found: 4083164 (hit rate: 89%) Apr 7 16:55:27 pillbox kernel: find_page loops: 2322162 loops/lookup: 508/1000
as you can see, this is lots better than the 11 bit hash. in order to test Doug's varying hash table patch, i'll need to test 11, 12, 13, 14, 15 bits, and so on. also with +offset. i tried a little of this last night at home, and noticed that even numbered bits (12 and 14) don't work as well as 11 and 13.
the buffer hash function i used is this:
#define _hashfn(dev,block) \ ((((unsigned long)(block) * (40499UL * 65543UL)) >> 17) & bh_hash_mask)
this is the same number of instructions as the old function, except that one of the instructions is IMUL. i haven't looked up how expensive this might be. however, i believe a fixed expense is better than a higher loops/lookup average, since IMUL with a constant multiplier doesn't incur any memory overhead once it's in the instruction cache, whereas an extra iteration of find_buffer might be another 2 memory references, either or both of which might be cache misses.
and the size histogram produced is this:
Apr 7 16:55:27 pillbox kernel: total buffers in hash table: 13009 Apr 7 16:55:27 pillbox kernel: total buckets: 32768 largest: 7 Apr 7 16:55:27 pillbox kernel: times find_buffer looped: 1652176 loops/lookup: 933/1000 Apr 7 16:55:27 pillbox kernel: hash table histogram: Apr 7 16:55:27 pillbox kernel: size: 0 buckets: 23539 buffers: 0 Apr 7 16:55:27 pillbox kernel: size: 1 buckets: 6571 buffers: 6571 Apr 7 16:55:27 pillbox kernel: size: 2 buckets: 1899 buffers: 3798 Apr 7 16:55:27 pillbox kernel: size: 3 buckets: 559 buffers: 1677 Apr 7 16:55:27 pillbox kernel: size: 4 buckets: 102 buffers: 408 Apr 7 16:55:27 pillbox kernel: size: 5 buckets: 39 buffers: 195 Apr 7 16:55:27 pillbox kernel: size: 6 buckets: 53 buffers: 318 Apr 7 16:55:27 pillbox kernel: size: 7 buckets: 6 buffers: 42 Apr 7 16:55:27 pillbox kernel: size: 8 buckets: 0 buffers: 0 Apr 7 16:55:27 pillbox kernel: size: 9 buckets: 0 buffers: 0 Apr 7 16:55:27 pillbox kernel: size: 10 buckets: 0 buffers: 0 Apr 7 16:55:27 pillbox kernel: size: 11 buckets: 0 buffers: 0 Apr 7 16:55:27 pillbox kernel: size: 12 buckets: 0 buffers: 0 Apr 7 16:55:27 pillbox kernel: size: 13 buckets: 0 buffers: 0 Apr 7 16:55:27 pillbox kernel: size: 14 buckets: 0 buffers: 0 Apr 7 16:55:27 pillbox kernel: size: 15 buckets: 0 buffers: 0 Apr 7 16:55:27 pillbox kernel: size:>15 buckets: 0 buffers: 0
a significant improvement over the previous hash, in terms of bucket size distribution. in fact this function is so much better, we can reduce the size of the hash table by 2 or even 4 times and get equal throughput. even so, notice that loops/lookup is still high. the cache hit rate is 81%, so most of those loops are for successful lookups. would it help to move a bucket entry to the front of the list after a successful lookup ? i tried this, and it doesn't appear to help.
i have a full-blown patch that replaces the inode, dentry, fib, buffer, uid, and pid hashes with the simple function listed above. in general, the system feels more responsive, and throughput appears the same or slightly better than an unpatched system. when i've finished testing the page hash stuff, i'll include that and post the full patch.
how it works:
/* * Based on Knuth, "The Art of Computer Programming", Vol. 3 * Searching and Sorting, pp. 513-549. * * Essentially, multiplication by a number that is relatively * prime to the word-size of the computer results in division * by its reciprocal, modulus the machine' word size. We * select a number that is a golden ratio with the machine's * word size, as that has certain desirable properties for * hashing, as discussed in Knuth. * * (HASH_MULTIPLIER / word-size) ~= ((sqrt(5) - 1) / 2) * * A better approximation to the golden ratio could be chosen than below, * but this works sufficiently well. * * 40499 and 65543 are both prime, guaranteeing that HASH_MULTIPLIER * is relatively prime to 2^32, and doesn't exhibit certain side effects * that might occur if we used small primes. Note that HASH_MULTIPLIER * itself doesn't need to be prime; it simply needs to be relatively prime * to the machine's word size. I haven't tested how well it works * with 64-bit machines, but evidence suggests it will do well. */ #define HASH_MULTIPLIER (40499UL * 65543UL)
/* this is a typical hash function using Knuth's idea */ #define shash_function(key, range) \ ((((unsigned long)(key) * HASH_MULTIPLIER) >> 17) & ((range) - 1))
- Chuck Lever -- corporate: <chuckl@netscape.com> personal: <chucklever@netscape.net> or <cel@monkey.org>
The Linux Scalability project: http://www.citi.umich.edu/projects/citi-netscape/
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |