[PING][PATCH] More effective generic strrchr.

[Will Newton]

On 4 December 2013 15:41, Ondřej Bílka <neleai@seznam.cz> wrote:
> On Wed, Dec 04, 2013 at 01:13:34PM +0000, Will Newton wrote:
>> On 4 December 2013 12:58, Ondřej Bílka <neleai@seznam.cz> wrote:
>> > ping
>> > On Sat, Oct 05, 2013 at 09:15:42AM +0200, Ondřej Bílka wrote:
>> >>
>> >> A generic implementation of strrchr could be improved by following
>> >> patch. As it is likely that last occurrence of c will be near end we
>> >> could quickly find it. This is also much faster for degenerate inputs
>> >> like:
>> >>
>> >> strrchr("xyxyxyxyxyxyxyxyxyxyxyxyx...",'x');
>> >>
>> >> where a loop slows us down.
>> >>
>> >>       * string/strrchr.c: Improve implementation.
>>
>> This changelog is not really adequate or correct.
>>
>> >>
>> >> ---
>> >>  string/strrchr.c | 19 ++-----------------
>> >>  1 file changed, 2 insertions(+), 17 deletions(-)
>> >>
>> >> diff --git a/string/strrchr.c b/string/strrchr.c
>> >> index bdec841..ad242b6 100644
>> >> --- a/string/strrchr.c
>> >> +++ b/string/strrchr.c
>> >> @@ -23,23 +23,8 @@
>> >>  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;
>> >> +  /* We need to include terminating zero for case c == 0.  */
>> >> +  return __memrchr (s, c, strlen (s) + 1);
>>
>> Do you have benchmark results for this? It would be good to test on
>> systems that have fast memrchr (e.g. i386/powerpc/x86_64) and ones
>> that don't (the rest).
>>
>> --
>> Will Newton
>> Toolchain Working Group, Linaro
> Yes I did benchmarking and implementation is around 60 times faster than
> old string one on x86.
>
> New implementation is around three times slower than old one.
>
> And there is no difference between implementations.
>
> This variance was caused by choosing different inputs (string consisting
> in 50% from searched character, string with character only at start and
> string with character only at end) so you need to find which factors are
> important in practice.

It is not necessarily a great idea to optimize for degenerate cases as
you can often end up slowing down the common case to improve the worst
case that rarely happens in practice. We could generate strings that
are representative of e.g. pathnames and use those to benchmark. We
have a benchtest for strrchr in the tree already, if it is no good
then we should fix it.

-- 
Will Newton
Toolchain Working Group, Linaro