Re: [PATCH v3 4/4] connected: add incremental connectivity check via rev-list

On Thu, Oct 15, 2026 at 11:51:46AM +0200, Kristofer Karlsson wrote:

On Thu, 15 Oct 2026 at 08:55, Patrick Steinhardt [off-list ref] wrote:

quoted

On Mon, Oct 12, 2026 at 12:07:57PM +0000, Kristofer Karlsson via GitGitGadget wrote:

quoted

From: Kristofer Karlsson <redacted>

[snip]

quoted

quoted

Scaling incoming commit count (200K files, 10 files/commit):

    commits    full  incr.  full/incr
          1    0.14s  0.01s   14.0x
         10    0.15s  0.01s   15.0x
        100    0.19s  0.05s    3.8x
        500    0.32s  0.27s    1.2x
       3000    1.23s  1.52s    0.8x
       5000    1.88s  2.43s    0.8x
      10000    3.72s  5.36s    0.7x

With many commits the per-commit overhead of scanning both
the new and parent root trees accumulates and incremental
becomes slower.  Breakeven is between 500 and 3000 commits
and the ratio stabilizes near 0.7x for this fixture.

And worse the more commits we have. So the new mode is only really
applicable in scenarios where you know what your typical workload looks
like. The big question is of course whether we can have the best of both
worlds, where Git knows to switch between the two modes once it crosses
the threshold.

I think this is where it gets tricky to reason about.  The win
from from larger trees pays off without bound -- the larger
trees you have, the larger the win.

Scaling with commits on the other hand we have ceiling of how
much it can regress.  I am thinking that could be reasonable
that anyone who enables the config flag for this mode could
simply accept that it would likely speed things up in most
cases but in other cases they could see a ~1.5x regression.

I am hoping that this tradeoff would then be acceptable,
otherwise we would indeed need to add some way of switching,
though I don't think there's a single good indicator value
for when it's better to switch.

I could add a new config flag like
transfer.connectivityCheckIncrementalMaxCommits to control it
perhaps.

Yeah, making this configurable may be reasonable. The way I understand
it, the new connectivity check is most likely to be usable for smaller,
incremental pushes. And based on the above table you have, we see that
up to 1k commits the new algorithm is faster. Sure, it's an artificial
benchmark, but maybe this is a good enough cutoff for now?

quoted

quoted

diff --git a/Documentation/technical/connectivity-check.adoc b/Documentation/technical/connectivity-check.adoc
index abef02debd..a1d2e9709c 100644
--- a/Documentation/technical/connectivity-check.adoc
+++ b/Documentation/technical/connectivity-check.adoc

[snip]

quoted

quoted

+struct verify_state {
+     kh_oid_tree_t *trees;
+     struct oidset trusted_blobs;
+     int trees_loaded;
+     int blobs_checked;

These probably should be `size_t`.

Sure, I can change that.  Or intmax_t since we'll need to cast
to that later anyway for the trace2 output?

Hm, okay. Not a fan of using signed integers as counters, but so be it.

quoted

quoted

+     if (type >= 0)
+             die(_("object %s is a %s, not a %s"),
+                 oid_to_hex(oid), type_name(type), "blob");

I'd love not having all these calls to `die()`, as this logic is
essentially part of a library, and dying inside a library is a bad
smell. We do this everywhere else in Git, too, but we're slowly getting
rid of this as part of our libification efforts.

I think this would be a bigger refactor in general --
the existing connectivity check also dies as the way to
report problems.  This works since it's running as a subprocess.

If this is something we want to change, I think it would be
good to do that refactoring separately and make the connectivity
check subprocess only die() at the very edge, and making all of
the internal library code support not dying.  My first prototype
tried to do this but the amount of changes to internal code got
out of hand, so this version was the simplest I could make it.

But I'm happy to take a step back and revisit that approach if
this is a blocker.

I mostly aim at not making _new_ library code die anymore. In any case,
I don't think it's a blocker, but I nowadays consider this to be a code
smell.

It would be great if we eventually deny-listed `die()` completely for
anything compiled into libgit.a.

Patrick