Re: [RFC][PATCH] Faster generic_fls

[hugang <hugang@soulinfo.com>]

On Thu, 1 May 2003 12:22:30 +0200
Willy TARREAU <willy@w.ods.org> wrote:

> On Thu, May 01, 2003 at 01:16:05PM +0800, hugang wrote:
> 
> > Here is table version of the fls. Yes it fast than other.
> 
> Sorry, but this code returns wrong results. Test it with less
> iterations, it doesn't return the same result.
> 
> >         unsigned i = 0;
> > 
> >         do {
> >                 i++;
> >         } while (n <= fls_table[i].max && n > fls_table[i].min);
> 
> You never even compare with table[0] !
> 
> > --test log is here----
> 
> I recoded a table based on your idea, and it's clearly faster than others, and
> even faster than yours :
> 
> ============
> static unsigned tbl[33] = { 2147483648, 1073741824, 536870912, 268435456,
> 			    134217728, 67108864, 33554432, 16777216,
> 			    8388608, 4194304, 2097152, 1048576,
> 			    524288, 262144, 131072, 65536,
> 			    32768, 16384, 8192, 4096,
> 			    2048, 1024, 512, 256,
> 			    128, 64, 32, 16,
> 			    8, 4, 2, 1, 0 };
> 
> 
> static inline int fls_tbl_fls(unsigned n)
> {
>         unsigned i = 0;
> 
> 	while (n < tbl[i])
> 	    i++;
> 
>         return 32 - i;
> }
> ===========

Do see the mail by Andrew Morton? -----

From: Andrew Morton <akpm@digeo.com>
To: hugang <hugang@soulinfo.com>
Cc: linux-kernel@vger.kernel.org
Subject: Re: [RFC][PATCH] Faster generic_fls
Date: Wed, 30 Apr 2003 22:11:29 -0700
Sender: linux-kernel-owner@vger.kernel.org
X-Mailer: Sylpheed version 0.8.11 (GTK+ 1.2.10; i586-pc-linux-gnu)

 hugang <hugang@soulinfo.com> wrote:
 >
 > Here is table version of the fls. Yes it fast than other.

 nooo..  That has a big cache footprint.  At the very least you should use
 a binary search.  gcc will do it for you:

 	switch (n) {
 	case 0 ... 1:
 		return 1;
 	case 2 ... 3:
 		return 2;
 	case 4 ... 7:
 		return 3;
 	case 8 ... 15:
 		return 4;

 etc.
----------
I agree him, The Lastest code my posted has works fine, Please check it.

-- 
Hu Gang / Steve
Email        : huagng@soulinfo.com, steve@soulinfo.com
GPG FinePrint: 4099 3F1D AE01 1817 68F7  D499 A6C2 C418 86C8 610E
ICQ#         : 205800361
Registered Linux User : 204016