git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Jeff King <peff@peff.net>
Date
Mar 22, 2020, 19:18 UTC
Message-ID
<20200322191838.GA671552@coredump.intra.peff.net>
In-Reply-To
<20200322184519.GA654322@coredump.intra.peff.net>
On Sun, Mar 22, 2020 at 02:45:19PM -0400, Jeff King wrote:
Show 13 quoted lines
> 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.

Sadly, it doesn't seem to help. Here's a hacky implementation (I tested it only on my limited cat-file case; I wouldn't be at all surprised if it causes problems for users of the delta cache that want the actual object contents).

After some rudimentary profiling (which I _should_ have done in the first place before opening my mouth), it looks like finding the types isn't actually the most expensive thing anyway: it's just dealing with the sheer number of objects in the pack.

That implies that teaching packed_object_info() to use bitmaps to find the individual types wouldn't help much either (but being able to ask "just give me the commits" and iterating over the commit-type bitmap probably _would_).

Anyway, here's the patch for the curious.
---
diff --git a/packfile.c b/packfile.c
index f4e752996d..482733689a 100644
--- a/packfile.c
+++ b/packfile.c
@@ -1273,6 +1273,13 @@ static int retry_bad_packed_offset(struct repository *r,
 
 #define POI_STACK_PREALLOC 64
 
+/* some reordering of static functions could avoid these */
+static enum object_type get_delta_base_cache_type(struct packed_git *p,
+						  off_t curpos);
+static void add_delta_base_cache(struct packed_git *p, off_t base_offset,
+				 void *base, unsigned long base_size,
+				 enum object_type type);
+
 static enum object_type packed_to_object_type(struct repository *r,
 					      struct packed_git *p,
 					      off_t obj_offset,
@@ -1287,6 +1294,14 @@ static enum object_type packed_to_object_type(struct repository *r,
 	while (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {
 		off_t base_offset;
 		unsigned long size;
+		enum object_type cached_type;
+
+		cached_type = get_delta_base_cache_type(p, obj_offset);
+		if (cached_type > 0) {
+			type = cached_type;
+			goto out;
+		}
+
 		/* Push the object we're going to leave behind */
 		if (poi_stack_nr >= poi_stack_alloc && poi_stack == small_poi_stack) {
 			poi_stack_alloc = alloc_nr(poi_stack_nr);
@@ -1326,6 +1341,11 @@ static enum object_type packed_to_object_type(struct repository *r,
 	}
 
 out:
+	if (type != OBJ_BAD) {
+		size_t i;
+		for (i = 0; i < poi_stack_nr; i++)
+			add_delta_base_cache(p, poi_stack[i], NULL, 0, type);
+	}
 	if (poi_stack != small_poi_stack)
 		free(poi_stack);
 	return type;
@@ -1385,6 +1405,13 @@ get_delta_base_cache_entry(struct packed_git *p, off_t base_offset)
 	return e ? container_of(e, struct delta_base_cache_entry, ent) : NULL;
 }
 
+static enum object_type get_delta_base_cache_type(struct packed_git *p, off_t curpos)
+{
+	struct delta_base_cache_entry *ent =
+		get_delta_base_cache_entry(p, curpos);
+	return ent ? ent->type : OBJ_BAD;
+}
+
 static int delta_base_cache_key_eq(const struct delta_base_cache_key *a,
 				   const struct delta_base_cache_key *b)
 {
@@ -1433,7 +1460,7 @@ static void *cache_or_unpack_entry(struct repository *r, struct packed_git *p,
 	struct delta_base_cache_entry *ent;
 
 	ent = get_delta_base_cache_entry(p, base_offset);
-	if (!ent)
+	if (!ent || !ent->data)
 		return unpack_entry(r, p, base_offset, type, base_size);
 
 	if (type)
@@ -1677,7 +1704,7 @@ void *unpack_entry(struct repository *r, struct packed_git *p, off_t obj_offset,
 		struct delta_base_cache_entry *ent;
 
 		ent = get_delta_base_cache_entry(p, curpos);
-		if (ent) {
+		if (ent && ent->data) {
 			type = ent->type;
 			data = ent->data;
 			size = ent->size;
Previous: Jeff KingNext: Taylor Blau
Message 11 of 31 in “commit-graph: avoid unnecessary tag deference when merging”
  1. 0/1 commit-graph: avoid unnecessary tag deference when mergingTaylor Blau, Mar 21, 2020
  2. 1/1 commit-graph.c: avoid unnecessary tag dereference when mergingTaylor Blau, Mar 21, 2020
  3. Jeff KingMar 21, 2020
  4. Taylor BlauMar 21, 2020
  5. Taylor BlauMar 21, 2020
  6. Jeff KingMar 21, 2020
  7. Taylor BlauMar 21, 2020
  8. Jeff KingMar 22, 2020
  9. SZEDER GáborMar 22, 2020
  10. looking up object types quickly, was Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when mergingJeff King, Mar 22, 2020
  11. Jeff KingMar 22, 2020
  12. Taylor BlauMar 23, 2020
  13. Taylor BlauMar 22, 2020
  14. Jeff KingMar 24, 2020
  15. Junio C HamanoMar 21, 2020
  16. Derrick StoleeMar 22, 2020
  17. Taylor BlauMar 22, 2020
  18. Derrick StoleeMar 22, 2020
  19. Jeff KingMar 22, 2020
  20. Jeff KingMar 22, 2020
  21. Taylor BlauMar 22, 2020
  22. Jeff KingMar 24, 2020
  23. Taylor BlauMar 24, 2020
  24. Jeff KingMar 27, 2020
  25. Taylor BlauMar 27, 2020
  26. Taylor BlauMar 22, 2020
  27. Jeff KingMar 24, 2020
  28. Junio C HamanoMar 21, 2020
  29. Junio C HamanoMar 21, 2020
  30. Jeff KingMar 21, 2020
  31. Taylor BlauMar 21, 2020

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.