threads / patch / 35091

patch, 9 partsv4-aware tree walker API

Subject: [BAD PATCH 0/9] v4-aware tree walker API

## tl;dr

15 messages between Oct 9, 2013 and Oct 12, 2013. Diffs are folded; open one to read it.

replies: 14people: 2as markdown or json

Nguyễn Thái Ngọc Duy· Oct 9, 2013, 14:46 UTC · lore

I know I still have a lot of holes to plug, but this was more interesting because we could see some encouraging numbers. Unfortunately the result is disappointing. Maybe I did it in a stupid way and need to restart with a totally different way.

"rev-list --objects" on v2 takes 4 secs, v4 with current walker 11s and the new walker 16s (worst!). perf's top functions with v2 are

 23,51%  git  libz.so.1.2.7       [.] inflate
 16,66%  git  git                 [.] lookup_object
 11,46%  git  libz.so.1.2.7       [.] inflate_fast
  6,89%  git  libc-2.16.so        [.] __memcpy_ssse3_back
  4,19%  git  libz.so.1.2.7       [.] inflate_table
  4,15%  git  git                 [.] find_pack_entry_one
  3,84%  git  git                 [.] decode_tree_entry
and with new walker
 58,61%  git  git                [.] decode_entries
 18,66%  git  git                [.] decode_varint
  9,73%  git  git                [.] use_pack
  3,31%  git  git                [.] nth_packed_object_offset
  1,73%  git  git                [.] process_tree
  1,66%  git  git                [.] pv4_lookup_blob
  1,09%  git  git                [.] get_pathref
  1,03%  git  libc-2.16.so       [.] __memcpy_ssse3_back
  0,90%  git  libz.so.1.2.7      [.] inflate
  0,50%  git  libz.so.1.2.7      [.] inflate_table

It's no surprise that lookup_object is no longer hot. The closet is pv4_lookup_blob. nth_packed_object_offset is getting hotter as it's used extensively by decode_entries.

And decode_entries is getting toooo hot. This function is now called for each tree entry of every tree. And it does get_tree_offset_cache() lookup for every call (ironically we try hard to avoid hash lookup in lookup_object).

The only bit I haven't done is avoid checking if a tree is already examined, if so do not bother with copy sequences referring to it. That should cut down the number of decode_entries but not sure how much because there's no relation between tree traversing order and how copy sequences are made.

Maybe we could make an exception and allow the tree walker to pass pv4_tree_cache* directly to decode_entries so it does not need to do the first lookup every time..

Suggestions?
Nguyễn Thái Ngọc Duy (9):
  sha1_file: provide real packed type in object_info_extended
  pack v4: move v2 tree entry generation code out of decode_entries
  pv4_tree_desc: introduce new struct for pack v4 tree walker
  pv4_tree_desc: use struct tree_desc from pv4_tree_desc
  pv4_tree_desc: allow decode_entries to return v4 trees, one at a time
  pv4_tree_desc: complete interface
  pv4_tree_desc: don't bother looking for v4 trees if no v4 packs are present
  pv4_tree_desc: avoid lookup_object() when possible
  list-object.c: take "advantage" of new pv4_tree_desc interface
 cache.h        |   3 +-
 list-objects.c |  38 +++++----
 packv4-parse.c | 263 ++++++++++++++++++++++++++++++++++++++++++++++-----------
 packv4-parse.h |  48 +++++++++++
 sha1_file.c    |   9 +-
 streaming.c    |   9 +-
 6 files changed, 300 insertions(+), 70 deletions(-)
-- 
1.8.2.83.gc99314b
Nguyễn Thái Ngọc Duy· Oct 9, 2013, 14:46 UTC · re: Nguyễn Thái Ngọc Duy · lore

[PATCH 1/9] sha1_file: provide real packed type in object_info_extended

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 cache.h     | 2 +-
 sha1_file.c | 3 +--
 streaming.c | 9 ++++++++-
 3 files changed, 10 insertions(+), 4 deletions(-)
Show changes to 3 files +10 −4

cache.h, sha1_file.c, streaming.c

diff --git a/cache.h b/cache.h
index 20c2d6d..5028ded 100644
--- a/cache.h
+++ b/cache.h
@@ -1168,7 +1168,7 @@ struct object_info {
 		struct {
 			struct packed_git *pack;
 			off_t offset;
-			unsigned int is_delta;
+			unsigned int real_type;
 		} packed;
 	} u;
 };
diff --git a/sha1_file.c b/sha1_file.c
index ef6ecc8..5848008 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -2557,8 +2557,7 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi)
 		oi->whence = OI_PACKED;
 		oi->u.packed.offset = e.offset;
 		oi->u.packed.pack = e.p;
-		oi->u.packed.is_delta = (rtype == OBJ_REF_DELTA ||
-					 rtype == OBJ_OFS_DELTA);
+		oi->u.packed.real_type = rtype;
 	}
 
 	return 0;
diff --git a/streaming.c b/streaming.c
index c7edebb..2cc4c03 100644
--- a/streaming.c
+++ b/streaming.c
@@ -104,6 +104,12 @@ ssize_t read_istream(struct git_istream *st, void *buf, size_t sz)
 	return st->vtbl->read(st, buf, sz);
 }
 
+static int is_canonical(int type)
+{
+	return type != OBJ_COMMIT && type != OBJ_TREE &&
+		type != OBJ_BLOB && type != OBJ_TAG;
+}
+
 static enum input_source istream_source(const unsigned char *sha1,
 					enum object_type *type,
 					struct object_info *oi)
