Re: Poor performance of git describe in big repos

Thomas Rast [off-list ref] writes:

I had a brief look around sha1_file.c, in particular sha1_object_info,
and it turns out we lack the "deflate only early part" logic as I
suspected.  So that'll have to be fixed first.  After that I *think* it
should automatically carry over into the tag readers.

Strike that, I'm wrong.  sha1_object_info is fast even for these big
loose objects.

The culprit, according to some callgrind investigation, is
lookup_commit_reference_gently() [for the unannotated case] or
deref_tag() [annotated case] calling parse_object().

-- 
Thomas Rast
trast@{inf,student}.ethz.ch

The culprit, according to some callgrind investigation, is
lookup_commit_reference_gently() [for the unannotated case] or
deref_tag() [annotated case] calling parse_object().

Using the scenario you described earlier, I think it ends-up spending
most of its time in check_sha1_signature (both deref_tag and
lookup_commit_reference_gently() go there) with 20% inflating, 80% in
SHA1_Update(). Not much we can do about that, can we ?

lookup_commit_reference_gently unconditionally parses the object given
to it.  This slows down git-describe a lot if you have a repository
with large tagged blobs in it: parse_object() will read the entire
blob and verify that its sha1 matches, only to then throw it away.

Speed it up by checking the type with sha1_object_info() prior to
unpacking.

The reason that deref_tag() does not need the same fix is a bit
subtle: parse_tag_buffer() does not fill the 'tagged' member of the
tag struct if the tagged object is a blob.

Reported-by: Alex Bennée <redacted>
Signed-off-by: Thomas Rast <redacted>
---
 commit.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

diff --git a/commit.c b/commit.c
index 888e02a..00e8d4a 100644
--- a/commit.c
+++ b/commit.c

@@ -31,8 +31,12 @@ static struct commit *check_commit(struct object *obj,
 struct commit *lookup_commit_reference_gently(const unsigned char *sha1,
 					      int quiet)
 {
-	struct object *obj = deref_tag(parse_object(sha1), NULL, 0);
-
+	struct object *obj;
+	int type = sha1_object_info(sha1, NULL);
+	/* If it's neither tag nor commit, parsing the object is wasted effort */
+	if (type != OBJ_TAG && type != OBJ_COMMIT)
+		return NULL;
+	obj = deref_tag(parse_object(sha1), NULL, 0);
 	if (!obj)
 		return NULL;
 	return check_commit(obj, sha1, quiet);

-- 
1.8.3.506.g4fdeee5

sha1_object_info() returns -1 (OBJ_BAD) if it cannot find the object
for some reason, which suggests that it wants the _caller_ to report
this error.  However, part of its work happens in
sha1_loose_object_info, which _does_ report errors itself.  This is
doubly strange because:

* packed_object_info(), which is the other half of the duo, does _not_
  report this.

* In the event that an object is packed and pruned while
  sha1_object_info_extended() goes looking for it, we would
  erroneously show the error -- even though the code of the latter
  function purports to handle this case gracefully.

* A caller might invoke sha1_object_info() to find the type of an
  object even if that object is not known to exist.

Silence this error.  The others remain untouched as a corrupt object
is a much more grave error than it merely being absent.

Signed-off-by: Thomas Rast <redacted>
---
 sha1_file.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/sha1_file.c b/sha1_file.c
index 67e815b..c0f6a0e 100644
--- a/sha1_file.c
+++ b/sha1_file.c

@@ -2348,7 +2348,7 @@ static int sha1_loose_object_info(const unsigned char *sha1, unsigned long *size
 
 	map = map_sha1_file(sha1, &mapsize);
 	if (!map)
-		return error("unable to find %s", sha1_to_hex(sha1));
+		return -1;
 	if (unpack_sha1_header(&stream, map, mapsize, hdr, sizeof(hdr)) < 0)
 		status = error("unable to unpack %s header",
 			       sha1_to_hex(sha1));

-- 
1.8.3.506.g4fdeee5

On Thu, May 30, 2013 at 10:00:23PM +0200, Thomas Rast wrote:

lookup_commit_reference_gently unconditionally parses the object given
to it.  This slows down git-describe a lot if you have a repository
with large tagged blobs in it: parse_object() will read the entire
blob and verify that its sha1 matches, only to then throw it away.

Speed it up by checking the type with sha1_object_info() prior to
unpacking.

This would speed up the case where we do not end up looking at the
object at all, but it will slow down the (presumably common) case where
we will in fact find a commit and end up parsing the object anyway.

Have you measured the impact of this on normal operations? During a
traversal, we spend a measurable amount of time looking up commits in
packfiles, and this would presumably double it.

This is not the first time I have seen this tradeoff in git.  It would
be nice if our object access was structured to do incremental
examination of the objects (i.e., store the packfile index lookup or
partial unpack of a loose object header, and then use that to complete
the next step of actually getting the contents).

-Peff

On Fri, May 31, 2013 at 4:22 AM, Jeff King [off-list ref] wrote:

On Thu, May 30, 2013 at 10:00:23PM +0200, Thomas Rast wrote:

quoted

lookup_commit_reference_gently unconditionally parses the object given
to it.  This slows down git-describe a lot if you have a repository
with large tagged blobs in it: parse_object() will read the entire
blob and verify that its sha1 matches, only to then throw it away.

Speed it up by checking the type with sha1_object_info() prior to
unpacking.

This would speed up the case where we do not end up looking at the
object at all, but it will slow down the (presumably common) case where
we will in fact find a commit and end up parsing the object anyway.

Perhaps turn "quiet" into a bitmap and only let git-describe do this?
--
Duy

Thomas Rast wrote:

As Jeff points out, you've introduced an extra sha1_object_info() call
in the common case of tag (which derefs into a commit anyway) and
commit slowing things down.

So, my main doubt centres around how sha1_object_info() determines the
type of the object without actually parsing it.  You have to open up
the file and look at the fields near the top, no? (or fallback to blob
failing that).  I am reading it:

1. It calls sha1_loose_object_info() or sha1_packed_object_info(),
depending on whether the particular file is in-pack or not.  Lets see
what is common between them.

2. The loose counterpart seems to call unpack_sha1_header() after
mmap'ing the file.  This ultimately ends up calling
unpack_object_header_buffer(), which is also what the packed
counterpart calls.

3. I didn't understand what unpack_object_header_buffer() is doing.
And'ing with some magic 0x80 and shifting by 4 bits iteratively? type
= (c >> 4) & 7?

In contrast, parse_object() first calls lookup_object() to look it up
in some hashtable to get the type -- the packfile idx, presumably?
Why don't you also do that instead of sha1_object_info()?  Or, why
don't you wrap parse_object() in an API that doesn't go beyond the
first blob check (and not execute parse_object_buffer())?

Also, does this patch fix the bug Alex reported?

Apologies if I've misunderstood something horribly (which does seem to
be the case).

Thanks.