git tag --contains now takes a long time

git tag --contains now takes a long time

[Jerry Snitselaar]

Is this known and being looked into? I've seen a jump from 12 seconds
to over 9 minutes with running git tag --contains on my kernel repo.


snits ~/dev/linux> git --version
git version 2.6.1.145.gb27dacc

snits ~/dev/linux> time git tag --contains 825fcfc
next-20151012
next-20151013
v4.3-rc5

real	9m4.765s
user	8m56.157s
sys	0m2.450s



snits ~/dev/linux> git --version
git version 2.5.0.275.gac4cc86

snits ~/dev/linux> time git tag --contains 825fcfc
next-20151012
next-20151013
v4.3-rc5

real	0m12.842s
user	0m11.536s
sys	0m1.098s



b7cc53e92c806b73e14b03f60c17b7c29e52b4a4 is the first bad commit
commit b7cc53e92c806b73e14b03f60c17b7c29e52b4a4
Author: Karthik Nayak <karthik.188@gmail.com>
Date:   Fri Sep 11 20:36:16 2015 +0530

    tag.c: use 'ref-filter' APIs

    Make 'tag.c' use 'ref-filter' APIs for iterating through refs, sorting
    and printing of refs. This removes most of the code used in 'tag.c'
    replacing it with calls to the 'ref-filter' library.

    Make 'tag.c' use the 'filter_refs()' function provided by 'ref-filter'
    to filter out tags based on the options set.

    For printing tags we use 'show_ref_array_item()' function provided by
    'ref-filter'.

    We improve the sorting option provided by 'tag.c' by using the sorting
    options provided by 'ref-filter'. This causes the test 'invalid sort
    parameter on command line' in t7004 to fail, as 'ref-filter' throws an
    error for all sorting fields which are incorrect. The test is changed
    to reflect the same.

    Modify documentation for the same.

    Mentored-by: Christian Couder <christian.couder@gmail.com>
    Mentored-by: Matthieu Moy <matthieu.moy@grenoble-inp.fr>
    Signed-off-by: Karthik Nayak <karthik.188@gmail.com>
    Signed-off-by: Junio C Hamano <gitster@pobox.com>

Re: git tag --contains now takes a long time

[Junio C Hamano]

Jerry Snitselaar <jsnitsel@redhat.com> writes:

> Is this known and being looked into? I've seen a jump from 12 seconds
> to over 9 minutes with running git tag --contains on my kernel repo.

Thanks for a report.  Yes, it seems that there is a recent
regression on the 'master' branch, not yet in any released version,
and we can observe with a much smaller repository X-<.  E.g.

    git tag --contains v2.5.0~12

in git itself seems to have got 10 times slower.


> snits ~/dev/linux> git --version
> git version 2.6.1.145.gb27dacc
>
> snits ~/dev/linux> time git tag --contains 825fcfc
> next-20151012
> next-20151013
> v4.3-rc5
>
> real	9m4.765s
> user	8m56.157s
> sys	0m2.450s
>
>
>
> snits ~/dev/linux> git --version
> git version 2.5.0.275.gac4cc86
>
> snits ~/dev/linux> time git tag --contains 825fcfc
> next-20151012
> next-20151013
> v4.3-rc5
>
> real	0m12.842s
> user	0m11.536s
> sys	0m1.098s
>
>
>
> b7cc53e92c806b73e14b03f60c17b7c29e52b4a4 is the first bad commit
> commit b7cc53e92c806b73e14b03f60c17b7c29e52b4a4
> Author: Karthik Nayak <karthik.188@gmail.com>
> Date:   Fri Sep 11 20:36:16 2015 +0530
>
>    tag.c: use 'ref-filter' APIs
>
>    Make 'tag.c' use 'ref-filter' APIs for iterating through refs, sorting
>    and printing of refs. This removes most of the code used in 'tag.c'
>    replacing it with calls to the 'ref-filter' library.
>
>    Make 'tag.c' use the 'filter_refs()' function provided by 'ref-filter'
>    to filter out tags based on the options set.
>
>    For printing tags we use 'show_ref_array_item()' function provided by
>    'ref-filter'.
>
>    We improve the sorting option provided by 'tag.c' by using the sorting
>    options provided by 'ref-filter'. This causes the test 'invalid sort
>    parameter on command line' in t7004 to fail, as 'ref-filter' throws an
>    error for all sorting fields which are incorrect. The test is changed
>    to reflect the same.
>
>    Modify documentation for the same.
>
>    Mentored-by: Christian Couder <christian.couder@gmail.com>
>    Mentored-by: Matthieu Moy <matthieu.moy@grenoble-inp.fr>
>    Signed-off-by: Karthik Nayak <karthik.188@gmail.com>
>    Signed-off-by: Junio C Hamano <gitster@pobox.com>

