Messages in this thread | | | Date | Tue, 8 Jan 2002 19:20:27 +0000 (GMT) | From | Hugh Dickins <> | Subject | Re: hashed waitqueues |
| |
On Tue, 8 Jan 2002, William Lee Irwin III wrote: > On January 5, 2002 02:39 am, William Lee Irwin III wrote: > >>> 2 or 3 shift/adds is really not possible, the population counts of the > >>> primes in those ranges tends to be high, much to my chagrin. > > On Sat, Jan 05, 2002 at 03:44:06AM +0100, Daniel Phillips wrote: > >> It doesn't really have to be a prime, being relatively prime is also > >> good, i.e., not too many or too small factors. Surely there's a multiplier > >> in the right range with just two prime factors that can be computed with 3 > >> shift-adds. > > The (theoretically) best 64-bit prime with 5 high bits I found is: > > 11673330234145374209 == 0xa200000000100001 > which has continued fraction of p/2^64 > = 0,1,1,1,2,1,1,1,1,1,1,1073740799,2,1,1,1,1,6,1,1,5,1023,1,4,1,1,3,3 > > and the (theoretically) best 64-bit prime with 4 high bits I found is: > 11529215046068994049 == 0xa000000000080001 > which has continued fraction of p/2^64 > = 0,1,1,1,2,549754765313,1,1,1,1,1,4095,2,1,1,1,1,2,1,2 > > (the continued fractions terminate after the points given here) > > Which of the two would be better should depend on whether the penalty > against the distribution for the sixth term of the 4-bit prime is worse > than the computational expense of the extra shift/add for the 5-bit prime. > > I need to start benching this stuff.
Why is all this sophistication needed for hashing pages to wait queues? I understand that you should avoid a stupid hash (such as one where all pages end up on the same wait queue), and I understand why a cache needs a well-chosen hash, and I understand why shift is preferred to multiply; but I don't get why so much discussion of the precise hash for choosing the wait queue of a page: aren't the waits rare, and the pages mostly well-distributed anyway?
Hugh
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |