[PATCH 0/5] some "log --decorate" optimizations

[PATCH 0/5] some "log --decorate" optimizations

[Jeff King]

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

[PATCH 1/5] pretty.h: update and expand docstring for userformat_find_requirements()

[Jeff King]

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(-)

diff --git a/pretty.h b/pretty.h
index f034609e4d..c81cf40d38 100644
--- a/pretty.h
+++ b/pretty.h
@@ -65,12 +65,15 @@ static inline int cmit_fmt_is_mail(enum cmit_fmt fmt)
 	return (fmt == CMIT_FMT_EMAIL || fmt == CMIT_FMT_MBOXRD);
 }
 
+/*
+ * Examine the user-specified format given by "fmt" (or if NULL, the global one
+ * previously saved by get_commit_format()), and set flags based on which items
+ * the format will need when it is expanded.
+ */
 struct userformat_want {
 	unsigned notes:1;
 	unsigned source:1;
 };
-
-/* Set the flag "w->notes" if there is placeholder %N in "fmt". */
 void userformat_find_requirements(const char *fmt, struct userformat_want *w);
 
 /*
-- 
2.32.0.352.gff02c21e72

[PATCH 2/5] log: avoid loading decorations for userformats that don't need it

[Jeff King]

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(+)

diff --git a/builtin/log.c b/builtin/log.c
index 6102893fcc..6ba7f20726 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -245,6 +245,9 @@ static void cmd_log_init_finish(int argc, const char **argv, const char *prefix,
 			rev->abbrev_commit = 0;
 	}
 
+	if (rev->commit_format == CMIT_FMT_USERFORMAT && !w.decorate)
+		decoration_style = 0;
+
 	if (decoration_style) {
 		const struct string_list *config_exclude =
 			repo_config_get_value_multi(the_repository,
diff --git a/pretty.c b/pretty.c
index b1ecd039ce..9631529c10 100644
--- a/pretty.c
+++ b/pretty.c
@@ -1735,6 +1735,10 @@ static size_t userformat_want_item(struct strbuf *sb, const char *placeholder,
 	case 'S':
 		w->source = 1;
 		break;
+	case 'd':
+	case 'D':
+		w->decorate = 1;
+		break;
 	}
 	return 0;
 }
diff --git a/pretty.h b/pretty.h
index c81cf40d38..2f16acd213 100644
--- a/pretty.h
+++ b/pretty.h
@@ -73,6 +73,7 @@ static inline int cmit_fmt_is_mail(enum cmit_fmt fmt)
 struct userformat_want {
 	unsigned notes:1;
 	unsigned source:1;
+	unsigned decorate:1;
 };
 void userformat_find_requirements(const char *fmt, struct userformat_want *w);
 
-- 
2.32.0.352.gff02c21e72

[PATCH 3/5] object.h: expand docstring for lookup_unknown_object()

[Jeff King]

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(-)

diff --git a/object.h b/object.h
index 8bca310713..eb7e481c39 100644
--- a/object.h
+++ b/object.h
@@ -144,7 +144,18 @@ struct object *parse_object_or_die(const struct object_id *oid, const char *name
  */
 struct object *parse_object_buffer(struct repository *r, const struct object_id *oid, enum object_type type, unsigned long size, void *buffer, int *eaten_p);
 