Re: git tag --contains now takes a long time

[Karthik Nayak]

On Sat, Oct 17, 2015 at 3:37 AM, Jerry Snitselaar <jsnitsel@redhat.com> wrote:
> Is this known and being looked into? I've seen a jump from 12 seconds
> to over 9 minutes with running git tag --contains on my kernel repo.
>

This wasn't known, thanks for bringing it up.

>
> snits ~/dev/linux> git --version
> git version 2.6.1.145.gb27dacc
>
> snits ~/dev/linux> time git tag --contains 825fcfc
> next-20151012
> next-20151013
> v4.3-rc5
>
> real    9m4.765s
> user    8m56.157s
> sys     0m2.450s
>
>
>
> snits ~/dev/linux> git --version
> git version 2.5.0.275.gac4cc86
>
> snits ~/dev/linux> time git tag --contains 825fcfc
> next-20151012
> next-20151013
> v4.3-rc5
>
> real    0m12.842s
> user    0m11.536s
> sys     0m1.098s
>
>
> b7cc53e92c806b73e14b03f60c17b7c29e52b4a4 is the first bad commit
> commit b7cc53e92c806b73e14b03f60c17b7c29e52b4a4
> Author: Karthik Nayak <karthik.188@gmail.com>
> Date:   Fri Sep 11 20:36:16 2015 +0530
>
>    tag.c: use 'ref-filter' APIs
>
>    Make 'tag.c' use 'ref-filter' APIs for iterating through refs, sorting
>    and printing of refs. This removes most of the code used in 'tag.c'
>    replacing it with calls to the 'ref-filter' library.
>
>    Make 'tag.c' use the 'filter_refs()' function provided by 'ref-filter'
>    to filter out tags based on the options set.
>
>    For printing tags we use 'show_ref_array_item()' function provided by
>    'ref-filter'.
>
>    We improve the sorting option provided by 'tag.c' by using the sorting
>    options provided by 'ref-filter'. This causes the test 'invalid sort
>    parameter on command line' in t7004 to fail, as 'ref-filter' throws an
>    error for all sorting fields which are incorrect. The test is changed
>    to reflect the same.
>
>    Modify documentation for the same.
>
>    Mentored-by: Christian Couder <christian.couder@gmail.com>
>    Mentored-by: Matthieu Moy <matthieu.moy@grenoble-inp.fr>
>    Signed-off-by: Karthik Nayak <karthik.188@gmail.com>
>    Signed-off-by: Junio C Hamano <gitster@pobox.com>

As Junio mentioned I did notice ~13x slower speed.

 $ git version

[12:02:08]
git version 2.5.0.275.gac4cc86

$ time git tag --contains HEAD~300
                                                    [12:06:03]
next-20150924
next-20151016
v4.3-rc1
v4.3-rc2
v4.3-rc3
v4.3-rc4
v4.3-rc5
git tag --contains HEAD~300  2.89s user 0.14s system 99% cpu 3.031 total

After applying b7cc53e92c806b73e14b03f60c17b7c29e52b4a4

 $ git version

[12:07:33]
git version 2.5.0.276.gb7cc53e

 $ time git tag --contains HEAD~300
                                                     [12:07:35]
next-20150924
next-20151016
v4.3-rc1
v4.3-rc2
v4.3-rc3
v4.3-rc4
v4.3-rc5
../Git/git tag --contains HEAD~300  38.30s user 0.19s system 99% cpu
38.519 total

So I did poke around a little. I think I missed this out on the
original commit (b7cc53e92c806b73e14b03f60c17b7c29e52b4a4).

diff --git a/builtin/tag.c b/builtin/tag.c
index 977a18c..2c5a9f1 100644
--- a/builtin/tag.c
+++ b/builtin/tag.c
@@ -49,6 +49,7 @@ static int list_tags(struct ref_filter *filter,
struct ref_sorting *sorting)
                format = "%(refname:short)";

        verify_ref_format(format);
+       filter->with_commit_tag_algo = 1;
        filter_refs(&array, filter, FILTER_REFS_TAGS);
        ref_array_sort(sorting, &array);

After applying this and running the test again, we get:

 $ git version

[12:09:13]
git version 2.5.0.276.gb7cc53e.dirty

 $ time git tag --contains HEAD~300
                                                [12:12:00]
next-20150924
next-20151016
v4.3-rc1
v4.3-rc2
v4.3-rc3
v4.3-rc4
v4.3-rc5
../Git/git tag --contains HEAD~300  2.85s user 0.18s system 99% cpu 3.031 total


Could you Squash that in, Junio?

-- 
Regards,
Karthik Nayak

Re: git tag --contains now takes a long time

[Jerry Snitselaar]

