patch, 5 partstree-walk: drop unused parameter from match_dir_prefix

>  tree-walk.c |    4 ++--
>  1 files changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/tree-walk.c b/tree-walk.c
> index 322becc..9be8007 100644
> --- a/tree-walk.c
> +++ b/tree-walk.c
> @@ -522,7 +522,7 @@ static int match_entry(const struct name_entry *entry, int pathlen,
>        return 0;
>  }
>
> -static int match_dir_prefix(const char *base, int baselen,
> +static int match_dir_prefix(const char *base,
>                            const char *match, int matchlen)
>  {
>        if (strncmp(base, match, matchlen))
> @@ -579,7 +579,7 @@ int tree_entry_interesting(const struct name_entry *entry,
>
>                if (baselen >= matchlen) {
>                        /* If it doesn't match, move along... */
> -                       if (!match_dir_prefix(base_str, baselen, match, matchlen))
> +                       if (!match_dir_prefix(base_str, match, matchlen))
>                                goto match_wildcards;
>
>                        if (!ps->recursive || ps->max_depth == -1)
> --
> 1.7.4.2

> In the case of a wide breadth top-level tree (~2400 entries, all trees
> in this case), we can see a noticeable cost in the profiler calling
> strncmp() here. Most of the time we are at the base level of the
> repository, so base is "" and baselen == 0, which means we will always
> test true. Break out this one tiny case so we can short circuit the
> strncmp() call.
> 
> This resulted in an ~11% improvement (43 to 38 secs) for a reasonable
> log operation on the Arch Linux Packages SVN clone repository, which
> contained 117220 commits and the aforementioned 2400 top-level objects:
>     git log -- autogen/trunk pacman/trunk/ wget/trunk/
> 
> Negligible slowdown was noted with other repositories (e.g. linux-2.6).
> 
> Signed-off-by: Dan McGee <dpmcgee@gmail.com>

> In the case of a wide breadth top-level tree (~2400 entries, all trees
> in this case), we can see a noticeable cost in the profiler calling
> strncmp() here. Most of the time we are at the base level of the
> repository, so base is "" and baselen == 0, which means we will always
> test true. Break out this one tiny case so we can short circuit the
> strncmp() call.

> This resulted in an ~11% improvement (43 to 38 secs) for a reasonable
> log operation on the Arch Linux Packages SVN clone repository, which
> contained 117220 commits and the aforementioned 2400 top-level objects:
>     git log -- autogen/trunk pacman/trunk/ wget/trunk/
>
> Negligible slowdown was noted with other repositories (e.g. linux-2.6).

> Signed-off-by: Dan McGee <dpmcgee@gmail.com>
> ---
>  tree-walk.c |    4 ++--
>  1 files changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/tree-walk.c b/tree-walk.c
> index 9be8007..f386151 100644
> --- a/tree-walk.c
> +++ b/tree-walk.c
> @@ -591,8 +591,8 @@ int tree_entry_interesting(const struct name_entry *entry,
>  					      ps->max_depth);
>  		}
>  
> -		/* Does the base match? */
> -		if (!strncmp(base_str, match, baselen)) {
> +		/* Either there must be no base, or the base must match. */
> +		if (baselen == 0 || !strncmp(base_str, match, baselen)) {
>  			if (match_entry(entry, pathlen,
>  					match + baselen, matchlen - baselen,
>  					&never_interesting))

> Dan McGee <dpmcgee@gmail.com> writes:
>
>> In the case of a wide breadth top-level tree (~2400 entries, all trees
>> in this case), we can see a noticeable cost in the profiler calling
>> strncmp() here. Most of the time we are at the base level of the
>> repository, so base is "" and baselen == 0, which means we will always
>> test true. Break out this one tiny case so we can short circuit the
>> strncmp() call.
>
> This sounds as if the patch helps only when you have a superfat tree at
> the "top-level" of the project, but wouldn't this benefit any superfat
> tree at _any_ level while we recursively descend into it?

>> This resulted in an ~11% improvement (43 to 38 secs) for a reasonable
>> log operation on the Arch Linux Packages SVN clone repository, which
>> contained 117220 commits and the aforementioned 2400 top-level objects:
>>     git log -- autogen/trunk pacman/trunk/ wget/trunk/
>>
>> Negligible slowdown was noted with other repositories (e.g. linux-2.6).
>
> It would have been easier to swallow if the last sentence were "This could
> lead to a slowdown in repositories without directories that are too wide,
> but in practice it was not even measurable."  "Negligible" sounds as if it
> had still measurable downside, and as if you decided that the slowdown can
> be ignored---but obviously you are not an unbiased judge.

> There is nothing wrong in the patch per-se, but I really wish we didn't
> have to do this; it feels like the compiler should be helping us in this
> case.
>
>> Signed-off-by: Dan McGee <dpmcgee@gmail.com>
>> ---
>>  tree-walk.c |    4 ++--
>>  1 files changed, 2 insertions(+), 2 deletions(-)
>>
>> diff --git a/tree-walk.c b/tree-walk.c
>> index 9be8007..f386151 100644
>> --- a/tree-walk.c
>> +++ b/tree-walk.c
>> @@ -591,8 +591,8 @@ int tree_entry_interesting(const struct name_entry *entry,
>>                                             ps->max_depth);
>>               }
>>
>> -             /* Does the base match? */
>> -             if (!strncmp(base_str, match, baselen)) {
>> +             /* Either there must be no base, or the base must match. */
>> +             if (baselen == 0 || !strncmp(base_str, match, baselen)) {
>>                       if (match_entry(entry, pathlen,
>>                                       match + baselen, matchlen - baselen,
>>                                       &never_interesting))
>

> On Thu, Mar 31, 2011 at 8: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.
>
> I'm skeptical. Did you measure signficant gain after this patch? I
> looked at asm output with -O3 and failed to see the compiler doing
> anything fancy. Perhaps it's because I'm on x86 with quite small
> register set.

> On Sat, Apr 2, 2011 at 4:28 AM, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:
>> On Thu, Mar 31, 2011 at 8: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.
>>
>> I'm skeptical. Did you measure signficant gain after this patch? I
>> looked at asm output with -O3 and failed to see the compiler doing
>> anything fancy. Perhaps it's because I'm on x86 with quite small
>> register set.
>
> I'm on x86_64 and was just using -O2; -O3 produces the same output
> actually. You can see it below. I had taken a look at this before I
> submitted, and noticed a few things:
> 1. We do use multiple registers now since we aren't constrained to a loop.
> 2. movzbl (for the string parts) and cmb instructions tend to get
> clustered first.
> 3. mozbl (for the mode shifting) and leal instructions tend to get
> clustered later.
> 4. The normal case now involves no conditional jumps until the ' '
> (space) comparison.
>
> Call these "trivial", but on my worst case operation times went from
> (shown below) 27.41 secs to 26.49 secs. Considering this operation is
> called 530,588,868 times (that is not a typo) during this operation,
> every saved instruction or non-missed branch prediction does seem to
> make a difference.

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

> +       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) {

>
> 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.

> Dan McGee <dpmcgee@gmail.com> writes:
>
>> We know our mode entry in our tree objects should be 5 or 6 characters
>> long. This change both enforces this fact...
>
> I find the implementation later shown in the thread is cleaner,

> but I'd
> comment on the word "enforces" here.
>
> It is more like "versions of git we know how to read from writes mode bits
> with 5 or 6 characters---if we see something else, either the tree object
> is corrupt, or we are too old to read the new type of entry in the tree
> object".

> So returning NULL is fine and it tells the caller that we do not
> understand the tree object.  The caller says "corrupt tree file" when we
> do so here, but this change needs to rephrase it.  If we stopped because
> we saw something other than ' ' after the run of octal digits, then we
> know the tree is corrupt.  If we saw a three octal digits 644 in the mode
> field, terminated with ' ', maybe we are seeing a new kind of tree entry
> generated from later versions of git.
>
> Ideally, I'd rather see error checking done even higher layer than
> decode_tree_entry() for the "we are too old" case, though.  We should
> return mode 0644 in such a case, and let the caller suggest that the
> version of git we are running might be too old, or the tree may have been
> written by a broken system that tried to mimic git in its error message.
>

> ....
> Totally agree; I should have tried to do it this way in the first
> place. However, compiling the fixed-length 0 to 5 loop does not
> produce fully-unrolled assembly for me with CFLAGS="-march=native
> -mtune=native -O2 -pipe -g" on x86_64. I see two copies of the loop
> only, and even worse is the (lack of) performance (each is the mode of
> 3 runs). Compilers are stupid apparently.
> ....

> On Mon, Apr 4, 2011 at 10:33 PM, Dan McGee <dpmcgee@gmail.com> wrote:
>> ....
>> Totally agree; I should have tried to do it this way in the first
>> place. However, compiling the fixed-length 0 to 5 loop does not
>> produce fully-unrolled assembly for me with CFLAGS="-march=native
>> -mtune=native -O2 -pipe -g" on x86_64. I see two copies of the loop
>> only, and even worse is the (lack of) performance (each is the mode of
>> 3 runs). Compilers are stupid apparently.
>> ....
>
> Can you try -O3? Or an explicit '-funroll-loops'?
> gcc I think does not do aggressive speed optimizations at the cost of
> space when at O2.

> On Thu, Mar 31, 2011 at 8:38 AM, Dan McGee <dpmcgee@gmail.com> wrote:
>> Before calling strncmp(), see if we can get away with checking only the
>> first character of the passed path components instead.
>>
>> Signed-off-by: Dan McGee <dpmcgee@gmail.com>
>
> I wonder if inlining strcmp() would be better (at least cleaner code).
> It seems like you try to avoid the function call cost here.

> These next few patches are all derived from trying to make operations on this
> repository a bit faster:
>    http://projects.archlinux.org/svntogit/packages.git/
>
> ...
>
> time git log -- zzzzz_not_exist >/dev/null
>                          35.558s      0.976s

> On Thu, Mar 31, 2011 at 8:37 AM, Dan McGee <dpmcgee@gmail.com> wrote:
>> These next few patches are all derived from trying to make operations on this
>> repository a bit faster:
>>    http://projects.archlinux.org/svntogit/packages.git/
>>
>> ...
>>
>> time git log -- zzzzz_not_exist >/dev/null
>>                          35.558s      0.976s
>
> Do you have numbers before and after applying this series? It'd be
> interesting to see how much we gain from the series.

> diff --git a/tree-diff.c b/tree-diff.c
> index 76f83fc..ab90f1a 100644
> --- a/tree-diff.c
> +++ b/tree-diff.c
> @@ -286,6 +286,9 @@ int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const cha
>  	unsigned long size1, size2;
>  	int retval;
>  
> +	if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(old, new))
> +		return 0;
> +

> These next few patches are all derived from trying to make operations on this
> repository a bit faster:
>    http://projects.archlinux.org/svntogit/packages.git/
>
> As far as a different shape of repository, this one qualifies. Some stats from
> after running `git gc --prune` and looking at things from count-objects among
> others:

> Dan McGee <dpmcgee@gmail.com> writes:
>
>> This was seen to happen in some invocations of git-log with a filtered
>> path. Only do it if we are not recursively descending, as otherwise we
>> mess with copy and rename detection in full tree moves.
>
> There is no code that corresponds to your "Only do it..." description in
> your patch, though.  The existing code already takes care of that part
> with or without your patch, no?

>> diff --git a/tree-diff.c b/tree-diff.c
>> index 76f83fc..ab90f1a 100644
>> --- a/tree-diff.c
>> +++ b/tree-diff.c
>> @@ -286,6 +286,9 @@ int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const cha
>>       unsigned long size1, size2;
>>       int retval;
>>
>> +     if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(old, new))
>> +             return 0;
>> +
>
> I am very curious why this patch makes a difference; doesn't an existing
> test in compare_tree_entry() oalready cull extra recursion?  There is:

>        if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(sha1, sha2) &&
>                mode1 == mode2)
>                return 0;
>
> before a recursive call to diff_tree_sha1() to dig deeper.
>

> On Sun, Apr 3, 2011 at 1:55 PM, Junio C Hamano <gitster@pobox.com> wrote:
>> Dan McGee <dpmcgee@gmail.com> writes:
>>
>>> In the case of a wide breadth top-level tree (~2400 entries, all trees
>>> in this case), we can see a noticeable cost in the profiler calling
>>> strncmp() here. Most of the time we are at the base level of the
>>> repository, so base is "" and baselen == 0, which means we will always
>>> test true. Break out this one tiny case so we can short circuit the
>>> strncmp() call.
>>
>> This sounds as if the patch helps only when you have a superfat tree at
>> the "top-level" of the project, but wouldn't this benefit any superfat
>> tree at _any_ level while we recursively descend into it?
>
> Correct. I looked at the fact that more often than not, we wouldn't
> have to descend into subtrees unless searching for a path underneath
> it, so that is why I phrased it that way. So the "in the case of" was
> quite literally the case I was testing, but didn't mean to exclude
> other potential test cases.
>
>>> This resulted in an ~11% improvement (43 to 38 secs) for a reasonable
>>> log operation on the Arch Linux Packages SVN clone repository, which
>>> contained 117220 commits and the aforementioned 2400 top-level objects:
>>>     git log -- autogen/trunk pacman/trunk/ wget/trunk/
>>>
>>> Negligible slowdown was noted with other repositories (e.g. linux-2.6).
>>
>> It would have been easier to swallow if the last sentence were "This could
>> lead to a slowdown in repositories without directories that are too wide,
>> but in practice it was not even measurable."  "Negligible" sounds as if it
>> had still measurable downside, and as if you decided that the slowdown can
>> be ignored---but obviously you are not an unbiased judge.
>
> Perhaps I was too cautious with my words- but I was also trying to not
> be biased. Considering this same operation takes < 1 second in
> linux-2.6, I only wanted to mention it could have a slight effect. In
> reality I saw nothing more than an extra 0.01s or so, and definitely
> nothing significant. Let me know if you see otherwise.
>
> dmcgee@galway ~/projects/linux-2.6 (master)
> $ time ../git/git-log -- zzzzz_not_exist > /dev/null
>
> real    0m0.945s
> user    0m0.857s
> sys     0m0.083s
>
>> There is nothing wrong in the patch per-se, but I really wish we didn't
>> have to do this; it feels like the compiler should be helping us in this
>> case.

>>> Signed-off-by: Dan McGee <dpmcgee@gmail.com>
>>> ---
>>>  tree-walk.c |    4 ++--
>>>  1 files changed, 2 insertions(+), 2 deletions(-)
>>>
>>> diff --git a/tree-walk.c b/tree-walk.c
>>> index 9be8007..f386151 100644
>>> --- a/tree-walk.c
>>> +++ b/tree-walk.c
>>> @@ -591,8 +591,8 @@ int tree_entry_interesting(const struct name_entry *entry,
>>>                                             ps->max_depth);
>>>               }
>>>
>>> -             /* Does the base match? */
>>> -             if (!strncmp(base_str, match, baselen)) {
>>> +             /* Either there must be no base, or the base must match. */
>>> +             if (baselen == 0 || !strncmp(base_str, match, baselen)) {
>>>                       if (match_entry(entry, pathlen,
>>>                                       match + baselen, matchlen - baselen,
>>>                                       &never_interesting))
>>
>

>> dmcgee@galway ~/projects/linux-2.6 (master)
>> $ time ../git/git-log -- zzzzz_not_exist > /dev/null
>>
>> real    0m0.945s
>> user    0m0.857s
>> sys     0m0.083s
>>
>>> There is nothing wrong in the patch per-se, but I really wish we didn't
>>> have to do this; it feels like the compiler should be helping us in this
>>> case.
>
> If I resurrect this with an updated commit message reflecting concerns
> raised, can it be merged? Given that it is a noticeable performance
> boost on real-life repositories and I can show it has little (<1%) to
> no impact on most repos, it is a definite win.