Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id ; Mon, 18 Feb 2002 19:35:27 -0500 Received: (majordomo@vger.kernel.org) by vger.kernel.org id ; Mon, 18 Feb 2002 19:35:18 -0500 Received: from holomorphy.com ([216.36.33.161]:16015 "EHLO holomorphy") by vger.kernel.org with ESMTP id ; Mon, 18 Feb 2002 19:35:04 -0500 Date: Mon, 18 Feb 2002 16:34:50 -0800 From: William Lee Irwin III To: Daniel Phillips Cc: linux-kernel@vger.kernel.org, riel@surriel.com, davem@redhat.com, rwhron@earthlink.net Subject: Re: [PATCH] [rmap] operator-sparse Fibonacci hashing of waitqueues Message-ID: <20020219003450.GF3511@holomorphy.com> Mail-Followup-To: William Lee Irwin III , Daniel Phillips , linux-kernel@vger.kernel.org, riel@surriel.com, davem@redhat.com, rwhron@earthlink.net In-Reply-To: <20020217090111.GF832@holomorphy.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Description: brief message Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.3.25i Organization: The Domain of Holomorphy Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org 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/