[PATCH] un-improve strrchr()

[PATCH] un-improve strrchr()

[Alexey Dobriyan]

Commit 8da53d4595a53fb9a3380dd4d1c9bc24c7c9aab8
("lib/string.c: improve strrchr()") changed strrchr() implementation
from "rewind to the end and search backwards" to "search forward"
optimizing for characher not found case. However, common case is exactly
the opposite: string is absolute pathname, c is '/' always to be found.

Previous code did 1 branch per character + 1 branch for every character
in the last path component. Current code does 2 branches per characher
regardless.

Patch reverts to previous implementation (sans fixed coding style).

Signed-off-by: Alexey Dobriyan <adobriyan@gmail.com>
---

	Cc linux-kernel

 lib/string.c |   11 ++++++-----
 1 file changed, 6 insertions(+), 5 deletions(-)

--- a/lib/string.c
+++ b/lib/string.c
@@ -313,12 +313,13 @@ EXPORT_SYMBOL(strchrnul);
  */
 char *strrchr(const char *s, int c)
 {
-	const char *last = NULL;
+	const char *p = s + strlen(s);
+
 	do {
-		if (*s == (char)c)
-			last = s;
-	} while (*s++);
-	return (char *)last;
+		if (*p == (char)c)
+			return (char *)p;
+	} while (--p >= s);
+	return NULL;
 }
 EXPORT_SYMBOL(strrchr);
 #endif

Re: [PATCH] un-improve strrchr()

[Joe Perches]

On Sun, 2015-06-28 at 19:44 +0300, Alexey Dobriyan wrote:
> Commit 8da53d4595a53fb9a3380dd4d1c9bc24c7c9aab8
> ("lib/string.c: improve strrchr()") changed strrchr() implementation
> from "rewind to the end and search backwards" to "search forward"
> optimizing for characher not found case. However, common case is exactly
> the opposite: string is absolute pathname, c is '/' always to be found.
> 
> Previous code did 1 branch per character + 1 branch for every character
> in the last path component. Current code does 2 branches per characher
> regardless.

Are you comparing total cycles of all of the branches
in the called functions too?

As written the current version removes the strlen call.

> --- a/lib/string.c
> +++ b/lib/string.c
> @@ -313,12 +313,13 @@ EXPORT_SYMBOL(strchrnul);
>   */
>  char *strrchr(const char *s, int c)
>  {
> -	const char *last = NULL;
> +	const char *p = s + strlen(s);
> +
>  	do {
> -		if (*s == (char)c)
> -			last = s;
> -	} while (*s++);
> -	return (char *)last;
> +		if (*p == (char)c)
> +			return (char *)p;
> +	} while (--p >= s);
> +	return NULL;
>  }
>  EXPORT_SYMBOL(strrchr);
>  #endif

Re: [PATCH] un-improve strrchr()

[Alexey Dobriyan]

Joe Perches wrote:

> On Sun, 2015-06-28 at 19:44 +0300, Alexey Dobriyan wrote:
> > Commit 8da53d4595a53fb9a3380dd4d1c9bc24c7c9aab8
> > ("lib/string.c: improve strrchr()") changed strrchr() implementation
> > from "rewind to the end and search backwards" to "search forward"
> > optimizing for characher not found case. However, common case is exactly
> > the opposite: string is absolute pathname, c is '/' always to be found.
> > 
> > Previous code did 1 branch per character + 1 branch for every character
> > in the last path component. Current code does 2 branches per characher
> > regardless.
> 
> Are you comparing total cycles of all of the branches
> in the called functions too?

I'm comparing branches to branches. For strrchr() you don't need 2xN branches
even in theory. strlen() might even be optimized (gcc does have the impudence
to inline it's own CMPB version though).

> As written the current version removes the strlen call.

It does.

> > --- a/lib/string.c
> > +++ b/lib/string.c
> > @@ -313,12 +313,13 @@ EXPORT_SYMBOL(strchrnul);
> >   */
> >  char *strrchr(const char *s, int c)
> >  {
> > -	const char *last = NULL;
> > +	const char *p = s + strlen(s);
> > +
> >  	do {
> > -		if (*s == (char)c)
> > -			last = s;
> > -	} while (*s++);
> > -	return (char *)last;
> > +		if (*p == (char)c)
> > +			return (char *)p;
> > +	} while (--p >= s);
> > +	return NULL;
> >  }
> >  EXPORT_SYMBOL(strrchr);
> >  #endif

Re: [PATCH] un-improve strrchr()

[Chris Rorvick]

[ resending w/o HTML formatting ]

On Sun, Jun 28, 2015 at 11:44 AM, Alexey Dobriyan <adobriyan@gmail.com> wrote:
> Previous code did 1 branch per character + 1 branch for every character
> in the last path component. Current code does 2 branches per characher
> regardless.

Shouldn't that be "+ 2 branches for every character in the last path
component"?  The structure of the loop is basically the same; you're
just performing fewer iterations if the character is found when
searching from the end.

Regards,

Chris

Re: [PATCH] un-improve strrchr()

[Alexey Dobriyan]

On Wed, Jul 1, 2015 at 2:52 AM, Chris Rorvick <chris@rorvick.com> wrote:
> [ resending w/o HTML formatting ]
>
> On Sun, Jun 28, 2015 at 11:44 AM, Alexey Dobriyan <adobriyan@gmail.com> wrote:
>> Previous code did 1 branch per character + 1 branch for every character
>> in the last path component. Current code does 2 branches per characher
>> regardless.
>
> Shouldn't that be "+ 2 branches for every character in the last path
> component"?  The structure of the loop is basically the same; you're
> just performing fewer iterations if the character is found when
> searching from the end.

Yes, changelog is inaccurate.

It is "1 branch per character + 2 branches per character in
the last path component" vs "2 branches per character".

Rasmus posted benchmark (obvious rdtsc/strrchr/rdtsc) in private.

Speed highly depends on -O2/-Os setting and current mainline code
is not uniformly faster at least for me. I'll probably resend with new
and improved changelog.