lkml.org 
[lkml]   [2002]   [Feb]   [18]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH] [rmap] operator-sparse Fibonacci hashing of waitqueues
On February 17, 2002 10:01 am, William Lee Irwin III wrote:
>> After distilling with hpa's help the results of some weeks-old
>> numerological experiments^W^Wnumber crunching, I've devised a patch
>> here for -rmap to make the waitqueue hashing somewhat more palatable
>> for SPARC and several others.
>>
>> This patch uses some operator-sparse Fibonacci hashing primes in order
>> to allow shift/add implementations of the hash function used for hashed
>> waitqueues.
>>
>> Dan, Dave, could you take a look here and please comment?

On Mon, Feb 18, 2002 at 11:31:15PM +0100, Daniel Phillips wrote:
> Could you explain in very simple terms, suitable for Aunt Tillie (ok, not
> *that* simple) how the continued fraction works, how it's notated, and how
> the terms of the expansion relate to good performance as a hash?

Do you want it just in a post or in-line?

Here's the posted brief version:

Numbers have "integer parts" and "fractional parts", for instance, if
you have a number such as 10 1/2 (ten and one half) the integer part
is 10 and the fractional part is 1/2. The fractional part of a number
x is written {x}.

Now, there is something called the "spectrum" of a number, which for
a number x is the set of all the numbers of the form n * x, where n
is an integer. So we have {1*x}, {2*x}, {3*x}, and so on.

If we want to measure how well a number distributes things we can try
to see how uniform the spectrum is as a distribution. There is a
theorem which states the "most uniform" distribution results from the
number phi = (sqrt(5)-1)/2, which is related to Fibonacci numbers.

The continued fraction of phi is

0 + 1
-----
1 + 1
-----
1 + 1
-----
1 + 1
-----
1 + 1
...

where it's 1's all the way down. Some additional study also revealed
that how close the continued fraction of a number is to phi is related
to how uniform the spectrum is. For brevity, I write continued fractions
in-line, for instance, 0,1,1,1,1,... for phi, or 0,1,2,3,4,... for

0 + 1
-----
1 + 2
-----
1 + 3
-----
1 + 4
....

One way to evaluate these is to "chop off" the fraction at some point
(for instance, where I put ...) and then reduce it like an ordinary
fraction expression.

Fibonacci hashing considers the number p/2^n where n is BITS_PER_LONG
and p is a prime number, and this is supposed to have a relationship
to how evenly-distributed all the n-bit numbers multiplied by p in
n-bit arithmetic are. Which is where the hash functions come in, since
you want hash functions to evenly distribute things. There are reasons
why primes are better, too.

And I think that covers most of what you had in mind.

In my own opinion, this stuff borders on numerology, but it seems to be
a convenient supply of hash functions that pass chi^2 tests on the
bucket distributions, so I sort of tolerate it. If I'm not using a strict
enough test then I'm all ears...

Cheers,
Bill
-
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:24    [W:0.116 / U:0.020 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site