ffs() arch optimization

[tqh]

Our ffs can be optimized at least for x86. Providing a test-program based on FreeBsd's ffs. No real implementation as I don't know how you want to do arch optimizations and fallbacks.

On newer x86, it can even be done in two ops with cmov, but that would require runtime configuration which might be overkill. Other platforms tries to inline function as well.

[tqh]

x86 ffs optimization

[tqh]

Learning by doing :) Might have missed something in the patch, but it works fine here.

[tqh]

This patch may be overkill though and the function just defined in the arch_string.S, I just wanted to learn to be able to go all the way to runtime cpu-optimized functions.

[tqh]

Final version?

[axeld]

I guess that's better on your plate now :-)

[jackburton]

Also check out this one: ​http://osdir.com/ml/solaris.opensolaris.performance/2006-01/msg00000.html

Hi,

Not sure if this can be of any interest, but I noticed the ffs function is
implemented using a loop.

A faster implementation exists using the "pcount" assembler instruction (where
available and fast - this does not seem to be the case on all processors), or
through another algorithm using only a few instructions.

Check out: http://supertech.csail.mit.edu/papers/debruijn.pdf

For a 32-bit word, the optimized function could be written this way:

int
ffs(int field)
{
static const int index[] = { 1, 2, 29, 3, 30, 15, 25, 4, 31, 23, 21,
16, 26, 18, 5, 9, 32, 28, 14, 24, 22, 20, 17, 8, 27, 13, 19, 7, 12, 6, 11, 10 };
unsigned int w = field;
if (w == 0)
return (0);
w &= -w;
w *= 125613361U;
w >>= 27;
return index[w];
}

Regards,
Olivier.
This message posted from opensolaris.org

[tqh]

It's faster as long as the result is 9 or higher.

[korli]

I'd prefer to let GCC use its built-in ffs (I mean at least on GCC 4).

[tqh]

Sounds like a plan. Other OS'es seem to try to inline functions like these, it would be nice to try to reduce function overhead on all these small helper functions. Any ideas in this regard or experiments to perform?

[tqh]

Updated test with new example, and also with builtin version.

[tqh]

For gcc 4 builtin_ffs is always at least twice as fast. It should probably be ok on gcc2.95 as well. Should we just change the header to #define ffs(x) builtin_ffs(x) ?
Since we use gcc on other archs it should work there as well.

[waddlesplash]

Reverting earlier milestone change

[waddlesplash]

Fix merged in hrev54145.

[nielx]

Assign tickets with status=closed and resolution=fixed within the R1/beta2 development window to the R1/beta2 Milestone