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, 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;
}
===========

it returns the right result. Compiled with gcc 2.95.3 -march=i686 -O3, athlon
1.533 GHz (1800+) :

4294967295 iterations of new... checksum = 4294967265

real 1m6.182s
user 1m6.060s
sys 0m0.133s
4294967295 iterations of new2... checksum = 4294967265

real 0m36.504s
user 0m36.294s
sys 0m0.202s
4294967295 iterations of fls_table... checksum = 4294967295

real 0m21.962s
user 0m21.833s
sys 0m0.124s
4294967295 iterations of fls_tbl... checksum = 4294967265

real 0m19.268s
user 0m19.102s
sys 0m0.168s

The same compiled with gcc-3.2.3 :

4294967295 iterations of fls_table... checksum = 4294967295

real 0m14.211s
user 0m14.210s
sys 0m0.000s

Cheers,
Willy

-
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.135 / U:0.420 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site