On Sat Oct 17 15, Karthik Nayak wrote:
>On Sat, Oct 17, 2015 at 3:37 AM, Jerry Snitselaar <jsnitsel@redhat.com> wrote:
>> Is this known and being looked into? I've seen a jump from 12 seconds
>> to over 9 minutes with running git tag --contains on my kernel repo.
>>
>
>This wasn't known, thanks for bringing it up.
>
>>
>> snits ~/dev/linux> git --version
>> git version 2.6.1.145.gb27dacc
>>
>> snits ~/dev/linux> time git tag --contains 825fcfc
>> next-20151012
>> next-20151013
>> v4.3-rc5
>>
>> real    9m4.765s
>> user    8m56.157s
>> sys     0m2.450s
>>
>>
>>
>> snits ~/dev/linux> git --version
>> git version 2.5.0.275.gac4cc86
>>
>> snits ~/dev/linux> time git tag --contains 825fcfc
>> next-20151012
>> next-20151013
>> v4.3-rc5
>>
>> real    0m12.842s
>> user    0m11.536s
>> sys     0m1.098s
>>
>>
>> b7cc53e92c806b73e14b03f60c17b7c29e52b4a4 is the first bad commit
>> commit b7cc53e92c806b73e14b03f60c17b7c29e52b4a4
>> Author: Karthik Nayak <karthik.188@gmail.com>
>> Date:   Fri Sep 11 20:36:16 2015 +0530
>>
>>    tag.c: use 'ref-filter' APIs
>>
>>    Make 'tag.c' use 'ref-filter' APIs for iterating through refs, sorting
>>    and printing of refs. This removes most of the code used in 'tag.c'
>>    replacing it with calls to the 'ref-filter' library.
>>
>>    Make 'tag.c' use the 'filter_refs()' function provided by 'ref-filter'
>>    to filter out tags based on the options set.
>>
>>    For printing tags we use 'show_ref_array_item()' function provided by
>>    'ref-filter'.
>>
>>    We improve the sorting option provided by 'tag.c' by using the sorting
>>    options provided by 'ref-filter'. This causes the test 'invalid sort
>>    parameter on command line' in t7004 to fail, as 'ref-filter' throws an
>>    error for all sorting fields which are incorrect. The test is changed
>>    to reflect the same.
>>
>>    Modify documentation for the same.
>>
>>    Mentored-by: Christian Couder <christian.couder@gmail.com>
>>    Mentored-by: Matthieu Moy <matthieu.moy@grenoble-inp.fr>
>>    Signed-off-by: Karthik Nayak <karthik.188@gmail.com>
>>    Signed-off-by: Junio C Hamano <gitster@pobox.com>
>
>As Junio mentioned I did notice ~13x slower speed.
>
> $ git version
>
>[12:02:08]
>git version 2.5.0.275.gac4cc86
>
>$ time git tag --contains HEAD~300
>                                                    [12:06:03]
>next-20150924
>next-20151016
>v4.3-rc1
>v4.3-rc2
>v4.3-rc3
>v4.3-rc4
>v4.3-rc5
>git tag --contains HEAD~300  2.89s user 0.14s system 99% cpu 3.031 total
>
>After applying b7cc53e92c806b73e14b03f60c17b7c29e52b4a4
>
> $ git version
>
>[12:07:33]
>git version 2.5.0.276.gb7cc53e
>
> $ time git tag --contains HEAD~300
>                                                     [12:07:35]
>next-20150924
>next-20151016
>v4.3-rc1
>v4.3-rc2
>v4.3-rc3
>v4.3-rc4
>v4.3-rc5
>../Git/git tag --contains HEAD~300  38.30s user 0.19s system 99% cpu
>38.519 total
>
>So I did poke around a little. I think I missed this out on the
>original commit (b7cc53e92c806b73e14b03f60c17b7c29e52b4a4).
>
>diff --git a/builtin/tag.c b/builtin/tag.c
>index 977a18c..2c5a9f1 100644
>--- a/builtin/tag.c
>+++ b/builtin/tag.c
>@@ -49,6 +49,7 @@ static int list_tags(struct ref_filter *filter,
>struct ref_sorting *sorting)
>                format = "%(refname:short)";
>
>        verify_ref_format(format);
>+       filter->with_commit_tag_algo = 1;
>        filter_refs(&array, filter, FILTER_REFS_TAGS);
>        ref_array_sort(sorting, &array);
>
>After applying this and running the test again, we get:
>
> $ git version
>
>[12:09:13]
>git version 2.5.0.276.gb7cc53e.dirty
>
> $ time git tag --contains HEAD~300
>                                                [12:12:00]
>next-20150924
>next-20151016
>v4.3-rc1
>v4.3-rc2
>v4.3-rc3
>v4.3-rc4
>v4.3-rc5
>../Git/git tag --contains HEAD~300  2.85s user 0.18s system 99% cpu 3.031 total
>
>
>Could you Squash that in, Junio?
>
>-- 
>Regards,
>Karthik Nayak

