Re: [PATCH] un-improve strrchr()
On Wed, Jul 1, 2015 at 2:52 AM, Chris Rorvick wrote: > [ resending w/o HTML formatting ] > > On Sun, Jun 28, 2015 at 11:44 AM, Alexey Dobriyan 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. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH] un-improve strrchr()
On Wed, Jul 1, 2015 at 2:52 AM, Chris Rorvick ch...@rorvick.com wrote: [ resending w/o HTML formatting ] On Sun, Jun 28, 2015 at 11:44 AM, Alexey Dobriyan adobri...@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. -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH] un-improve strrchr()
[ resending w/o HTML formatting ] On Sun, Jun 28, 2015 at 11:44 AM, Alexey Dobriyan 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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH] un-improve strrchr()
[ resending w/o HTML formatting ] On Sun, Jun 28, 2015 at 11:44 AM, Alexey Dobriyan adobri...@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 -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH] un-improve strrchr()
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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH] un-improve strrchr()
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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH] un-improve strrchr()
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
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH] un-improve strrchr()
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
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
