From: Derrick Stolee <stolee@gmail.com>
To: "Thomas Gummerer" <t.gummerer@gmail.com>, "René Scharfe" <l.s.r@web.de>
Cc: git@vger.kernel.org, Jeff King <peff@peff.net>
Subject: Re: [PATCH] commit-reach: fix sorting commits by generation
Date: Wed, 24 Oct 2018 09:19:15 -0400 [thread overview]
Message-ID: <e2e1bfd8-bb43-0567-0eb7-770ae16da7e2@gmail.com> (raw)
In-Reply-To: <20181023203237.GF4883@hank.intra.tgummerer.com>
On 10/23/2018 4:32 PM, Thomas Gummerer wrote:
> On 10/22, René Scharfe wrote:
>> Am 22.10.2018 um 23:10 schrieb Thomas Gummerer:
>>
>> Anyway, your implied question was discussed back then. Derrick wrote:
>>
>> The reason to sort is to hopefully minimize the amount we walk by
>> exploring the "lower" commits first. This is a performance-only thing,
>> not a correctness issue (which is why the bug exists). Even then, it is
>> just a heuristic.
> Thanks for pointing that out!
>
>> Does b6723e4671 in pu (commit-reach: fix first-parent heuristic) change
>> that picture? Did a quick test and found no performance difference with
>> and without the fix on top, i.e. proper sorting didn't seem to matter.
> I just gave 'test-tool reach can_all_from_reach' a try and got the
> same results, with or without the fix the times are very similar. I
> haven't had time to follow the commit-graph series though, so I'm not
> sure I used it correctly.
Thanks for your attention here. I've been thinking a lot about this
heuristic and have concluded the following two things are true:
(1) When we return 1, the order that we explore the 'from' commits does
not change the explored set of commits.
(2) When we return 0, the order that we explore the 'to' commits will
change the explored set, but it is difficult to say that the heuristic
helps more than it hurts.
Item (1) is contrary to what I had thought when I first created the
heuristic.
The details are tricky, but essentially each DFS starting at a 'from'
commit may be short-circuited due to a prior walk, but swapping the
order of those two 'from' commits would lead to the same set of commits
to be explored (with the short-circuit happening in the other commit).
The only change is that we can terminate early if we fully explore a
'from' commit and do not find a commit marked with 'with_flag'. In this
sense, it would be best to explore the commits that are "closest" to the
generation number cutoff first, as we can maybe find a negative answer
earlier in the search.
In this sense, we could remove the sort entirely and probably not have
much performance hit. But since the set of 'from' commits is probably
much smaller than the set of commits to explore, the sort is likely
inexpensive.
In conclusion: I cannot say that this sort is super-important. As for
the potential benefits in (2), I'll leave that to people who run git as
a server who may have telemetry around fetch negotiation. How often do
we actually say we need more rounds of negotiation? What kinds of data
shapes matter there?
Thanks,
-Stolee
prev parent reply other threads:[~2018-10-24 13:19 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-10-22 21:10 [PATCH] commit-reach: fix sorting commits by generation Thomas Gummerer
2018-10-22 21:53 ` René Scharfe
2018-10-23 20:32 ` Thomas Gummerer
2018-10-24 13:19 ` Derrick Stolee [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=e2e1bfd8-bb43-0567-0eb7-770ae16da7e2@gmail.com \
--to=stolee@gmail.com \
--cc=git@vger.kernel.org \
--cc=l.s.r@web.de \
--cc=peff@peff.net \
--cc=t.gummerer@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).