Re: [PATCH 1/6] fetch: speed up lookup of want refs via commit-graph

Derrick Stolee [off-list ref] writes:

I do worry about the case where annotated tags greatly outnumber
branches, so this binary search is extra overhead and the performance
may degrade. Would it be worth checking the ref to see if it lies
within "refs/heads/" (or even _not_ in "refs/tags/") before doing
this commit-graph check?

Ah, clever.

On Fri, Aug 20, 2021 at 10:18:22AM -0700, Junio C Hamano wrote:

Derrick Stolee [off-list ref] writes:

quoted

I do worry about the case where annotated tags greatly outnumber
branches, so this binary search is extra overhead and the performance
may degrade. Would it be worth checking the ref to see if it lies
within "refs/heads/" (or even _not_ in "refs/tags/") before doing
this commit-graph check?

Ah, clever.

Good idea. Benchmarks for my test repository (which definitely isn't
representative, but it's at least some numbers) show that restricting to
"refs/heads/" diminishes almost all the gains, while restricting to
everything but "refs/tags/" performs almost the same (it's a tiny bit
slower, probably because of the added string comparisons):

    Benchmark #1: all refs: git-fetch
      Time (mean ± σ):     32.959 s ±  0.282 s    [User: 29.801 s, System: 5.137 s]
      Range (min … max):   32.760 s … 33.158 s    2 runs

    Benchmark #2: refs/heads: git-fetch
      Time (mean ± σ):     56.955 s ±  0.002 s    [User: 53.447 s, System: 5.362 s]
      Range (min … max):   56.953 s … 56.957 s    2 runs

    Benchmark #3: !refs/tags: git-fetch
      Time (mean ± σ):     33.447 s ±  0.003 s    [User: 30.160 s, System: 5.027 s]
      Range (min … max):   33.444 s … 33.449 s    2 runs

    Summary
      'all refs: git-fetch' ran
        1.01 ± 0.01 times faster than '!refs/tags: git-fetch'
        1.73 ± 0.01 times faster than 'refs/heads: git-fetch'

This is easily explained by the fact that the test repo has most of its
refs neither in "refs/tags/" nor in "refs/heads/", but rather in special
namespaces like "refs/merge-requests/", "refs/environments/" or
"refs/keep-around/".

I like the idea of excluding "refs/tags/" though: as you point out,
chances are high that these don't point to commits but to annotated tags
instead. So I'll go with that, thanks!

Patrick

On 8/23/2021 2:46 AM, Patrick Steinhardt wrote:

On Fri, Aug 20, 2021 at 10:18:22AM -0700, Junio C Hamano wrote:

quoted

Derrick Stolee [off-list ref] writes:

quoted

I do worry about the case where annotated tags greatly outnumber
branches, so this binary search is extra overhead and the performance
may degrade. Would it be worth checking the ref to see if it lies
within "refs/heads/" (or even _not_ in "refs/tags/") before doing
this commit-graph check?

Ah, clever.

Good idea. Benchmarks for my test repository (which definitely isn't
representative, but it's at least some numbers) show that restricting to
"refs/heads/" diminishes almost all the gains, while restricting to
everything but "refs/tags/" performs almost the same (it's a tiny bit
slower, probably because of the added string comparisons):

    Benchmark #1: all refs: git-fetch
      Time (mean ± σ):     32.959 s ±  0.282 s    [User: 29.801 s, System: 5.137 s]
      Range (min … max):   32.760 s … 33.158 s    2 runs

    Benchmark #2: refs/heads: git-fetch
      Time (mean ± σ):     56.955 s ±  0.002 s    [User: 53.447 s, System: 5.362 s]
      Range (min … max):   56.953 s … 56.957 s    2 runs

    Benchmark #3: !refs/tags: git-fetch
      Time (mean ± σ):     33.447 s ±  0.003 s    [User: 30.160 s, System: 5.027 s]
      Range (min … max):   33.444 s … 33.449 s    2 runs

    Summary
      'all refs: git-fetch' ran
        1.01 ± 0.01 times faster than '!refs/tags: git-fetch'
        1.73 ± 0.01 times faster than 'refs/heads: git-fetch'

Thanks for testing both options.

This is easily explained by the fact that the test repo has most of its
refs neither in "refs/tags/" nor in "refs/heads/", but rather in special
namespaces like "refs/merge-requests/", "refs/environments/" or
"refs/keep-around/".

That makes sense to me. GitHub also stores refs like refs/pull/ so I can
understand not wanting to restrict to refs/heads/.

I like the idea of excluding "refs/tags/" though: as you point out,
chances are high that these don't point to commits but to annotated tags
instead. So I'll go with that, thanks!

Yeah, that makes sense as a good way forward.

Thanks,
-Stolee