Re: [PATCH] bitops/32: Convert variable_ffs() and fls() zero-case handling to C

[Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>]

On Mon, 28 Apr 2025 at 00:14, Ingo Molnar <mingo@xxxxxxxxxx> wrote:
>
> And, just out of intellectual curiosity, I also tried to measure the
> code generation price of the +1 standards-quirk in the fls()/ffs()
> interface as well:
>
> ... and unless I messed up the patch, it seems to have a surprisingly
> low impact - maybe because the compiler can amortize its cost by
> adjusting all dependent code mostly at build time, so the +1 doesn't
> end up being generated most of the time?

No, I think one issue is that most users actually end up subtracting
one from the return value of 'ffs()', because the "bit #0 returns 1"
semantics of the standard ffs() function really is insane.

It's not just that it doesn't match sane hardware, it's also that it
doesn't match sane *users*. If bit #0 is set, people want '0', so they
typically subtract 1.

So when you stop adding one, you aren't actually removing code -
you're often adding it.

Just see how many hits you get from

    git grep '\<ffs(.*).*-.*1'

which is obviously not a very precise pattern, but just look at the
output and see just *how* common that "subtract one" thing is.

I really don't understand how anybody *ever* thought that the whole
"return one bigger" was a good idea for ffs().

Sure, I understand that zero is special and needs a special return
value, but returning a negative value would have been pretty simple
(or just do what our bitops finding functions do, which is to return
past the end, which is often convenient but does tend to make the
error condition check a bit more complex).

Anyway, the fact that so many users subtract one means that your "look
at the size of the binary" model doesn't work. You're counting both
the wins (when that addition doesn't happen) and the losses (when the
"subtract one in the user" happens).

So the "+1" doesn't cause much code generation - as long as it's done
by the compiler that can also undo it - but it's just a horrid user
interface.

But maybe people really were poisoned by the Pascal mindset. Or maybe
it was invented by some ancient Roman who hadn't heard of the concept
of zero. Who knows?

               Linus