From: Willy Tarreau <willy@w.ods.org>
To: Thomas Schlichter <schlicht@uni-mannheim.de>
Cc: dphillips@sistina.com, hugang <hugang@soulinfo.com>,
linux-kernel@vger.kernel.org
Subject: Re: [RFC][PATCH] Faster generic_fls
Date: Fri, 2 May 2003 15:24:06 +0200 [thread overview]
Message-ID: <20030502132406.GB1803@alpha.home.local> (raw)
In-Reply-To: <200305020347.42682.schlicht@uni-mannheim.de>
On Fri, May 02, 2003 at 03:47:37AM +0200, Thomas Schlichter wrote:
> That is what I posted in my first message in this thread... The shift
> algorithm only works fine for uniform distributed input values... But here is
> a version that behaves better for small values, too. I don't think it will
> reach the tree version but it should be much better that the old version!
I also tried to change your version into this, and at least it's not slower,
so it's good anyway, considering the small code size.
> If this is the case the tree version will surely be the best!
>
> But I think this topic is not worth any further work as this is not used very
> often... So this version will be my last one!
I agree. Just for the record, I'll post two other original implementations
which are not intersting for their real-life performance, but may be
interesting to reuse in other projects or in cheap hardware implementations,
or as a base for other algos. One of the downsides is that they need many
registers. They both are about twice as slow as the tree on athlon, alpha and
sparc.
The first one uses no jump at all if the CPU can do CMOV. It's about twice as
slow as tree, but may be a win on machines with a big jump cost. And since
there's no jump, its execution time is constant :
unsigned fls32_1(unsigned n)
{
/* this code is totally jumpless on architectures that support CMOV,
and can execute up to 4 instructions per cycle. However, it uses
lots of instructions and registers and is not as fast as it should be.
It's about 20 cycles on a dual-pipeline CPU.
*/
register unsigned x = n, bits = 0, bits2, a, b;
a = x & 0xffff0000;
bits2 = bits + 16;
b = x & 0xff00ff00;
if (x & a) { bits = bits2;}
if (x & a) { x &= a;}
bits2 = bits + 8;
a = x & 0xf0f0f0f0;
if (x & b) { bits = bits2;}
if (x & b) { x &= b;}
bits2 = bits + 4;
b = x & 0xcccccccc;
if (x & a) { bits = bits2;}
if (x & a) { x &= a;}
bits2 = bits + 2;
a = x & 0xaaaaaaaa;
if (x & b) { bits = bits2;}
if (x & b) { x &= b;}
bits2 = bits + 1;
if (x & a) { bits = bits2;}
if (x & a) { x &= a;}
if (x) { bits += 1; }
return bits;
}
The second one has a radically different approach. It converges int 5 shifts.
However, each iteration has a non neglileable cost, and its time is nearly
constant too. The code is rather small (about 70 bytes), but it needs a CPU
which can shift and jump fast to be efficient. It consumes about the same
time as above.
unsigned fls32_2(unsigned n)
{
register unsigned t = 16, r = 0;
register unsigned m = 0xffff0000;
// it only needs 5 iterations to complete, and some
// instructions can be executed in parallel. It's
// more efficient than the pure shift on small values.
// But it needs many registers :-(
if (n) {
while (t) {
if (n & m) {
n >>= t;
r += t;
t >>= 1;
m >>= t;
} else {
n <<= t;
t >>= 1;
m <<= t ? t : 1;
}
}
return r + 1;
}
else
return n;
}
These were my last versions, and not particularly performant ones ;-)
Regards,
Willy
next prev parent reply other threads:[~2003-05-02 13:12 UTC|newest]
Thread overview: 65+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-04-30 2:46 Daniel Phillips
2003-04-30 7:19 ` Willy Tarreau
2003-04-30 8:36 ` Aaron Lehmann
2003-04-30 8:43 ` Aaron Lehmann
2003-04-30 8:52 ` Aaron Lehmann
2003-04-30 8:51 ` P
2003-04-30 13:51 ` Daniel Phillips
2003-04-30 11:14 ` Falk Hueffner
2003-04-30 13:03 ` Daniel Phillips
2003-04-30 13:17 ` Falk Hueffner
2003-04-30 14:07 ` Daniel Phillips
2003-04-30 14:11 ` Linus Torvalds
2003-04-30 14:53 ` Falk Hueffner
2003-04-30 15:28 ` Linus Torvalds
2003-04-30 16:03 ` Falk Hueffner
2003-04-30 16:16 ` Linus Torvalds
2003-04-30 16:43 ` Falk Hueffner
2003-04-30 20:25 ` Alan Cox
2003-04-30 21:59 ` Falk Hueffner
2003-04-30 22:22 ` Alan Cox
2003-04-30 23:41 ` Linus Torvalds
2003-04-30 22:47 ` Alan Cox
2003-05-01 0:12 ` Falk Hueffner
2003-05-01 1:07 ` Linus Torvalds
2003-04-30 19:15 ` Daniel Phillips
2003-04-30 20:59 ` Willy Tarreau
2003-05-01 1:02 ` Daniel Phillips
2003-05-01 9:19 ` Willy Tarreau
2003-05-01 16:02 ` Linus Torvalds
2003-04-30 20:55 ` Andrew Morton
2003-05-01 5:03 ` hugang
2003-05-01 5:11 ` Andrew Morton
2003-05-01 5:33 ` hugang
2003-05-01 7:05 ` hugang
2003-05-01 13:52 ` Willy TARREAU
2003-05-01 14:14 ` Falk Hueffner
2003-05-01 14:26 ` Willy TARREAU
2003-05-01 14:53 ` hugang
2003-05-01 15:54 ` Thomas Schlichter
2003-05-02 0:33 ` hugang
2003-05-01 17:16 ` Willy TARREAU
2003-05-01 23:27 ` Thomas Schlichter
2003-05-02 0:10 ` Willy Tarreau
2003-05-02 0:43 ` Daniel Phillips
2003-05-02 0:54 ` Andrew Morton
2003-05-02 12:21 ` Daniel Phillips
2003-05-02 1:47 ` Thomas Schlichter
2003-05-02 13:24 ` Willy Tarreau [this message]
2003-05-02 0:13 ` Daniel Phillips
2003-05-02 0:13 ` Lincoln Dale
2003-05-01 5:16 ` hugang
2003-05-01 10:22 ` Willy TARREAU
2003-05-01 11:17 ` hugang
2003-05-01 11:45 ` Willy TARREAU
[not found] <87d6j34jad.fsf@student.uni-tuebingen.de.suse.lists.linux.kernel>
[not found] ` <Pine.LNX.4.44.0304301801210.20283-100000@home.transmeta.com.suse.lists.linux.kernel>
2003-05-01 1:46 ` Andi Kleen
2003-05-01 4:40 ` Linus Torvalds
2003-05-01 12:00 ` David S. Miller
2003-05-02 5:14 ` Linus Torvalds
2003-05-01 13:31 linux
2003-05-01 17:15 Chuck Ebbert
2003-05-02 8:50 Chuck Ebbert
2003-05-02 9:37 ` Peter Osterlund
2003-05-02 10:04 Chuck Ebbert
2003-05-02 22:55 ` David S. Miller
2003-05-03 2:21 Chuck Ebbert
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20030502132406.GB1803@alpha.home.local \
--to=willy@w.ods.org \
--cc=dphillips@sistina.com \
--cc=hugang@soulinfo.com \
--cc=linux-kernel@vger.kernel.org \
--cc=schlicht@uni-mannheim.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®