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

    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/

    \
     
     \ /
      Last update: 2005-03-22 13:15    [W:0.023 / U:30.724 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site