Skip to content

Optimize GCD performance on RISC-V by selecting implementation at runtime

Kuan-Wei Chiu linux-riscv lkml 2 versions – Applied

Status from this message: This series was applied to riscv/linux.git (fixes)

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v3 Latest3 patches 4 repliesApplied 3/3
  2. v23 patches 2 repliesSuperseded

Changes in v3 from the cover letter

- Drop if (!a || !b) check in binary_gcd()
- Move DECLARE_STATIC_KEY_TRUE(efficient_ffs_key) to gcd.h v1 -> v2:
- Use a static key to select the GCD implementation at runtime.

Patches in v3 All 3 applied

#Subject and filesSizeRepliesApplied
1/3lib/math/gcd: Use static key to select implementation at runtimeinclude/linux/gcd.h lib/math/gcd.c+18 -120 repliesApplied
2/3riscv: Optimize gcd() code size when CONFIG_RISCV_ISA_ZBB is disabledarch/riscv/Kconfig+1 -01 replyApplied
3/3riscv: Optimize gcd() performance on RISC-V without Zbb extensionarch/riscv/kernel/setup.c+5 -01 replyApplied

Reviews trailers per patch

2 of 3 patches have a Reviewed-by or Acked-by.

PatchAlexandre Ghiti
1/3
2/3A-b
3/3A-b

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v3 thread

Cover letter [PATCH v3 0/3] Optimize GCD performance on RISC-V by selecting implementation at runtime

The current implementation of gcd() selects between the binary GCD and the odd-even GCD algorithm at compile time, depending on whether CONFIG_CPU_NO_EFFICIENT_FFS is set. On platforms like RISC-V, however, this compile-time decision can be misleading: even when the compiler emits ctz instructions based on the assumption that they are efficient (as is the case when CONFIG_RISCV_ISA_ZBB is enabled), the actual hardware may lack support for the Zbb extension. In such cases, ffs() falls back to a software implementation at runtime, making the binary GCD algorithm significantly slower than the odd-even variant.

To address this, we introduce a static key to allow runtime selection between the binary and odd-even GCD implementations. On RISC-V, the kernel now checks for Zbb support during boot. If Zbb is unavailable, the static key is disabled so that gcd() consistently uses the more efficient odd-even algorithm in that scenario. Additionally, to further reduce code size, we select CONFIG_CPU_NO_EFFICIENT_FFS automatically when CONFIG_RISCV_ISA_ZBB is not enabled, avoiding compilation of the unused binary GCD implementation entirely on systems where it would never be executed.

This series ensures that the most efficient GCD algorithm is used in practice and avoids compiling unnecessary code based on hardware capabilities and kernel configuration.

---
This series has been tested on QEMU to verify that the correct GCD implementation is used both with and without Zbb support.

v2 -> v3:
- Drop if (!a || !b) check in binary_gcd()
- Move DECLARE_STATIC_KEY_TRUE(efficient_ffs_key) to gcd.h v1 -> v2:
- Use a static key to select the GCD implementation at runtime.

v2: https://lore.kernel.org/lkml/[email protected]/
v1: https://lore.kernel.org/lkml/[email protected]/

Kuan-Wei Chiu (3):
lib/math/gcd: Use static key to select implementation at runtime
riscv: Optimize gcd() code size when CONFIG_RISCV_ISA_ZBB is disabled
riscv: Optimize gcd() performance on RISC-V without Zbb extension

 arch/riscv/Kconfig        |  1 +
 arch/riscv/kernel/setup.c |  5 +++++
 include/linux/gcd.h       |  3 +++
 lib/math/gcd.c            | 27 +++++++++++++++------------
 4 files changed, 24 insertions(+), 12 deletions(-)
Signature · 1 line
2.34.1