-/** Returns the object, with potentially excess memory allocated. **/
+/*
+ * Allocate and return an object struct, even if you do not know the type of
+ * the object. The returned object may have its "type" field set to a real type
+ * (if somebody previously called lookup_blob(), etc), or it may be set to
+ * OBJ_NONE. In the latter case, subsequent calls to lookup_blob(), etc, will
+ * set the type field as appropriate.
+ *
+ * Use this when you do not know the expected type of an object and want to
+ * avoid parsing it for efficiency reasons. Try to avoid it otherwise; it
+ * may allocate excess memory, since the returned object must be as large as
+ * the maximum struct of any type.
+ */
 struct object *lookup_unknown_object(struct repository *r, const struct object_id *oid);
 
 struct object_list *object_list_insert(struct object *item,
-- 
2.32.0.352.gff02c21e72

[PATCH 4/5] object.h: add lookup_object_by_type() function

[Jeff King]

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(-)

diff --git a/object.c b/object.c
index 14188453c5..07fcf23d7b 100644
--- a/object.c
+++ b/object.c
@@ -185,6 +185,24 @@ struct object *lookup_unknown_object(struct repository *r, const struct object_i
 	return obj;
 }
 
+struct object *lookup_object_by_type(struct repository *r,
+			    const struct object_id *oid,
+			    enum object_type type)
+{
+	switch (type) {
+	case OBJ_COMMIT:
+		return (struct object *)lookup_commit(r, oid);
+	case OBJ_TREE:
+		return (struct object *)lookup_tree(r, oid);
+	case OBJ_TAG:
+		return (struct object *)lookup_tag(r, oid);
+	case OBJ_BLOB:
+		return (struct object *)lookup_blob(r, oid);
+	default:
+		die("BUG: unknown object type %d", type);
+	}
+}
+
 struct object *parse_object_buffer(struct repository *r, const struct object_id *oid, enum object_type type, unsigned long size, void *buffer, int *eaten_p)
 {
 	struct object *obj;
diff --git a/object.h b/object.h
index eb7e481c39..3b38c9cc98 100644
--- a/object.h
+++ b/object.h
@@ -158,6 +158,13 @@ struct object *parse_object_buffer(struct repository *r, const struct object_id
  */
 struct object *lookup_unknown_object(struct repository *r, const struct object_id *oid);
 
+/*
+ * Dispatch to the appropriate lookup_blob(), lookup_commit(), etc, based on
+ * "type".
+ */
+struct object *lookup_object_by_type(struct repository *r, const struct object_id *oid,
+				     enum object_type type);
+
 struct object_list *object_list_insert(struct object *item,
 				       struct object_list **list_p);
 
diff --git a/reachable.c b/reachable.c
index c59847257a..84e3d0d75e 100644
--- a/reachable.c
+++ b/reachable.c
@@ -159,24 +159,6 @@ int add_unseen_recent_objects_to_traversal(struct rev_info *revs,
 				      FOR_EACH_OBJECT_LOCAL_ONLY);
 }
 
-static void *lookup_object_by_type(struct repository *r,
-				   const struct object_id *oid,
-				   enum object_type type)
-{
-	switch (type) {
-	case OBJ_COMMIT:
-		return lookup_commit(r, oid);
-	case OBJ_TREE:
-		return lookup_tree(r, oid);
-	case OBJ_TAG:
-		return lookup_tag(r, oid);
-	case OBJ_BLOB:
-		return lookup_blob(r, oid);
-	default:
-		die("BUG: unknown object type %d", type);
-	}
-}
-
 static int mark_object_seen(const struct object_id *oid,
 			     enum object_type type,
 			     int exclude,
-- 
2.32.0.352.gff02c21e72

[PATCH 5/5] load_ref_decorations(): avoid parsing non-tag objects

[Jeff King]

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(-)

diff --git a/log-tree.c b/log-tree.c
index 7b823786c2..8b700e9c14 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -134,6 +134,7 @@ static int add_ref_decoration(const char *refname, const struct object_id *oid,
 			      int flags, void *cb_data)
 {
 	struct object *obj;
+	enum object_type objtype;
 	enum decoration_type type = DECORATION_NONE;
 	struct decoration_filter *filter = (struct decoration_filter *)cb_data;
 
@@ -155,9 +156,10 @@ static int add_ref_decoration(const char *refname, const struct object_id *oid,
 		return 0;
 	}
 
-	obj = parse_object(the_repository, oid);
-	if (!obj)
+	objtype = oid_object_info(the_repository, oid, NULL);
+	if (type < 0)
 		return 0;
+	obj = lookup_object_by_type(the_repository, oid, objtype);
 
 	if (starts_with(refname, "refs/heads/"))
 		type = DECORATION_REF_LOCAL;
-- 
2.32.0.352.gff02c21e72

Re: [PATCH 5/5] load_ref_decorations(): avoid parsing non-tag objects

[Derrick Stolee]

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

> -	obj = parse_object(the_repository, oid);
> -	if (!obj)
> +	objtype = oid_object_info(the_repository, oid, NULL);
> +	if (type < 0)
>  		return 0;

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

Re: [PATCH 5/5] load_ref_decorations(): avoid parsing non-tag objects

[Jeff King]

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

> On 6/22/2021 12:08 PM, Jeff King wrote:
> 
> > -	obj = parse_object(the_repository, oid);
> > -	if (!obj)
> > +	objtype = oid_object_info(the_repository, oid, NULL);
> > +	if (type < 0)
> >  		return 0;
> 
> 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.

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.

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

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(-)

diff --git a/log-tree.c b/log-tree.c
index 7b823786c2..c3c8e7e1df 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -134,6 +134,7 @@ static int add_ref_decoration(const char *refname, const struct object_id *oid,
 			      int flags, void *cb_data)
 {
 	struct object *obj;
+	enum object_type objtype;
 	enum decoration_type type = DECORATION_NONE;
 	struct decoration_filter *filter = (struct decoration_filter *)cb_data;
 
@@ -155,9 +156,10 @@ static int add_ref_decoration(const char *refname, const struct object_id *oid,
 		return 0;
 	}
 
-	obj = parse_object(the_repository, oid);
-	if (!obj)
+	objtype = oid_object_info(the_repository, oid, NULL);
+	if (objtype < 0)
 		return 0;
+	obj = lookup_object_by_type(the_repository, oid, objtype);
 
 	if (starts_with(refname, "refs/heads/"))
 		type = DECORATION_REF_LOCAL;
-- 
2.32.0.352.gff02c21e72

Re: [PATCH 5/5] load_ref_decorations(): avoid parsing non-tag objects

[Jeff King]

On Tue, Jun 22, 2021 at 01:06:48PM -0400, 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.
> 
> 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.

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(-)

diff --git a/log-tree.c b/log-tree.c
index c3c8e7e1df..4f69ed176d 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -135,7 +135,7 @@ static int add_ref_decoration(const char *refname, const struct object_id *oid,
 {
 	struct object *obj;
 	enum object_type objtype;
-	enum decoration_type type = DECORATION_NONE;
+	enum decoration_type deco_type = DECORATION_NONE;
 	struct decoration_filter *filter = (struct decoration_filter *)cb_data;
 
 	if (filter && !ref_filter_match(refname, filter))
@@ -162,17 +162,17 @@ static int add_ref_decoration(const char *refname, const struct object_id *oid,
 	obj = lookup_object_by_type(the_repository, oid, objtype);
 
 	if (starts_with(refname, "refs/heads/"))
-		type = DECORATION_REF_LOCAL;
+		deco_type = DECORATION_REF_LOCAL;
 	else if (starts_with(refname, "refs/remotes/"))
-		type = DECORATION_REF_REMOTE;
+		deco_type = DECORATION_REF_REMOTE;
 	else if (starts_with(refname, "refs/tags/"))
-		type = DECORATION_REF_TAG;
+		deco_type = DECORATION_REF_TAG;
 	else if (!strcmp(refname, "refs/stash"))
-		type = DECORATION_REF_STASH;
+		deco_type = DECORATION_REF_STASH;
 	else if (!strcmp(refname, "HEAD"))
-		type = DECORATION_REF_HEAD;
+		deco_type = DECORATION_REF_HEAD;
 
-	add_name_decoration(type, refname, obj);
+	add_name_decoration(deco_type, refname, obj);
 	while (obj->type == OBJ_TAG) {
 		obj = ((struct tag *)obj)->tagged;
 		if (!obj)
-- 
2.32.0.352.gff02c21e72

Re: [PATCH 5/5] load_ref_decorations(): avoid parsing non-tag objects

[Derrick Stolee]

On 6/22/2021 1:09 PM, Jeff King wrote:
> On Tue, Jun 22, 2021 at 01:06:48PM -0400, 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.
>>
>> 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.
> 
> 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.

Naming is hard. This change seems worth it.

Thanks,
-Stolee

Re: [PATCH 5/5] load_ref_decorations(): avoid parsing non-tag objects

[Ævar Arnfjörð Bjarmason]

On Tue, Jun 22 2021, Jeff King wrote:

> On Tue, Jun 22, 2021 at 12:35:46PM -0400, Derrick Stolee wrote:
>
>> On 6/22/2021 12:08 PM, Jeff King wrote:
>> 
>> > -	obj = parse_object(the_repository, oid);
>> > -	if (!obj)
>> > +	objtype = oid_object_info(the_repository, oid, NULL);
>> > +	if (type < 0)
>> >  		return 0;
>> 
>> 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.
>
> 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. :)

[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 :)

Re: [PATCH 5/5] load_ref_decorations(): avoid parsing non-tag objects

[Jeff King]

On Tue, Jun 22, 2021 at 08:27:53PM +0200, Ævar Arnfjörð Bjarmason 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. :)
> 
> [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;

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

> 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:
> 	             ^

...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.

> 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/

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...

> 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):
> [...]
> 	-	objtype = oid_object_info(the_repository, oid, NULL);
> 	-	if (type < 0)
> 	+	if (!oid_object_info_ok(the_repository, oid, &type, NULL))
> 	 		return 0;

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

Re: [PATCH 5/5] load_ref_decorations(): avoid parsing non-tag objects

[Ævar Arnfjörð Bjarmason]

On Tue, Jun 22 2021, Jeff King wrote:

> 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(-)
>
> diff --git a/log-tree.c b/log-tree.c
> index 7b823786c2..8b700e9c14 100644
> --- a/log-tree.c
> +++ b/log-tree.c
> @@ -134,6 +134,7 @@ static int add_ref_decoration(const char *refname, const struct object_id *oid,
>  			      int flags, void *cb_data)
>  {
>  	struct object *obj;
> +	enum object_type objtype;
>  	enum decoration_type type = DECORATION_NONE;
>  	struct decoration_filter *filter = (struct decoration_filter *)cb_data;
>  
> @@ -155,9 +156,10 @@ static int add_ref_decoration(const char *refname, const struct object_id *oid,
>  		return 0;
>  	}
>  
> -	obj = parse_object(the_repository, oid);
> -	if (!obj)
> +	objtype = oid_object_info(the_repository, oid, NULL);
> +	if (type < 0)
>  		return 0;
> +	obj = lookup_object_by_type(the_repository, oid, objtype);

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/

Re: [PATCH 5/5] load_ref_decorations(): avoid parsing non-tag objects

[Jeff King]

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

> > @@ -155,9 +156,10 @@ static int add_ref_decoration(const char *refname, const struct object_id *oid,
> >  		return 0;
> >  	}
> >  
> > -	obj = parse_object(the_repository, oid);
> > -	if (!obj)
> > +	objtype = oid_object_info(the_repository, oid, NULL);
> > +	if (type < 0)
> >  		return 0;
> > +	obj = lookup_object_by_type(the_repository, oid, objtype);
> 
> 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.

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

Re: [PATCH 5/5] load_ref_decorations(): avoid parsing non-tag objects

[Taylor Blau]

On Tue, Jun 22, 2021 at 12:08:40PM -0400, Jeff King wrote:
> 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.

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.

> Signed-off-by: Jeff King <peff@peff.net>
> ---
>  log-tree.c | 6 ++++--
>  1 file changed, 4 insertions(+), 2 deletions(-)
>
> diff --git a/log-tree.c b/log-tree.c
> index 7b823786c2..8b700e9c14 100644
> --- a/log-tree.c
> +++ b/log-tree.c
> @@ -134,6 +134,7 @@ static int add_ref_decoration(const char *refname, const struct object_id *oid,
>  			      int flags, void *cb_data)
>  {
>  	struct object *obj;
> +	enum object_type objtype;
>  	enum decoration_type type = DECORATION_NONE;
>  	struct decoration_filter *filter = (struct decoration_filter *)cb_data;
>
> @@ -155,9 +156,10 @@ static int add_ref_decoration(const char *refname, const struct object_id *oid,
>  		return 0;
>  	}
>
> -	obj = parse_object(the_repository, oid);
> -	if (!obj)
> +	objtype = oid_object_info(the_repository, oid, NULL);
> +	if (type < 0)
>  		return 0;
> +	obj = lookup_object_by_type(the_repository, oid, objtype);

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

Re: [PATCH 5/5] load_ref_decorations(): avoid parsing non-tag objects

[Jeff King]

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

> On Tue, Jun 22, 2021 at 12:08:40PM -0400, Jeff King wrote:
> > 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.
> 
> 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.

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