Messages in this thread | | | Date | Thu, 1 May 2003 19:17:30 +0800 | From | hugang <> | Subject | Re: [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/
| |