linux-kernel - Re: [PATCH] un-improve strrchr()

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Sun, 28 Jun 2015 22:43:14 +0300
From:	Alexey Dobriyan <adobriyan@...il.com>
To:	joe@...ches.com
Cc:	linux-kernel@...r.kernel.org, linux@...musvillemoes.dk,
	akpm@...ux-foundation.org
Subject: 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 majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/