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 - 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/
This archive was generated by hypermail 2b29 : Wed May 07 2003 - 22:00:12 EST