patch, 5 partssome "log --decorate" optimizations

I was recently pointed to a repository where:

  git log --format="%H %P" old..new

was abysmally slow, even though old..new only had a few commits, because load_ref_decorations() takes a long time (and kicks in due to the auto-decorate behavior). Leaving aside that "rev-list" would probably be a better tool here, it seems there's some low-hanging fruit:

  - a user-format that doesn't show decorations doesn't need to load
    them (fixed in patch 2 below)

  - we're pretty eager to parse the objects at the tip of each ref
    (fixed in patch 5 below)

The other commits are just cleanups and preparatory refactors.

  [1/5]: pretty.h: update and expand docstring for userformat_find_requirements()
  [2/5]: log: avoid loading decorations for userformats that don't need it
  [3/5]: object.h: expand docstring for lookup_unknown_object()
  [4/5]: object.h: add lookup_object_by_type() function
  [5/5]: load_ref_decorations(): avoid parsing non-tag objects

 builtin/log.c |  3 +++
 log-tree.c    |  6 ++++--
 object.c      | 18 ++++++++++++++++++
 object.h      | 20 +++++++++++++++++++-
 pretty.c      |  4 ++++
 pretty.h      |  8 ++++++--
 reachable.c   | 18 ------------------
 7 files changed, 54 insertions(+), 23 deletions(-)

-Peff

The comment only mentions "notes", but there are more fields now (and I'm about to add another). Let's make it more general, and stick the struct next to the function to make the list of possibilities obvious.

While we're touching this comment, let's also mention the behavior of NULL, which some callers rely on (though in the long run, this global is pretty nasty and probably should get moved into rev_info).

Signed-off-by: Jeff King <peff@peff.net>
---
 pretty.h | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)

If no --decorate option is given, we default to auto-decoration. And when that kicks in, cmd_log_init_finish() will unconditionally load the decoration refs.

However, if we are using a user-format that does not include "%d" or "%D", we won't show the decorations at all, so we don't need to load them. We can detect this case and auto-disable them by adding a new field to our userformat_want helper. We can do this even when the user explicitly asked for --decorate, because it can't affect the output at all.

This patch consistently reduces the time to run "git log -1 --format=%H" on my git.git clone (with ~2k refs) from 34ms to 7ms. On a much more extreme real-world repository (with ~220k refs), it goes from 2.5s to 4ms.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/log.c | 3 +++
 pretty.c      | 4 ++++
 pretty.h      | 1 +
 3 files changed, 8 insertions(+)

The lookup_unknown_object() system is not often used and is somewhat confusing. Let's try to explain it a bit more (which is especially important as I'm adding a related but slightly different function in the next commit).

Signed-off-by: Jeff King <peff@peff.net>
---
 object.h | 13 ++++++++++++-
 1 file changed, 12 insertions(+), 1 deletion(-)

In some cases it's useful for efficiency reasons to get the type of an object before deciding whether to parse it, but we still want an object struct. E.g., in reachable.c, bitmaps give us the type, but we just want to mark flags on each object. Likewise, we may loop over every object and only parse tags in order to peel them; checking the type first lets us avoid parsing the non-tags.

But our lookup_blob(), etc, functions make getting an object struct annoying: we have to call the right function for every type. And we cannot just use the generic lookup_object(), because it only returns an already-seen object; it won't allocate a new object struct.

Let's provide a function that dispatches to the correct lookup_* function based on a run-time type. In fact, reachable.c already has such a helper, so we'll just make that public.

I did change the return type from "void *" to "struct object *". While the former is a clever way to avoid casting inside the function, it's less safe and less informative to people reading the function declaration.

The next commit will add a new caller.

Signed-off-by: Jeff King <peff@peff.net>
---
 object.c    | 18 ++++++++++++++++++
 object.h    |  7 +++++++
 reachable.c | 18 ------------------
 3 files changed, 25 insertions(+), 18 deletions(-)

When we load the ref decorations, we parse the object pointed to by each ref in order to get a "struct object". This is unnecessarily expensive; we really only need the object struct, and don't even look at the parsed contents. The exception is tags, which we do need to peel.

We can improve this by looking up the object type first (which is much cheaper), and skipping the parse entirely for non-tags. This increases the work slightly for annotated tags (which now do a type lookup _and_ a parse), but decreases it a lot for other types. On balance, this seems to be a good tradeoff.

