[lkml]   [2002]   [Jan]   [8]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: 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?


To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at
Please read the FAQ at

 \ /
  Last update: 2005-03-22 13:15    [W:0.136 / U:25.300 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site