Re: [PATCH 4/5] tree-walk: unroll get_mode since loop boundaries are well-known

[Erik Faye-Lund <kusmabite@gmail.com>]

On Thu, Mar 31, 2011 at 3:38 AM, Dan McGee <dpmcgee@gmail.com> wrote:
> 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.

> +       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;