Re: hashed waitqueues

[William Lee Irwin III <wli@holomorphy.com>]

On Tue, 8 Jan 2002, William Lee Irwin III wrote:
>> I need to start benching this stuff.

On Tue, Jan 08, 2002 at 07:20:27PM +0000, Hugh Dickins wrote:
> 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?

All this "sophistication" boils down to a single number, perhaps a single
#define. I'd at least like to put some thought into it, at the very least
as due diligence. And also I want to be able to answer the question of
"Where did the number come from?"

It doesn't really require that much effort, either. The non-bitsparse
golden ratio prime was just looked up in Chuck Lever's paper, and the
criteria I'm using to determine potentially useful bitsparse factors
(aside from sparsity itself) are largely from Knuth, who (paraphrasing)
says the important characteristic is the first several terms in the
continued fraction expansion of p/w, where w is the wordsize.

And the sieving "algorithm" is just me asking a couple of people how
they'd do it, and the sieve took well under a minute to run, and maybe
5 or 10 minutes to write.

And if it doesn't matter to you, please remember anyway that when I
wrote my hash functions I did put some thought into it.


Thanks,
Bill