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

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 
      <YMypONmXt142dhbb@coredump.intra.peff.net> [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