In my git.git clone, with ~2k refs, most of which are branches, the time to run "git log -1 --decorate" drops from 34ms to 11ms. Even on my linux.git clone, which contains mostly tags and only a handful of branches, the time drops from 30ms to 19ms. And on a more extreme real-world case with ~220k refs, mostly non-tags, the time drops from 2.6s to 650ms.

That command is a lop-sided example, of course, because it does as little non-loading work as possible. But it does show the absolute time improvement. Even in something like a full "git log --decorate" on that extreme repo, we'd still be saving 2s of CPU time.

Ideally we could push this even further, and avoid parsing even tags, by relying on the packed-refs "peel" optimization (which we could do by calling peel_iterated_oid() instead of peeling manually). But we can't do that here. The packed-refs file only stores the bottom-layer of the peel (so in a "tag->tag->commit" chain, it stores only the commit as the peel result). But the decoration code wants to peel the layers individually, annotating the middle layers of the chain.

If the packed-refs file ever learns to store all of the peeled layers, then we could switch to it. Or even if it stored a flag to indicate the peel was not multi-layer (because most of them aren't), then we could use it most of the time and fall back to a manual peel for the rare cases.

Signed-off-by: Jeff King <peff@peff.net>
---
 log-tree.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

On 6/22/2021 12:08 PM, Jeff King wrote:

Do you mean "if (objtype < 0)" here? There is a 'type' variable, but it is an enum decoration_type and I can't find a reason why it would be negative. oid_object_info() _does_ return -1 if there is a problem loading the object, so that would make sense.

This is the only question I had about the entire series. Everything else LGTM.

Thanks, -Stolee

On Tue, Jun 22, 2021 at 12:35:46PM -0400, Derrick Stolee wrote:

Whoops, thanks for catching that. I originally called it "enum object_type type", but then of course the compiler informed that there was already a "type" variable in the function. So I renamed it to "objtype" but missed updating that line. But it still compiled. Yikes. :)

It doesn't trigger in the test suite because it only happens if the repository is corrupted.

Thanks. Here's an amended version of the patch, in case there are no other fixups necessary (fingers crossed).

-Peff

-- >8 --
Subject: [PATCH] load_ref_decorations(): avoid parsing non-tag objects

When we load the ref decorations, we parse the object pointed to by each ref in order to get a "struct object". This is unnecessarily expensive; we really only need the object struct, and don't even look at the parsed contents. The exception is tags, which we do need to peel.

We can improve this by looking up the object type first (which is much cheaper), and skipping the parse entirely for non-tags. This increases the work slightly for annotated tags (which now do a type lookup _and_ a parse), but decreases it a lot for other types. On balance, this seems to be a good tradeoff.

In my git.git clone, with ~2k refs, most of which are branches, the time to run "git log -1 --decorate" drops from 34ms to 11ms. Even on my linux.git clone, which contains mostly tags and only a handful of branches, the time drops from 30ms to 19ms. And on a more extreme real-world case with ~220k refs, mostly non-tags, the time drops from 2.6s to 650ms.

That command is a lop-sided example, of course, because it does as little non-loading work as possible. But it does show the absolute time improvement. Even in something like a full "git log --decorate" on that extreme repo, we'd still be saving 2s of CPU time.

Ideally we could push this even further, and avoid parsing even tags, by relying on the packed-refs "peel" optimization (which we could do by calling peel_iterated_oid() instead of peeling manually). But we can't do that here. The packed-refs file only stores the bottom-layer of the peel (so in a "tag->tag->commit" chain, it stores only the commit as the peel result). But the decoration code wants to peel the layers individually, annotating the middle layers of the chain.

If the packed-refs file ever learns to store all of the peeled layers, then we could switch to it. Or even if it stored a flag to indicate the peel was not multi-layer (because most of them aren't), then we could use it most of the time and fall back to a manual peel for the rare cases.

Signed-off-by: Jeff King <peff@peff.net>
---
 log-tree.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

On Tue, Jun 22, 2021 at 01:06:48PM -0400, Jeff King wrote:

I'm tempted by this as a cleanup on top (I don't want to do it inline, since the diff is so noisy). But I'm also content to leave it.

-- >8 --
Subject: [PATCH] add_ref_decoration(): rename s/type/deco_type/

Now that we have two types (a decoration type and an object type) in the function, let's give them both unique names to avoid accidentally using one instead of the other.

