radix_trie: eliminate iteration in keydiff
ClosedPublic
Actions

Authored by dougm on Jun 17 2023, 6:20 PM.

Details

Reviewers

alc
markj

Commits

rG05963ea4d130: radix_trie: eliminate iteration in keydiff

Summary

The implementations of *_keydiff iterate. By using flsl(), they don't have to.

If flsl() is implemented as a loop, though, this is a loss. Of particular concern is behavior on riscv, where the standard loop implementations of ffs, fls, etc appear to be in place. The change proposed at https://reviews.freebsd.org/D40594 seems like it ought to replace the loops with __builtin_ffs and the like, but I don't see obvious benefits (the presence of ctz and clz opcodes in objdump output) from this change after building a riscv kernel.

Mark, do you have any suggestions on how to (or who could) get ffs and fls inlined on riscv?

Test Plan

Kernel boots.

Diff Detail

Lint

Lint Skipped

Unit

Tests Skipped

Event Timeline

dougm requested review of this revision.Jun 17 2023, 6:20 PM

dougm created this revision.

dougm edited the summary of this revision. (Show Details)Jun 19 2023, 7:47 AM

dougm added a subscriber: markj.

The change proposed at https://reviews.freebsd.org/D40594 seems like it ought to replace the loops with __builtin_ffs and the like, but I don't see obvious benefits (the presence of ctz and clz opcodes in objdump output) from this change after building a riscv kernel.

Mark, do you have any suggestions on how to (or who could) get ffs and fls inlined on riscv?

Those instructions are not part of the base ISA, but instead belong to one of a set of ratified "bit-manipulation" extensions. There appears to be some LLVM support for them but I'm not sure how to turn it on, and presumably we don't want to do that for GENERIC kernels? @jrtc27 or @mhorne could possibly say more.

In D40585#924441, @markj wrote:

The change proposed at https://reviews.freebsd.org/D40594 seems like it ought to replace the loops with __builtin_ffs and the like, but I don't see obvious benefits (the presence of ctz and clz opcodes in objdump output) from this change after building a riscv kernel.

Mark, do you have any suggestions on how to (or who could) get ffs and fls inlined on riscv?

Those instructions are not part of the base ISA, but instead belong to one of a set of ratified "bit-manipulation" extensions. There appears to be some LLVM support for them but I'm not sure how to turn it on, and presumably we don't want to do that for GENERIC kernels? @jrtc27 or @mhorne could possibly say more.