lkml.org 
[lkml]   [2003]   [Apr]   [30]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [RFC][PATCH] Faster generic_fls
On Wed, Apr 30, 2003 at 09:15:33PM +0200, Daniel Phillips wrote:

> In the dawn of time, before God gave us Cache, my version would have been the
> fastest, because it executes the fewest instructions. In the misty future,
> as cache continues to scale and processors sprout more parallel execution
> units, it will be clearly better once again.

Daniel,

I must acknowledge that your simple code was not easy to beat ! You can try this
one on your PIII, I could only test it on an athlon mobile and a P4. With gcc 2.95.3,
it gives me a boost of about 25%, because it seems as gcc cannot optimize shifts
efficiently. On 3.2.3, however, it's between 0 and 5% depending on optimization/CPU.

But the code is a lot smaller (about 105 bytes total for the function). I could also
code a version with parallel execution of several branches, but it was slower,
because every branch not taken was computed for nothing, and the glue around it had
a cost. I tried to implement it with as many booleans as possible so that the compiler
can try to emit conditionnal instructions and make use of carries. I did operations
on an unsigned char because it has some advantages, such as 0x80 being negative ;-)

I also let the other tests in, so that you can try them if you want. Looking through
the generated code, it's clear that an assembler version would be faster. Not much,
but a bit.

Cheers,
Willy

static inline
unsigned new2_fls32(unsigned n32)
{
unsigned t = 0;
unsigned char n;

if (n32 >> 16) {
n32 >>= 16;
t = 16;
}

n = n32;
if (n32 >> 8) {
n = (unsigned char)(n32 >> 8);
t += 8;
}
#if 0
else
if (!n) return t;
// this one uses comparisons and jumps, but is short and fast
return (n < 0x10) ?
t + ((n < 0x04) ? 2 - (n < 0x02) : 4 - (n < 0x08)) :
t + ((n < 0x40) ? 6 - (n < 0x20) : 8 - (n < 0x80)) ;
#endif
#if 0
// this one compiles into several parallel branches, but is slower
if (n < 0x10) {
return t += (n < 0x04) ? n - ((n + 1) >> 2) : 4 - (n < 8);
} else {
return t += (n < 0x40) ? 6 - (n < 0x20) : 8 - (n < 0x80) ;
}
#endif
#if 0
// the same as above
return t += (n < 0x10) ? (n < 0x04) ? n - ((n + 1) >> 2) : 4 - (n < 8) :
(n < 0x40) ? 6 - (n < 0x20) : 8 - (n < 0x80) ;
#endif
#if 1
// this one uses comparisons and jumps, but is short and the fastest
return (n < 0x10) ?
(n < 0x04) ? n + t - ((n + 1) >> 2) : 4 + t - (n < 8) :
(n < 0x40) ? 6 + t - (n < 0x20) : 8 + t - (n < 0x80) ;
#endif
}

-
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.137 / U:28.960 seconds]
©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site