Signed-off-by: Jeff King <peff@peff.net>
---
 log-tree.c | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)

On 6/22/2021 1:09 PM, Jeff King wrote:

Naming is hard. This change seems worth it.

Thanks, -Stolee

On Tue, Jun 22 2021, Jeff King wrote:

[Enter Captain Hindsight]

If you use a slightly different coding style and leverage the information the compiler has to work with you'd get it to error for you, e.g. this on your original patch would catch it:

	diff --git a/log-tree.c b/log-tree.c
	index 8b700e9c142..7e3a011b533 100644
	--- a/log-tree.c
	+++ b/log-tree.c
	@@ -157,9 +157,12 @@ static int add_ref_decoration(const char *refname, const struct object_id *oid,
	 	}
	 
	 	objtype = oid_object_info(the_repository, oid, NULL);
	-	if (type < 0)
	+	switch (type) {
	+	case OBJ_BAD:
	 		return 0;
	-	obj = lookup_object_by_type(the_repository, oid, objtype);
	+	default:
	+		obj = lookup_object_by_type(the_repository, oid, objtype);
	+	}
	 
	 	if (starts_with(refname, "refs/heads/"))
	 		type = DECORATION_REF_LOCAL;

IMO the real problem is an over-reliance on C being so happy to treat
enums as ints (well, with them being ints). If you consistently use
labels you get the compiler to do the checking. For me with gcc and
clang with that on top:
	
	log-tree.c:161:2: error: case value ‘4294967295’ not in enumerated type ‘enum decoration_type’ [-Werror=switch]
	  case OBJ_BAD:
	  ^~~~
	log-tree.c:161:7: error: case value not in enumerated type 'enum decoration_type' [-Werror,-Wswitch]
	        case OBJ_BAD:
	             ^

I think we've disagreed on that exact point before recently, i.e. you think we shouldn't rely on OBJ_BAD in that way, and instead check for any negative value: https://lore.kernel.org/git/YHCZh5nLNVEHCWV2@coredump.intra.peff.net/

This sort of thing is a good reason to pick the opposite pattern. You get the same type checking you'd usually get with anything else in C.

Yes, it is more verbose e.g. in this case, and particularly (as noted downthread of what I linked to) because "enum object_type" contains so many uncommon things, and really should be split up.

