Re: [PATCH 4/5] tree-walk: unroll get_mode since loop boundaries are well-known
- From
Erik Faye-Lund <kusmabite@gmail.com>
- Date
- Apr 4, 2011, 10:29 UTC
- Message-ID
- <BANLkTi=dF7p9K5c8SYFJjZ7uognwizuuaQ@mail.gmail.com>
- In-Reply-To
- <1301535481-1085-4-git-send-email-dpmcgee@gmail.com>
On Thu, Mar 31, 2011 at 3:38 AM, Dan McGee <dpmcgee@gmail.com> wrote:
Show 33 quoted lines
> We know our mode entry in our tree objects should be 5 or 6 characters
> long. This change both enforces this fact and also unrolls the parsing
> of the information giving the compiler more room for optimization of the
> operations.
>
> Signed-off-by: Dan McGee <dpmcgee@gmail.com>
> ---
> tree-walk.c | 41 ++++++++++++++++++++++++++++++++++-------
> 1 files changed, 34 insertions(+), 7 deletions(-)
>
> diff --git a/tree-walk.c b/tree-walk.c
> index f386151..41383b0 100644
> --- a/tree-walk.c
> +++ b/tree-walk.c
> @@ -9,16 +9,43 @@ static const char *get_mode(const char *str, unsigned int *modep)
> unsigned char c;
> unsigned int mode = 0;
>
> - if (*str == ' ')
> - return NULL;
> -
> - while ((c = *str++) != ' ') {
> - if (c < '0' || c > '7')
> - return NULL;
> + /*
> + * Unroll what looks like a 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;We perfer this style:
if (c < '0' || c > '7') return NULL;
i.e a line-break and a tab between the if-statement and the conditional code.
Show 17 quoted lines
> + 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');
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...
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) { + c = *str++; + if (c < '0' || c > '7') + return NULL; + mode = (mode << 3) + (c - '0'); + } /* char 6, optional */ if (*str != ' ') { c = *str++; - if (c < '0' || c > '7') return NULL; + if (c < '0' || c > '7') + return NULL; mode = (mode << 3) + (c - '0'); } - if (*str != ' ') return NULL; + if (*str != ' ') + return NULL; *modep = mode; return str + 1;