Re: commit-graph is cool (overcoming add_missing_tags() perf issues)

From: Jeff King <peff@peff.net>
Date: Oct 17, 2018, 18:31 UTC
Message-ID: <20181017183125.GE28326@sigill.intra.peff.net>
In-Reply-To: <CABPp-BECpSOxudovjbDG_3W9wus102RW+E+qPmd4g3Qyd-QDKQ@mail.gmail.com>

On Wed, Oct 17, 2018 at 11:00:03AM -0700, Elijah Newren wrote:

Show 15 quoted lines

> Digging in, almost all the time was CPU-bound and spent in
> add_missing_tags()[2].  If I'm reading the code correctly, it appears
> that function loops over each tag, calling in_merge_bases_many() once
> per tag.  Thus, for his case, we were potentially walking all of
> history of the main branch 2.5k times.  That seemed rather suboptimal.
> 
> Before attempting to optimize, I decided to try out the commit-graph
> with a version of git from pu.  While I expected a speed-up, I was a
> bit suprised that it was a factor of over 100; dropping the time for
> local dry-run push[2] to sub-second.  A quick look suggests that
> commit-graph doesn't fix the fact that we call in_merge_bases_many() N
> times from add_missing_tags() and thus likely need to do N merge base
> computations, it just makes each of the N much faster.  So, perhaps
> there's still another scaling issue we'll eventually need to address,
> but for now, I'm pretty excited about commit-graph.

Yeah, I think this case would probably still benefit from an all-points traversal. This want to be basically the same as what "git tag --merged" is doing, I would think (see ref-filter.c:do_merge_filter).

  As an aside, it looks like do_merge_filter uses prepare_revision_walk(),
  which IIRC means that it is susceptible to wrong answers due to
  clock skew (basically because of the use of commit timestamps for
  traversal order). This seems like another place where generation
  numbers could make a quiet improvement.

-Peff