Subject: [PATCH v2 0/3] Speed up connectivity checks via bitmaps

From: Patrick Steinhardt <[email-masked]>
Date: Mon, 28 Jun 2021 07:33:02 +0200

Hi,

this is version 2 of my patch series which tries to speed up
connectivity checks in git-receive-pack(1).

This version is a complete rewrite after my initial approach of using
the quarantine directory has been shot down due to changes in semantics.
This second version is thus an alternative approach using bitmaps. The
implementation is quite simple: if we have a bitmap, then we walk the
new tips until we hit a bitmapped object. Given that bitmapped objects
are by definition fully connected, we can then be sure that all pushed
tips are, too.

I'm not sure I'm happy with results in this series. While it does show a
speedup in the area I'm trying to optimize (repos with many refs), there
are two things which make me hesitant:

    - First, there seems to be significant overhead in loading the
      packfile. This is something Peff has already pointed out in 
      <[email-masked]> [1].

    - In repos which have out-of-date bitmaps, we're potentially going
      to walk a lot more objects than we used to.

Taking these two issues together, this version is probably more of a
request for comments: do we want to make above tradeoffs? Are there
better alternatives? Any input is welcome.

Patrick

Patrick Steinhardt (3):
  p5400: add perf tests for git-receive-pack(1)
  receive-pack: skip connectivity checks on delete-only commands
  connected: implement connectivity check using bitmaps

 builtin/receive-pack.c       |  49 ++++++++-----
 connected.c                  | 136 +++++++++++++++++++++++++++++++++++
 pack-bitmap.c                |   4 +-
 pack-bitmap.h                |   2 +
 t/perf/p5400-receive-pack.sh |  97 +++++++++++++++++++++++++
 5 files changed, 267 insertions(+), 21 deletions(-)
 create mode 100755 t/perf/p5400-receive-pack.sh

-- 
2.32.0