Re: [PATCH 3/5] tree-walk: micro-optimization in tree_entry_interesting

From: Junio C Hamano <gitster@pobox.com>
Date: Apr 3, 2011, 18:55 UTC
Message-ID: <7vaag7dv0z.fsf@alter.siamese.dyndns.org>
In-Reply-To: <1301535481-1085-3-git-send-email-dpmcgee@gmail.com>

Dan McGee <dpmcgee@gmail.com> writes:

Show 6 quoted lines

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

Show 6 quoted lines

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

Show 20 quoted lines

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