lkml.org 
[lkml]   [2003]   [May]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [RFC][PATCH] Faster generic_fls
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/

\
 
 \ /
  Last update: 2005-03-22 13:35    [W:0.101 / U:0.284 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site