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

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

[Nguyễn Thái Ngọc Duy]

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

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

[Nguyễn Thái Ngọc Duy]

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

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

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

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 packv4-parse.c | 41 ++++++++++++++++++++++++++---------------
 1 file changed, 26 insertions(+), 15 deletions(-)

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

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

[Nguyễn Thái Ngọc Duy]

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

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

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

[Nguyễn Thái Ngọc Duy]

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

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

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

[Nguyễn Thái Ngọc Duy]

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

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

[PATCH 6/9] pv4_tree_desc: complete interface

[Nguyễn Thái Ngọc Duy]

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

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

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

[Nguyễn Thái Ngọc Duy]

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

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

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

[Nguyễn Thái Ngọc Duy]

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

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

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 list-objects.c | 38 ++++++++++++++++++++++----------------
 1 file changed, 22 insertions(+), 16 deletions(-)

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

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

[Nicolas Pitre]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 3800 bytes --]

On Wed, 9 Oct 2013, Nguyễn Thái Ngọc Duy wrote:

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

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

> 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

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

[Duy Nguyen]

On Wed, Oct 09, 2013 at 12:51:26PM -0400, Nicolas Pitre wrote:
> 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.

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

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

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;
 }
 

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

[Duy Nguyen]

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.

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

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

[Nicolas Pitre]

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.


Nicolas

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

[Duy Nguyen]

On Sat, Oct 12, 2013 at 9:42 PM, Nicolas Pitre <nico@fluxnic.net> wrote:
> 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