{"thread":{"id":"7347","subject":"[PATCH 0/3] Clean up and optimize tree walking some more","startedAt":"2007-03-21T17:07:09Z","lastAt":"2007-03-21T18:32:06Z","messageCount":5,"participants":["Linus Torvalds"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"37682","messageId":"Pine.LNX.4.64.0703210955370.6730@woody.linux-foundation.org","threadId":"7347","inReplyTo":null,"subject":"[PATCH 0/3] Clean up and optimize tree walking some more","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-21T17:07:09Z","receivedAt":"2007-03-21T17:07:09Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis series of three patches improves blame performance on the eclipse \ntree by about 15% in my tests by improving the tree walk a bit.\n\n  [ Before-best-of-five: 11.649s\n    After-best-of-five:   9.675s ]\n\nThe first two patches are just boring cleanups: the first removes an \nunnecessary field from the \"name_entry\" structure, because I wanted to \nembed it into the \"tree_desc\" one and it was just totally redundant and I \nfelt bad about growing tree_desc more than necessary. No real code \nchanges, just replacing the use of \"pathlen\" with the helper function we \nintroduced ealier (\"tree_entry_len()\").\n\nThe second one just makes sure that we always initialize the tree_desc \nstructure with a helper function rather than doing it by hand. Again, this \ndoesn't actually change any code, although I changed the name of the \"buf\" \nentry to \"buffer\", and the type of \"size\", so that we get nice compiler \nwarnings if they are used the old way by mistake.\n\nThe second patch is the largest of the lot, but really doesn't do \nanything interesting, just preparatory cleanup.\n\nThe third patch is the one that actually changes any code, and is fairly \nstraightforward: it just switches around where we actually do the tree \nentry parsing, which is now possible thanks to patch #2. By doing it \nup-front, we only need to do it once (we used to have to do it both when \ndoing the \"extract\" *and* when doing the \"update\" op - now we do it only \nonce per entry, and \"extract\" is just about looking at the cached \ncontents).\n\nThe resulting diffstat of the tree patches ends up removing a few more \nlines than it adds (not by a lot), but perhaps more importantly (even more \nthan the performance advantage) the code looks nicer, I think.\n\n builtin-fsck.c         |    5 +-\n builtin-grep.c         |   13 +++--\n builtin-pack-objects.c |    8 +--\n builtin-read-tree.c    |    3 +-\n builtin-reflog.c       |   10 ++--\n fetch.c                |    3 +-\n http-push.c            |    3 +-\n list-objects.c         |    3 +-\n merge-tree.c           |    9 ++--\n reachable.c            |    3 +-\n revision.c             |   12 ++---\n tree-diff.c            |   22 +++++----\n tree-walk.c            |  123 ++++++++++++++++++++++--------------------------\n tree-walk.h            |   20 ++++++--\n tree.c                 |   18 +++----\n unpack-trees.c         |    3 +-\n 16 files changed, 125 insertions(+), 133 deletions(-)\n\nI'm pretty sure this is all good, and it obviously passes all the tests, \nbut more importantly none of the changes were really very complicated, and \npatch#2 (which is the big one) was set up so that the compiler would not \neven compile code that wasn't properly converted, so it should all be \ngood.\n\n\t\t\tLinus\n"},{"id":"37683","messageId":"Pine.LNX.4.64.0703211007160.6730@woody.linux-foundation.org","threadId":"7347","inReplyTo":"Pine.LNX.4.64.0703210955370.6730@woody.linux-foundation.org","subject":"[PATCH 1/3] Remove \"pathlen\" from \"struct name_entry\"","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-21T17:07:46Z","receivedAt":"2007-03-21T17:07:46Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nSince we have the \"tree_entry_len()\" helper function these days, and\ndon't need to do a full strlen(), there's no point in saving the path\nlength - it's just redundant information.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n builtin-grep.c         |    2 +-\n builtin-pack-objects.c |    2 +-\n merge-tree.c           |    9 +++++----\n tree-walk.c            |    6 ++----\n tree-walk.h            |    1 -\n tree.c                 |    9 +++++----\n 6 files changed, 14 insertions(+), 15 deletions(-)\n\ndiff --git a/builtin-grep.c b/builtin-grep.c\nindex 4510d35..1348cc9 100644\n--- a/builtin-grep.c\n+++ b/builtin-grep.c\n@@ -378,7 +378,7 @@ static int grep_tree(struct grep_opt *opt, const char **paths,\n \t\t\t * decide if we want to descend into \"abc\"\n \t\t\t * directory.\n \t\t\t */\n-\t\t\tstrcpy(path_buf + len + entry.pathlen, \"/\");\n+\t\t\tstrcpy(path_buf + len + tree_entry_len(entry.path, entry.sha1), \"/\");\n \n \t\tif (!pathspec_matches(paths, down))\n \t\t\t;\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 73d448b..9231b65 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -854,7 +854,7 @@ static void add_pbase_object(struct tree_desc *tree,\n \t\tunsigned long size;\n \t\tenum object_type type;\n \n-\t\tif (entry.pathlen != cmplen ||\n+\t\tif (tree_entry_len(entry.path, entry.sha1) != cmplen ||\n \t\t    memcmp(entry.path, name, cmplen) ||\n \t\t    !has_sha1_file(entry.sha1) ||\n \t\t    (type = sha1_object_info(entry.sha1, &size)) < 0)\ndiff --git a/merge-tree.c b/merge-tree.c\nindex b2867ba..3b8d9e6 100644\n--- a/merge-tree.c\n+++ b/merge-tree.c\n@@ -188,7 +188,7 @@ static void resolve(const char *base, struct name_entry *branch1, struct name_en\n \n static int unresolved_directory(const char *base, struct name_entry n[3])\n {\n-\tint baselen;\n+\tint baselen, pathlen;\n \tchar *newbase;\n \tstruct name_entry *p;\n \tstruct tree_desc t[3];\n@@ -205,10 +205,11 @@ static int unresolved_directory(const char *base, struct name_entry n[3])\n \tif (!S_ISDIR(p->mode))\n \t\treturn 0;\n \tbaselen = strlen(base);\n-\tnewbase = xmalloc(baselen + p->pathlen + 2);\n+\tpathlen = tree_entry_len(p->path, p->sha1);\n+\tnewbase = xmalloc(baselen + pathlen + 2);\n \tmemcpy(newbase, base, baselen);\n-\tmemcpy(newbase + baselen, p->path, p->pathlen);\n-\tmemcpy(newbase + baselen + p->pathlen, \"/\", 2);\n+\tmemcpy(newbase + baselen, p->path, pathlen);\n+\tmemcpy(newbase + baselen + pathlen, \"/\", 2);\n \n \tbuf0 = fill_tree_descriptor(t+0, n[0].sha1);\n \tbuf1 = fill_tree_descriptor(t+1, n[1].sha1);\ndiff --git a/tree-walk.c b/tree-walk.c\nindex a4a4e2a..1869bae 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -20,8 +20,8 @@ void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)\n static int entry_compare(struct name_entry *a, struct name_entry *b)\n {\n \treturn base_name_compare(\n-\t\t\ta->path, a->pathlen, a->mode,\n-\t\t\tb->path, b->pathlen, b->mode);\n+\t\t\ta->path, tree_entry_len(a->path, a->sha1), a->mode,\n+\t\t\tb->path, tree_entry_len(b->path, b->sha1), b->mode);\n }\n \n static void entry_clear(struct name_entry *a)\n@@ -32,7 +32,6 @@ static void entry_clear(struct name_entry *a)\n static void entry_extract(struct tree_desc *t, struct name_entry *a)\n {\n \ta->sha1 = tree_entry_extract(t, &a->path, &a->mode);\n-\ta->pathlen = tree_entry_len(a->path, a->sha1);\n }\n \n void update_tree_entry(struct tree_desc *desc)\n@@ -93,7 +92,6 @@ int tree_entry(struct tree_desc *desc, struct name_entry *entry)\n \n \tentry->path = path;\n \tlen = strlen(path);\n-\tentry->pathlen = len;\n \n \tpath += len + 1;\n \tentry->sha1 = (const unsigned char *) path;\ndiff --git a/tree-walk.h b/tree-walk.h\nindex a0d7afd..149393a 100644\n--- a/tree-walk.h\n+++ b/tree-walk.h\n@@ -10,7 +10,6 @@ struct name_entry {\n \tconst unsigned char *sha1;\n \tconst char *path;\n \tunsigned int mode;\n-\tint pathlen;\n };\n \n static inline int tree_entry_len(const char *name, const unsigned char *sha1)\ndiff --git a/tree.c b/tree.c\nindex 24f8fb6..705a481 100644\n--- a/tree.c\n+++ b/tree.c\n@@ -101,14 +101,15 @@ int read_tree_recursive(struct tree *tree,\n \t\tif (S_ISDIR(entry.mode)) {\n \t\t\tint retval;\n \t\t\tchar *newbase;\n+\t\t\tunsigned int pathlen = tree_entry_len(entry.path, entry.sha1);\n \n-\t\t\tnewbase = xmalloc(baselen + 1 + entry.pathlen);\n+\t\t\tnewbase = xmalloc(baselen + 1 + pathlen);\n \t\t\tmemcpy(newbase, base, baselen);\n-\t\t\tmemcpy(newbase + baselen, entry.path, entry.pathlen);\n-\t\t\tnewbase[baselen + entry.pathlen] = '/';\n+\t\t\tmemcpy(newbase + baselen, entry.path, pathlen);\n+\t\t\tnewbase[baselen + pathlen] = '/';\n \t\t\tretval = read_tree_recursive(lookup_tree(entry.sha1),\n \t\t\t\t\t\t     newbase,\n-\t\t\t\t\t\t     baselen + entry.pathlen + 1,\n+\t\t\t\t\t\t     baselen + pathlen + 1,\n \t\t\t\t\t\t     stage, match, fn);\n \t\t\tfree(newbase);\n \t\t\tif (retval)\n-- \n1.5.1.rc1.13.g0872-dirty\n"},{"id":"37684","messageId":"Pine.LNX.4.64.0703211007480.6730@woody.linux-foundation.org","threadId":"7347","inReplyTo":"Pine.LNX.4.64.0703210955370.6730@woody.linux-foundation.org","subject":"[PATCH 2/3] Initialize tree descriptors with a helper function rather than by hand.","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-21T17:08:25Z","receivedAt":"2007-03-21T17:08:25Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis removes slightly more lines than it adds, but the real reason for\ndoing this is that future optimizations will require more setup of the\ntree descriptor, and so we want to do it in one place.\n\nAlso renamed the \"desc.buf\" field to \"desc.buffer\" just to trigger\ncompiler errors for old-style manual initializations, making sure I\ndidn't miss anything.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n builtin-fsck.c         |    5 ++---\n builtin-grep.c         |   11 +++++++----\n builtin-pack-objects.c |    6 ++----\n builtin-read-tree.c    |    3 +--\n builtin-reflog.c       |   10 +++++-----\n fetch.c                |    3 +--\n http-push.c            |    3 +--\n list-objects.c         |    3 +--\n reachable.c            |    3 +--\n revision.c             |   12 +++++-------\n tree-diff.c            |   22 ++++++++++++----------\n tree-walk.c            |   24 +++++++++++++++---------\n tree-walk.h            |    5 +++--\n tree.c                 |    9 +++------\n unpack-trees.c         |    3 +--\n 15 files changed, 60 insertions(+), 62 deletions(-)\n\ndiff --git a/builtin-fsck.c b/builtin-fsck.c\nindex b8e71b6..21f1f9e 100644\n--- a/builtin-fsck.c\n+++ b/builtin-fsck.c\n@@ -227,8 +227,7 @@ static int fsck_tree(struct tree *item)\n \tconst char *o_name;\n \tconst unsigned char *o_sha1;\n \n-\tdesc.buf = item->buffer;\n-\tdesc.size = item->size;\n+\tinit_tree_desc(&desc, item->buffer, item->size);\n \n \to_mode = 0;\n \to_name = NULL;\n@@ -242,7 +241,7 @@ static int fsck_tree(struct tree *item)\n \n \t\tif (strchr(name, '/'))\n \t\t\thas_full_path = 1;\n-\t\thas_zero_pad |= *(char *)desc.buf == '0';\n+\t\thas_zero_pad |= *(char *)desc.buffer == '0';\n \t\tupdate_tree_entry(&desc);\n \n \t\tswitch (mode) {\ndiff --git a/builtin-grep.c b/builtin-grep.c\nindex 1348cc9..981f3d4 100644\n--- a/builtin-grep.c\n+++ b/builtin-grep.c\n@@ -388,11 +388,13 @@ static int grep_tree(struct grep_opt *opt, const char **paths,\n \t\t\tenum object_type type;\n \t\t\tstruct tree_desc sub;\n \t\t\tvoid *data;\n-\t\t\tdata = read_sha1_file(entry.sha1, &type, &sub.size);\n+\t\t\tunsigned long size;\n+\n+\t\t\tdata = read_sha1_file(entry.sha1, &type, &size);\n \t\t\tif (!data)\n \t\t\t\tdie(\"unable to read tree (%s)\",\n \t\t\t\t    sha1_to_hex(entry.sha1));\n-\t\t\tsub.buf = data;\n+\t\t\tinit_tree_desc(&sub, data, size);\n \t\t\thit |= grep_tree(opt, paths, &sub, tree_name, down);\n \t\t\tfree(data);\n \t\t}\n@@ -408,12 +410,13 @@ static int grep_object(struct grep_opt *opt, const char **paths,\n \tif (obj->type == OBJ_COMMIT || obj->type == OBJ_TREE) {\n \t\tstruct tree_desc tree;\n \t\tvoid *data;\n+\t\tunsigned long size;\n \t\tint hit;\n \t\tdata = read_object_with_reference(obj->sha1, tree_type,\n-\t\t\t\t\t\t  &tree.size, NULL);\n+\t\t\t\t\t\t  &size, NULL);\n \t\tif (!data)\n \t\t\tdie(\"unable to read tree (%s)\", sha1_to_hex(obj->sha1));\n-\t\ttree.buf = data;\n+\t\tinit_tree_desc(&tree, data, size);\n \t\thit = grep_tree(opt, paths, &tree, name, \"\");\n \t\tfree(data);\n \t\treturn hit;\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 9231b65..b5f9648 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -873,8 +873,7 @@ static void add_pbase_object(struct tree_desc *tree,\n \t\t\ttree = pbase_tree_get(entry.sha1);\n \t\t\tif (!tree)\n \t\t\t\treturn;\n-\t\t\tsub.buf = tree->tree_data;\n-\t\t\tsub.size = tree->tree_size;\n+\t\t\tinit_tree_desc(&sub, tree->tree_data, tree->tree_size);\n \n \t\t\tadd_pbase_object(&sub, down, downlen, fullname);\n \t\t\tpbase_tree_put(tree);\n@@ -937,8 +936,7 @@ static void add_preferred_base_object(const char *name, unsigned hash)\n \t\t}\n \t\telse {\n \t\t\tstruct tree_desc tree;\n-\t\t\ttree.buf = it->pcache.tree_data;\n-\t\t\ttree.size = it->pcache.tree_size;\n+\t\t\tinit_tree_desc(&tree, it->pcache.tree_data, it->pcache.tree_size);\n \t\t\tadd_pbase_object(&tree, name, cmplen, name);\n \t\t}\n \t}\ndiff --git a/builtin-read-tree.c b/builtin-read-tree.c\nindex e477155..82df941 100644\n--- a/builtin-read-tree.c\n+++ b/builtin-read-tree.c\n@@ -55,8 +55,7 @@ static void prime_cache_tree_rec(struct cache_tree *it, struct tree *tree)\n \tint cnt;\n \n \thashcpy(it->sha1, tree->object.sha1);\n-\tdesc.buf = tree->buffer;\n-\tdesc.size = tree->size;\n+\tinit_tree_desc(&desc, tree->buffer, tree->size);\n \tcnt = 0;\n \twhile (tree_entry(&desc, &entry)) {\n \t\tif (!S_ISDIR(entry.mode))\ndiff --git a/builtin-reflog.c b/builtin-reflog.c\nindex 186aabc..4c39f1d 100644\n--- a/builtin-reflog.c\n+++ b/builtin-reflog.c\n@@ -52,18 +52,18 @@ static int tree_is_complete(const unsigned char *sha1)\n \tif (tree->object.flags & INCOMPLETE)\n \t\treturn 0;\n \n-\tdesc.buf = tree->buffer;\n-\tdesc.size = tree->size;\n-\tif (!desc.buf) {\n+\tif (!tree->buffer) {\n \t\tenum object_type type;\n-\t\tvoid *data = read_sha1_file(sha1, &type, &desc.size);\n+\t\tunsigned long size;\n+\t\tvoid *data = read_sha1_file(sha1, &type, &size);\n \t\tif (!data) {\n \t\t\ttree->object.flags |= INCOMPLETE;\n \t\t\treturn 0;\n \t\t}\n-\t\tdesc.buf = data;\n \t\ttree->buffer = data;\n+\t\ttree->size = size;\n \t}\n+\tinit_tree_desc(&desc, tree->buffer, tree->size);\n \tcomplete = 1;\n \twhile (tree_entry(&desc, &entry)) {\n \t\tif (!has_sha1_file(entry.sha1) ||\ndiff --git a/fetch.c b/fetch.c\nindex f69be82..8e29d31 100644\n--- a/fetch.c\n+++ b/fetch.c\n@@ -42,8 +42,7 @@ static int process_tree(struct tree *tree)\n \tif (parse_tree(tree))\n \t\treturn -1;\n \n-\tdesc.buf = tree->buffer;\n-\tdesc.size = tree->size;\n+\tinit_tree_desc(&desc, tree->buffer, tree->size);\n \twhile (tree_entry(&desc, &entry)) {\n \t\tstruct object *obj = NULL;\n \ndiff --git a/http-push.c b/http-push.c\nindex cbb02d3..724720c 100644\n--- a/http-push.c\n+++ b/http-push.c\n@@ -1750,8 +1750,7 @@ static struct object_list **process_tree(struct tree *tree,\n \tme.elem = name;\n \tme.elem_len = strlen(name);\n \n-\tdesc.buf = tree->buffer;\n-\tdesc.size = tree->size;\n+\tinit_tree_desc(&desc, tree->buffer, tree->size);\n \n \twhile (tree_entry(&desc, &entry)) {\n \t\tif (S_ISDIR(entry.mode))\ndiff --git a/list-objects.c b/list-objects.c\nindex f1fa21c..2ba2c95 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -49,8 +49,7 @@ static void process_tree(struct rev_info *revs,\n \tme.elem = name;\n \tme.elem_len = strlen(name);\n \n-\tdesc.buf = tree->buffer;\n-\tdesc.size = tree->size;\n+\tinit_tree_desc(&desc, tree->buffer, tree->size);\n \n \twhile (tree_entry(&desc, &entry)) {\n \t\tif (S_ISDIR(entry.mode))\ndiff --git a/reachable.c b/reachable.c\nindex 01760d7..ff3dd34 100644\n--- a/reachable.c\n+++ b/reachable.c\n@@ -42,8 +42,7 @@ static void process_tree(struct tree *tree,\n \tme.elem = name;\n \tme.elem_len = strlen(name);\n \n-\tdesc.buf = tree->buffer;\n-\tdesc.size = tree->size;\n+\tinit_tree_desc(&desc, tree->buffer, tree->size);\n \n \twhile (tree_entry(&desc, &entry)) {\n \t\tif (S_ISDIR(entry.mode))\ndiff --git a/revision.c b/revision.c\nindex c680dcb..adc381c 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -62,8 +62,7 @@ void mark_tree_uninteresting(struct tree *tree)\n \tif (parse_tree(tree) < 0)\n \t\tdie(\"bad tree %s\", sha1_to_hex(obj->sha1));\n \n-\tdesc.buf = tree->buffer;\n-\tdesc.size = tree->size;\n+\tinit_tree_desc(&desc, tree->buffer, tree->size);\n \twhile (tree_entry(&desc, &entry)) {\n \t\tif (S_ISDIR(entry.mode))\n \t\t\tmark_tree_uninteresting(lookup_tree(entry.sha1));\n@@ -275,18 +274,17 @@ int rev_same_tree_as_empty(struct rev_info *revs, struct tree *t1)\n {\n \tint retval;\n \tvoid *tree;\n+\tunsigned long size;\n \tstruct tree_desc empty, real;\n \n \tif (!t1)\n \t\treturn 0;\n \n-\ttree = read_object_with_reference(t1->object.sha1, tree_type, &real.size, NULL);\n+\ttree = read_object_with_reference(t1->object.sha1, tree_type, &size, NULL);\n \tif (!tree)\n \t\treturn 0;\n-\treal.buf = tree;\n-\n-\tempty.buf = \"\";\n-\tempty.size = 0;\n+\tinit_tree_desc(&real, tree, size);\n+\tinit_tree_desc(&empty, \"\", 0);\n \n \ttree_difference = REV_TREE_SAME;\n \trevs->pruning.has_changes = 0;\ndiff --git a/tree-diff.c b/tree-diff.c\nindex b2f35dc..3678805 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -154,12 +154,13 @@ static void show_entry(struct diff_options *opt, const char *prefix, struct tree\n \t\tchar *newbase = malloc_base(base, baselen, path, pathlen);\n \t\tstruct tree_desc inner;\n \t\tvoid *tree;\n+\t\tunsigned long size;\n \n-\t\ttree = read_sha1_file(sha1, &type, &inner.size);\n+\t\ttree = read_sha1_file(sha1, &type, &size);\n \t\tif (!tree || type != OBJ_TREE)\n \t\t\tdie(\"corrupt tree sha %s\", sha1_to_hex(sha1));\n \n-\t\tinner.buf = tree;\n+\t\tinit_tree_desc(&inner, tree, size);\n \t\tshow_tree(opt, prefix, &inner, newbase, baselen + 1 + pathlen);\n \n \t\tfree(tree);\n@@ -227,16 +228,17 @@ int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const cha\n {\n \tvoid *tree1, *tree2;\n \tstruct tree_desc t1, t2;\n+\tunsigned long size1, size2;\n \tint retval;\n \n-\ttree1 = read_object_with_reference(old, tree_type, &t1.size, NULL);\n+\ttree1 = read_object_with_reference(old, tree_type, &size1, NULL);\n \tif (!tree1)\n \t\tdie(\"unable to read source tree (%s)\", sha1_to_hex(old));\n-\ttree2 = read_object_with_reference(new, tree_type, &t2.size, NULL);\n+\ttree2 = read_object_with_reference(new, tree_type, &size2, NULL);\n \tif (!tree2)\n \t\tdie(\"unable to read destination tree (%s)\", sha1_to_hex(new));\n-\tt1.buf = tree1;\n-\tt2.buf = tree2;\n+\tinit_tree_desc(&t1, tree1, size1);\n+\tinit_tree_desc(&t2, tree2, size2);\n \tretval = diff_tree(&t1, &t2, base, opt);\n \tfree(tree1);\n \tfree(tree2);\n@@ -247,15 +249,15 @@ int diff_root_tree_sha1(const unsigned char *new, const char *base, struct diff_\n {\n \tint retval;\n \tvoid *tree;\n+\tunsigned long size;\n \tstruct tree_desc empty, real;\n \n-\ttree = read_object_with_reference(new, tree_type, &real.size, NULL);\n+\ttree = read_object_with_reference(new, tree_type, &size, NULL);\n \tif (!tree)\n \t\tdie(\"unable to read root tree (%s)\", sha1_to_hex(new));\n-\treal.buf = tree;\n+\tinit_tree_desc(&real, tree, size);\n \n-\tempty.size = 0;\n-\tempty.buf = \"\";\n+\tinit_tree_desc(&empty, \"\", 0);\n \tretval = diff_tree(&empty, &real, base, opt);\n \tfree(tree);\n \treturn retval;\ndiff --git a/tree-walk.c b/tree-walk.c\nindex 1869bae..c65492c 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -2,6 +2,12 @@\n #include \"tree-walk.h\"\n #include \"tree.h\"\n \n+void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size)\n+{\n+\tdesc->buffer = buffer;\n+\tdesc->size = size;\n+}\n+\n void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)\n {\n \tunsigned long size = 0;\n@@ -12,8 +18,7 @@ void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)\n \t\tif (!buf)\n \t\t\tdie(\"unable to read tree %s\", sha1_to_hex(sha1));\n \t}\n-\tdesc->size = size;\n-\tdesc->buf = buf;\n+\tinit_tree_desc(desc, buf, size);\n \treturn buf;\n }\n \n@@ -36,13 +41,13 @@ static void entry_extract(struct tree_desc *t, struct name_entry *a)\n \n void update_tree_entry(struct tree_desc *desc)\n {\n-\tconst void *buf = desc->buf;\n+\tconst void *buf = desc->buffer;\n \tunsigned long size = desc->size;\n \tint len = strlen(buf) + 1 + 20;\n \n \tif (size < len)\n \t\tdie(\"corrupt tree file\");\n-\tdesc->buf = (char *) buf + len;\n+\tdesc->buffer = (char *) buf + len;\n \tdesc->size = size - len;\n }\n \n@@ -62,7 +67,7 @@ static const char *get_mode(const char *str, unsigned int *modep)\n \n const unsigned char *tree_entry_extract(struct tree_desc *desc, const char **pathp, unsigned int *modep)\n {\n-\tconst void *tree = desc->buf;\n+\tconst void *tree = desc->buffer;\n \tunsigned long size = desc->size;\n \tint len = strlen(tree)+1;\n \tconst unsigned char *sha1 = (unsigned char *) tree + len;\n@@ -79,7 +84,7 @@ const unsigned char *tree_entry_extract(struct tree_desc *desc, const char **pat\n \n int tree_entry(struct tree_desc *desc, struct name_entry *entry)\n {\n-\tconst void *tree = desc->buf;\n+\tconst void *tree = desc->buffer;\n \tconst char *path;\n \tunsigned long len, size = desc->size;\n \n@@ -101,7 +106,7 @@ int tree_entry(struct tree_desc *desc, struct name_entry *entry)\n \tif (len > size)\n \t\tdie(\"corrupt tree file\");\n \n-\tdesc->buf = path;\n+\tdesc->buffer = path;\n \tdesc->size = size - len;\n \treturn 1;\n }\n@@ -196,10 +201,11 @@ int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned ch\n {\n \tint retval;\n \tvoid *tree;\n+\tunsigned long size;\n \tstruct tree_desc t;\n \tunsigned char root[20];\n \n-\ttree = read_object_with_reference(tree_sha1, tree_type, &t.size, root);\n+\ttree = read_object_with_reference(tree_sha1, tree_type, &size, root);\n \tif (!tree)\n \t\treturn -1;\n \n@@ -208,7 +214,7 @@ int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned ch\n \t\treturn 0;\n \t}\n \n-\tt.buf = tree;\n+\tinit_tree_desc(&t, tree, size);\n \tretval = find_tree_entry(&t, name, sha1, mode);\n \tfree(tree);\n \treturn retval;\ndiff --git a/tree-walk.h b/tree-walk.h\nindex 149393a..ca0c29f 100644\n--- a/tree-walk.h\n+++ b/tree-walk.h\n@@ -2,8 +2,8 @@\n #define TREE_WALK_H\n \n struct tree_desc {\n-\tconst void *buf;\n-\tunsigned long size;\n+\tconst void *buffer;\n+\tunsigned int size;\n };\n \n struct name_entry {\n@@ -18,6 +18,7 @@ static inline int tree_entry_len(const char *name, const unsigned char *sha1)\n }\n \n void update_tree_entry(struct tree_desc *);\n+void init_tree_desc(struct tree_desc *desc, const void *buf, unsigned long size);\n const unsigned char *tree_entry_extract(struct tree_desc *, const char **, unsigned int *);\n \n /* Helper function that does both of the above and returns true for success */\ndiff --git a/tree.c b/tree.c\nindex 705a481..d188c0f 100644\n--- a/tree.c\n+++ b/tree.c\n@@ -83,8 +83,7 @@ int read_tree_recursive(struct tree *tree,\n \tif (parse_tree(tree))\n \t\treturn -1;\n \n-\tdesc.buf = tree->buffer;\n-\tdesc.size = tree->size;\n+\tinit_tree_desc(&desc, tree->buffer, tree->size);\n \n \twhile (tree_entry(&desc, &entry)) {\n \t\tif (!match_tree_entry(base, baselen, entry.path, entry.mode, match))\n@@ -152,16 +151,14 @@ static void track_tree_refs(struct tree *item)\n \tstruct name_entry entry;\n \n \t/* Count how many entries there are.. */\n-\tdesc.buf = item->buffer;\n-\tdesc.size = item->size;\n+\tinit_tree_desc(&desc, item->buffer, item->size);\n \twhile (tree_entry(&desc, &entry))\n \t\tn_refs++;\n \n \t/* Allocate object refs and walk it again.. */\n \ti = 0;\n \trefs = alloc_object_refs(n_refs);\n-\tdesc.buf = item->buffer;\n-\tdesc.size = item->size;\n+\tinit_tree_desc(&desc, item->buffer, item->size);\n \twhile (tree_entry(&desc, &entry)) {\n \t\tstruct object *obj;\n \ndiff --git a/unpack-trees.c b/unpack-trees.c\nindex 2e2232c..ee10eea 100644\n--- a/unpack-trees.c\n+++ b/unpack-trees.c\n@@ -27,8 +27,7 @@ static struct tree_entry_list *create_tree_entry_list(struct tree *tree)\n \tif (!tree->object.parsed)\n \t\tparse_tree(tree);\n \n-\tdesc.buf = tree->buffer;\n-\tdesc.size = tree->size;\n+\tinit_tree_desc(&desc, tree->buffer, tree->size);\n \n \twhile (tree_entry(&desc, &one)) {\n \t\tstruct tree_entry_list *entry;\n-- \n1.5.1.rc1.13.g0872-dirty\n"},{"id":"37685","messageId":"Pine.LNX.4.64.0703211008290.6730@woody.linux-foundation.org","threadId":"7347","inReplyTo":"Pine.LNX.4.64.0703210955370.6730@woody.linux-foundation.org","subject":"[PATCH 3/3] Switch over tree descriptors to contain a pre-parsed entry","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-21T17:09:56Z","receivedAt":"2007-03-21T17:09:56Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis makes the tree descriptor contain a \"struct name_entry\" as part of \nit, and it gets filled in so that it always contains a valid entry. On \nsome benchmarks, it improves performance by up to 15%.\n\nThat makes tree entry \"extract\" trivial, and means that we only actually\nneed to decode each tree entry just once: we decode the first one when\nwe initialize the tree descriptor, and each subsequent one when doing\n\"update_tree_entry()\".  In particular, this means that we don't need to\ndo strlen() both at extract time _and_ at update time.\n\nFinally, it also allows more sharing of code (entry_extract(), that\nwanted a \"struct name_entry\", just got totally trivial, along with the\n\"tree_entry()\" function).\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n tree-walk.c |  101 +++++++++++++++++++++++++---------------------------------\n tree-walk.h |   18 +++++++---\n 2 files changed, 57 insertions(+), 62 deletions(-)\n\ndiff --git a/tree-walk.c b/tree-walk.c\nindex c65492c..3cb757b 100644\n--- a/tree-walk.c\n+++ b/tree-walk.c\n@@ -2,10 +2,42 @@\n #include \"tree-walk.h\"\n #include \"tree.h\"\n \n+static const char *get_mode(const char *str, unsigned int *modep)\n+{\n+\tunsigned char c;\n+\tunsigned int mode = 0;\n+\n+\twhile ((c = *str++) != ' ') {\n+\t\tif (c < '0' || c > '7')\n+\t\t\treturn NULL;\n+\t\tmode = (mode << 3) + (c - '0');\n+\t}\n+\t*modep = mode;\n+\treturn str;\n+}\n+\n+static void decode_tree_entry(struct tree_desc *desc, const void *buf, unsigned long size)\n+{\n+\tconst char *path;\n+\tunsigned int mode, len;\n+\n+\tpath = get_mode(buf, &mode);\n+\tif (!path)\n+\t\tdie(\"corrupt tree file\");\n+\tlen = strlen(path) + 1;\n+\n+\t/* Initialize the descriptor entry */\n+\tdesc->entry.path = path;\n+\tdesc->entry.mode = mode;\n+\tdesc->entry.sha1 = (const unsigned char *)(path + len);\n+}\n+\n void init_tree_desc(struct tree_desc *desc, const void *buffer, unsigned long size)\n {\n \tdesc->buffer = buffer;\n \tdesc->size = size;\n+\tif (size)\n+\t\tdecode_tree_entry(desc, buffer, size);\n }\n \n void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1)\n@@ -36,78 +68,33 @@ static void entry_clear(struct name_entry *a)\n \n static void entry_extract(struct tree_desc *t, struct name_entry *a)\n {\n-\ta->sha1 = tree_entry_extract(t, &a->path, &a->mode);\n+\t*a = t->entry;\n }\n \n void update_tree_entry(struct tree_desc *desc)\n {\n \tconst void *buf = desc->buffer;\n+\tconst void *end = desc->entry.sha1 + 20;\n \tunsigned long size = desc->size;\n-\tint len = strlen(buf) + 1 + 20;\n+\tunsigned long len = end - buf;\n \n \tif (size < len)\n \t\tdie(\"corrupt tree file\");\n-\tdesc->buffer = (char *) buf + len;\n-\tdesc->size = size - len;\n-}\n-\n-static const char *get_mode(const char *str, unsigned int *modep)\n-{\n-\tunsigned char c;\n-\tunsigned int mode = 0;\n-\n-\twhile ((c = *str++) != ' ') {\n-\t\tif (c < '0' || c > '7')\n-\t\t\treturn NULL;\n-\t\tmode = (mode << 3) + (c - '0');\n-\t}\n-\t*modep = mode;\n-\treturn str;\n-}\n-\n-const unsigned char *tree_entry_extract(struct tree_desc *desc, const char **pathp, unsigned int *modep)\n-{\n-\tconst void *tree = desc->buffer;\n-\tunsigned long size = desc->size;\n-\tint len = strlen(tree)+1;\n-\tconst unsigned char *sha1 = (unsigned char *) tree + len;\n-\tconst char *path;\n-\tunsigned int mode;\n-\n-\tpath = get_mode(tree, &mode);\n-\tif (!path || size < len + 20)\n-\t\tdie(\"corrupt tree file\");\n-\t*pathp = path;\n-\t*modep = canon_mode(mode);\n-\treturn sha1;\n+\tbuf = end;\n+\tsize -= len;\n+\tdesc->buffer = buf;\n+\tdesc->size = size;\n+\tif (size)\n+\t\tdecode_tree_entry(desc, buf, size);\n }\n \n int tree_entry(struct tree_desc *desc, struct name_entry *entry)\n {\n-\tconst void *tree = desc->buffer;\n-\tconst char *path;\n-\tunsigned long len, size = desc->size;\n-\n-\tif (!size)\n+\tif (!desc->size)\n \t\treturn 0;\n \n-\tpath = get_mode(tree, &entry->mode);\n-\tif (!path)\n-\t\tdie(\"corrupt tree file\");\n-\n-\tentry->path = path;\n-\tlen = strlen(path);\n-\n-\tpath += len + 1;\n-\tentry->sha1 = (const unsigned char *) path;\n-\n-\tpath += 20;\n-\tlen = path - (char *) tree;\n-\tif (len > size)\n-\t\tdie(\"corrupt tree file\");\n-\n-\tdesc->buffer = path;\n-\tdesc->size = size - len;\n+\t*entry = desc->entry;\n+\tupdate_tree_entry(desc);\n \treturn 1;\n }\n \ndiff --git a/tree-walk.h b/tree-walk.h\nindex ca0c29f..43458cf 100644\n--- a/tree-walk.h\n+++ b/tree-walk.h\n@@ -1,17 +1,25 @@\n #ifndef TREE_WALK_H\n #define TREE_WALK_H\n \n-struct tree_desc {\n-\tconst void *buffer;\n-\tunsigned int size;\n-};\n-\n struct name_entry {\n \tconst unsigned char *sha1;\n \tconst char *path;\n \tunsigned int mode;\n };\n \n+struct tree_desc {\n+\tconst void *buffer;\n+\tstruct name_entry entry;\n+\tunsigned int size;\n+};\n+\n+static inline const unsigned char *tree_entry_extract(struct tree_desc *desc, const char **pathp, unsigned int *modep)\n+{\n+\t*pathp = desc->entry.path;\n+\t*modep = canon_mode(desc->entry.mode);\n+\treturn desc->entry.sha1;\n+}\n+\n static inline int tree_entry_len(const char *name, const unsigned char *sha1)\n {\n \treturn (char *)sha1 - (char *)name - 1;\n-- \n1.5.1.rc1.13.g0872-dirty\n"},{"id":"37691","messageId":"Pine.LNX.4.64.0703211130270.6730@woody.linux-foundation.org","threadId":"7347","inReplyTo":"Pine.LNX.4.64.0703210955370.6730@woody.linux-foundation.org","subject":"Resend: [PATCH 0/3] Clean up and optimize tree walking some more","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-21T18:32:06Z","receivedAt":"2007-03-21T18:32:06Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nHmm.. There may be something wrong with my isp and/or email setup, but I \nnever saw this one come back to me, so I'm re-sending just in case it got \nlost.. \n\n\t\tLinus\n\nOn Wed, 21 Mar 2007, Linus Torvalds wrote:\n> \n> This series of three patches improves blame performance on the eclipse \n> tree by about 15% in my tests by improving the tree walk a bit.\n> \n>   [ Before-best-of-five: 11.649s\n>     After-best-of-five:   9.675s ]\n> \n> The first two patches are just boring cleanups: the first removes an \n> unnecessary field from the \"name_entry\" structure, because I wanted to \n> embed it into the \"tree_desc\" one and it was just totally redundant and I \n> felt bad about growing tree_desc more than necessary. No real code \n> changes, just replacing the use of \"pathlen\" with the helper function we \n> introduced ealier (\"tree_entry_len()\").\n> \n> The second one just makes sure that we always initialize the tree_desc \n> structure with a helper function rather than doing it by hand. Again, this \n> doesn't actually change any code, although I changed the name of the \"buf\" \n> entry to \"buffer\", and the type of \"size\", so that we get nice compiler \n> warnings if they are used the old way by mistake.\n> \n> The second patch is the largest of the lot, but really doesn't do \n> anything interesting, just preparatory cleanup.\n> \n> The third patch is the one that actually changes any code, and is fairly \n> straightforward: it just switches around where we actually do the tree \n> entry parsing, which is now possible thanks to patch #2. By doing it \n> up-front, we only need to do it once (we used to have to do it both when \n> doing the \"extract\" *and* when doing the \"update\" op - now we do it only \n> once per entry, and \"extract\" is just about looking at the cached \n> contents).\n> \n> The resulting diffstat of the tree patches ends up removing a few more \n> lines than it adds (not by a lot), but perhaps more importantly (even more \n> than the performance advantage) the code looks nicer, I think.\n> \n>  builtin-fsck.c         |    5 +-\n>  builtin-grep.c         |   13 +++--\n>  builtin-pack-objects.c |    8 +--\n>  builtin-read-tree.c    |    3 +-\n>  builtin-reflog.c       |   10 ++--\n>  fetch.c                |    3 +-\n>  http-push.c            |    3 +-\n>  list-objects.c         |    3 +-\n>  merge-tree.c           |    9 ++--\n>  reachable.c            |    3 +-\n>  revision.c             |   12 ++---\n>  tree-diff.c            |   22 +++++----\n>  tree-walk.c            |  123 ++++++++++++++++++++++--------------------------\n>  tree-walk.h            |   20 ++++++--\n>  tree.c                 |   18 +++----\n>  unpack-trees.c         |    3 +-\n>  16 files changed, 125 insertions(+), 133 deletions(-)\n> \n> I'm pretty sure this is all good, and it obviously passes all the tests, \n> but more importantly none of the changes were really very complicated, and \n> patch#2 (which is the big one) was set up so that the compiler would not \n> even compile code that wasn't properly converted, so it should all be \n> good.\n> \n> \t\t\tLinus\n> \n"}]}