From: Andreas Ericsson <ae@op5.se>
To: kusmabite@gmail.com
Cc: Dan McGee <dpmcgee@gmail.com>, git@vger.kernel.org
Subject: Re: [PATCH 4/5] tree-walk: unroll get_mode since loop boundaries are well-known
Date: Mon, 04 Apr 2011 14:30:17 +0200 [thread overview]
Message-ID: <4D99B9D9.1020101@op5.se> (raw)
In-Reply-To: <BANLkTi=dF7p9K5c8SYFJjZ7uognwizuuaQ@mail.gmail.com>
On 04/04/2011 12:29 PM, Erik Faye-Lund wrote:
>
> Wouldn't this part be cleaner as a constant-length loop? Any
> optimizing compiler should end up unrolling this, and we don't get as
> much code-duplication...
>
It would.
> Oddly enough, this change gave me a drastic (> 20%) performance
> increase in my test (isolating get_mode in a separate compilation
> unit, and calling it in a loop):
>
> diff --git a/tree-walk.c b/tree-walk.c
> index b8d504b..114ad63 100644
> --- a/tree-walk.c
> +++ b/tree-walk.c
> @@ -7,42 +7,30 @@
> static const char *get_mode(const char *str, unsigned int *modep)
> {
> unsigned char c;
> - unsigned int mode = 0;
> + unsigned int mode = 0, i;
>
> /*
> - * Unroll what looks like a loop since the bounds are
> + * Allow the compiler to unroll the loop since the bounds are
> * well-known. There should be at least 5 and at most 6
> * characters available in any valid mode, as '40000' is the
> * shortest while '160000' (S_IFGITLINK) is the longest.
> */
> - /* char 1 */
> - c = *str++;
> - if (c< '0' || c> '7') return NULL;
> - mode = (mode<< 3) + (c - '0');
> - /* char 2 */
> - c = *str++;
> - if (c< '0' || c> '7') return NULL;
> - mode = (mode<< 3) + (c - '0');
> - /* char 3 */
> - c = *str++;
> - if (c< '0' || c> '7') return NULL;
> - mode = (mode<< 3) + (c - '0');
> - /* char 4 */
> - c = *str++;
> - if (c< '0' || c> '7') return NULL;
> - mode = (mode<< 3) + (c - '0');
> - /* char 5 */
> - c = *str++;
> - if (c< '0' || c> '7') return NULL;
> - mode = (mode<< 3) + (c - '0');
> + for (i = 0; i< 5; ++i) {
s/i< 5/i < 5/ (nitpicking, yes)
> + c = *str++;
> + if (c< '0' || c> '7')
> + return NULL;
> + mode = (mode<< 3) + (c - '0');
This could be (micro-)optimized further as:
--%<--%<--
for (i = 0; i < 5; i++) {
int c = *str++ - '0';
if (c & ~7) {
/* 5 chars is ok, so long as *str is now a space */
if (i == 5 && c == ' ') {
*modep = mode;
return str;
}
return NULL;
}
mode = (mode << 3) + c;
}
/* this should be a space, or we've got a malformed entry */
if (*str != ' ')
return NULL;
return str + 1;
--%<--%<--
This should be slightly faster since there's now only one comparison
inside the loop and since one branch contains a second branch fork-point
and an inevitable early return the branch prediction machinery in gcc
will favor the most common case properly, but pre-computations on 'mode'
have to be undone in one case of hitting the early return, it might be
faster to play pickup after a loop to 5 is done.
--
Andreas Ericsson andreas.ericsson@op5.se
OP5 AB www.op5.se
Tel: +46 8-230225 Fax: +46 8-230231
Considering the successes of the wars on alcohol, poverty, drugs and
terror, I think we should give some serious thought to declaring war
on peace.
next prev parent reply other threads:[~2011-04-04 12:30 UTC|newest]
Thread overview: 30+ messages / expand[flat|nested] mbox.gz Atom feed top
2011-03-31 1:37 [PATCH 1/5] diff_tree_sha1: skip diff_tree if old == new Dan McGee
2011-03-31 1:37 ` [PATCH 2/5] tree-walk: drop unused parameter from match_dir_prefix Dan McGee
2011-08-30 18:55 ` Dan McGee
2011-03-31 1:37 ` [PATCH 3/5] tree-walk: micro-optimization in tree_entry_interesting Dan McGee
2011-04-03 4:01 ` Nguyen Thai Ngoc Duy
2011-04-03 18:55 ` Junio C Hamano
2011-04-05 0:22 ` Dan McGee
[not found] ` <CAEik5nOKrpFycZYVnSu4_5LYWxn0JS_hVXyiQH-80Bu-C4k8VQ@mail.gmail.com>
2011-08-30 19:51 ` Dan McGee
2011-08-30 20:40 ` Junio C Hamano
2011-09-09 2:02 ` [PATCH 1/2] tree-walk: drop unused parameter from match_dir_prefix Dan McGee
2011-09-09 2:02 ` [PATCH 2/2] tree-walk: micro-optimization in tree_entry_interesting Dan McGee
2011-04-04 14:46 ` [PATCH] tree_entry_interesting: inline strncmp() Nguyễn Thái Ngọc Duy
2011-03-31 1:38 ` [PATCH 4/5] tree-walk: unroll get_mode since loop boundaries are well-known Dan McGee
2011-04-02 9:28 ` Nguyen Thai Ngoc Duy
2011-04-02 17:28 ` Dan McGee
2011-04-03 4:07 ` Nguyen Thai Ngoc Duy
2011-04-04 10:29 ` Erik Faye-Lund
2011-04-04 12:30 ` Andreas Ericsson [this message]
2011-04-04 16:55 ` Junio C Hamano
2011-04-05 5:33 ` Dan McGee
2011-04-05 23:55 ` Antriksh Pany
2011-04-06 20:45 ` Dan McGee
2011-03-31 1:38 ` [PATCH 5/5] tree-walk: match_entry microoptimization Dan McGee
2011-04-02 9:06 ` Nguyen Thai Ngoc Duy
2011-04-02 17:54 ` Dan McGee
2011-03-31 12:58 ` [PATCH 1/5] diff_tree_sha1: skip diff_tree if old == new Nguyen Thai Ngoc Duy
2011-03-31 13:56 ` Dan McGee
2011-04-01 22:28 ` Junio C Hamano
[not found] ` <AANLkTinPSqDPdGi5nA3sH1D2wMSW1SQc+5gRqdLy++y0@mail.gmail.com>
2011-04-02 18:38 ` Fwd: " Dan McGee
2011-05-03 7:34 ` Nguyen Thai Ngoc Duy
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=4D99B9D9.1020101@op5.se \
--to=ae@op5.se \
--cc=dpmcgee@gmail.com \
--cc=git@vger.kernel.org \
--cc=kusmabite@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).