looking up object types quickly, was Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging

On Sun, Mar 22, 2020 at 12:04:24PM +0100, SZEDER Gábor wrote:

They don't necessarily produce the same set of commits, of course, but for the purposes of "commit-graph write" I think they can generally be considered interchangeable.

The speed depends on a couple of factors. One is just the makeup of the repository: tree size, how many are deltas, etc. But a big one is whether commit-graphs are already enabled. :)

On linux.git without commit-graphs, both of these take about 7.5s for me:

  git cat-file --batch-all-objects --unordered --batch-check='%(objecttype) %(objectname)'

  git rev-list --all

But with graphs, the latter takes about 700ms.

I was coincidentally thinking about this problem ("show me all commits") for something unrelated recently, and I do think that cat-file invocation could be sped up in some cases. Here are a few ideas:

1. If the pack has a .bitmap file, it contains 4 "type" bitmaps that you
   can use to quickly determine the type of a given object. But:

   - the current code for loading bitmaps files is slower than we'd
     need; it indexes all of the commit bitmaps, but we wouldn't use
     them. So we'd want something that just loads the type bitmaps and
     stops.

   - you have to know the bit position of the object you're interested
     in, which implies computing the revidx. We could provide a "bit
     position" cache in the bitmap file (basically one uint32_t for each
     object giving the packfile order position, but stored in pack .idx
     order).

   Neither is too hard a problem, but it's clearly not just a small
   patch to consult the bitmap.

   It could be patched directly into oid_object_info_extended(), which
   could do individual type lookups this way. But it would be faster
   still if callers could say "I'm only interested in commits", in which
   case we could just quickly walk the commit-type bitmap in one pass
   (to get the commits in just that packfile, and then go through the
   other objects the old-fashioned way).

2. The commit-graph file can quickly tell us whether an object is a
   commit. But unfortunately it can give us a definite "yes", but not a
   definite "no" (because it might be a commit that just isn't (yet) in
   the graph file). So we'd have to find the real type of any
   non-commits, and I think that's where we spend the bulk of our time
   anyway.

3. To find the type of a delta object, we have to walk back to a base
   object with a concrete type. When we access the actual object
   contents, we cache intermediate bases to avoid digging down the same
   chain over and over. But I don't think there's any such cache for the
   type lookup. So if you have a 50-deep delta chain and want the type
   of each object, you'll walk down 49 links, then 48 links, and so on.
   It probably wouldn't be that hard to have a small type cache (or just
   allow the existing cache to have entries for "I know the type, but
   don't have the contents").

I suspect (1) would give the biggest speedup, but is more work and requires bitmaps. I think (3) is likely to give a moderate win and probably isn't that big a patch.

-Peff