From: Daniel Phillips <dphillips@sistina.com>
Reply-To: dphillips@sistina.com
Organization: Sistina
To: Willy Tarreau <willy@w.ods.org>,
       Thomas Schlichter <schlicht@uni-mannheim.de>
Subject: Re: [RFC][PATCH] Faster generic_fls
Date: Fri, 2 May 2003 02:43:15 +0200
User-Agent: KMail/1.5.1
Cc: Willy TARREAU <willy@w.ods.org>, hugang <hugang@soulinfo.com>,
       linux-kernel@vger.kernel.org, akpm@digeo.com
References: <200304300446.24330.dphillips@sistina.com> <200305020127.26279.schlicht@uni-mannheim.de> <20030502001050.GA25789@alpha.home.local>
In-Reply-To: <20030502001050.GA25789@alpha.home.local>
MIME-Version: 1.0
Content-Type: text/plain;
  charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Message-Id: <200305020243.15248.dphillips@sistina.com>
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 1163
Lines: 26

On Friday 02 May 2003 02:10, Willy Tarreau wrote:
> At first, I thought you had coded an FFS instead of an FLS. But I realized
> it's valid, and is fast because one half of the numbers tested will not even
> take one iteration.

Aha, and duh.  At 1 million iterations, my binary search clobbers the shift 
version by a factor of four.  At 2**31 iterations, my version also wins, by 
20%.

I should note that the iterations parameter to my benchmark program is deeply 
flawed, since it changes the nature of the input set, not just the number of 
iterations.  Fortunately, all tests I've done have been with 2**32 
iterations, giving a perfectly uniform distribution of input values.

For uniformly distributed inputs the simple shift loop does well, but for 
calculating floor(log2(x)) it's much worse than the fancier alternatives.  I 
suspect typical usage leans more to the latter than the former.

Regards,

Daniel
-
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/