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/