{"thread":{"id":"35091","subject":"[BAD PATCH 0/9] v4-aware tree walker API","startedAt":"2013-10-09T14:46:07Z","lastAt":"2013-10-12T15:59:24Z","messageCount":15,"participants":["Nguyễn Thái Ngọc Duy","Nicolas Pitre","Duy Nguyen"],"isPatch":true,"patchVersion":1,"patchTotal":9},"messages":[{"id":"228646","messageId":"1381329976-32082-1-git-send-email-pclouds@gmail.com","threadId":"35091","inReplyTo":null,"subject":"[BAD PATCH 0/9] v4-aware tree walker API","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-09T14:46:07Z","receivedAt":"2013-10-09T14:46:07Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"I know I still have a lot of holes to plug, but this was more\ninteresting because we could see some encouraging numbers.\nUnfortunately the result is disappointing. Maybe I did it in a stupid\nway and need to restart with a totally different way.\n\n\"rev-list --objects\" on v2 takes 4 secs, v4 with current walker 11s\nand the new walker 16s (worst!). perf's top functions with v2 are\n\n 23,51%  git  libz.so.1.2.7       [.] inflate\n 16,66%  git  git                 [.] lookup_object\n 11,46%  git  libz.so.1.2.7       [.] inflate_fast\n  6,89%  git  libc-2.16.so        [.] __memcpy_ssse3_back\n  4,19%  git  libz.so.1.2.7       [.] inflate_table\n  4,15%  git  git                 [.] find_pack_entry_one\n  3,84%  git  git                 [.] decode_tree_entry\n\nand with new walker\n\n 58,61%  git  git                [.] decode_entries\n 18,66%  git  git                [.] decode_varint\n  9,73%  git  git                [.] use_pack\n  3,31%  git  git                [.] nth_packed_object_offset\n  1,73%  git  git                [.] process_tree\n  1,66%  git  git                [.] pv4_lookup_blob\n  1,09%  git  git                [.] get_pathref\n  1,03%  git  libc-2.16.so       [.] __memcpy_ssse3_back\n  0,90%  git  libz.so.1.2.7      [.] inflate\n  0,50%  git  libz.so.1.2.7      [.] inflate_table\n\nIt's no surprise that lookup_object is no longer hot. The closet is\npv4_lookup_blob. nth_packed_object_offset is getting hotter as it's\nused extensively by decode_entries.\n\nAnd decode_entries is getting toooo hot. This function is now called\nfor each tree entry of every tree. And it does get_tree_offset_cache()\nlookup for every call (ironically we try hard to avoid hash lookup in\nlookup_object).\n\nThe only bit I haven't done is avoid checking if a tree is already\nexamined, if so do not bother with copy sequences referring to it.\nThat should cut down the number of decode_entries but not sure how\nmuch because there's no relation between tree traversing order and how\ncopy sequences are made.\n\nMaybe we could make an exception and allow the tree walker to pass\npv4_tree_cache* directly to decode_entries so it does not need to do\nthe first lookup every time..\n\nSuggestions?\n\nNguyễn Thái Ngọc Duy (9):\n  sha1_file: provide real packed type in object_info_extended\n  pack v4: move v2 tree entry generation code out of decode_entries\n  pv4_tree_desc: introduce new struct for pack v4 tree walker\n  pv4_tree_desc: use struct tree_desc from pv4_tree_desc\n  pv4_tree_desc: allow decode_entries to return v4 trees, one at a time\n  pv4_tree_desc: complete interface\n  pv4_tree_desc: don't bother looking for v4 trees if no v4 packs are present\n  pv4_tree_desc: avoid lookup_object() when possible\n  list-object.c: take \"advantage\" of new pv4_tree_desc interface\n\n cache.h        |   3 +-\n list-objects.c |  38 +++++----\n packv4-parse.c | 263 ++++++++++++++++++++++++++++++++++++++++++++++-----------\n packv4-parse.h |  48 +++++++++++\n sha1_file.c    |   9 +-\n streaming.c    |   9 +-\n 6 files changed, 300 insertions(+), 70 deletions(-)\n\n-- \n1.8.2.83.gc99314b\n"},{"id":"228647","messageId":"1381329976-32082-2-git-send-email-pclouds@gmail.com","threadId":"35091","inReplyTo":"1381329976-32082-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 1/9] sha1_file: provide real packed type in object_info_extended","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-09T14:46:08Z","receivedAt":"2013-10-09T14:46:08Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n cache.h     | 2 +-\n sha1_file.c | 3 +--\n streaming.c | 9 ++++++++-\n 3 files changed, 10 insertions(+), 4 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex 20c2d6d..5028ded 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1168,7 +1168,7 @@ struct object_info {\n \t\tstruct {\n \t\t\tstruct packed_git *pack;\n \t\t\toff_t offset;\n-\t\t\tunsigned int is_delta;\n+\t\t\tunsigned int real_type;\n \t\t} packed;\n \t} u;\n };\ndiff --git a/sha1_file.c b/sha1_file.c\nindex ef6ecc8..5848008 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -2557,8 +2557,7 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi)\n \t\toi->whence = OI_PACKED;\n \t\toi->u.packed.offset = e.offset;\n \t\toi->u.packed.pack = e.p;\n-\t\toi->u.packed.is_delta = (rtype == OBJ_REF_DELTA ||\n-\t\t\t\t\t rtype == OBJ_OFS_DELTA);\n+\t\toi->u.packed.real_type = rtype;\n \t}\n \n \treturn 0;\ndiff --git a/streaming.c b/streaming.c\nindex c7edebb..2cc4c03 100644\n--- a/streaming.c\n+++ b/streaming.c\n@@ -104,6 +104,12 @@ ssize_t read_istream(struct git_istream *st, void *buf, size_t sz)\n \treturn st->vtbl->read(st, buf, sz);\n }\n \n+static int is_canonical(int type)\n+{\n+\treturn type != OBJ_COMMIT && type != OBJ_TREE &&\n+\t\ttype != OBJ_BLOB && type != OBJ_TAG;\n+}\n+\n static enum input_source istream_source(const unsigned char *sha1,\n \t\t\t\t\tenum object_type *type,\n \t\t\t\t\tstruct object_info *oi)\n@@ -121,7 +127,8 @@ static enum input_source istream_source(const unsigned char *sha1,\n \tcase OI_LOOSE:\n \t\treturn loose;\n \tcase OI_PACKED:\n-\t\tif (!oi->u.packed.is_delta && big_file_threshold < size)\n+\t\tif (is_canonical(oi->u.packed.real_type) &&\n+\t\t    big_file_threshold < size)\n \t\t\treturn pack_non_delta;\n \t\t/* fallthru */\n \tdefault:\n-- \n1.8.2.83.gc99314b\n"},{"id":"228648","messageId":"1381329976-32082-3-git-send-email-pclouds@gmail.com","threadId":"35091","inReplyTo":"1381329976-32082-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 2/9] pack v4: move v2 tree entry generation code out of decode_entries","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-09T14:46:09Z","receivedAt":"2013-10-09T14:46:09Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n packv4-parse.c | 41 ++++++++++++++++++++++++++---------------\n 1 file changed, 26 insertions(+), 15 deletions(-)\n\ndiff --git a/packv4-parse.c b/packv4-parse.c\nindex 31c89c7..7b096cb 100644\n--- a/packv4-parse.c\n+++ b/packv4-parse.c\n@@ -443,6 +443,31 @@ static int tree_entry_prefix(unsigned char *buf, unsigned long size,\n \treturn len;\n }\n \n+static int generate_tree_entry(struct packed_git *p,\n+\t\t\t       const unsigned char **bufp,\n+\t\t\t       unsigned char **dstp, unsigned long *sizep,\n+\t\t\t       int what)\n+{\n+\tconst unsigned char *path, *sha1;\n+\tunsigned mode;\n+\tint len, pathlen;\n+\n+\tpath = get_pathref(p, what >> 1, &pathlen);\n+\tsha1 = get_sha1ref(p, bufp);\n+\tif (!path || !sha1)\n+\t\treturn -1;\n+\tmode = (path[0] << 8) | path[1];\n+\tlen = tree_entry_prefix(*dstp, *sizep,\n+\t\t\t\tpath + 2, pathlen - 2, mode);\n+\tif (!len || len + 20 > *sizep)\n+\t\treturn -1;\n+\thashcpy(*dstp + len, sha1);\n+\tlen += 20;\n+\t*dstp += len;\n+\t*sizep -= len;\n+\treturn 0;\n+}\n+\n static int decode_entries(struct packed_git *p, struct pack_window **w_curs,\n \t\t\t  off_t obj_offset, unsigned int start, unsigned int count,\n \t\t\t  unsigned char **dstp, unsigned long *sizep)\n@@ -543,22 +568,8 @@ static int decode_entries(struct packed_git *p, struct pack_window **w_curs,\n \t\t\t/*\n \t\t\t * This is an actual tree entry to recreate.\n \t\t\t */\n-\t\t\tconst unsigned char *path, *sha1;\n-\t\t\tunsigned mode;\n-\t\t\tint len, pathlen;\n-\n-\t\t\tpath = get_pathref(p, what >> 1, &pathlen);\n-\t\t\tsha1 = get_sha1ref(p, &scp);\n-\t\t\tif (!path || !sha1)\n-\t\t\t\treturn -1;\n-\t\t\tmode = (path[0] << 8) | path[1];\n-\t\t\tlen = tree_entry_prefix(*dstp, *sizep,\n-\t\t\t\t\t\tpath + 2, pathlen - 2, mode);\n-\t\t\tif (!len || len + 20 > *sizep)\n+\t\t\tif (generate_tree_entry(p, &scp, dstp, sizep, what))\n \t\t\t\treturn -1;\n-\t\t\thashcpy(*dstp + len, sha1);\n-\t\t\t*dstp += len + 20;\n-\t\t\t*sizep -= len + 20;\n \t\t\tcount--;\n \t\t\tcurpos++;\n \t\t} else if (what & 1) {\n-- \n1.8.2.83.gc99314b\n"},{"id":"228649","messageId":"1381329976-32082-4-git-send-email-pclouds@gmail.com","threadId":"35091","inReplyTo":"1381329976-32082-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 3/9] pv4_tree_desc: introduce new struct for pack v4 tree walker","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-09T14:46:10Z","receivedAt":"2013-10-09T14:46:10Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This struct is intended to be the successor of struct tree_desc. For\nnow it only holds a buffer for converting pv4 tree to canonical format.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n packv4-parse.c | 73 ++++++++++++++++++++++++++++------------------------------\n packv4-parse.h |  9 ++++++++\n 2 files changed, 44 insertions(+), 38 deletions(-)\n\ndiff --git a/packv4-parse.c b/packv4-parse.c\nindex 7b096cb..f9db364 100644\n--- a/packv4-parse.c\n+++ b/packv4-parse.c\n@@ -344,9 +344,8 @@ void *pv4_get_commit(struct packed_git *p, struct pack_window **w_curs,\n \treturn dst;\n }\n \n-static int copy_canonical_tree_entries(struct packed_git *p, off_t offset,\n-\t\t\t\t       unsigned int start, unsigned int count,\n-\t\t\t\t       unsigned char **dstp, unsigned long *sizep)\n+static int copy_canonical_tree_entries(struct pv4_tree_desc *v4, off_t offset,\n+\t\t\t\t       unsigned int start, unsigned int count)\n {\n \tvoid *data;\n \tconst unsigned char *from, *end;\n@@ -354,7 +353,7 @@ static int copy_canonical_tree_entries(struct packed_git *p, off_t offset,\n \tunsigned long size;\n \tstruct tree_desc desc;\n \n-\tdata = unpack_entry(p, offset, &type, &size);\n+\tdata = unpack_entry(v4->p, offset, &type, &size);\n \tif (!data)\n \t\treturn -1;\n \tif (type != OBJ_TREE) {\n@@ -372,13 +371,11 @@ static int copy_canonical_tree_entries(struct packed_git *p, off_t offset,\n \t\tupdate_tree_entry(&desc);\n \tend = desc.buffer;\n \n-\tif (end - from > *sizep) {\n+\tif (end - from > strbuf_avail(&v4->buf)) {\n \t\tfree(data);\n \t\treturn -1;\n \t}\n-\tmemcpy(*dstp, from, end - from);\n-\t*dstp += end - from;\n-\t*sizep -= end - from;\n+\tstrbuf_add(&v4->buf, from, end - from);\n \tfree(data);\n \treturn 0;\n }\n@@ -417,7 +414,7 @@ static struct pv4_tree_cache *get_tree_offset_cache(struct packed_git *p, off_t\n \treturn c;\n }\n \n-static int tree_entry_prefix(unsigned char *buf, unsigned long size,\n+static int tree_entry_prefix(char *buf, unsigned long size,\n \t\t\t     const unsigned char *path, int path_len,\n \t\t\t     unsigned mode)\n {\n@@ -443,35 +440,33 @@ static int tree_entry_prefix(unsigned char *buf, unsigned long size,\n \treturn len;\n }\n \n-static int generate_tree_entry(struct packed_git *p,\n+static int generate_tree_entry(struct pv4_tree_desc *desc,\n \t\t\t       const unsigned char **bufp,\n-\t\t\t       unsigned char **dstp, unsigned long *sizep,\n \t\t\t       int what)\n {\n \tconst unsigned char *path, *sha1;\n+\tchar *buf = desc->buf.buf + desc->buf.len;\n \tunsigned mode;\n \tint len, pathlen;\n \n-\tpath = get_pathref(p, what >> 1, &pathlen);\n-\tsha1 = get_sha1ref(p, bufp);\n+\tpath = get_pathref(desc->p, what >> 1, &pathlen);\n+\tsha1 = get_sha1ref(desc->p, bufp);\n \tif (!path || !sha1)\n \t\treturn -1;\n \tmode = (path[0] << 8) | path[1];\n-\tlen = tree_entry_prefix(*dstp, *sizep,\n+\tlen = tree_entry_prefix(buf, strbuf_avail(&desc->buf),\n \t\t\t\tpath + 2, pathlen - 2, mode);\n-\tif (!len || len + 20 > *sizep)\n+\tif (!len || len + 20 > strbuf_avail(&desc->buf))\n \t\treturn -1;\n-\thashcpy(*dstp + len, sha1);\n-\tlen += 20;\n-\t*dstp += len;\n-\t*sizep -= len;\n+\tmemcpy(buf + len, sha1, 20);\n+\tdesc->buf.len += len + 20;\n \treturn 0;\n }\n \n-static int decode_entries(struct packed_git *p, struct pack_window **w_curs,\n-\t\t\t  off_t obj_offset, unsigned int start, unsigned int count,\n-\t\t\t  unsigned char **dstp, unsigned long *sizep)\n+static int decode_entries(struct pv4_tree_desc *desc, off_t obj_offset,\n+\t\t\t  unsigned int start, unsigned int count)\n {\n+\tstruct packed_git *p = desc->p;\n \tunsigned long avail;\n \tconst unsigned char *src, *scp;\n \tunsigned int curpos;\n@@ -490,7 +485,7 @@ static int decode_entries(struct packed_git *p, struct pack_window **w_curs,\n \t} else {\n \t\tunsigned int nb_entries;\n \n-\t\tsrc = use_pack(p, w_curs, obj_offset, &avail);\n+\t\tsrc = use_pack(p, &desc->w_curs, obj_offset, &avail);\n \t\tscp = src;\n \n \t\t/* we need to skip over the object header */\n@@ -502,9 +497,8 @@ static int decode_entries(struct packed_git *p, struct pack_window **w_curs,\n \t\t/* is this a canonical tree object? */\n \t\tcase OBJ_TREE:\n \t\tcase OBJ_REF_DELTA:\n-\t\t\treturn copy_canonical_tree_entries(p, obj_offset,\n-\t\t\t\t\t\t\t   start, count,\n-\t\t\t\t\t\t\t   dstp, sizep);\n+\t\t\treturn copy_canonical_tree_entries(desc, obj_offset,\n+\t\t\t\t\t\t\t   start, count);\n \t\t/* let's still make sure this is actually a pv4 tree */\n \t\tcase OBJ_PV4_TREE:\n \t\t\tbreak;\n@@ -542,7 +536,7 @@ static int decode_entries(struct packed_git *p, struct pack_window **w_curs,\n \t\tunsigned int what;\n \n \t\tif (avail < 20) {\n-\t\t\tsrc = use_pack(p, w_curs, offset, &avail);\n+\t\t\tsrc = use_pack(p, &desc->w_curs, offset, &avail);\n \t\t\tif (avail < 20)\n \t\t\t\treturn -1;\n \t\t}\n@@ -568,7 +562,7 @@ static int decode_entries(struct packed_git *p, struct pack_window **w_curs,\n \t\t\t/*\n \t\t\t * This is an actual tree entry to recreate.\n \t\t\t */\n-\t\t\tif (generate_tree_entry(p, &scp, dstp, sizep, what))\n+\t\t\tif (generate_tree_entry(desc, &scp, what))\n \t\t\t\treturn -1;\n \t\t\tcount--;\n \t\t\tcurpos++;\n@@ -638,9 +632,8 @@ static int decode_entries(struct packed_git *p, struct pack_window **w_curs,\n \t\t\t\t\tstart = 0;\n \t\t\t\t}\n \n-\t\t\t\tret = decode_entries(p, w_curs, copy_objoffset,\n-\t\t\t\t\t\t     copy_start, copy_count,\n-\t\t\t\t\t\t     dstp, sizep);\n+\t\t\t\tret = decode_entries(desc, copy_objoffset,\n+\t\t\t\t\t\t     copy_start, copy_count);\n \t\t\t\tif (ret)\n \t\t\t\t\treturn ret;\n \n@@ -672,17 +665,21 @@ static int decode_entries(struct packed_git *p, struct pack_window **w_curs,\n void *pv4_get_tree(struct packed_git *p, struct pack_window **w_curs,\n \t\t   off_t obj_offset, unsigned long size)\n {\n-\tunsigned char *dst, *dcp;\n+\tstruct pv4_tree_desc desc;\n \tint ret;\n \n-\tdst = xmallocz(size);\n-\tdcp = dst;\n-\tret = decode_entries(p, w_curs, obj_offset, 0, 0, &dcp, &size);\n-\tif (ret < 0 || size != 0) {\n-\t\tfree(dst);\n+\tmemset(&desc, 0, sizeof(desc));\n+\tdesc.p = p;\n+\tdesc.w_curs = *w_curs;\n+\tstrbuf_init(&desc.buf, size);\n+\n+\tret = decode_entries(&desc, obj_offset, 0, 0);\n+\t*w_curs = desc.w_curs;\n+\tif (ret < 0 || desc.buf.len != size) {\n+\t\tstrbuf_release(&desc.buf);\n \t\treturn NULL;\n \t}\n-\treturn dst;\n+\treturn strbuf_detach(&desc.buf, NULL);\n }\n \n unsigned long pv4_unpack_object_header_buffer(const unsigned char *base,\ndiff --git a/packv4-parse.h b/packv4-parse.h\nindex b437159..cad7a82 100644\n--- a/packv4-parse.h\n+++ b/packv4-parse.h\n@@ -22,4 +22,13 @@ void *pv4_get_commit(struct packed_git *p, struct pack_window **w_curs,\n void *pv4_get_tree(struct packed_git *p, struct pack_window **w_curs,\n \t\t   off_t obj_offset, unsigned long size);\n \n+struct pv4_tree_desc {\n+\t/* v4 entry */\n+\tstruct packed_git *p;\n+\tstruct pack_window *w_curs;\n+\n+\t/* full canonical tree */\n+\tstruct strbuf buf;\n+};\n+\n #endif\n-- \n1.8.2.83.gc99314b\n"},{"id":"228650","messageId":"1381329976-32082-5-git-send-email-pclouds@gmail.com","threadId":"35091","inReplyTo":"1381329976-32082-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 4/9] pv4_tree_desc: use struct tree_desc from pv4_tree_desc","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-09T14:46:11Z","receivedAt":"2013-10-09T14:46:11Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n packv4-parse.c | 13 ++++++-------\n packv4-parse.h |  5 +++++\n 2 files changed, 11 insertions(+), 7 deletions(-)\n\ndiff --git a/packv4-parse.c b/packv4-parse.c\nindex f9db364..f5c486e 100644\n--- a/packv4-parse.c\n+++ b/packv4-parse.c\n@@ -10,7 +10,6 @@\n \n #include \"cache.h\"\n #include \"packv4-parse.h\"\n-#include \"tree-walk.h\"\n #include \"varint.h\"\n \n const unsigned char *get_sha1ref(struct packed_git *p,\n@@ -351,7 +350,7 @@ static int copy_canonical_tree_entries(struct pv4_tree_desc *v4, off_t offset,\n \tconst unsigned char *from, *end;\n \tenum object_type type;\n \tunsigned long size;\n-\tstruct tree_desc desc;\n+\tstruct tree_desc *desc = &v4->v2;\n \n \tdata = unpack_entry(v4->p, offset, &type, &size);\n \tif (!data)\n@@ -361,15 +360,15 @@ static int copy_canonical_tree_entries(struct pv4_tree_desc *v4, off_t offset,\n \t\treturn -1;\n \t}\n \n-\tinit_tree_desc(&desc, data, size);\n+\tinit_tree_desc(desc, data, size);\n \n \twhile (start--)\n-\t\tupdate_tree_entry(&desc);\n+\t\tupdate_tree_entry(desc);\n \n-\tfrom = desc.buffer;\n+\tfrom = desc->buffer;\n \twhile (count--)\n-\t\tupdate_tree_entry(&desc);\n-\tend = desc.buffer;\n+\t\tupdate_tree_entry(desc);\n+\tend = desc->buffer;\n \n \tif (end - from > strbuf_avail(&v4->buf)) {\n \t\tfree(data);\ndiff --git a/packv4-parse.h b/packv4-parse.h\nindex cad7a82..04b9a59 100644\n--- a/packv4-parse.h\n+++ b/packv4-parse.h\n@@ -1,6 +1,8 @@\n #ifndef PACKV4_PARSE_H\n #define PACKV4_PARSE_H\n \n+#include \"tree-walk.h\"\n+\n struct packv4_dict {\n \tconst unsigned char *data;\n \tunsigned int nb_entries;\n@@ -27,6 +29,9 @@ struct pv4_tree_desc {\n \tstruct packed_git *p;\n \tstruct pack_window *w_curs;\n \n+\t/* v2 entry */\n+\tstruct tree_desc v2;\n+\n \t/* full canonical tree */\n \tstruct strbuf buf;\n };\n-- \n1.8.2.83.gc99314b\n"},{"id":"228651","messageId":"1381329976-32082-6-git-send-email-pclouds@gmail.com","threadId":"35091","inReplyTo":"1381329976-32082-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 5/9] pv4_tree_desc: allow decode_entries to return v4 trees, one at a time","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-09T14:46:12Z","receivedAt":"2013-10-09T14:46:12Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"When PV4_TREE_CANONICAL is passed, decode_entries() generates <count>\ntree entries in canonical format. When this flag is not passed _and_\ncount is 1, decode_entries fills struct name_entry and saves\nsha1_index.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n packv4-parse.c | 44 ++++++++++++++++++++++++++++++++++++++++++--\n packv4-parse.h | 10 ++++++++++\n 2 files changed, 52 insertions(+), 2 deletions(-)\n\ndiff --git a/packv4-parse.c b/packv4-parse.c\nindex f5c486e..f222456 100644\n--- a/packv4-parse.c\n+++ b/packv4-parse.c\n@@ -365,6 +365,12 @@ static int copy_canonical_tree_entries(struct pv4_tree_desc *v4, off_t offset,\n \twhile (start--)\n \t\tupdate_tree_entry(desc);\n \n+\tif (!(v4->flags & PV4_TREE_CANONICAL)) {\n+\t\tv4->sha1_index = 0;\n+\t\tv4->pathlen = tree_entry_len(&desc->entry);\n+\t\treturn 0;\n+\t}\n+\n \tfrom = desc->buffer;\n \twhile (count--)\n \t\tupdate_tree_entry(desc);\n@@ -462,6 +468,33 @@ static int generate_tree_entry(struct pv4_tree_desc *desc,\n \treturn 0;\n }\n \n+static int get_tree_entry_v4(struct pv4_tree_desc *desc,\n+\t\t\t     const unsigned char **bufp,\n+\t\t\t     int what)\n+{\n+\tconst unsigned char *path;\n+\n+\tpath = get_pathref(desc->p, what >> 1, &desc->pathlen);\n+\tif (!path)\n+\t\treturn -1;\n+\tdesc->v2.entry.mode = (path[0] << 8) | path[1];\n+\tdesc->v2.entry.path = (const char *)path + 2;\n+\n+\tif (**bufp) {\n+\t\tdesc->sha1_index = decode_varint(bufp);\n+\t\tif (desc->sha1_index < 1 ||\n+\t\t    desc->sha1_index - 1 > desc->p->num_objects)\n+\t\t\treturn error(\"bad index in get_sha1ref\");\n+\t\tdesc->v2.entry.sha1 = desc->p->sha1_table + (desc->sha1_index - 1) * 20;\n+\t} else {\n+\t\tdesc->sha1_index = 0;\n+\t\tdesc->v2.entry.sha1 = *bufp + 1;\n+\t\t*bufp += 21;\n+\t}\n+\n+\treturn 0;\n+}\n+\n static int decode_entries(struct pv4_tree_desc *desc, off_t obj_offset,\n \t\t\t  unsigned int start, unsigned int count)\n {\n@@ -561,8 +594,14 @@ static int decode_entries(struct pv4_tree_desc *desc, off_t obj_offset,\n \t\t\t/*\n \t\t\t * This is an actual tree entry to recreate.\n \t\t\t */\n-\t\t\tif (generate_tree_entry(desc, &scp, what))\n-\t\t\t\treturn -1;\n+\t\t\tif (desc->flags & PV4_TREE_CANONICAL) {\n+\t\t\t\tif (generate_tree_entry(desc, &scp, what))\n+\t\t\t\t\treturn -1;\n+\t\t\t} else if (count == 1) {\n+\t\t\t\tif (get_tree_entry_v4(desc, &scp, what))\n+\t\t\t\t\treturn -1;\n+\t\t\t} else\n+\t\t\t\tdie(\"generating multiple v4 entries is not supported\");\n \t\t\tcount--;\n \t\t\tcurpos++;\n \t\t} else if (what & 1) {\n@@ -668,6 +707,7 @@ void *pv4_get_tree(struct packed_git *p, struct pack_window **w_curs,\n \tint ret;\n \n \tmemset(&desc, 0, sizeof(desc));\n+\tdesc.flags = PV4_TREE_CANONICAL;\n \tdesc.p = p;\n \tdesc.w_curs = *w_curs;\n \tstrbuf_init(&desc.buf, size);\ndiff --git a/packv4-parse.h b/packv4-parse.h\nindex 04b9a59..fe0ea38 100644\n--- a/packv4-parse.h\n+++ b/packv4-parse.h\n@@ -24,10 +24,20 @@ void *pv4_get_commit(struct packed_git *p, struct pack_window **w_curs,\n void *pv4_get_tree(struct packed_git *p, struct pack_window **w_curs,\n \t\t   off_t obj_offset, unsigned long size);\n \n+/*\n+ * These are private flags, never pass them directly to\n+ * pv4_tree_desc_*\n+ */\n+#define PV4_TREE_CANONICAL   0x800\n+\n struct pv4_tree_desc {\n+\tunsigned flags;\n+\n \t/* v4 entry */\n \tstruct packed_git *p;\n \tstruct pack_window *w_curs;\n+\tunsigned int sha1_index;\n+\tint pathlen;\n \n \t/* v2 entry */\n \tstruct tree_desc v2;\n-- \n1.8.2.83.gc99314b\n"},{"id":"228652","messageId":"1381329976-32082-7-git-send-email-pclouds@gmail.com","threadId":"35091","inReplyTo":"1381329976-32082-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 6/9] pv4_tree_desc: complete interface","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-09T14:46:13Z","receivedAt":"2013-10-09T14:46:13Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"Best \"explained\" with an example\n\n  void walk(const unsigned char *sha1)\n  {\n    struct pv4_tree_desc desc;\n    /*\n     * Start pv4_tree_desc from an SHA-1. If it's a v4 tree, v4 walker\n     * will be used. Otherwise v2 is walked.\n     */\n    pv4_tree_desc_from_sha1(&desc, sha1, 0);\n    recurse(&desc);\n    pv4_release_tree_desc(&desc);\n  }\n\n  void recurse(struct pv4_tree_desc *desc)\n  {\n    /*\n     * Then you can go over entries, one by one, similar to the\n     * current tree walker. Current entry is in desc->v2.entry.\n     * Pathlen in desc->pathlen. Do not use tree_entry_len() because\n     * that one is only correct for v2 entries\n     */\n    while (pv4_get_entry(desc)) {\n      printf(\"%s %s\\n\", sha1_to_hex(desc->v2.entry.sha1),\n             desc->v2.entry.path);\n\n      /*\n       * Once you have an initialized pv4_tree_desc you may skip the\n       * SHA-1 lookup step if the next tree is in the same pack.\n       */\n      if (S_ISDIR(desc->v2.entry.mode)) {\n        struct pv4_tree_desc new_desc;\n        pv4_tree_desc_from_entry(&new_desc, desc);\n        recurse(&new_desc);\n\n        /* Finally release everything */\n        pv4_release_tree_desc(&new_desc);\n      }\n    }\n  }\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n packv4-parse.c | 80 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n packv4-parse.h | 12 +++++++++\n 2 files changed, 92 insertions(+)\n\ndiff --git a/packv4-parse.c b/packv4-parse.c\nindex f222456..7d257af 100644\n--- a/packv4-parse.c\n+++ b/packv4-parse.c\n@@ -732,3 +732,83 @@ unsigned long pv4_unpack_object_header_buffer(const unsigned char *base,\n \t*sizep = val >> 4;\n \treturn cp - base;\n }\n+\n+int pv4_tree_desc_from_sha1(struct pv4_tree_desc *desc,\n+\t\t\t    const unsigned char *sha1,\n+\t\t\t    unsigned flags)\n+{\n+\tunsigned long size;\n+\tenum object_type type;\n+\tvoid *data;\n+\tstruct object_info oi;\n+\n+\tassert(!(flags & ~0xff) &&\n+\t       \"you are not supposed to set these from outside!\");\n+\n+\tmemset(desc, 0, sizeof(*desc));\n+\tstrbuf_init(&desc->buf, 0);\n+\n+\tmemset(&oi, 0, sizeof(oi));\n+\tif (!sha1_object_info_extended(sha1, &oi) &&\n+\t    oi.whence == OI_PACKED &&\n+\t    oi.u.packed.real_type == OBJ_PV4_TREE &&\n+\t    oi.u.packed.pack->version >= 4) {\n+\t\tdesc->p = oi.u.packed.pack;\n+\t\tdesc->obj_offset = oi.u.packed.offset;\n+\t\tdesc->flags = flags;\n+\t\treturn 0;\n+\t}\n+\n+\tdata = read_sha1_file(sha1, &type, &size);\n+\tif (!data || type != OBJ_TREE) {\n+\t\tfree(data);\n+\t\treturn -1;\n+\t}\n+\tdesc->flags = flags;\n+\tdesc->flags |= PV4_TREE_CANONICAL;\n+\tinit_tree_desc(&desc->v2, data, size);\n+\t/*\n+\t * we can attach to strbuf because read_sha1_file always\n+\t * appends NUL at the end\n+\t */\n+\tstrbuf_attach(&desc->buf, data, size, size + 1);\n+\treturn 0;\n+}\n+\n+int pv4_tree_desc_from_entry(struct pv4_tree_desc *desc,\n+\t\t\t     const struct pv4_tree_desc *src,\n+\t\t\t     unsigned flags)\n+{\n+\tif (!src->sha1_index)\n+\t\treturn pv4_tree_desc_from_sha1(desc,\n+\t\t\t\t\t       src->v2.entry.sha1,\n+\t\t\t\t\t       flags);\n+\tassert(!(flags & ~0xff) &&\n+\t       \"you are not supposed to set these from outside!\");\n+\tmemset(desc, 0, sizeof(*desc));\n+\tstrbuf_init(&desc->buf, 0);\n+\tdesc->p = src->p;\n+\tdesc->obj_offset =\n+\t\tnth_packed_object_offset(desc->p, src->sha1_index - 1);\n+\tdesc->flags = flags;\n+\treturn 0;\n+}\n+\n+void pv4_release_tree_desc(struct pv4_tree_desc *desc)\n+{\n+\tstrbuf_release(&desc->buf);\n+\tunuse_pack(&desc->w_curs);\n+}\n+\n+int pv4_tree_entry(struct pv4_tree_desc *desc)\n+{\n+\tif (desc->flags & PV4_TREE_CANONICAL) {\n+\t\tif (!desc->v2.size)\n+\t\t\treturn 0;\n+\t\tif (desc->start)\n+\t\t\tupdate_tree_entry(&desc->v2);\n+\t\tdesc->start++;\n+\t\treturn 1;\n+\t}\n+\treturn !decode_entries(desc, desc->obj_offset, desc->start++, 1);\n+}\ndiff --git a/packv4-parse.h b/packv4-parse.h\nindex fe0ea38..874f57c 100644\n--- a/packv4-parse.h\n+++ b/packv4-parse.h\n@@ -36,6 +36,8 @@ struct pv4_tree_desc {\n \t/* v4 entry */\n \tstruct packed_git *p;\n \tstruct pack_window *w_curs;\n+\toff_t obj_offset;\n+\tunsigned start;\n \tunsigned int sha1_index;\n \tint pathlen;\n \n@@ -46,4 +48,14 @@ struct pv4_tree_desc {\n \tstruct strbuf buf;\n };\n \n+int pv4_tree_desc_from_sha1(struct pv4_tree_desc *desc,\n+\t\t\t    const unsigned char *sha1,\n+\t\t\t    unsigned flags);\n+int pv4_tree_desc_from_entry(struct pv4_tree_desc *desc,\n+\t\t\t     const struct pv4_tree_desc *src,\n+\t\t\t     unsigned flags);\n+void pv4_release_tree_desc(struct pv4_tree_desc *desc);\n+\n+int pv4_tree_entry(struct pv4_tree_desc *desc);\n+\n #endif\n-- \n1.8.2.83.gc99314b\n"},{"id":"228654","messageId":"1381329976-32082-8-git-send-email-pclouds@gmail.com","threadId":"35091","inReplyTo":"1381329976-32082-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 7/9] pv4_tree_desc: don't bother looking for v4 trees if no v4 packs are present","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-09T14:46:14Z","receivedAt":"2013-10-09T14:46:14Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This is mostly to avoid overhead on v2 only systems.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n packv4-parse.c | 5 ++++-\n sha1_file.c    | 5 +++++\n 2 files changed, 9 insertions(+), 1 deletion(-)\n\ndiff --git a/packv4-parse.c b/packv4-parse.c\nindex 7d257af..4354ee3 100644\n--- a/packv4-parse.c\n+++ b/packv4-parse.c\n@@ -12,6 +12,8 @@\n #include \"packv4-parse.h\"\n #include \"varint.h\"\n \n+int packv4_available;\n+\n const unsigned char *get_sha1ref(struct packed_git *p,\n \t\t\t\t const unsigned char **bufp)\n {\n@@ -749,7 +751,8 @@ int pv4_tree_desc_from_sha1(struct pv4_tree_desc *desc,\n \tstrbuf_init(&desc->buf, 0);\n \n \tmemset(&oi, 0, sizeof(oi));\n-\tif (!sha1_object_info_extended(sha1, &oi) &&\n+\tif (packv4_available &&\n+\t    !sha1_object_info_extended(sha1, &oi) &&\n \t    oi.whence == OI_PACKED &&\n \t    oi.u.packed.real_type == OBJ_PV4_TREE &&\n \t    oi.u.packed.pack->version >= 4) {\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 5848008..4744132 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -40,6 +40,7 @@ const unsigned char null_sha1[20];\n \n static const char *no_log_pack_access = \"no_log_pack_access\";\n static const char *log_pack_access;\n+extern int packv4_available;\n \n /*\n  * This is meant to hold a *small* number of objects that you would\n@@ -763,6 +764,8 @@ void free_pack_by_name(const char *pack_name)\n \t\t\t\tclose(p->pack_fd);\n \t\t\t\tpack_open_fds--;\n \t\t\t}\n+\t\t\tif (p->version >= 4)\n+\t\t\t\tpackv4_available--;\n \t\t\tclose_pack_index(p);\n \t\t\tfree(p->bad_object_sha1);\n \t\t\tpv4_free_dict(p->ident_dict);\n@@ -856,6 +859,8 @@ static int open_packed_git_1(struct packed_git *p)\n \t\t\t\" supported (try upgrading GIT to a newer version)\",\n \t\t\tp->pack_name, ntohl(hdr.hdr_version));\n \tp->version = ntohl(hdr.hdr_version);\n+\tif (p->version >= 4)\n+\t\tpackv4_available++;\n \n \t/* Verify the pack matches its index. */\n \tif (p->num_objects != ntohl(hdr.hdr_entries))\n-- \n1.8.2.83.gc99314b\n"},{"id":"228655","messageId":"1381329976-32082-9-git-send-email-pclouds@gmail.com","threadId":"35091","inReplyTo":"1381329976-32082-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 8/9] pv4_tree_desc: avoid lookup_object() when possible","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-09T14:46:15Z","receivedAt":"2013-10-09T14:46:15Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"pv4_tree_desc_from_entry() cuts out SHA-1 index lookups when\npossible. This patch provides a new set of lookup functions that avoid\nlooking up object hash table.\n\nWe maintain an object pointer array and use SHA-1 table as\nkey. Because we know index in SHA-1 table in v4 trees, we can skip\nbinary search and go straight to the object.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n cache.h        |  1 +\n packv4-parse.c | 33 +++++++++++++++++++++++++++++++++\n packv4-parse.h | 12 ++++++++++++\n sha1_file.c    |  1 +\n 4 files changed, 47 insertions(+)\n\ndiff --git a/cache.h b/cache.h\nindex 5028ded..da65063 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -1035,6 +1035,7 @@ extern struct packed_git {\n \tstruct packv4_dict *ident_dict;\n \toff_t ident_dict_end;\n \tstruct packv4_dict *path_dict;\n+\tstruct object **objs;\n \ttime_t mtime;\n \tint pack_fd;\n \tunsigned pack_local:1,\ndiff --git a/packv4-parse.c b/packv4-parse.c\nindex 4354ee3..6f6152c 100644\n--- a/packv4-parse.c\n+++ b/packv4-parse.c\n@@ -11,6 +11,10 @@\n #include \"cache.h\"\n #include \"packv4-parse.h\"\n #include \"varint.h\"\n+#include \"commit.h\"\n+#include \"tree.h\"\n+#include \"blob.h\"\n+#include \"tag.h\"\n \n int packv4_available;\n \n@@ -815,3 +819,32 @@ int pv4_tree_entry(struct pv4_tree_desc *desc)\n \t}\n \treturn !decode_entries(desc, desc->obj_offset, desc->start++, 1);\n }\n+\n+static struct object **get_packed_objs(struct pv4_tree_desc *desc)\n+{\n+\tif (!desc->p || !desc->sha1_index)\n+\t\treturn NULL;\n+\tif (desc->p->version >= 4 && !desc->p->objs)\n+\t\tdesc->p->objs =\n+\t\t\txmalloc(sizeof(struct object *) * desc->p->num_objects);\n+\treturn desc->p->objs;\n+}\n+\n+#define DEFINE_LOOKUP(TYPE)\t\t\t\t\t\\\n+struct TYPE *pv4_lookup_##TYPE(struct pv4_tree_desc *desc)\t\\\n+{\t\t\t\t\t\t\t\t\\\n+\tstruct object **objs = get_packed_objs(desc);\t\t\\\n+\tif (!objs)\t\t\t\t\t\t\\\n+\t\treturn lookup_##TYPE(desc->v2.entry.sha1);\t\\\n+\tobjs += desc->sha1_index - 1;\t\t\t\t\\\n+\tif (!*objs)\t\t\t\t\t\t\\\n+\t\t*objs = (struct object *)\t\t\t\\\n+\t\t\tlookup_##TYPE(desc->v2.entry.sha1);\t\\\n+\treturn (struct TYPE *)objs[0];\t\t\t\t\\\n+}\n+\n+DEFINE_LOOKUP(object)\n+DEFINE_LOOKUP(commit)\n+DEFINE_LOOKUP(tree)\n+DEFINE_LOOKUP(blob)\n+DEFINE_LOOKUP(tag)\ndiff --git a/packv4-parse.h b/packv4-parse.h\nindex 874f57c..3bf69bc 100644\n--- a/packv4-parse.h\n+++ b/packv4-parse.h\n@@ -3,6 +3,12 @@\n \n #include \"tree-walk.h\"\n \n+struct object;\n+struct commit;\n+struct tree;\n+struct blob;\n+struct tag;\n+\n struct packv4_dict {\n \tconst unsigned char *data;\n \tunsigned int nb_entries;\n@@ -58,4 +64,10 @@ void pv4_release_tree_desc(struct pv4_tree_desc *desc);\n \n int pv4_tree_entry(struct pv4_tree_desc *desc);\n \n+struct object *pv4_lookup_object(struct pv4_tree_desc *desc);\n+struct commit *pv4_lookup_commit(struct pv4_tree_desc *desc);\n+struct tree   *pv4_lookup_tree(struct pv4_tree_desc *desc);\n+struct blob   *pv4_lookup_blob(struct pv4_tree_desc *desc);\n+struct tag    *pv4_lookup_tag(struct pv4_tree_desc *desc);\n+\n #endif\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 4744132..88a6273 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -773,6 +773,7 @@ void free_pack_by_name(const char *pack_name)\n \t\t\t*pp = p->next;\n \t\t\tif (last_found_pack == p)\n \t\t\t\tlast_found_pack = NULL;\n+\t\t\tfree(p->objs);\n \t\t\tfree(p);\n \t\t\treturn;\n \t\t}\n-- \n1.8.2.83.gc99314b\n"},{"id":"228653","messageId":"1381329976-32082-10-git-send-email-pclouds@gmail.com","threadId":"35091","inReplyTo":"1381329976-32082-1-git-send-email-pclouds@gmail.com","subject":"[PATCH 9/9] list-object.c: take \"advantage\" of new pv4_tree_desc interface","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-09T14:46:16Z","receivedAt":"2013-10-09T14:46:16Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\n---\n list-objects.c | 38 ++++++++++++++++++++++----------------\n 1 file changed, 22 insertions(+), 16 deletions(-)\n\ndiff --git a/list-objects.c b/list-objects.c\nindex 6def897..39ad3e6 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -7,6 +7,7 @@\n #include \"tree-walk.h\"\n #include \"revision.h\"\n #include \"list-objects.h\"\n+#include \"packv4-parse.h\"\n \n static void process_blob(struct rev_info *revs,\n \t\t\t struct blob *blob,\n@@ -60,6 +61,7 @@ static void process_gitlink(struct rev_info *revs,\n }\n \n static void process_tree(struct rev_info *revs,\n+\t\t\t struct pv4_tree_desc *desc,\n \t\t\t struct tree *tree,\n \t\t\t show_tree_entry_fn show_tree_entry,\n \t\t\t show_object_fn show,\n@@ -69,8 +71,6 @@ static void process_tree(struct rev_info *revs,\n \t\t\t void *cb_data)\n {\n \tstruct object *obj = &tree->object;\n-\tstruct tree_desc desc;\n-\tstruct name_entry entry;\n \tstruct name_path me;\n \tenum interesting match = revs->diffopt.pathspec.nr == 0 ?\n \t\tall_entries_interesting: entry_not_interesting;\n@@ -96,11 +96,10 @@ static void process_tree(struct rev_info *revs,\n \t\t\tstrbuf_addch(base, '/');\n \t}\n \n-\tinit_tree_desc(&desc, tree->buffer, tree->size);\n-\n-\twhile (tree_entry(&desc, &entry)) {\n+\twhile (pv4_tree_entry(desc)) {\n+\t\tstruct name_entry *entry = &desc->v2.entry;\n \t\tif (match != all_entries_interesting) {\n-\t\t\tmatch = tree_entry_interesting(&entry, base, 0,\n+\t\t\tmatch = tree_entry_interesting(entry, base, 0,\n \t\t\t\t\t\t       &revs->diffopt.pathspec);\n \t\t\tif (match == all_entries_not_interesting)\n \t\t\t\tbreak;\n@@ -109,22 +108,26 @@ static void process_tree(struct rev_info *revs,\n \t\t}\n \n \t\tif (show_tree_entry)\n-\t\t\tshow_tree_entry(&entry, cb_data);\n+\t\t\tshow_tree_entry(entry, cb_data);\n \n-\t\tif (S_ISDIR(entry.mode))\n+\t\tif (S_ISDIR(entry->mode)) {\n+\t\t\tstruct pv4_tree_desc sub_desc;\n+\t\t\tpv4_tree_desc_from_entry(&sub_desc, desc, 0);\n \t\t\tprocess_tree(revs,\n-\t\t\t\t     lookup_tree(entry.sha1),\n+\t\t\t\t     &sub_desc,\n+\t\t\t\t     pv4_lookup_tree(desc),\n \t\t\t\t     show_tree_entry,\n-\t\t\t\t     show, &me, base, entry.path,\n+\t\t\t\t     show, &me, base, entry->path,\n \t\t\t\t     cb_data);\n-\t\telse if (S_ISGITLINK(entry.mode))\n-\t\t\tprocess_gitlink(revs, entry.sha1,\n-\t\t\t\t\tshow, &me, entry.path,\n+\t\t\tpv4_release_tree_desc(&sub_desc);\n+\t\t} else if (S_ISGITLINK(entry->mode))\n+\t\t\tprocess_gitlink(revs, entry->sha1,\n+\t\t\t\t\tshow, &me, entry->path,\n \t\t\t\t\tcb_data);\n \t\telse\n \t\t\tprocess_blob(revs,\n-\t\t\t\t     lookup_blob(entry.sha1),\n-\t\t\t\t     show, &me, entry.path,\n+\t\t\t\t     pv4_lookup_blob(desc),\n+\t\t\t\t     show, &me, entry->path,\n \t\t\t\t     cb_data);\n \t}\n \tstrbuf_setlen(base, baselen);\n@@ -202,9 +205,12 @@ void traverse_commit_list(struct rev_info *revs,\n \t\t\tcontinue;\n \t\t}\n \t\tif (obj->type == OBJ_TREE) {\n-\t\t\tprocess_tree(revs, (struct tree *)obj,\n+\t\t\tstruct pv4_tree_desc desc;\n+\t\t\tpv4_tree_desc_from_sha1(&desc, obj->sha1, 0);\n+\t\t\tprocess_tree(revs, &desc, (struct tree *)obj,\n \t\t\t\t     show_tree_entry, show_object,\n \t\t\t\t     NULL, &base, name, data);\n+\t\t\tpv4_release_tree_desc(&desc);\n \t\t\tcontinue;\n \t\t}\n \t\tif (obj->type == OBJ_BLOB) {\n-- \n1.8.2.83.gc99314b\n"},{"id":"228663","messageId":"alpine.LFD.2.03.1310091137310.3023@syhkavp.arg","threadId":"35091","inReplyTo":"1381329976-32082-1-git-send-email-pclouds@gmail.com","subject":"Re: [BAD PATCH 0/9] v4-aware tree walker API","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-10-09T16:51:26Z","receivedAt":"2013-10-09T16:51:26Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 9 Oct 2013, Nguy�n Th�i Ng�c Duy wrote:\n\n> I know I still have a lot of holes to plug, but this was more\n> interesting because we could see some encouraging numbers.\n> Unfortunately the result is disappointing. Maybe I did it in a stupid\n> way and need to restart with a totally different way.\n> \n> \"rev-list --objects\" on v2 takes 4 secs, v4 with current walker 11s\n> and the new walker 16s (worst!).\n\nClear indication that something is wrong if the intermediate step of \nconverting to the canonical object representation is faster than your \nattempt at a native pv4 walker.\n\nHowever here's the numbers I get here after a fresh clone of git.git\n\n$ time git revlist --objects --all > /dev/null\n\nreal    0m2.619s\nuser    0m2.577s\nsys     0m0.033s\n$ mkdir orig\n$ mv .git/objects/pack/pack-* orig/\n$ ../../git/test-packv4 orig/pack-*.pack .git/objects/pack/pack-foo.pack\nScanning objects: 100% (162785/162785), done.\nWriting objects: 100% (162785/162785), done.\n$ time git rev-list --objects --all > /dev/null\n\nreal    0m6.210s\nuser    0m6.140s\nsys     0m0.027s\n\n[installing git with your latest patches applied here]\n\n$ time git rev-list --objects --all > /dev/null\n\nreal    0m20.409s\nuser    0m20.337s\nsys     0m0.029s\n\nSo... I get even *worse* numbers relative to v2 than you do!\n\nNow let's mitigate the deep delta chaining effect in the tree encoding:\n\n$ rm .git/objects/pack/pack-foo.*\n$ ../../git/test-packv4 --min-tree-copy=50 orig/pack-*.pack .git/objects/pack/pack-foo.pack\nScanning objects: 100% (162785/162785), done.\nWriting objects: 100% (162785/162785), done.\n$ time git rev-list --objects --all > /dev/null\n\nreal    0m9.451s\nuser    0m9.393s\nsys     0m0.036s\n\nUsing --min-tree-copy=50 produces a pack which is still smaller than \npack v2 but any tree copy sequence must refer to a minimum of 50 \nentries.  This significantly reduces the CPU usage in decode_entries() \nby reducing the needless chaining effect I mentioned here:\n\nhttp://article.gmane.org/gmane.comp.version-control.git/234975\n\nNow let's keep that pack and back out your patches.\n\n[installing git with your latest patches reverted here]\n\n$ time git rev-list --objects --all > /dev/null\n\nreal    0m3.751s\nuser    0m3.711s\nsys     0m0.029s\n\nSo I shoved almost 2.5 seconds of runtime here.  Not the half of the \noriginal runtime, but still significant.\n\nLet's push the chaining theory even further:\n\n$ rm .git/objects/pack/pack-foo.*\n$ ../../git/test-packv4 --min-tree-copy=100 orig/pack-*.pack .git/objects/pack/pack-foo.pack\nScanning objects: 100% (162785/162785), done.\nWriting objects: 100% (162785/162785), done.\n$ time git rev-list --objects --all > /dev/null\n\nreal    0m3.445s\nuser    0m3.406s\nsys     0m0.029s\n\nWith --min-tree-copy=100 the resulting pack gets somewhat larger than \nthe v2 equivalent, but still smaller if we take into account the size of \nboth the pack and index files.  However the runtime benefit is no more \nsignificant.\n\nSo, there are 2 conclusions here:\n\n1: The current tree delta euristic is inefficient for pack v4.\n\n2- Something must be very wrong in your latest patches as they make it\n   close to 3 times more expensive than without them.\n\n> The only bit I haven't done is avoid checking if a tree is already\n> examined, if so do not bother with copy sequences referring to it.\n> That should cut down the number of decode_entries but not sure how\n> much because there's no relation between tree traversing order and how\n> copy sequences are made.\n\nI'm sure it would help mitigate the deep delta chaining effect as well.\n\n> Maybe we could make an exception and allow the tree walker to pass\n> pv4_tree_cache* directly to decode_entries so it does not need to do\n> the first lookup every time..\n> \n> Suggestions?\n\nI'll try to have a look at your patches in more details soon.\n\n\nNicolas\n"},{"id":"228730","messageId":"20131011122259.GA7776@lanh","threadId":"35091","inReplyTo":"alpine.LFD.2.03.1310091137310.3023@syhkavp.arg","subject":"Re: [BAD PATCH 0/9] v4-aware tree walker API","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-11T12:22:59Z","receivedAt":"2013-10-11T12:22:59Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Oct 09, 2013 at 12:51:26PM -0400, Nicolas Pitre wrote:\n> Now let's mitigate the deep delta chaining effect in the tree encoding:\n> \n> $ rm .git/objects/pack/pack-foo.*\n> $ ../../git/test-packv4 --min-tree-copy=50 orig/pack-*.pack .git/objects/pack/pack-foo.pack\n> Scanning objects: 100% (162785/162785), done.\n> Writing objects: 100% (162785/162785), done.\n> $ time git rev-list --objects --all > /dev/null\n> \n> real    0m9.451s\n> user    0m9.393s\n> sys     0m0.036s\n> \n> Using --min-tree-copy=50 produces a pack which is still smaller than \n> pack v2 but any tree copy sequence must refer to a minimum of 50 \n> entries.  This significantly reduces the CPU usage in decode_entries() \n> by reducing the needless chaining effect I mentioned here:\n> \n> http://article.gmane.org/gmane.comp.version-control.git/234975\n\nYeah I was frustrated and did not think about trying --min-tree-copy.\n\n> So, there are 2 conclusions here:\n> \n> 1: The current tree delta euristic is inefficient for pack v4.\n> \n> 2- Something must be very wrong in your latest patches as they make it\n>    close to 3 times more expensive than without them.\n\nFor one I know that get_tree_offset_cache() is called a lot more with\nthe new API. I do rev-list on v1.8.4. With compatibility layer on,\nit's 211m calls (*). With new API it's 655m calls. The new API is\nbasically do decode_entries() on every tree_entry() call. Perhaps I\nscrewed up something in decode_entries() itself..\n\n(*) for 15m tree entries, 211m are a lot of calls, which might\ntranslate to a lot of copy sequences..\n\n> > Maybe we could make an exception and allow the tree walker to pass\n> > pv4_tree_cache* directly to decode_entries so it does not need to do\n> > the first lookup every time..\n> > \n> > Suggestions?\n> \n> I'll try to have a look at your patches in more details soon.\n\nShameful fixup (though it does not seem to impact the timing)\n\ndiff --git a/packv4-parse.c b/packv4-parse.c\nindex 6f6152c..9d7589e 100644\n--- a/packv4-parse.c\n+++ b/packv4-parse.c\n@@ -825,8 +825,8 @@ static struct object **get_packed_objs(struct pv4_tree_desc *desc)\n \tif (!desc->p || !desc->sha1_index)\n \t\treturn NULL;\n \tif (desc->p->version >= 4 && !desc->p->objs)\n-\t\tdesc->p->objs =\n-\t\t\txmalloc(sizeof(struct object *) * desc->p->num_objects);\n+\t\tdesc->p->objs = xcalloc(desc->p->num_objects,\n+\t\t\t\t\tsizeof(struct object *));\n \treturn desc->p->objs;\n }\n \n"},{"id":"228735","messageId":"20131011130528.GA10014@lanh","threadId":"35091","inReplyTo":"20131011122259.GA7776@lanh","subject":"Re: [BAD PATCH 0/9] v4-aware tree walker API","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-11T13:05:28Z","receivedAt":"2013-10-11T13:05:28Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Oct 11, 2013 at 07:22:59PM +0700, Duy Nguyen wrote:\n> > > Maybe we could make an exception and allow the tree walker to pass\n> > > pv4_tree_cache* directly to decode_entries so it does not need to do\n> > > the first lookup every time..\n> > > \n> > > Suggestions?\n\nLooking at decode_entries() traces I think the \"one decode_entries()\nfor one tree_entry()\" just amplifies the delta chain effect. If you\nhide 3 entries behind 5 layers of copy sequences\n(i.e. tree1->tree2->..->tree5->real-tree-entry), then every\ndecode_entries(count=1) will have to go through 5 layers.\n\nIt makes me wonder if we should cache shortcuts so that after the\nfirst going through 5 layers, the second can jump directly to the tree\nentries.\n\n> > \n> > I'll try to have a look at your patches in more details soon.\n> \n> Shameful fixup (though it does not seem to impact the timing)\n\nAnd here's another one\n\n-- 8< --\ndiff --git a/list-objects.c b/list-objects.c\nindex 39ad3e6..85dc14e 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -82,8 +82,10 @@ static void process_tree(struct rev_info *revs,\n \t\tdie(\"bad tree object\");\n \tif (obj->flags & (UNINTERESTING | SEEN))\n \t\treturn;\n+#if 0\n \tif (parse_tree(tree) < 0)\n \t\tdie(\"bad tree object %s\", sha1_to_hex(obj->sha1));\n+#endif\n \tobj->flags |= SEEN;\n \tshow(obj, path, name, cb_data);\n \tme.up = path;\n"},{"id":"228879","messageId":"alpine.LFD.2.03.1310121001000.3023@syhkavp.arg","threadId":"35091","inReplyTo":"20131011130528.GA10014@lanh","subject":"Re: [BAD PATCH 0/9] v4-aware tree walker API","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-10-12T14:42:05Z","receivedAt":"2013-10-12T14:42:05Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 11 Oct 2013, Duy Nguyen wrote:\n\n> On Fri, Oct 11, 2013 at 07:22:59PM +0700, Duy Nguyen wrote:\n> > > > Maybe we could make an exception and allow the tree walker to pass\n> > > > pv4_tree_cache* directly to decode_entries so it does not need to do\n> > > > the first lookup every time..\n> > > > \n> > > > Suggestions?\n> \n> Looking at decode_entries() traces I think the \"one decode_entries()\n> for one tree_entry()\" just amplifies the delta chain effect. If you\n> hide 3 entries behind 5 layers of copy sequences\n> (i.e. tree1->tree2->..->tree5->real-tree-entry), then every\n> decode_entries(count=1) will have to go through 5 layers.\n\nCalling decode_entries() for every tree entry is a bad approach.  We \nshould really implement this as a state machine preserving the entire \nstate between entries so that moving to the next entry is just a matter \nof advancing a pointer in most cases.\n\n\nNicolas\n"},{"id":"228881","messageId":"CACsJy8DZvdWyKSvLzPhS7OqKUU-OKG40M7M1HxN4eADsx0od6Q@mail.gmail.com","threadId":"35091","inReplyTo":"alpine.LFD.2.03.1310121001000.3023@syhkavp.arg","subject":"Re: [BAD PATCH 0/9] v4-aware tree walker API","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-12T15:59:24Z","receivedAt":"2013-10-12T15:59:24Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Oct 12, 2013 at 9:42 PM, Nicolas Pitre <nico@fluxnic.net> wrote:\n> On Fri, 11 Oct 2013, Duy Nguyen wrote:\n>\n>> On Fri, Oct 11, 2013 at 07:22:59PM +0700, Duy Nguyen wrote:\n>> > > > Maybe we could make an exception and allow the tree walker to pass\n>> > > > pv4_tree_cache* directly to decode_entries so it does not need to do\n>> > > > the first lookup every time..\n>> > > >\n>> > > > Suggestions?\n>>\n>> Looking at decode_entries() traces I think the \"one decode_entries()\n>> for one tree_entry()\" just amplifies the delta chain effect. If you\n>> hide 3 entries behind 5 layers of copy sequences\n>> (i.e. tree1->tree2->..->tree5->real-tree-entry), then every\n>> decode_entries(count=1) will have to go through 5 layers.\n>\n> Calling decode_entries() for every tree entry is a bad approach.  We\n> should really implement this as a state machine preserving the entire\n> state between entries so that moving to the next entry is just a matter\n> of advancing a pointer in most cases.\n\nYeah. Maybe first step is avoid recursion in decode_entries(). We need\nto do that eventually to avoid stack overlow due to long depths.\n-- \nDuy\n"}]}