This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PING][PATCH] More effective generic strrchr.


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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]