[PATCH v12 14/31] string: Improve generic strrchr with memrchr and strlen

[PATCH v12 14/31] string: Improve generic strrchr with memrchr and strlen

[Wilco Dijkstra]

Hi Adhemerval,

 STRRCHR (const char *s, int c)
 {
+  return __memrchr (s, c, strlen (s) + 1);
 }

LGTM

I did a quick check on AArch64 and the speedup vs the old generic version
on bench-strrchr is 9.9 times! It's ~15% slower overall than the assembler
strrchr.

While the benchmark is not perfect, it shows that if you have decent strlen
and memrchr then strlen+memchr gives a competitive strrchr.

Cheers,
Wilco

Re: [PATCH v12 14/31] string: Improve generic strrchr with memrchr and strlen

[Adhemerval Zanella Netto]

On 02/02/23 16:54, Wilco Dijkstra wrote:
> Hi Adhemerval,
> 
>  STRRCHR (const char *s, int c)
>  {
> +  return __memrchr (s, c, strlen (s) + 1);
>  }
> 
> LGTM
> 
> I did a quick check on AArch64 and the speedup vs the old generic version
> on bench-strrchr is 9.9 times! It's ~15% slower overall than the assembler
> strrchr.
> 
> While the benchmark is not perfect, it shows that if you have decent strlen
> and memrchr then strlen+memchr gives a competitive strrchr.

Yeah, I saw a similar improvement on my side as well.  Thanks for verify it
as well.

Re: [PATCH v12 14/31] string: Improve generic strrchr with memrchr and strlen

[Adhemerval Zanella Netto]

On 04/02/23 00:06, Richard Henderson wrote:
> On 2/2/23 08:11, Adhemerval Zanella wrote:
>> Now that both strlen and memrchr have word vectorized implementation,
>> it should be faster to implement strrchr based on memrchr over the
>> string length instead of calling strchr on a loop.
>>
>> Checked on x86_64-linux-gnu, i686-linux-gnu, powerpc-linux-gnu,
>> and powerpc64-linux-gnu by removing the arch-specific assembly
>> implementation and disabling multi-arch (it covers both LE and BE
>> for 64 and 32 bits).
>> ---
>>   string/strrchr.c | 18 +-----------------
>>   1 file changed, 1 insertion(+), 17 deletions(-)
> 
> memrchr needs libc_hidden_builtin_proto.  On riscv64:
> 
>    c:   00000097                auipc   ra,0x0
>                         c: R_RISCV_CALL __GI_strlen
>                         c: R_RISCV_RELAX        *ABS*
>   10:   000080e7                jalr    ra # c <__GI_strrchr+0xc>
> ...
>   24:   00000317                auipc   t1,0x0
>                         24: R_RISCV_CALL_PLT    __memrchr
>                         24: R_RISCV_RELAX       *ABS*
>   28:   00030067                jr      t1 # 24 <.LVL2+0x8>
> 
> 
> r~

Similar to strchr [1], static linker ends up creating the expected local
call:

$ riscv64-glibc-linux-gnu-objdump -dr libc.so
[...]
0000000000088f5c <strrchr>:
   88f5c:       7179                    addi    sp,sp,-48
   88f5e:       e84a                    sd      s2,16(sp)
   88f60:       000e7917                auipc   s2,0xe7
   88f64:       73893903                ld      s2,1848(s2) # 170698 <__stack_chk_guard@GLIBC_2.27>
   88f68:       00093783                ld      a5,0(s2)
[...]
   88f9a:       6145                    addi    sp,sp,48
   88f9c:       c70fd06f                j       8640c <memrchr>
   88fa0:       193500ef                jal     ra,d9932 <__stack_chk_fail>
[...]

But I agree that we should change to have the libc_hidden_builin_proto
in this case.  I will send a patch to fix it.

[1] https://sourceware.org/pipermail/libc-alpha/2023-February/145322.html

Re: [PATCH v12 14/31] string: Improve generic strrchr with memrchr and strlen

[Richard Henderson]

On 2/2/23 08:11, Adhemerval Zanella wrote:
> Now that both strlen and memrchr have word vectorized implementation,
> it should be faster to implement strrchr based on memrchr over the
> string length instead of calling strchr on a loop.
> 
> Checked on x86_64-linux-gnu, i686-linux-gnu, powerpc-linux-gnu,
> and powerpc64-linux-gnu by removing the arch-specific assembly
> implementation and disabling multi-arch (it covers both LE and BE
> for 64 and 32 bits).
> ---
>   string/strrchr.c | 18 +-----------------
>   1 file changed, 1 insertion(+), 17 deletions(-)

memrchr needs libc_hidden_builtin_proto.  On riscv64:

    c:   00000097                auipc   ra,0x0
                         c: R_RISCV_CALL __GI_strlen
                         c: R_RISCV_RELAX        *ABS*
   10:   000080e7                jalr    ra # c <__GI_strrchr+0xc>
...
   24:   00000317                auipc   t1,0x0
                         24: R_RISCV_CALL_PLT    __memrchr
                         24: R_RISCV_RELAX       *ABS*
   28:   00030067                jr      t1 # 24 <.LVL2+0x8>


r~

[PATCH v12 14/31] string: Improve generic strrchr with memrchr and strlen

[Adhemerval Zanella]

Now that both strlen and memrchr have word vectorized implementation,
it should be faster to implement strrchr based on memrchr over the
string length instead of calling strchr on a loop.

Checked on x86_64-linux-gnu, i686-linux-gnu, powerpc-linux-gnu,
and powerpc64-linux-gnu by removing the arch-specific assembly
implementation and disabling multi-arch (it covers both LE and BE
for 64 and 32 bits).
---
 string/strrchr.c | 18 +-----------------
 1 file changed, 1 insertion(+), 17 deletions(-)

diff --git a/string/strrchr.c b/string/strrchr.c
index 3c6e715d3b..7b76dea4e0 100644
--- a/string/strrchr.c
+++ b/string/strrchr.c
@@ -27,23 +27,7 @@
 char *
 STRRCHR (const char *s, int c)
 {
-  const char *found, *p;
-
-  c = (unsigned char) c;
-
-  /* Since strchr is fast, we use it rather than the obvious loop.  */
-
-  if (c == '\0')
-    return strchr (s, '\0');
-
-  found = NULL;
-  while ((p = strchr (s, c)) != NULL)
-    {
-      found = p;
-      s = p + 1;
-    }
-
-  return (char *) found;
+  return __memrchr (s, c, strlen (s) + 1);
 }
 
 #ifdef weak_alias
-- 
2.34.1