snits ~/dev/linux> time git tag --contains 825fcfc
next-20151012
next-20151013
v4.3-rc5

real	0m16.998s
user	0m12.539s
sys	0m1.572s


That worked for me.


Tested-by: Jerry Snitselaar <jsnitsel@redhat.com>

Re: git tag --contains now takes a long time

[Matthieu Moy]

Karthik Nayak <karthik.188@gmail.com> writes:

> Could you Squash that in, Junio?

The guilty commit is in master, so you'll need a new commit to fix the
old one. Can you send a patch with a proper commit message (referencing
b7cc53e92c806b73e14b03f60c17b7c29e52b4a4)?

We should both have catched this earlier (by review and/or benchmark).
Sorry we didn't, and thanks to Jerry for the report.

-- 
Matthieu Moy
http://www-verimag.imag.fr/~moy/

Re: git tag --contains now takes a long time

[Karthik Nayak]

On Sat, Oct 17, 2015 at 9:28 PM, Matthieu Moy
<Matthieu.Moy@grenoble-inp.fr> wrote:
> Karthik Nayak <karthik.188@gmail.com> writes:
>
>> Could you Squash that in, Junio?
>
> The guilty commit is in master, so you'll need a new commit to fix the
> old one. Can you send a patch with a proper commit message (referencing
> b7cc53e92c806b73e14b03f60c17b7c29e52b4a4)?
>
> We should both have catched this earlier (by review and/or benchmark).
> Sorry we didn't, and thanks to Jerry for the report.
>

Yea, I'm surprised we didn't notice. Either ways, I'll reply with a
fix commit :)

-- 
Regards,
Karthik Nayak

Re: git tag --contains now takes a long time

[Junio C Hamano]

Karthik Nayak <karthik.188@gmail.com> writes:

> So I did poke around a little. I think I missed this out on the
> original commit (b7cc53e92c806b73e14b03f60c17b7c29e52b4a4).
>
> diff --git a/builtin/tag.c b/builtin/tag.c
> index 977a18c..2c5a9f1 100644
> --- a/builtin/tag.c
> +++ b/builtin/tag.c
> @@ -49,6 +49,7 @@ static int list_tags(struct ref_filter *filter,
> struct ref_sorting *sorting)
>                 format = "%(refname:short)";
>
>         verify_ref_format(format);
> +       filter->with_commit_tag_algo = 1;
>         filter_refs(&array, filter, FILTER_REFS_TAGS);
>         ref_array_sort(sorting, &array);
> ...
>
> Could you Squash that in, Junio?

Do we have two implementations that are supposed to compute the same
thing, and with the bit set to 1, the faster of these two is used?
Is there a reason somebody may want to use the slower one?  What
difference other than performance does the choice of this bit makes,
and why?

I think the answers to the above questions deserve to be in the log
message (no, I do not think I can "squash it in", rewriting the
commit that has already been merged to 'next' and 'master').

Thanks.

Re: git tag --contains now takes a long time

[Karthik Nayak]

On Sun, Oct 18, 2015 at 2:58 AM, Junio C Hamano <gitster@pobox.com> wrote:
> Karthik Nayak <karthik.188@gmail.com> writes:
>
>> So I did poke around a little. I think I missed this out on the
>> original commit (b7cc53e92c806b73e14b03f60c17b7c29e52b4a4).
>>
>> diff --git a/builtin/tag.c b/builtin/tag.c
>> index 977a18c..2c5a9f1 100644
>> --- a/builtin/tag.c
>> +++ b/builtin/tag.c
>> @@ -49,6 +49,7 @@ static int list_tags(struct ref_filter *filter,
>> struct ref_sorting *sorting)
>>                 format = "%(refname:short)";
>>
>>         verify_ref_format(format);
>> +       filter->with_commit_tag_algo = 1;
>>         filter_refs(&array, filter, FILTER_REFS_TAGS);
>>         ref_array_sort(sorting, &array);
>> ...
>>
>> Could you Squash that in, Junio?
>
> Do we have two implementations that are supposed to compute the same
> thing, and with the bit set to 1, the faster of these two is used?
> Is there a reason somebody may want to use the slower one?  What
> difference other than performance does the choice of this bit makes,
> and why?
>
> I think the answers to the above questions deserve to be in the log
> message (no, I do not think I can "squash it in", rewriting the
> commit that has already been merged to 'next' and 'master').
>
> Thanks.

I'll resend the patch then with the changed commit message.

Thanks.

-- 
Regards,
Karthik Nayak