[PATCH] riscv: Add RVV strrchr
daichengrong
daichengrong@iscas.ac.cn
Sun Jun 14 05:41:56 GMT 2026
Hi,
I would like to ping my strrchr optimization patch and provide some
additional performance data.
When I submitted my optimized version on 2026-03-03, the initial RVV
strrchr implementation had not been merged yet. About one week ago, on
2026-06-05, an earlier version was merged, and that is now the current
implementation in the source tree.
I may have missed some context in the review process, so I would like to
better understand the current status and the expected next step for my
pending optimization. My intention is not to question the merge, but to
understand whether the pending version should be rebased and submitted
as an incremental improvement, or whether there are other concerns that
need to be addressed first.
I compared the current implementation from the git tree with the version
from my pending patch.
For strrchr, the cost is not only related to the string length. A simple
model is that strrchr first needs to find the terminating NUL byte, and
then it needs to find the last matching character from the end of the
string. Therefore I used the following effective byte count:
distance = len - pos
If pos is larger than len, I treated it as a no-match case:
distance = len
Then:
effective_bytes = len + distance
For each individual test result, I computed:
CPB_eff = timing / effective_bytes
I then grouped the results into effective-bytes buckets. The small
ranges below 256 bytes are merged into one 0-256 bucket to make the
threshold behavior easier to see.
The winner below is determined by the average time per call, while
CPB_eff is included to show the per-byte efficiency trend.
Bucket N Git_eff New_eff Git_t New_t
-------------------------------------------------
0-256 1086 2.125 2.150 46.753 38.518
winner: pending version is about 1.21x faster
257-511 354 0.298 0.164 118.920 66.162
winner: pending version is about 1.80x faster
512-1023 258 0.286 0.132 193.527 89.087
winner: pending version is about 2.17x faster
1024-2047 216 0.279 0.112 383.950 155.671
winner: pending version is about 2.47x faster
2048-4095 294 0.251 0.099 720.090 289.023
winner: pending version is about 2.49x faster
4096-8191 24 0.174 0.073 710.987 298.913
winner: pending version is about 2.38x faster
Here, Git means the current __strrchr_vector implementation in the
source tree, and New means the __strrchr_vector implementation from my
pending patch. Git_eff/New_eff are computed as timing / effective_bytes.
Git_t/New_t are the average time per call in the benchmark timing unit.
The data shows that the pending version is faster in every effective
bucket on K3. The improvement is small but still positive in the 0-256
bucket, and becomes much more visible from 257 effective bytes onward.
For effective sizes from 512 bytes and above, the pending version is
about 2.17x to 2.49x faster in this benchmark.
Could you please let me know if there are any concerns with the pending
optimization, such as correctness coverage, maintainability, code size,
threshold selection, or benchmark methodology? This would help me
understand whether the patch needs further changes beyond the
performance results shown above.
If the current implementation in the source tree is now the preferred
baseline, I can rebase my patch on top of it and resend it as an
incremental optimization.
Thanks.
> 2026年3月3日 10:58，daichengrong <daichengrong@iscas.ac.cn> 写道：
>
> This patch adds an RVV-optimized implementation of strrchr for RISC-V.
>
> Benchmark results show no noticeable regression on small inputs,
> while delivering clear performance improvements on larger inputs.
>
> Signed-off-by: daichengrong <daichengrong@iscas.ac.cn>
> ---
> sysdeps/riscv/multiarch/strrchr-generic.c | 28 ++++
> sysdeps/riscv/multiarch/strrchr-vector.S | 26 ++++
> sysdeps/riscv/rvv/strrchr.S | 126 ++++++++++++++++++
> .../unix/sysv/linux/riscv/multiarch/Makefile | 3 +
> .../linux/riscv/multiarch/ifunc-impl-list.c | 5 +
> .../unix/sysv/linux/riscv/multiarch/strrchr.c | 59 ++++++++
> 6 files changed, 247 insertions(+)
> create mode 100644 sysdeps/riscv/multiarch/strrchr-generic.c
> create mode 100644 sysdeps/riscv/multiarch/strrchr-vector.S
> create mode 100644 sysdeps/riscv/rvv/strrchr.S
> create mode 100644 sysdeps/unix/sysv/linux/riscv/multiarch/strrchr.c
>
> diff --git a/sysdeps/riscv/multiarch/strrchr-generic.c b/sysdeps/riscv/multiarch/strrchr-generic.c
> new file mode 100644
> index 0000000000..c61c6e1a03
> --- /dev/null
> +++ b/sysdeps/riscv/multiarch/strrchr-generic.c
> @@ -0,0 +1,28 @@
> +/* Re-include the default strrchr implementation.
> + Copyright (C) 2026 Free Software Foundation, Inc.
> + This file is part of the GNU C Library.
> +
> + The GNU C Library is free software; you can redistribute it and/or
> + modify it under the terms of the GNU Lesser General Public
> + License as published by the Free Software Foundation; either
> + version 2.1 of the License, or (at your option) any later version.
> +
> + The GNU C Library is distributed in the hope that it will be useful,
> + but WITHOUT ANY WARRANTY; without even the implied warranty of
> + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> + Lesser General Public License for more details.
> +
> + You should have received a copy of the GNU Lesser General Public
> + License along with the GNU C Library; if not, see
> + <https://www.gnu.org/licenses/>. */
> +
> +#include <string.h>
> +
> +#if IS_IN(libc)
> +# define STRRCHR __strrchr_generic
> +# undef libc_hidden_builtin_def
> +# define libc_hidden_builtin_def(x)
> +# undef weak_alias
> +# define weak_alias(x, x2)
> +# include <string/strrchr.c>
> +#endif
> diff --git a/sysdeps/riscv/multiarch/strrchr-vector.S b/sysdeps/riscv/multiarch/strrchr-vector.S
> new file mode 100644
> index 0000000000..8fef68eae0
> --- /dev/null
> +++ b/sysdeps/riscv/multiarch/strrchr-vector.S
> @@ -0,0 +1,26 @@
> +/* Re-include the RISC-V RVV based strrchr implementation.
> + Copyright (C) 2026 Free Software Foundation, Inc.
> + This file is part of the GNU C Library.
> +
> + The GNU C Library is free software; you can redistribute it and/or
> + modify it under the terms of the GNU Lesser General Public
> + License as published by the Free Software Foundation; either
> + version 2.1 of the License, or (at your option) any later version.
> +
> + The GNU C Library is distributed in the hope that it will be useful,
> + but WITHOUT ANY WARRANTY; without even the implied warranty of
> + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> + Lesser General Public License for more details.
> +
> + You should have received a copy of the GNU Lesser General Public
> + License along with the GNU C Library; if not, see
> + <https://www.gnu.org/licenses/>. */
> +
> +#if IS_IN(libc)
> +# define STRRCHR __strrchr_vector
> +# undef libc_hidden_builtin_def
> +# define libc_hidden_builtin_def(name)
> +# undef weak_alias
> +# define weak_alias(name, alias)
> +# include <sysdeps/riscv/rvv/strrchr.S>
> +#endif
> diff --git a/sysdeps/riscv/rvv/strrchr.S b/sysdeps/riscv/rvv/strrchr.S
> new file mode 100644
> index 0000000000..f1471b2c32
> --- /dev/null
> +++ b/sysdeps/riscv/rvv/strrchr.S
> @@ -0,0 +1,126 @@
> +/* RISC-V RVV zbb based strrchr: find the last instance of a character in a string.
> + Copyright (C) 2026 Free Software Foundation, Inc.
> + This file is part of the GNU C Library.
> +
> + The GNU C Library is free software; you can redistribute it and/or
> + modify it under the terms of the GNU Lesser General Public
> + License as published by the Free Software Foundation; either
> + version 2.1 of the License, or (at your option) any later version.
> +
> + The GNU C Library is distributed in the hope that it will be useful,
> + but WITHOUT ANY WARRANTY; without even the implied warranty of
> + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> + Lesser General Public License for more details.
> +
> + You should have received a copy of the GNU Lesser General Public
> + License along with the GNU C Library; if not, see
> + <https://www.gnu.org/licenses/>. */
> +
> +#include <sysdep.h>
> +#include <sys/asm.h>
> +
> +#ifndef STRRCHR
> +# define STRRCHR strrchr
> +#endif
> +
> +#define str a0
> +#define ch a1
> +#define len a2
> +#define in a3
> +#define match a4
> +#define end a5
> +#define vmask v0
> +#define vmask_t v0.t
> +#define vdata v8
> +#define vmatch_null v16
> +#define vmatch_ch v24
> +
> +#define vindex v16
> +#define vmax v24
> +
> +#define chr_hit t1
> +#define null_hit t2
> +
> +#define cur_vl t0
> +#define tmp t0
> +
> +ENTRY (STRRCHR)
> +.option push
> +.option arch, +v
> +.option arch, +zbb
> + lbu tmp, (str)
> + beq tmp, ch, L(hit_0)
> + beqz ch, L(search_null)
> + add tmp, str, -1
> +L(start):
> + mv match, tmp
> + mv in, str
> + mv cur_vl, zero
> +L(loop):
> + add str, str, cur_vl
> + vsetvli cur_vl, zero, e8, m4, ta, ma
> + vle8ff.v vdata, (str)
> + vmseq.vx vmatch_null, vdata, zero
> + vmseq.vx vmatch_ch, vdata, ch
> + vfirst.m null_hit, vmatch_null
> + vfirst.m chr_hit, vmatch_ch
> +
> + bgez null_hit, L(finish)
> + csrr cur_vl, vl
> + bgez chr_hit, L(update)
> + j L(loop)
> +L(update):
> + add match, str, chr_hit
> + j L(loop)
> +
> +L(finish):
> + mv tmp, zero
> + bltz chr_hit, L(no_update)
> + bgt chr_hit, null_hit, L(no_update)
> + sub tmp, str, match
> + add tmp, tmp, chr_hit
> +L(no_update):
> + add match, match, tmp
> + blt match, in, L(not_found)
> +
> + add end, str, null_hit
> + sub len, end, match
> + vsetvli cur_vl, zero, e8, m4, ta, ma
> + min len, len, cur_vl
> +
> + vsetvli zero, len, e8, m4, ta, ma
> + vle8.v vdata, (match)
> + vmseq.vx vmask, vdata, ch
> + vsetvli zero, zero, e16, m8, ta, ma
> + vid.v vindex
> + vmv.s.x vmax, zero
> + vredmaxu.vs vmax, vindex, vmax, vmask_t
> + vmv.x.s tmp, vmax
> + add str, match, tmp
> + ret
> +
> +L(hit_0):
> + beqz ch, L(ret_0)
> + mv tmp, str
> + j L(start)
> +
> +L(search_null):
> + mv cur_vl, zero
> +L(search_null_loop):
> + add str, str, cur_vl
> + vsetvli cur_vl, zero, e8, m8, ta, ma
> + vle8ff.v vdata, (str)
> + vmseq.vx vmatch_null, vdata, zero
> + vfirst.m null_hit, vmatch_null
> + bltz null_hit, L(search_null_loop)
> + add str, str, null_hit
> + ret
> +
> +L(not_found):
> + li a0, 0
> +L(ret_0):
> + ret
> +.option pop
> +END (STRRCHR)
> +weak_alias (STRRCHR, rindex)
> +libc_hidden_builtin_def (strrchr)
> diff --git a/sysdeps/unix/sysv/linux/riscv/multiarch/Makefile b/sysdeps/unix/sysv/linux/riscv/multiarch/Makefile
> index a865090a53..cd59fb39f3 100644
> --- a/sysdeps/unix/sysv/linux/riscv/multiarch/Makefile
> +++ b/sysdeps/unix/sysv/linux/riscv/multiarch/Makefile
> @@ -6,6 +6,9 @@ sysdep_routines += \
> memset \
> memset-generic \
> memset-vector \
> + strrchr \
> + strrchr-generic \
> + strrchr-vector \
> # sysdep_routines
>
> CFLAGS-memcpy_noalignment.c += -mno-strict-align
> diff --git a/sysdeps/unix/sysv/linux/riscv/multiarch/ifunc-impl-list.c b/sysdeps/unix/sysv/linux/riscv/multiarch/ifunc-impl-list.c
> index a3b5731411..dc39335b76 100644
> --- a/sysdeps/unix/sysv/linux/riscv/multiarch/ifunc-impl-list.c
> +++ b/sysdeps/unix/sysv/linux/riscv/multiarch/ifunc-impl-list.c
> @@ -53,5 +53,10 @@ __libc_ifunc_impl_list (const char *name, struct libc_ifunc_impl *array,
> __memset_vector)
> IFUNC_IMPL_ADD (array, i, memset, 1, __memset_generic))
>
> + IFUNC_IMPL (i, name, strrchr,
> + IFUNC_IMPL_ADD (array, i, strrchr, rvv_enabled,
> + __strrchr_vector)
> + IFUNC_IMPL_ADD (array, i, strrchr, 1, __strrchr_generic))
> +
> return 0;
> }
> diff --git a/sysdeps/unix/sysv/linux/riscv/multiarch/strrchr.c b/sysdeps/unix/sysv/linux/riscv/multiarch/strrchr.c
> new file mode 100644
> index 0000000000..3532af0dc0
> --- /dev/null
> +++ b/sysdeps/unix/sysv/linux/riscv/multiarch/strrchr.c
> @@ -0,0 +1,59 @@
> +/* Multiple versions of strrchr.
> + All versions must be listed in ifunc-impl-list.c.
> + Copyright (C) 2026 Free Software Foundation, Inc.
> + This file is part of the GNU C Library.
> +
> + The GNU C Library is free software; you can redistribute it and/or
> + modify it under the terms of the GNU Lesser General Public
> + License as published by the Free Software Foundation; either
> + version 2.1 of the License, or (at your option) any later version.
> +
> + The GNU C Library is distributed in the hope that it will be useful,
> + but WITHOUT ANY WARRANTY; without even the implied warranty of
> + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> + Lesser General Public License for more details.
> +
> + You should have received a copy of the GNU Lesser General Public
> + License along with the GNU C Library; if not, see
> + <https://www.gnu.org/licenses/>. */
> +
> +#if IS_IN (libc)
> +/* Redefine strrchr so that the compiler won't complain about the type
> + mismatch with the IFUNC selector in strong_alias, below. */
> +# undef strrchr
> +# define strrchr __redirect_strrchr
> +# include <stdint.h>
> +# include <string.h>
> +# include <ifunc-init.h>
> +# include <riscv-ifunc.h>
> +# include <sys/hwprobe.h>
> +
> +extern __typeof (__redirect_strrchr) __libc_strrchr;
> +
> +extern __typeof (__redirect_strrchr) __strrchr_generic attribute_hidden;
> +extern __typeof (__redirect_strrchr) __strrchr_vector attribute_hidden;
> +
> +static inline __typeof (__redirect_strrchr) *
> +select_strrchr_ifunc (uint64_t dl_hwcap, __riscv_hwprobe_t hwprobe_func)
> +{
> + unsigned long long v;
> +
> + if (__riscv_hwprobe_one (hwprobe_func, RISCV_HWPROBE_KEY_IMA_EXT_0, &v) == 0
> + && (v & RISCV_HWPROBE_IMA_V) == RISCV_HWPROBE_IMA_V)
> + return __strrchr_vector;
> + return __strrchr_generic;
> +}
> +
> +riscv_libc_ifunc (__libc_strrchr, select_strrchr_ifunc);
> +
> +# undef strrchr
> +# undef rindex
> +strong_alias (__libc_strrchr, strrchr);
> +weak_alias (strrchr, rindex);
> +# ifdef SHARED
> +__hidden_ver1 (strrchr, __GI_strrchr, __redirect_strrchr)
> + __attribute__ ((visibility ("hidden"))) __attribute_copy__ (strrchr);
> +# endif
> +#else
> +# include <string/strrchr.c>
> +#endif
> --
> 2.25.1
More information about the Libc-alpha
mailing list