Re: [PATCH 3/5] tree-walk: micro-optimization in tree_entry_interesting
- From
Dan McGee <dpmcgee@gmail.com>
- Date
- Apr 5, 2011, 00:22 UTC
- Message-ID
- <BANLkTi=yVrS9MsBF1YR9D-QWej-n1uDQyQ@mail.gmail.com>
- In-Reply-To
- <7vaag7dv0z.fsf@alter.siamese.dyndns.org>
On Sun, Apr 3, 2011 at 1:55 PM, Junio C Hamano <gitster@pobox.com> wrote:
Show 12 quoted lines
> 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.
Show 12 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.
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
Show 25 quoted lines
> 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))
>