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

[PATCH 8/9] pv4_tree_desc: avoid lookup_object() when possible

From
Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
Date
Oct 9, 2013, 14:46 UTC
Message-ID
<1381329976-32082-9-git-send-email-pclouds@gmail.com>
In-Reply-To
<1381329976-32082-1-git-send-email-pclouds@gmail.com>

pv4_tree_desc_from_entry() cuts out SHA-1 index lookups when possible. This patch provides a new set of lookup functions that avoid looking up object hash table.

We maintain an object pointer array and use SHA-1 table as key. Because we know index in SHA-1 table in v4 trees, we can skip binary search and go straight to the object.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 cache.h        |  1 +
 packv4-parse.c | 33 +++++++++++++++++++++++++++++++++
 packv4-parse.h | 12 ++++++++++++
 sha1_file.c    |  1 +
 4 files changed, 47 insertions(+)
diff --git a/cache.h b/cache.h
index 5028ded..da65063 100644
--- a/cache.h
+++ b/cache.h
@@ -1035,6 +1035,7 @@ extern struct packed_git {
 	struct packv4_dict *ident_dict;
 	off_t ident_dict_end;
 	struct packv4_dict *path_dict;
+	struct object **objs;
 	time_t mtime;
 	int pack_fd;
 	unsigned pack_local:1,
diff --git a/packv4-parse.c b/packv4-parse.c
index 4354ee3..6f6152c 100644
--- a/packv4-parse.c
+++ b/packv4-parse.c
@@ -11,6 +11,10 @@
 #include "cache.h"
 #include "packv4-parse.h"
 #include "varint.h"
+#include "commit.h"
+#include "tree.h"
+#include "blob.h"
+#include "tag.h"
 
 int packv4_available;
 
@@ -815,3 +819,32 @@ int pv4_tree_entry(struct pv4_tree_desc *desc)
 	}
 	return !decode_entries(desc, desc->obj_offset, desc->start++, 1);
 }
+
+static struct object **get_packed_objs(struct pv4_tree_desc *desc)
+{
+	if (!desc->p || !desc->sha1_index)
+		return NULL;
+	if (desc->p->version >= 4 && !desc->p->objs)
+		desc->p->objs =
+			xmalloc(sizeof(struct object *) * desc->p->num_objects);
+	return desc->p->objs;
+}
+
+#define DEFINE_LOOKUP(TYPE)					\
+struct TYPE *pv4_lookup_##TYPE(struct pv4_tree_desc *desc)	\
+{								\
+	struct object **objs = get_packed_objs(desc);		\
+	if (!objs)						\
+		return lookup_##TYPE(desc->v2.entry.sha1);	\
+	objs += desc->sha1_index - 1;				\
+	if (!*objs)						\
+		*objs = (struct object *)			\
+			lookup_##TYPE(desc->v2.entry.sha1);	\
+	return (struct TYPE *)objs[0];				\
+}
+
+DEFINE_LOOKUP(object)
+DEFINE_LOOKUP(commit)
+DEFINE_LOOKUP(tree)
+DEFINE_LOOKUP(blob)
+DEFINE_LOOKUP(tag)
diff --git a/packv4-parse.h b/packv4-parse.h
index 874f57c..3bf69bc 100644
--- a/packv4-parse.h
+++ b/packv4-parse.h
@@ -3,6 +3,12 @@
 
 #include "tree-walk.h"
 
+struct object;
+struct commit;
+struct tree;
+struct blob;
+struct tag;
+
 struct packv4_dict {
 	const unsigned char *data;
 	unsigned int nb_entries;
@@ -58,4 +64,10 @@ void pv4_release_tree_desc(struct pv4_tree_desc *desc);
 
 int pv4_tree_entry(struct pv4_tree_desc *desc);
 
+struct object *pv4_lookup_object(struct pv4_tree_desc *desc);
+struct commit *pv4_lookup_commit(struct pv4_tree_desc *desc);
+struct tree   *pv4_lookup_tree(struct pv4_tree_desc *desc);
+struct blob   *pv4_lookup_blob(struct pv4_tree_desc *desc);
+struct tag    *pv4_lookup_tag(struct pv4_tree_desc *desc);
+
 #endif
diff --git a/sha1_file.c b/sha1_file.c
index 4744132..88a6273 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -773,6 +773,7 @@ void free_pack_by_name(const char *pack_name)
 			*pp = p->next;
 			if (last_found_pack == p)
 				last_found_pack = NULL;
+			free(p->objs);
 			free(p);
 			return;
 		}
-- 
1.8.2.83.gc99314b
Previous: Nguyễn Thái Ngọc DuyNext: Nguyễn Thái Ngọc Duy
Message 9 of 15 in “v4-aware tree walker API”
  1. 0/9 v4-aware tree walker APINguyễn Thái Ngọc Duy, Oct 9, 2013
  2. 1/9 sha1_file: provide real packed type in object_info_extendedNguyễn Thái Ngọc Duy, Oct 9, 2013
  3. 2/9 pack v4: move v2 tree entry generation code out of decode_entriesNguyễn Thái Ngọc Duy, Oct 9, 2013
  4. 3/9 pv4_tree_desc: introduce new struct for pack v4 tree walkerNguyễn Thái Ngọc Duy, Oct 9, 2013
  5. 4/9 pv4_tree_desc: use struct tree_desc from pv4_tree_descNguyễn Thái Ngọc Duy, Oct 9, 2013
  6. 5/9 pv4_tree_desc: allow decode_entries to return v4 trees, one at a timeNguyễn Thái Ngọc Duy, Oct 9, 2013
  7. 6/9 pv4_tree_desc: complete interfaceNguyễn Thái Ngọc Duy, Oct 9, 2013
  8. 7/9 pv4_tree_desc: don't bother looking for v4 trees if no v4 packs are presentNguyễn Thái Ngọc Duy, Oct 9, 2013
  9. 8/9 pv4_tree_desc: avoid lookup_object() when possibleNguyễn Thái Ngọc Duy, Oct 9, 2013
  10. 9/9 list-object.c: take "advantage" of new pv4_tree_desc interfaceNguyễn Thái Ngọc Duy, Oct 9, 2013
  11. Nicolas PitreOct 9, 2013
  12. Duy NguyenOct 11, 2013
  13. Duy NguyenOct 11, 2013
  14. Nicolas PitreOct 12, 2013
  15. Duy NguyenOct 12, 2013

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.