@@ -121,7 +127,8 @@ static enum input_source istream_source(const unsigned char *sha1,
 	case OI_LOOSE:
 		return loose;
 	case OI_PACKED:
-		if (!oi->u.packed.is_delta && big_file_threshold < size)
+		if (is_canonical(oi->u.packed.real_type) &&
+		    big_file_threshold < size)
 			return pack_non_delta;
 		/* fallthru */
 	default:
-- 
1.8.2.83.gc99314b
Nguyễn Thái Ngọc Duy· Oct 9, 2013, 14:46 UTC · re: Nguyễn Thái Ngọc Duy · lore

[PATCH 2/9] pack v4: move v2 tree entry generation code out of decode_entries

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 packv4-parse.c | 41 ++++++++++++++++++++++++++---------------
 1 file changed, 26 insertions(+), 15 deletions(-)
Show changes to packv4-parse.c +26 −15
diff --git a/packv4-parse.c b/packv4-parse.c
index 31c89c7..7b096cb 100644
--- a/packv4-parse.c
+++ b/packv4-parse.c
@@ -443,6 +443,31 @@ static int tree_entry_prefix(unsigned char *buf, unsigned long size,
 	return len;
 }
 
+static int generate_tree_entry(struct packed_git *p,
+			       const unsigned char **bufp,
+			       unsigned char **dstp, unsigned long *sizep,
+			       int what)
+{
+	const unsigned char *path, *sha1;
+	unsigned mode;
+	int len, pathlen;
+
+	path = get_pathref(p, what >> 1, &pathlen);
+	sha1 = get_sha1ref(p, bufp);
+	if (!path || !sha1)
+		return -1;
+	mode = (path[0] << 8) | path[1];
+	len = tree_entry_prefix(*dstp, *sizep,
+				path + 2, pathlen - 2, mode);
+	if (!len || len + 20 > *sizep)
+		return -1;
+	hashcpy(*dstp + len, sha1);
+	len += 20;
+	*dstp += len;
+	*sizep -= len;
+	return 0;
+}
+
 static int decode_entries(struct packed_git *p, struct pack_window **w_curs,
 			  off_t obj_offset, unsigned int start, unsigned int count,
 			  unsigned char **dstp, unsigned long *sizep)
@@ -543,22 +568,8 @@ static int decode_entries(struct packed_git *p, struct pack_window **w_curs,
 			/*
 			 * This is an actual tree entry to recreate.
 			 */
-			const unsigned char *path, *sha1;
-			unsigned mode;
-			int len, pathlen;
-
-			path = get_pathref(p, what >> 1, &pathlen);
-			sha1 = get_sha1ref(p, &scp);
-			if (!path || !sha1)
-				return -1;
-			mode = (path[0] << 8) | path[1];
-			len = tree_entry_prefix(*dstp, *sizep,
-						path + 2, pathlen - 2, mode);
-			if (!len || len + 20 > *sizep)
+			if (generate_tree_entry(p, &scp, dstp, sizep, what))
 				return -1;
-			hashcpy(*dstp + len, sha1);
-			*dstp += len + 20;
-			*sizep -= len + 20;
 			count--;
 			curpos++;
 		} else if (what & 1) {
-- 
1.8.2.83.gc99314b
Nguyễn Thái Ngọc Duy· Oct 9, 2013, 14:46 UTC · re: Nguyễn Thái Ngọc Duy · lore

[PATCH 3/9] pv4_tree_desc: introduce new struct for pack v4 tree walker

This struct is intended to be the successor of struct tree_desc. For now it only holds a buffer for converting pv4 tree to canonical format.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 packv4-parse.c | 73 ++++++++++++++++++++++++++++------------------------------
 packv4-parse.h |  9 ++++++++
 2 files changed, 44 insertions(+), 38 deletions(-)
Show changes to 2 files +44 −38

packv4-parse.c, packv4-parse.h

diff --git a/packv4-parse.c b/packv4-parse.c
index 7b096cb..f9db364 100644
--- a/packv4-parse.c
+++ b/packv4-parse.c
@@ -344,9 +344,8 @@ void *pv4_get_commit(struct packed_git *p, struct pack_window **w_curs,
 	return dst;
 }
 
-static int copy_canonical_tree_entries(struct packed_git *p, off_t offset,
-				       unsigned int start, unsigned int count,
-				       unsigned char **dstp, unsigned long *sizep)
+static int copy_canonical_tree_entries(struct pv4_tree_desc *v4, off_t offset,
+				       unsigned int start, unsigned int count)
 {
 	void *data;
 	const unsigned char *from, *end;
@@ -354,7 +353,7 @@ static int copy_canonical_tree_entries(struct packed_git *p, off_t offset,
 	unsigned long size;
 	struct tree_desc desc;
 
-	data = unpack_entry(p, offset, &type, &size);
+	data = unpack_entry(v4->p, offset, &type, &size);
 	if (!data)
 		return -1;
 	if (type != OBJ_TREE) {
@@ -372,13 +371,11 @@ static int copy_canonical_tree_entries(struct packed_git *p, off_t offset,
 		update_tree_entry(&desc);
 	end = desc.buffer;
 
-	if (end - from > *sizep) {
+	if (end - from > strbuf_avail(&v4->buf)) {
 		free(data);
 		return -1;
 	}
-	memcpy(*dstp, from, end - from);
-	*dstp += end - from;
-	*sizep -= end - from;
+	strbuf_add(&v4->buf, from, end - from);
 	free(data);
 	return 0;
 }
@@ -417,7 +414,7 @@ static struct pv4_tree_cache *get_tree_offset_cache(struct packed_git *p, off_t
 	return c;
 }
 
-static int tree_entry_prefix(unsigned char *buf, unsigned long size,
+static int tree_entry_prefix(char *buf, unsigned long size,
 			     const unsigned char *path, int path_len,
 			     unsigned mode)
 {
@@ -443,35 +440,33 @@ static int tree_entry_prefix(unsigned char *buf, unsigned long size,
 	return len;
 }
 
-static int generate_tree_entry(struct packed_git *p,
+static int generate_tree_entry(struct pv4_tree_desc *desc,
 			       const unsigned char **bufp,
-			       unsigned char **dstp, unsigned long *sizep,
 			       int what)
 {
 	const unsigned char *path, *sha1;
+	char *buf = desc->buf.buf + desc->buf.len;
 	unsigned mode;
 	int len, pathlen;
 
-	path = get_pathref(p, what >> 1, &pathlen);
-	sha1 = get_sha1ref(p, bufp);
+	path = get_pathref(desc->p, what >> 1, &pathlen);
+	sha1 = get_sha1ref(desc->p, bufp);
 	if (!path || !sha1)
 		return -1;
 	mode = (path[0] << 8) | path[1];
-	len = tree_entry_prefix(*dstp, *sizep,
+	len = tree_entry_prefix(buf, strbuf_avail(&desc->buf),
 				path + 2, pathlen - 2, mode);
-	if (!len || len + 20 > *sizep)
+	if (!len || len + 20 > strbuf_avail(&desc->buf))
 		return -1;
-	hashcpy(*dstp + len, sha1);
-	len += 20;
-	*dstp += len;
-	*sizep -= len;
+	memcpy(buf + len, sha1, 20);
+	desc->buf.len += len + 20;
 	return 0;
 }
 
-static int decode_entries(struct packed_git *p, struct pack_window **w_curs,
-			  off_t obj_offset, unsigned int start, unsigned int count,
-			  unsigned char **dstp, unsigned long *sizep)
+static int decode_entries(struct pv4_tree_desc *desc, off_t obj_offset,
+			  unsigned int start, unsigned int count)
 {
+	struct packed_git *p = desc->p;
 	unsigned long avail;
 	const unsigned char *src, *scp;
 	unsigned int curpos;
@@ -490,7 +485,7 @@ static int decode_entries(struct packed_git *p, struct pack_window **w_curs,
 	} else {
 		unsigned int nb_entries;
 
-		src = use_pack(p, w_curs, obj_offset, &avail);
+		src = use_pack(p, &desc->w_curs, obj_offset, &avail);
 		scp = src;
 
 		/* we need to skip over the object header */
@@ -502,9 +497,8 @@ static int decode_entries(struct packed_git *p, struct pack_window **w_curs,
 		/* is this a canonical tree object? */
 		case OBJ_TREE:
 		case OBJ_REF_DELTA:
-			return copy_canonical_tree_entries(p, obj_offset,
-							   start, count,
-							   dstp, sizep);
+			return copy_canonical_tree_entries(desc, obj_offset,
+							   start, count);
 		/* let's still make sure this is actually a pv4 tree */
 		case OBJ_PV4_TREE:
 			break;
@@ -542,7 +536,7 @@ static int decode_entries(struct packed_git *p, struct pack_window **w_curs,
 		unsigned int what;
 
 		if (avail < 20) {
-			src = use_pack(p, w_curs, offset, &avail);
+			src = use_pack(p, &desc->w_curs, offset, &avail);
 			if (avail < 20)
 				return -1;
 		}
@@ -568,7 +562,7 @@ static int decode_entries(struct packed_git *p, struct pack_window **w_curs,
 			/*
 			 * This is an actual tree entry to recreate.
 			 */
-			if (generate_tree_entry(p, &scp, dstp, sizep, what))
+			if (generate_tree_entry(desc, &scp, what))
 				return -1;
 			count--;
 			curpos++;
@@ -638,9 +632,8 @@ static int decode_entries(struct packed_git *p, struct pack_window **w_curs,
 					start = 0;
 				}
 
-				ret = decode_entries(p, w_curs, copy_objoffset,
-						     copy_start, copy_count,
-						     dstp, sizep);
+				ret = decode_entries(desc, copy_objoffset,
+						     copy_start, copy_count);
 				if (ret)
 					return ret;
 
@@ -672,17 +665,21 @@ static int decode_entries(struct packed_git *p, struct pack_window **w_curs,
 void *pv4_get_tree(struct packed_git *p, struct pack_window **w_curs,
 		   off_t obj_offset, unsigned long size)
 {
-	unsigned char *dst, *dcp;
+	struct pv4_tree_desc desc;
 	int ret;
 
-	dst = xmallocz(size);
-	dcp = dst;
-	ret = decode_entries(p, w_curs, obj_offset, 0, 0, &dcp, &size);
-	if (ret < 0 || size != 0) {
-		free(dst);
+	memset(&desc, 0, sizeof(desc));
+	desc.p = p;
+	desc.w_curs = *w_curs;
+	strbuf_init(&desc.buf, size);
+
+	ret = decode_entries(&desc, obj_offset, 0, 0);
+	*w_curs = desc.w_curs;
+	if (ret < 0 || desc.buf.len != size) {
+		strbuf_release(&desc.buf);
 		return NULL;
 	}
-	return dst;
+	return strbuf_detach(&desc.buf, NULL);
 }
 
 unsigned long pv4_unpack_object_header_buffer(const unsigned char *base,
diff --git a/packv4-parse.h b/packv4-parse.h
index b437159..cad7a82 100644
--- a/packv4-parse.h
+++ b/packv4-parse.h
@@ -22,4 +22,13 @@ void *pv4_get_commit(struct packed_git *p, struct pack_window **w_curs,
 void *pv4_get_tree(struct packed_git *p, struct pack_window **w_curs,
 		   off_t obj_offset, unsigned long size);
 
+struct pv4_tree_desc {
+	/* v4 entry */
+	struct packed_git *p;
+	struct pack_window *w_curs;
+
+	/* full canonical tree */
+	struct strbuf buf;
+};
+
 #endif
-- 
1.8.2.83.gc99314b
Nguyễn Thái Ngọc Duy· Oct 9, 2013, 14:46 UTC · re: Nguyễn Thái Ngọc Duy · lore

[PATCH 4/9] pv4_tree_desc: use struct tree_desc from pv4_tree_desc

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 packv4-parse.c | 13 ++++++-------
 packv4-parse.h |  5 +++++
 2 files changed, 11 insertions(+), 7 deletions(-)
Show changes to 2 files +11 −7

packv4-parse.c, packv4-parse.h

diff --git a/packv4-parse.c b/packv4-parse.c
index f9db364..f5c486e 100644
--- a/packv4-parse.c
+++ b/packv4-parse.c
@@ -10,7 +10,6 @@
 
 #include "cache.h"
 #include "packv4-parse.h"
-#include "tree-walk.h"
 #include "varint.h"
 
 const unsigned char *get_sha1ref(struct packed_git *p,
@@ -351,7 +350,7 @@ static int copy_canonical_tree_entries(struct pv4_tree_desc *v4, off_t offset,
 	const unsigned char *from, *end;
 	enum object_type type;
 	unsigned long size;
-	struct tree_desc desc;
+	struct tree_desc *desc = &v4->v2;
 
 	data = unpack_entry(v4->p, offset, &type, &size);
 	if (!data)
@@ -361,15 +360,15 @@ static int copy_canonical_tree_entries(struct pv4_tree_desc *v4, off_t offset,
 		return -1;
 	}
 
-	init_tree_desc(&desc, data, size);
+	init_tree_desc(desc, data, size);
 
 	while (start--)
-		update_tree_entry(&desc);
+		update_tree_entry(desc);
 
-	from = desc.buffer;
+	from = desc->buffer;
 	while (count--)
-		update_tree_entry(&desc);
-	end = desc.buffer;
+		update_tree_entry(desc);
+	end = desc->buffer;
 
 	if (end - from > strbuf_avail(&v4->buf)) {
 		free(data);
diff --git a/packv4-parse.h b/packv4-parse.h
index cad7a82..04b9a59 100644
--- a/packv4-parse.h
+++ b/packv4-parse.h
@@ -1,6 +1,8 @@
 #ifndef PACKV4_PARSE_H
 #define PACKV4_PARSE_H
 
+#include "tree-walk.h"
+
 struct packv4_dict {
 	const unsigned char *data;
 	unsigned int nb_entries;
@@ -27,6 +29,9 @@ struct pv4_tree_desc {
 	struct packed_git *p;
 	struct pack_window *w_curs;
 
+	/* v2 entry */
+	struct tree_desc v2;
+
 	/* full canonical tree */
 	struct strbuf buf;
 };
-- 
1.8.2.83.gc99314b
Nguyễn Thái Ngọc Duy· Oct 9, 2013, 14:46 UTC · re: Nguyễn Thái Ngọc Duy · lore

[PATCH 5/9] pv4_tree_desc: allow decode_entries to return v4 trees, one at a time

When PV4_TREE_CANONICAL is passed, decode_entries() generates <count> tree entries in canonical format. When this flag is not passed _and_ count is 1, decode_entries fills struct name_entry and saves sha1_index.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 packv4-parse.c | 44 ++++++++++++++++++++++++++++++++++++++++++--
 packv4-parse.h | 10 ++++++++++
 2 files changed, 52 insertions(+), 2 deletions(-)
Show changes to 2 files +52 −2

packv4-parse.c, packv4-parse.h

diff --git a/packv4-parse.c b/packv4-parse.c
index f5c486e..f222456 100644
--- a/packv4-parse.c
+++ b/packv4-parse.c
@@ -365,6 +365,12 @@ static int copy_canonical_tree_entries(struct pv4_tree_desc *v4, off_t offset,
 	while (start--)
 		update_tree_entry(desc);
 
+	if (!(v4->flags & PV4_TREE_CANONICAL)) {
+		v4->sha1_index = 0;
+		v4->pathlen = tree_entry_len(&desc->entry);
+		return 0;
+	}
+
 	from = desc->buffer;
 	while (count--)
 		update_tree_entry(desc);
@@ -462,6 +468,33 @@ static int generate_tree_entry(struct pv4_tree_desc *desc,
 	return 0;
 }
 
+static int get_tree_entry_v4(struct pv4_tree_desc *desc,
+			     const unsigned char **bufp,
+			     int what)
+{
+	const unsigned char *path;
+
+	path = get_pathref(desc->p, what >> 1, &desc->pathlen);
+	if (!path)
+		return -1;
+	desc->v2.entry.mode = (path[0] << 8) | path[1];
+	desc->v2.entry.path = (const char *)path + 2;
+
+	if (**bufp) {
+		desc->sha1_index = decode_varint(bufp);
+		if (desc->sha1_index < 1 ||
+		    desc->sha1_index - 1 > desc->p->num_objects)
+			return error("bad index in get_sha1ref");
+		desc->v2.entry.sha1 = desc->p->sha1_table + (desc->sha1_index - 1) * 20;
+	} else {
+		desc->sha1_index = 0;
+		desc->v2.entry.sha1 = *bufp + 1;
+		*bufp += 21;
+	}
+
+	return 0;
+}
+
 static int decode_entries(struct pv4_tree_desc *desc, off_t obj_offset,
 			  unsigned int start, unsigned int count)
 {
@@ -561,8 +594,14 @@ static int decode_entries(struct pv4_tree_desc *desc, off_t obj_offset,
 			/*
 			 * This is an actual tree entry to recreate.
 			 */
-			if (generate_tree_entry(desc, &scp, what))
-				return -1;
+			if (desc->flags & PV4_TREE_CANONICAL) {
+				if (generate_tree_entry(desc, &scp, what))
+					return -1;
+			} else if (count == 1) {
+				if (get_tree_entry_v4(desc, &scp, what))
+					return -1;
+			} else
+				die("generating multiple v4 entries is not supported");
 			count--;
 			curpos++;
 		} else if (what & 1) {
@@ -668,6 +707,7 @@ void *pv4_get_tree(struct packed_git *p, struct pack_window **w_curs,
 	int ret;
 
 	memset(&desc, 0, sizeof(desc));
+	desc.flags = PV4_TREE_CANONICAL;
 	desc.p = p;
 	desc.w_curs = *w_curs;
 	strbuf_init(&desc.buf, size);
diff --git a/packv4-parse.h b/packv4-parse.h
index 04b9a59..fe0ea38 100644
--- a/packv4-parse.h
+++ b/packv4-parse.h
@@ -24,10 +24,20 @@ void *pv4_get_commit(struct packed_git *p, struct pack_window **w_curs,
 void *pv4_get_tree(struct packed_git *p, struct pack_window **w_curs,
 		   off_t obj_offset, unsigned long size);
 
+/*
+ * These are private flags, never pass them directly to
+ * pv4_tree_desc_*
+ */
+#define PV4_TREE_CANONICAL   0x800
+
 struct pv4_tree_desc {
+	unsigned flags;
+
 	/* v4 entry */
 	struct packed_git *p;
 	struct pack_window *w_curs;
+	unsigned int sha1_index;
+	int pathlen;
 
 	/* v2 entry */
 	struct tree_desc v2;
-- 
1.8.2.83.gc99314b
Nguyễn Thái Ngọc Duy· Oct 9, 2013, 14:46 UTC · re: Nguyễn Thái Ngọc Duy · lore

[PATCH 6/9] pv4_tree_desc: complete interface

Best "explained" with an example
  void walk(const unsigned char *sha1)
  {
    struct pv4_tree_desc desc;
    /*
     * Start pv4_tree_desc from an SHA-1. If it's a v4 tree, v4 walker
     * will be used. Otherwise v2 is walked.
     */
    pv4_tree_desc_from_sha1(&desc, sha1, 0);
    recurse(&desc);
    pv4_release_tree_desc(&desc);
  }
  void recurse(struct pv4_tree_desc *desc)
  {
    /*
     * Then you can go over entries, one by one, similar to the
     * current tree walker. Current entry is in desc->v2.entry.
     * Pathlen in desc->pathlen. Do not use tree_entry_len() because
     * that one is only correct for v2 entries
     */
    while (pv4_get_entry(desc)) {
      printf("%s %s\n", sha1_to_hex(desc->v2.entry.sha1),
             desc->v2.entry.path);
      /*
       * Once you have an initialized pv4_tree_desc you may skip the
       * SHA-1 lookup step if the next tree is in the same pack.
       */
      if (S_ISDIR(desc->v2.entry.mode)) {
        struct pv4_tree_desc new_desc;
        pv4_tree_desc_from_entry(&new_desc, desc);
        recurse(&new_desc);
        /* Finally release everything */
        pv4_release_tree_desc(&new_desc);
      }
    }
  }
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 packv4-parse.c | 80 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 packv4-parse.h | 12 +++++++++
 2 files changed, 92 insertions(+)
Show changes to 2 files +92 −0

packv4-parse.c, packv4-parse.h

diff --git a/packv4-parse.c b/packv4-parse.c
index f222456..7d257af 100644
--- a/packv4-parse.c
+++ b/packv4-parse.c
@@ -732,3 +732,83 @@ unsigned long pv4_unpack_object_header_buffer(const unsigned char *base,
 	*sizep = val >> 4;
 	return cp - base;
 }
+
+int pv4_tree_desc_from_sha1(struct pv4_tree_desc *desc,
+			    const unsigned char *sha1,
+			    unsigned flags)
+{
+	unsigned long size;
+	enum object_type type;
+	void *data;
+	struct object_info oi;
+
+	assert(!(flags & ~0xff) &&
+	       "you are not supposed to set these from outside!");
+
+	memset(desc, 0, sizeof(*desc));
+	strbuf_init(&desc->buf, 0);
+
+	memset(&oi, 0, sizeof(oi));
+	if (!sha1_object_info_extended(sha1, &oi) &&
+	    oi.whence == OI_PACKED &&
+	    oi.u.packed.real_type == OBJ_PV4_TREE &&
+	    oi.u.packed.pack->version >= 4) {
+		desc->p = oi.u.packed.pack;
+		desc->obj_offset = oi.u.packed.offset;
+		desc->flags = flags;
+		return 0;
+	}
+
+	data = read_sha1_file(sha1, &type, &size);
+	if (!data || type != OBJ_TREE) {
+		free(data);
+		return -1;
+	}
+	desc->flags = flags;
+	desc->flags |= PV4_TREE_CANONICAL;
+	init_tree_desc(&desc->v2, data, size);
+	/*
+	 * we can attach to strbuf because read_sha1_file always
+	 * appends NUL at the end
+	 */
+	strbuf_attach(&desc->buf, data, size, size + 1);
+	return 0;
+}
+
+int pv4_tree_desc_from_entry(struct pv4_tree_desc *desc,
+			     const struct pv4_tree_desc *src,
+			     unsigned flags)
+{
+	if (!src->sha1_index)
+		return pv4_tree_desc_from_sha1(desc,
+					       src->v2.entry.sha1,
+					       flags);
+	assert(!(flags & ~0xff) &&
+	       "you are not supposed to set these from outside!");
+	memset(desc, 0, sizeof(*desc));
+	strbuf_init(&desc->buf, 0);
+	desc->p = src->p;
+	desc->obj_offset =
+		nth_packed_object_offset(desc->p, src->sha1_index - 1);
+	desc->flags = flags;
+	return 0;
+}
+
+void pv4_release_tree_desc(struct pv4_tree_desc *desc)
+{
+	strbuf_release(&desc->buf);
+	unuse_pack(&desc->w_curs);
+}
+
+int pv4_tree_entry(struct pv4_tree_desc *desc)
+{
+	if (desc->flags & PV4_TREE_CANONICAL) {
+		if (!desc->v2.size)
+			return 0;
+		if (desc->start)
+			update_tree_entry(&desc->v2);
+		desc->start++;
+		return 1;
+	}
+	return !decode_entries(desc, desc->obj_offset, desc->start++, 1);
+}
diff --git a/packv4-parse.h b/packv4-parse.h
index fe0ea38..874f57c 100644
--- a/packv4-parse.h
+++ b/packv4-parse.h
@@ -36,6 +36,8 @@ struct pv4_tree_desc {
 	/* v4 entry */
 	struct packed_git *p;
 	struct pack_window *w_curs;
+	off_t obj_offset;
+	unsigned start;
 	unsigned int sha1_index;
 	int pathlen;
 
@@ -46,4 +48,14 @@ struct pv4_tree_desc {
 	struct strbuf buf;
 };
 
+int pv4_tree_desc_from_sha1(struct pv4_tree_desc *desc,
+			    const unsigned char *sha1,
+			    unsigned flags);
+int pv4_tree_desc_from_entry(struct pv4_tree_desc *desc,
+			     const struct pv4_tree_desc *src,
+			     unsigned flags);
+void pv4_release_tree_desc(struct pv4_tree_desc *desc);
+
+int pv4_tree_entry(struct pv4_tree_desc *desc);
+
 #endif
-- 
1.8.2.83.gc99314b
Nguyễn Thái Ngọc Duy· Oct 9, 2013, 14:46 UTC · re: Nguyễn Thái Ngọc Duy · lore

[PATCH 7/9] pv4_tree_desc: don't bother looking for v4 trees if no v4 packs are present

This is mostly to avoid overhead on v2 only systems.
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 packv4-parse.c | 5 ++++-
 sha1_file.c    | 5 +++++
 2 files changed, 9 insertions(+), 1 deletion(-)
Show changes to 2 files +9 −1

packv4-parse.c, sha1_file.c

diff --git a/packv4-parse.c b/packv4-parse.c
index 7d257af..4354ee3 100644
--- a/packv4-parse.c
+++ b/packv4-parse.c
@@ -12,6 +12,8 @@
 #include "packv4-parse.h"
 #include "varint.h"
 
+int packv4_available;
+
 const unsigned char *get_sha1ref(struct packed_git *p,
 				 const unsigned char **bufp)
 {
@@ -749,7 +751,8 @@ int pv4_tree_desc_from_sha1(struct pv4_tree_desc *desc,
 	strbuf_init(&desc->buf, 0);
 
 	memset(&oi, 0, sizeof(oi));
-	if (!sha1_object_info_extended(sha1, &oi) &&
+	if (packv4_available &&
+	    !sha1_object_info_extended(sha1, &oi) &&
 	    oi.whence == OI_PACKED &&
 	    oi.u.packed.real_type == OBJ_PV4_TREE &&
 	    oi.u.packed.pack->version >= 4) {
diff --git a/sha1_file.c b/sha1_file.c
index 5848008..4744132 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -40,6 +40,7 @@ const unsigned char null_sha1[20];
 
 static const char *no_log_pack_access = "no_log_pack_access";
 static const char *log_pack_access;
+extern int packv4_available;
 
 /*
  * This is meant to hold a *small* number of objects that you would
@@ -763,6 +764,8 @@ void free_pack_by_name(const char *pack_name)
 				close(p->pack_fd);
 				pack_open_fds--;
 			}
+			if (p->version >= 4)
+				packv4_available--;
 			close_pack_index(p);
 			free(p->bad_object_sha1);
 			pv4_free_dict(p->ident_dict);
@@ -856,6 +859,8 @@ static int open_packed_git_1(struct packed_git *p)
 			" supported (try upgrading GIT to a newer version)",
 			p->pack_name, ntohl(hdr.hdr_version));
 	p->version = ntohl(hdr.hdr_version);
+	if (p->version >= 4)
+		packv4_available++;
 
 	/* Verify the pack matches its index. */
 	if (p->num_objects != ntohl(hdr.hdr_entries))
-- 
1.8.2.83.gc99314b
Nguyễn Thái Ngọc Duy· Oct 9, 2013, 14:46 UTC · re: Nguyễn Thái Ngọc Duy · lore

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

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(+)
Show changes to 4 files +47 −0

cache.h, packv4-parse.c, packv4-parse.h, sha1_file.c

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
Nguyễn Thái Ngọc Duy· Oct 9, 2013, 14:46 UTC · re: Nguyễn Thái Ngọc Duy · lore

[PATCH 9/9] list-object.c: take "advantage" of new pv4_tree_desc interface

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 list-objects.c | 38 ++++++++++++++++++++++----------------
 1 file changed, 22 insertions(+), 16 deletions(-)
Show changes to list-objects.c +22 −16
diff --git a/list-objects.c b/list-objects.c
index 6def897..39ad3e6 100644
--- a/list-objects.c
+++ b/list-objects.c
@@ -7,6 +7,7 @@
 #include "tree-walk.h"
 #include "revision.h"
 #include "list-objects.h"
+#include "packv4-parse.h"
 
 static void process_blob(struct rev_info *revs,
 			 struct blob *blob,
@@ -60,6 +61,7 @@ static void process_gitlink(struct rev_info *revs,
 }
 
 static void process_tree(struct rev_info *revs,
+			 struct pv4_tree_desc *desc,
 			 struct tree *tree,
 			 show_tree_entry_fn show_tree_entry,
 			 show_object_fn show,
@@ -69,8 +71,6 @@ static void process_tree(struct rev_info *revs,
 			 void *cb_data)
 {
 	struct object *obj = &tree->object;
-	struct tree_desc desc;
-	struct name_entry entry;
 	struct name_path me;
 	enum interesting match = revs->diffopt.pathspec.nr == 0 ?
 		all_entries_interesting: entry_not_interesting;
@@ -96,11 +96,10 @@ static void process_tree(struct rev_info *revs,
 			strbuf_addch(base, '/');
 	}
 
-	init_tree_desc(&desc, tree->buffer, tree->size);
-
-	while (tree_entry(&desc, &entry)) {
+	while (pv4_tree_entry(desc)) {
+		struct name_entry *entry = &desc->v2.entry;
 		if (match != all_entries_interesting) {
-			match = tree_entry_interesting(&entry, base, 0,
+			match = tree_entry_interesting(entry, base, 0,
 						       &revs->diffopt.pathspec);
 			if (match == all_entries_not_interesting)
 				break;
@@ -109,22 +108,26 @@ static void process_tree(struct rev_info *revs,
 		}
 
 		if (show_tree_entry)
-			show_tree_entry(&entry, cb_data);
+			show_tree_entry(entry, cb_data);
 
-		if (S_ISDIR(entry.mode))
+		if (S_ISDIR(entry->mode)) {
+			struct pv4_tree_desc sub_desc;
+			pv4_tree_desc_from_entry(&sub_desc, desc, 0);
 			process_tree(revs,
-				     lookup_tree(entry.sha1),
+				     &sub_desc,
+				     pv4_lookup_tree(desc),
 				     show_tree_entry,
-				     show, &me, base, entry.path,
+				     show, &me, base, entry->path,
 				     cb_data);
-		else if (S_ISGITLINK(entry.mode))
-			process_gitlink(revs, entry.sha1,
-					show, &me, entry.path,
+			pv4_release_tree_desc(&sub_desc);
+		} else if (S_ISGITLINK(entry->mode))
+			process_gitlink(revs, entry->sha1,
+					show, &me, entry->path,
 					cb_data);
 		else
 			process_blob(revs,
-				     lookup_blob(entry.sha1),
-				     show, &me, entry.path,
+				     pv4_lookup_blob(desc),
+				     show, &me, entry->path,
 				     cb_data);
 	}
 	strbuf_setlen(base, baselen);
@@ -202,9 +205,12 @@ void traverse_commit_list(struct rev_info *revs,
 			continue;
 		}
 		if (obj->type == OBJ_TREE) {
-			process_tree(revs, (struct tree *)obj,
+			struct pv4_tree_desc desc;
+			pv4_tree_desc_from_sha1(&desc, obj->sha1, 0);
+			process_tree(revs, &desc, (struct tree *)obj,
 				     show_tree_entry, show_object,
 				     NULL, &base, name, data);
+			pv4_release_tree_desc(&desc);
 			continue;
 		}
 		if (obj->type == OBJ_BLOB) {
-- 
1.8.2.83.gc99314b
Nicolas Pitre· Oct 9, 2013, 16:51 UTC · re: Nguyễn Thái Ngọc Duy · lore

Re: [BAD PATCH 0/9] v4-aware tree walker API

On Wed, 9 Oct 2013, Nguy�n Th�i Ng�c Duy wrote:
Show 7 quoted lines
> I know I still have a lot of holes to plug, but this was more
> interesting because we could see some encouraging numbers.
> Unfortunately the result is disappointing. Maybe I did it in a stupid
> way and need to restart with a totally different way.
> 
> "rev-list --objects" on v2 takes 4 secs, v4 with current walker 11s
> and the new walker 16s (worst!).

Clear indication that something is wrong if the intermediate step of converting to the canonical object representation is faster than your attempt at a native pv4 walker.

However here's the numbers I get here after a fresh clone of git.git
$ time git revlist --objects --all > /dev/null

real 0m2.619s user 0m2.577s sys 0m0.033s $ mkdir orig $ mv .git/objects/pack/pack-* orig/ $ ../../git/test-packv4 orig/pack-*.pack .git/objects/pack/pack-foo.pack Scanning objects: 100% (162785/162785), done. Writing objects: 100% (162785/162785), done. $ time git rev-list --objects --all > /dev/null

real 0m6.210s user 0m6.140s sys 0m0.027s

[installing git with your latest patches applied here]
$ time git rev-list --objects --all > /dev/null

real 0m20.409s user 0m20.337s sys 0m0.029s

So... I get even *worse* numbers relative to v2 than you do!
Now let's mitigate the deep delta chaining effect in the tree encoding:

$ rm .git/objects/pack/pack-foo.* $ ../../git/test-packv4 --min-tree-copy=50 orig/pack-*.pack .git/objects/pack/pack-foo.pack Scanning objects: 100% (162785/162785), done. Writing objects: 100% (162785/162785), done. $ time git rev-list --objects --all > /dev/null

real 0m9.451s user 0m9.393s sys 0m0.036s

Using --min-tree-copy=50 produces a pack which is still smaller than pack v2 but any tree copy sequence must refer to a minimum of 50 entries. This significantly reduces the CPU usage in decode_entries() by reducing the needless chaining effect I mentioned here:

http://article.gmane.org/gmane.comp.version-control.git/234975
Now let's keep that pack and back out your patches.
[installing git with your latest patches reverted here]
$ time git rev-list --objects --all > /dev/null

real 0m3.751s user 0m3.711s sys 0m0.029s

So I shoved almost 2.5 seconds of runtime here. Not the half of the original runtime, but still significant.

Let's push the chaining theory even further:

$ rm .git/objects/pack/pack-foo.* $ ../../git/test-packv4 --min-tree-copy=100 orig/pack-*.pack .git/objects/pack/pack-foo.pack Scanning objects: 100% (162785/162785), done. Writing objects: 100% (162785/162785), done. $ time git rev-list --objects --all > /dev/null

real 0m3.445s user 0m3.406s sys 0m0.029s

With --min-tree-copy=100 the resulting pack gets somewhat larger than the v2 equivalent, but still smaller if we take into account the size of both the pack and index files. However the runtime benefit is no more significant.

So, there are 2 conclusions here:
1: The current tree delta euristic is inefficient for pack v4.
2- Something must be very wrong in your latest patches as they make it
   close to 3 times more expensive than without them.
Show 5 quoted lines
> The only bit I haven't done is avoid checking if a tree is already
> examined, if so do not bother with copy sequences referring to it.
> That should cut down the number of decode_entries but not sure how
> much because there's no relation between tree traversing order and how
> copy sequences are made.
I'm sure it would help mitigate the deep delta chaining effect as well.
Show 5 quoted lines
> Maybe we could make an exception and allow the tree walker to pass
> pv4_tree_cache* directly to decode_entries so it does not need to do
> the first lookup every time..
> 
> Suggestions?
I'll try to have a look at your patches in more details soon.
Nicolas
Duy Nguyen· Oct 11, 2013, 12:22 UTC · re: Nicolas Pitre · lore

Re: [BAD PATCH 0/9] v4-aware tree walker API

On Wed, Oct 09, 2013 at 12:51:26PM -0400, Nicolas Pitre wrote:
Show 18 quoted lines
> Now let's mitigate the deep delta chaining effect in the tree encoding:
> 
> $ rm .git/objects/pack/pack-foo.*
> $ ../../git/test-packv4 --min-tree-copy=50 orig/pack-*.pack .git/objects/pack/pack-foo.pack
> Scanning objects: 100% (162785/162785), done.
> Writing objects: 100% (162785/162785), done.
> $ time git rev-list --objects --all > /dev/null
> 
> real    0m9.451s
> user    0m9.393s
> sys     0m0.036s
> 
> Using --min-tree-copy=50 produces a pack which is still smaller than 
> pack v2 but any tree copy sequence must refer to a minimum of 50 
> entries.  This significantly reduces the CPU usage in decode_entries() 
> by reducing the needless chaining effect I mentioned here:
> 
> http://article.gmane.org/gmane.comp.version-control.git/234975
Yeah I was frustrated and did not think about trying --min-tree-copy.
Show 6 quoted lines
> So, there are 2 conclusions here:
> 
> 1: The current tree delta euristic is inefficient for pack v4.
> 
> 2- Something must be very wrong in your latest patches as they make it
>    close to 3 times more expensive than without them.

For one I know that get_tree_offset_cache() is called a lot more with the new API. I do rev-list on v1.8.4. With compatibility layer on, it's 211m calls (*). With new API it's 655m calls. The new API is basically do decode_entries() on every tree_entry() call. Perhaps I screwed up something in decode_entries() itself..

(*) for 15m tree entries, 211m are a lot of calls, which might translate to a lot of copy sequences..

Show 7 quoted lines
> > Maybe we could make an exception and allow the tree walker to pass
> > pv4_tree_cache* directly to decode_entries so it does not need to do
> > the first lookup every time..
> > 
> > Suggestions?
> 
> I'll try to have a look at your patches in more details soon.
Shameful fixup (though it does not seem to impact the timing)
Show changes to packv4-parse.c +2 −2
diff --git a/packv4-parse.c b/packv4-parse.c
index 6f6152c..9d7589e 100644
--- a/packv4-parse.c
+++ b/packv4-parse.c
@@ -825,8 +825,8 @@ 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);
+		desc->p->objs = xcalloc(desc->p->num_objects,
+					sizeof(struct object *));
 	return desc->p->objs;
 }
 
Duy Nguyen· Oct 11, 2013, 13:05 UTC · re: Duy Nguyen · lore

Re: [BAD PATCH 0/9] v4-aware tree walker API

On Fri, Oct 11, 2013 at 07:22:59PM +0700, Duy Nguyen wrote:
Show 5 quoted lines
> > > Maybe we could make an exception and allow the tree walker to pass
> > > pv4_tree_cache* directly to decode_entries so it does not need to do
> > > the first lookup every time..
> > > 
> > > Suggestions?

Looking at decode_entries() traces I think the "one decode_entries() for one tree_entry()" just amplifies the delta chain effect. If you hide 3 entries behind 5 layers of copy sequences (i.e. tree1->tree2->..->tree5->real-tree-entry), then every decode_entries(count=1) will have to go through 5 layers.

It makes me wonder if we should cache shortcuts so that after the first going through 5 layers, the second can jump directly to the tree entries.

> > 
> > I'll try to have a look at your patches in more details soon.
> 
> Shameful fixup (though it does not seem to impact the timing)
And here's another one
-- 8< --
Show changes to list-objects.c +2 −0
diff --git a/list-objects.c b/list-objects.c
index 39ad3e6..85dc14e 100644
--- a/list-objects.c
+++ b/list-objects.c
@@ -82,8 +82,10 @@ static void process_tree(struct rev_info *revs,
 		die("bad tree object");
 	if (obj->flags & (UNINTERESTING | SEEN))
 		return;
+#if 0
 	if (parse_tree(tree) < 0)
 		die("bad tree object %s", sha1_to_hex(obj->sha1));
+#endif
 	obj->flags |= SEEN;
 	show(obj, path, name, cb_data);
 	me.up = path;
Nicolas Pitre· Oct 12, 2013, 14:42 UTC · re: Duy Nguyen · lore

Re: [BAD PATCH 0/9] v4-aware tree walker API

On Fri, 11 Oct 2013, Duy Nguyen wrote:
Show 12 quoted lines
> On Fri, Oct 11, 2013 at 07:22:59PM +0700, Duy Nguyen wrote:
> > > > Maybe we could make an exception and allow the tree walker to pass
> > > > pv4_tree_cache* directly to decode_entries so it does not need to do
> > > > the first lookup every time..
> > > > 
> > > > Suggestions?
> 
> Looking at decode_entries() traces I think the "one decode_entries()
> for one tree_entry()" just amplifies the delta chain effect. If you
> hide 3 entries behind 5 layers of copy sequences
> (i.e. tree1->tree2->..->tree5->real-tree-entry), then every
> decode_entries(count=1) will have to go through 5 layers.

Calling decode_entries() for every tree entry is a bad approach. We should really implement this as a state machine preserving the entire state between entries so that moving to the next entry is just a matter of advancing a pointer in most cases.

Nicolas
Duy Nguyen· Oct 12, 2013, 15:59 UTC · re: Nicolas Pitre · lore

Re: [BAD PATCH 0/9] v4-aware tree walker API

On Sat, Oct 12, 2013 at 9:42 PM, Nicolas Pitre <nico@fluxnic.net> wrote:
Show 19 quoted lines
> On Fri, 11 Oct 2013, Duy Nguyen wrote:
>
>> On Fri, Oct 11, 2013 at 07:22:59PM +0700, Duy Nguyen wrote:
>> > > > Maybe we could make an exception and allow the tree walker to pass
>> > > > pv4_tree_cache* directly to decode_entries so it does not need to do
>> > > > the first lookup every time..
>> > > >
>> > > > Suggestions?
>>
>> Looking at decode_entries() traces I think the "one decode_entries()
>> for one tree_entry()" just amplifies the delta chain effect. If you
>> hide 3 entries behind 5 layers of copy sequences
>> (i.e. tree1->tree2->..->tree5->real-tree-entry), then every
>> decode_entries(count=1) will have to go through 5 layers.
>
> Calling decode_entries() for every tree entry is a bad approach.  We
> should really implement this as a state machine preserving the entire
> state between entries so that moving to the next entry is just a matter
> of advancing a pointer in most cases.

Yeah. Maybe first step is avoid recursion in decode_entries(). We need to do that eventually to avoid stack overlow due to long depths.

-- 
Duy

← back to recent threads