In practice I don't think it's too verbose, because once you start
consistently using the pattern you'll usually not be doing conversions
all over the place, and would just do this sort of thing via a helper
that does the type checking, e.g. something like this (or anything else
where you don't lose the type & labels):
	
	diff --git a/log-tree.c b/log-tree.c
	index 8b700e9c142..a61fb01ba3f 100644
	--- a/log-tree.c
	+++ b/log-tree.c
	@@ -130,6 +130,30 @@ static int ref_filter_match(const char *refname,
	 	return 1;
	 }
	 
	+static enum object_type oid_object_info_ok(struct repository *repo,
	+					   struct object_id *oid,
	+					   enum object_type *typep,
	+					   unsigned long *sizep)
	+{
	+	enum object_type type = oid_object_info(repo, oid, sizep);
	+	*typep = type;
	+	switch (type) {
	+	case OBJ_BAD:
	+		return 0;
	+	case OBJ_COMMIT:
	+	case OBJ_TREE:
	+	case OBJ_BLOB:
	+	case OBJ_TAG:
	+		return 1;
	+	case OBJ_NONE:
	+	case OBJ_OFS_DELTA:
	+	case OBJ_REF_DELTA:
	+	case OBJ_ANY:
	+	case OBJ_MAX:
	+		BUG("the enum_object type is too large!");
	+	}
	+}
	+
	 static int add_ref_decoration(const char *refname, const struct object_id *oid,
	 			      int flags, void *cb_data)
	 {
	@@ -156,8 +180,7 @@ static int add_ref_decoration(const char *refname, const struct object_id *oid,
	 		return 0;
	 	}
	 
	-	objtype = oid_object_info(the_repository, oid, NULL);
	-	if (type < 0)
	+	if (!oid_object_info_ok(the_repository, oid, &type, NULL))
	 		return 0;
	 	obj = lookup_object_by_type(the_repository, oid, objtype);
	 

With that pattern GCC narrowlry pulls ahead with showing 4 warnings just about the loss of the type, with Clang at 3 :)

On Tue, Jun 22, 2021 at 08:27:53PM +0200, Ævar Arnfjörð Bjarmason wrote:

Yeah, I agree that would find it in this case. I do find that style slightly harder to read, though. And...

...it would help in this case because OBJ_BAD happens to have a value that is not defined for decoration_type. If it did, then the compiler would be quite happy to consider them equivalent.

So I don't disagree with you exactly, but I'm not sure of the tradeoff of always using switches instead of conditionals (which IMHO is less readable) for more compiler safety that only works sometimes is worth it.

To be clear, my complaint about checking for OBJ_BAD exactly is that it closes the door on other negative return types. And indeed, the switch() you showed above would become a silent bug if we introduced OBJ_BAD_FOR_ANOTHER_READ as "-2" (without any compiler support, because of the "default" case in the switch statement).

Now that's somewhat hypothetical, but in the near-term it also means confirming that any of the functions which get converted from "int" to "enum object_type" are not in fact passing back "-2" in any circumstances.

That said...

Yes, that would deal with that problem. It's definitely a different style, but one that I could get used to. It's a lot more object oriented ("you are not allowed to do numeric logic on an object type; you can only use these accessor methods to query it"). If we were going that route, I would stop having "enum object_type" at all, and instead make it "struct object_type { enum { ... } value }". That would prevent anybody from accidentally just looking at it, and instead force people into that object-oriented style.

I dunno. It is is a big departure from how we do things now. And the bug here notwithstanding, I don't feel like enum confusion has generally been a big source of error for us.

-Peff

On Tue, Jun 22 2021, Jeff King wrote:

This series looks good. I just wonder if between this and my own lookup_{blob,tree,tag,commit}_type() in [1] whether exposing some function between what we have now in parse_object() and parse_object_buffer() wouldn't also do this for you.

I.e. in my patch if you pass a type into parse_object_buffer() I think you'll get the same behavior.

To be clear I see nothing wrong with this, it's more of a musing about how some functions in object.c discover the type on their own, others allow passing it in, sometimes (worse before that series of mine) we relay the not-real-but-inferred-type etc.

1. https://lore.kernel.org/git/patch-10.11-a84f670ac24-20210328T021238Z-avarab@gmail.com/

On Tue, Jun 22, 2021 at 07:06:43PM +0200, Ævar Arnfjörð Bjarmason wrote:

Maybe, but I'm having trouble seeing what would be a helpful abstraction. I don't think I'd want to use parse_object_buffer() here; we don't have a buffer at all (and obviously it could learn to handle NULL, but that's extra code there).

parse_object_buffer() could call this lookup_object_by_type() to get the struct, which would save it a few lines. But it still has to do the if-else chain for each type, because it does other type-specific things.

So I dunno. I would be happy if you came up with something, just because it's nice to minimize the number of places that do this if-else/switch on type. But I have a feeling it's diminishing returns in terms of complexity. If we can at least contain it all to object.c, that's something.

-Peff

On Tue, Jun 22, 2021 at 12:08:40PM -0400, Jeff King wrote:

Yeah, I would be in favor of either of these. Of the two, the latter seems like the simplest thing, but the former provides you all of the information you could hope for.

I suppose that if you are already changing the format of packed-refs, then we might as well do the thing which provides the most information and allows us to optimize *all* cases, not just the vast majority of them.

Of course, that's all way outside of the scope of this patch, which shouldn't have to deal with either of those.

The comments about s/type/obj&/ aside, this looks good to me (and the amended version below looks ready to be picked up, at least in my eyes).

One thing I did want to note which is elided by the limited context is that we *do* parse tags like you say, it's just hidden in the "while (obj->type == OBJ_TAG)" loop below.

So that's doing the right thing, but it wasn't clear from the limited context here that this patch was immediately correct.

Thanks, Taylor

On Tue, Jun 22, 2021 at 10:46:40PM -0400, Taylor Blau wrote:

One reason not to include all of them is that the list can be arbitrarily long, and regular readers of packed-refs (who may not even care about peeling at all) have to skip past it. That matters a little less these since we binary-search it (but you still might be iterating over the ref).

So I think either way it is a tradeoff, and you are making assumptions about which cases are less likely.

If I were to work on this (and I don't have any immediate plans to do so), I'd probably do whichever is easiest to implement, and to maintain backwards-compatibility. And I suspect that is the "flag" approach, but a lot would depend on the details of our parser and what it permits.

-Peff