{"thread":{"id":"3179","subject":"[PATCH 0/3] Remove more parsers","startedAt":"2006-01-29T19:04:19Z","lastAt":"2006-01-31T22:07:30Z","messageCount":11,"participants":["Daniel Barkalow","Junio C Hamano","Linus Torvalds"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"15212","messageId":"Pine.LNX.4.64.0601291336420.25300@iabervon.org","threadId":"3179","inReplyTo":null,"subject":"[PATCH 0/3] Remove more parsers","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2006-01-29T19:04:19Z","receivedAt":"2006-01-29T19:04:19Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"I found some more open-coded tree parsers and a commit parser. These \nchanges shouldn't affect behavior meaningfully, and all of the tests pass. \nI did notice, however, that the rev-list functionality of pruning by path \nisn't actually tested in the tests; I forgot to update it and it didn't \ncause any tests to fail. I also couldn't figure out if \n\"same_tree_as_empty\" has important side effects, so I updated its use of \ndiff_tree; in order to do what the name says, \"return t1 && !t1->entries\" \nwould suffice.\n\nThere's also a parser in convert-objects, but it may be best to keep it, \nsince it may want to deal with things which are now considered invalid, \nand would be rejected by the normal parser.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"15214","messageId":"Pine.LNX.4.64.0601291404320.25300@iabervon.org","threadId":"3179","inReplyTo":"Pine.LNX.4.64.0601291336420.25300@iabervon.org","subject":"[PATCH 1/3] Use struct tree in tar-tree","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2006-01-29T19:04:59Z","receivedAt":"2006-01-29T19:04:59Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"It was using an open-coded tree parser; use a struct tree instead.\n\nSigned-off-by: Daniel Barkalow <barkalow@iabervon.org>\n\n---\n\n tar-tree.c |   48 +++++++++++++++++++++++-------------------------\n 1 files changed, 23 insertions(+), 25 deletions(-)\n\nd2a4152dfd1b79f32a28ca4b2deb202a4e928441\ndiff --git a/tar-tree.c b/tar-tree.c\nindex f749d4b..6219754 100644\n--- a/tar-tree.c\n+++ b/tar-tree.c\n@@ -3,6 +3,7 @@\n  */\n #include <time.h>\n #include \"cache.h\"\n+#include \"tree.h\"\n \n #define RECORDSIZE\t(512)\n #define BLOCKSIZE\t(RECORDSIZE * 20)\n@@ -334,40 +335,37 @@ static void write_header(const unsigned \n \twrite_if_needed();\n }\n \n-static void traverse_tree(void *buffer, unsigned long size,\n+static void traverse_tree(struct tree *tree,\n \t\t\t  struct path_prefix *prefix)\n {\n \tstruct path_prefix this_prefix;\n+\tstruct tree_entry_list *item;\n \tthis_prefix.prev = prefix;\n \n-\twhile (size) {\n-\t\tint namelen = strlen(buffer)+1;\n+\tparse_tree(tree);\n+\titem = tree->entries;\n+\n+\twhile (item) {\n \t\tvoid *eltbuf;\n \t\tchar elttype[20];\n \t\tunsigned long eltsize;\n-\t\tunsigned char *sha1 = buffer + namelen;\n-\t\tchar *path = strchr(buffer, ' ') + 1;\n-\t\tunsigned int mode;\n-\n-\t\tif (size < namelen + 20 || sscanf(buffer, \"%o\", &mode) != 1)\n-\t\t\tdie(\"corrupt 'tree' file\");\n-\t\tif (S_ISDIR(mode) || S_ISREG(mode))\n-\t\t\tmode |= (mode & 0100) ? 0777 : 0666;\n-\t\tbuffer = sha1 + 20;\n-\t\tsize -= namelen + 20;\n \n-\t\teltbuf = read_sha1_file(sha1, elttype, &eltsize);\n+\t\teltbuf = read_sha1_file(item->item.any->sha1, \n+\t\t\t\t\telttype, &eltsize);\n \t\tif (!eltbuf)\n-\t\t\tdie(\"cannot read %s\", sha1_to_hex(sha1));\n-\t\twrite_header(sha1, TYPEFLAG_AUTO, basedir, prefix, path,\n-\t\t             mode, eltbuf, eltsize);\n-\t\tif (!strcmp(elttype, \"tree\")) {\n-\t\t\tthis_prefix.name = path;\n-\t\t\ttraverse_tree(eltbuf, eltsize, &this_prefix);\n-\t\t} else if (!strcmp(elttype, \"blob\") && !S_ISLNK(mode)) {\n+\t\t\tdie(\"cannot read %s\", \n+\t\t\t    sha1_to_hex(item->item.any->sha1));\n+\t\twrite_header(item->item.any->sha1, TYPEFLAG_AUTO, basedir, \n+\t\t\t     prefix, item->name,\n+\t\t             item->mode, eltbuf, eltsize);\n+\t\tif (item->directory) {\n+\t\t\tthis_prefix.name = item->name;\n+\t\t\ttraverse_tree(item->item.tree, &this_prefix);\n+\t\t} else if (!item->symlink) {\n \t\t\twrite_blocked(eltbuf, eltsize);\n \t\t}\n \t\tfree(eltbuf);\n+\t\titem = item->next;\n \t}\n }\n \n@@ -404,6 +402,7 @@ int main(int argc, char **argv)\n \tunsigned char commit_sha1[20];\n \tvoid *buffer;\n \tunsigned long size;\n+\tstruct tree *tree;\n \n \tsetup_git_directory();\n \n@@ -425,8 +424,8 @@ int main(int argc, char **argv)\n \t\tarchive_time = commit_time(buffer, size);\n \t\tfree(buffer);\n \t}\n-\tbuffer = read_object_with_reference(sha1, \"tree\", &size, NULL);\n-\tif (!buffer)\n+\ttree = parse_tree_indirect(sha1);\n+\tif (!tree)\n \t\tdie(\"not a reference to a tag, commit or tree object: %s\",\n \t\t    sha1_to_hex(sha1));\n \tif (!archive_time)\n@@ -434,8 +433,7 @@ int main(int argc, char **argv)\n \tif (basedir)\n \t\twrite_header((unsigned char *)\"0\", TYPEFLAG_DIR, NULL, NULL,\n \t\t\tbasedir, 040777, NULL, 0);\n-\ttraverse_tree(buffer, size, NULL);\n-\tfree(buffer);\n+\ttraverse_tree(tree, NULL);\n \twrite_trailer();\n \treturn 0;\n }\n-- \n1.0.GIT\n"},{"id":"15213","messageId":"Pine.LNX.4.64.0601291405030.25300@iabervon.org","threadId":"3179","inReplyTo":"Pine.LNX.4.64.0601291336420.25300@iabervon.org","subject":"[PATCH 2/3] Use struct commit in tar-tree","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2006-01-29T19:05:20Z","receivedAt":"2006-01-29T19:05:20Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"It was open-coding getting the commit date from a commit.\n\nSigned-off-by: Daniel Barkalow <barkalow@iabervon>\n\n---\n\n tar-tree.c |   41 ++++++-----------------------------------\n 1 files changed, 6 insertions(+), 35 deletions(-)\n\nca523a725295fff6f1456cd7207f6b24f8c2e843\ndiff --git a/tar-tree.c b/tar-tree.c\nindex 6219754..d36baed 100644\n--- a/tar-tree.c\n+++ b/tar-tree.c\n@@ -4,6 +4,7 @@\n #include <time.h>\n #include \"cache.h\"\n #include \"tree.h\"\n+#include \"commit.h\"\n \n #define RECORDSIZE\t(512)\n #define BLOCKSIZE\t(RECORDSIZE * 20)\n@@ -369,39 +370,10 @@ static void traverse_tree(struct tree *t\n \t}\n }\n \n-/* get commit time from committer line of commit object */\n-static time_t commit_time(void * buffer, unsigned long size)\n-{\n-\ttime_t result = 0;\n-\tchar *p = buffer;\n-\n-\twhile (size > 0) {\n-\t\tchar *endp = memchr(p, '\\n', size);\n-\t\tif (!endp || endp == p)\n-\t\t\tbreak;\n-\t\t*endp = '\\0';\n-\t\tif (endp - p > 10 && !memcmp(p, \"committer \", 10)) {\n-\t\t\tchar *nump = strrchr(p, '>');\n-\t\t\tif (!nump)\n-\t\t\t\tbreak;\n-\t\t\tnump++;\n-\t\t\tresult = strtoul(nump, &endp, 10);\n-\t\t\tif (*endp != ' ')\n-\t\t\t\tresult = 0;\n-\t\t\tbreak;\n-\t\t}\n-\t\tsize -= endp - p - 1;\n-\t\tp = endp + 1;\n-\t}\n-\treturn result;\n-}\n-\n int main(int argc, char **argv)\n {\n \tunsigned char sha1[20];\n-\tunsigned char commit_sha1[20];\n-\tvoid *buffer;\n-\tunsigned long size;\n+\tstruct commit *commit;\n \tstruct tree *tree;\n \n \tsetup_git_directory();\n@@ -418,11 +390,10 @@ int main(int argc, char **argv)\n \t\tusage(tar_tree_usage);\n \t}\n \n-\tbuffer = read_object_with_reference(sha1, \"commit\", &size, commit_sha1);\n-\tif (buffer) {\n-\t\twrite_global_extended_header(commit_sha1);\n-\t\tarchive_time = commit_time(buffer, size);\n-\t\tfree(buffer);\n+\tcommit = lookup_commit_reference(sha1);\n+\tif (commit) {\n+\t\twrite_global_extended_header(commit->object.sha1);\n+\t\tarchive_time = commit->date;\n \t}\n \ttree = parse_tree_indirect(sha1);\n \tif (!tree)\n-- \n1.0.GIT\n"},{"id":"15215","messageId":"Pine.LNX.4.64.0601291405250.25300@iabervon.org","threadId":"3179","inReplyTo":"Pine.LNX.4.64.0601291336420.25300@iabervon.org","subject":"[PATCH 3/3] Use struct tree in diff-tree","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2006-01-29T19:05:46Z","receivedAt":"2006-01-29T19:05:46Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"It had been open-coding a tree parser. This updates the programs that\ncall diff_tree() to send it the struct tree instead of a buffer and\nsize.\n\nSigned-off-by: Daniel Barkalow\n\n---\n\n diff-tree.c |   13 ++----\n diff.h      |    9 +---\n rev-list.c  |   13 ------\n tree-diff.c |  123 ++++++++++++++++++++++++++---------------------------------\n 4 files changed, 63 insertions(+), 95 deletions(-)\n\n1530551cfd7dbecfe3258cab09b01f10a9b8549d\ndiff --git a/diff-tree.c b/diff-tree.c\nindex 6593a69..d64cba0 100644\n--- a/diff-tree.c\n+++ b/diff-tree.c\n@@ -49,18 +49,13 @@ static int diff_tree_sha1_top(const unsi\n static int diff_root_tree(const unsigned char *new, const char *base)\n {\n \tint retval;\n-\tvoid *tree;\n-\tstruct tree_desc empty, real;\n+\tstruct tree *real;\n \n-\ttree = read_object_with_reference(new, \"tree\", &real.size, NULL);\n-\tif (!tree)\n+\treal = parse_tree_indirect(new);\n+\tif (!real)\n \t\tdie(\"unable to read root tree (%s)\", sha1_to_hex(new));\n-\treal.buf = tree;\n \n-\tempty.buf = \"\";\n-\tempty.size = 0;\n-\tretval = diff_tree(&empty, &real, base, &diff_options);\n-\tfree(tree);\n+\tretval = diff_tree(NULL, real, base, &diff_options);\n \tcall_diff_flush();\n \treturn retval;\n }\ndiff --git a/diff.h b/diff.h\nindex 9a0169c..9142c04 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -4,15 +4,12 @@\n #ifndef DIFF_H\n #define DIFF_H\n \n+#include \"tree.h\"\n+\n #define DIFF_FILE_CANON_MODE(mode) \\\n \t(S_ISREG(mode) ? (S_IFREG | ce_permissions(mode)) : \\\n \tS_ISLNK(mode) ? S_IFLNK : S_IFDIR)\n \n-struct tree_desc {\n-\tvoid *buf;\n-\tunsigned long size;\n-};\n-\n struct diff_options;\n \n typedef void (*change_fn_t)(struct diff_options *options,\n@@ -51,7 +48,7 @@ struct diff_options {\n };\n \n extern void diff_tree_setup_paths(const char **paths);\n-extern int diff_tree(struct tree_desc *t1, struct tree_desc *t2,\n+extern int diff_tree(struct tree *t1, struct tree *t2,\n \t\t     const char *base, struct diff_options *opt);\n extern int diff_tree_sha1(const unsigned char *old, const unsigned char *new,\n \t\t\t  const char *base, struct diff_options *opt);\ndiff --git a/rev-list.c b/rev-list.c\nindex 0b142c1..86da74a 100644\n--- a/rev-list.c\n+++ b/rev-list.c\n@@ -485,23 +485,12 @@ static int compare_tree(struct tree *t1,\n static int same_tree_as_empty(struct tree *t1)\n {\n \tint retval;\n-\tvoid *tree;\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\", &real.size, NULL);\n-\tif (!tree)\n-\t\treturn 0;\n-\treal.buf = tree;\n-\n-\tempty.buf = \"\";\n-\tempty.size = 0;\n-\n \ttree_difference = 0;\n-\tretval = diff_tree(&empty, &real, \"\", &diff_opt);\n-\tfree(tree);\n+\tretval = diff_tree(NULL, t1, \"\", &diff_opt);\n \n \treturn retval >= 0 && !tree_difference;\n }\ndiff --git a/tree-diff.c b/tree-diff.c\nindex 382092b..c3526d1 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -3,38 +3,18 @@\n  */\n #include \"cache.h\"\n #include \"diff.h\"\n+#include \"tree.h\"\n \n // What paths are we interested in?\n static int nr_paths = 0;\n static const char **paths = NULL;\n static int *pathlens = NULL;\n \n-static void update_tree_entry(struct tree_desc *desc)\n+static const unsigned char *extract(struct tree_entry_list *desc, const char **pathp, unsigned int *modep)\n {\n-\tvoid *buf = desc->buf;\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 = buf + len;\n-\tdesc->size = size - len;\n-}\n-\n-static const unsigned char *extract(struct tree_desc *desc, const char **pathp, unsigned int *modep)\n-{\n-\tvoid *tree = desc->buf;\n-\tunsigned long size = desc->size;\n-\tint len = strlen(tree)+1;\n-\tconst unsigned char *sha1 = tree + len;\n-\tconst char *path = strchr(tree, ' ');\n-\tunsigned int mode;\n-\n-\tif (!path || size < len + 20 || sscanf(tree, \"%o\", &mode) != 1)\n-\t\tdie(\"corrupt tree file\");\n-\t*pathp = path+1;\n-\t*modep = DIFF_FILE_CANON_MODE(mode);\n-\treturn sha1;\n+\t*pathp = desc->name;\n+\t*modep = DIFF_FILE_CANON_MODE(desc->mode);\n+\treturn desc->item.any->sha1;\n }\n \n static char *malloc_base(const char *base, const char *path, int pathlen)\n@@ -47,9 +27,11 @@ static char *malloc_base(const char *bas\n \treturn newbase;\n }\n \n-static int show_entry(struct diff_options *opt, const char *prefix, struct tree_desc *desc, const char *base);\n+static int show_entry(struct diff_options *opt, const char *prefix, struct tree_entry_list *desc, const char *base);\n \n-static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const char *base, struct diff_options *opt)\n+static int compare_tree_entry(struct tree_entry_list *t1, \n+\t\t\t      struct tree_entry_list *t2, \n+\t\t\t      const char *base, struct diff_options *opt)\n {\n \tunsigned mode1, mode2;\n \tconst char *path1, *path2;\n@@ -99,7 +81,7 @@ static int compare_tree_entry(struct tre\n \treturn 0;\n }\n \n-static int interesting(struct tree_desc *desc, const char *base)\n+static int interesting(struct tree_entry_list *desc, const char *base)\n {\n \tconst char *path;\n \tunsigned mode;\n@@ -153,36 +135,36 @@ static int interesting(struct tree_desc \n }\n \n /* A whole sub-tree went away or appeared */\n-static void show_tree(struct diff_options *opt, const char *prefix, struct tree_desc *desc, const char *base)\n+static void show_tree(struct diff_options *opt, const char *prefix, \n+\t\t      struct tree *desc, const char *base)\n {\n-\twhile (desc->size) {\n-\t\tif (interesting(desc, base))\n-\t\t\tshow_entry(opt, prefix, desc, base);\n-\t\tupdate_tree_entry(desc);\n+\tstruct tree_entry_list *list;\n+\tparse_tree(desc);\n+\tlist = desc->entries;\n+\twhile (list) {\n+\t\tif (interesting(list, base))\n+\t\t\tshow_entry(opt, prefix, list, base);\n+\t\tlist = list->next;\n \t}\n }\n \n /* A file entry went away or appeared */\n-static int show_entry(struct diff_options *opt, const char *prefix, struct tree_desc *desc, const char *base)\n+static int show_entry(struct diff_options *opt, const char *prefix,\n+\t\t      struct tree_entry_list *desc, const char *base)\n {\n \tunsigned mode;\n \tconst char *path;\n \tconst unsigned char *sha1 = extract(desc, &path, &mode);\n \n-\tif (opt->recursive && S_ISDIR(mode)) {\n-\t\tchar type[20];\n+\tif (opt->recursive && desc->directory) {\n \t\tchar *newbase = malloc_base(base, path, strlen(path));\n-\t\tstruct tree_desc inner;\n-\t\tvoid *tree;\n+\t\tstruct tree *tree;\n \n-\t\ttree = read_sha1_file(sha1, type, &inner.size);\n-\t\tif (!tree || strcmp(type, \"tree\"))\n-\t\t\tdie(\"corrupt tree sha %s\", sha1_to_hex(sha1));\n+\t\ttree = desc->item.tree;\n \n-\t\tinner.buf = tree;\n-\t\tshow_tree(opt, prefix, &inner, newbase);\n+\t\tparse_tree(tree);\n+\t\tshow_tree(opt, prefix, tree, newbase);\n \n-\t\tfree(tree);\n \t\tfree(newbase);\n \t\treturn 0;\n \t}\n@@ -191,36 +173,46 @@ static int show_entry(struct diff_option\n \treturn 0;\n }\n \n-int diff_tree(struct tree_desc *t1, struct tree_desc *t2, const char *base, struct diff_options *opt)\n+int diff_tree(struct tree *tree1, struct tree *tree2, const char *base,\n+\t      struct diff_options *opt)\n {\n-\twhile (t1->size | t2->size) {\n-\t\tif (nr_paths && t1->size && !interesting(t1, base)) {\n-\t\t\tupdate_tree_entry(t1);\n+\tstruct tree_entry_list *t1 = NULL, *t2 = NULL;\n+\tif (tree1) {\n+\t\tparse_tree(tree1);\n+\t\tt1 = tree1->entries;\n+\t}\n+\tif (tree2) {\n+\t\tparse_tree(tree2);\n+\t\tt2 = tree2->entries;\n+\t}\n+\twhile (t1 || t2) {\n+\t\tif (nr_paths && t1 && !interesting(t1, base)) {\n+\t\t\tt1 = t1->next;\n \t\t\tcontinue;\n \t\t}\n-\t\tif (nr_paths && t2->size && !interesting(t2, base)) {\n-\t\t\tupdate_tree_entry(t2);\n+\t\tif (nr_paths && t2 && !interesting(t2, base)) {\n+\t\t\tt2 = t2->next;\n \t\t\tcontinue;\n \t\t}\n-\t\tif (!t1->size) {\n+\t\tif (!t1) {\n \t\t\tshow_entry(opt, \"+\", t2, base);\n-\t\t\tupdate_tree_entry(t2);\n+\t\t\tt2 = t2->next;\n \t\t\tcontinue;\n \t\t}\n-\t\tif (!t2->size) {\n+\t\tif (!t2) {\n \t\t\tshow_entry(opt, \"-\", t1, base);\n-\t\t\tupdate_tree_entry(t1);\n+\t\t\tt1 = t1->next;\n \t\t\tcontinue;\n \t\t}\n \t\tswitch (compare_tree_entry(t1, t2, base, opt)) {\n \t\tcase -1:\n-\t\t\tupdate_tree_entry(t1);\n+\t\t\tt1 = t1->next;\n \t\t\tcontinue;\n \t\tcase 0:\n-\t\t\tupdate_tree_entry(t1);\n+\t\t\tt1 = t1->next;\n \t\t\t/* Fallthrough */\n \t\tcase 1:\n-\t\t\tupdate_tree_entry(t2);\n+\t\t\tt2 = t2->next;\n \t\t\tcontinue;\n \t\t}\n \t\tdie(\"git-diff-tree: internal error\");\n@@ -230,21 +222,16 @@ int diff_tree(struct tree_desc *t1, stru\n \n int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)\n {\n-\tvoid *tree1, *tree2;\n-\tstruct tree_desc t1, t2;\n+\tstruct tree *t1, *t2;\n \tint retval;\n \n-\ttree1 = read_object_with_reference(old, \"tree\", &t1.size, NULL);\n-\tif (!tree1)\n+\tt1 = parse_tree_indirect(old);\n+\tif (!t1)\n \t\tdie(\"unable to read source tree (%s)\", sha1_to_hex(old));\n-\ttree2 = read_object_with_reference(new, \"tree\", &t2.size, NULL);\n-\tif (!tree2)\n+\tt2 = parse_tree_indirect(new);\n+\tif (!t2)\n \t\tdie(\"unable to read destination tree (%s)\", sha1_to_hex(new));\n-\tt1.buf = tree1;\n-\tt2.buf = tree2;\n-\tretval = diff_tree(&t1, &t2, base, opt);\n-\tfree(tree1);\n-\tfree(tree2);\n+\tretval = diff_tree(t1, t2, base, opt);\n \treturn retval;\n }\n \n-- \n1.0.GIT\n"},{"id":"15224","messageId":"7vk6ciixv0.fsf@assigned-by-dhcp.cox.net","threadId":"3179","inReplyTo":"Pine.LNX.4.64.0601291336420.25300@iabervon.org","subject":"Re: [PATCH 0/3] Remove more parsers","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-01-29T20:26:59Z","receivedAt":"2006-01-29T20:26:59Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I do not have objections to git-tar-tree changes, but I am\nhesitant to use the tree parser in diff-tree due to its memory\nretention behaviour.  We already use the commit parser in\ndiff-tree but I think we currently do not ask for the tree part\nof the object to be parsed.  I suspect this patch would badly\ninteract with long-running \"diff-tree --stdin\", which is the\nworkhorse of whatchanged.  I haven't benched it though, and I'd\nbe happy to see the impact is proven to be negligible.\n"},{"id":"15229","messageId":"Pine.LNX.4.64.0601291645060.25300@iabervon.org","threadId":"3179","inReplyTo":"7vk6ciixv0.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 0/3] Remove more parsers","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2006-01-29T22:05:22Z","receivedAt":"2006-01-29T22:05:22Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Sun, 29 Jan 2006, Junio C Hamano wrote:\n\n> I do not have objections to git-tar-tree changes, but I am\n> hesitant to use the tree parser in diff-tree due to its memory\n> retention behaviour.  We already use the commit parser in\n> diff-tree but I think we currently do not ask for the tree part\n> of the object to be parsed.  I suspect this patch would badly\n> interact with long-running \"diff-tree --stdin\", which is the\n> workhorse of whatchanged.  I haven't benched it though, and I'd\n> be happy to see the impact is proven to be negligible.\n\nI'll look into discarding the struct trees after use (since we're not \nkeeping flags on them, or storing references to them long-term), so we can \nuse the same parser without worse memory behavior. It does seem to take a \nbunch more memory (and, oddly, be very slow) as I currently have it.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"15304","messageId":"Pine.LNX.4.64.0601310846380.7301@g5.osdl.org","threadId":"3179","inReplyTo":"Pine.LNX.4.64.0601291405250.25300@iabervon.org","subject":"Re: [PATCH 3/3] Use struct tree in diff-tree","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-01-31T16:53:53Z","receivedAt":"2006-01-31T16:53:53Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 29 Jan 2006, Daniel Barkalow wrote:\n>\n> It had been open-coding a tree parser. This updates the programs that\n> call diff_tree() to send it the struct tree instead of a buffer and\n> size.\n\nPlease don't.\n\nparse_tree() is extremely broken, and expensive. \n\nThe \"struct tree_desc\" is a much better abstraction, and avoids all \noverhead. Yes, it's slightly more opaque, and the interfaces could be \nimproved: for example, instead of having a\n\n\tdesc.buf = read_object_with_reference(new, \"tree\", &desc.size, NULL);\n\tif (!desc.buf)\n\t\tdie(\"unable to read tree\");\n\nit might make make sense to introduce a function that does this for you, \nie just a\n\n\tif (populate_tree_descriptor(new, &desc) < 0)\n\t\tdie(\"unable to read tree\");\n\t...\n\tfree_tree_descriptor(&desc);\n\nwhich is perhaps more readable and maintainable.\n\nThe \"diff_tree()\" functions are _extremely_ performance-critical, arguably \nmore so than _any_ other part of git. Diffing two trees is one of _the_ \nmost common operations, especially so when you want to follow just a \nsubset of files with \"git-rev-list -- <filename>*\", and it's extremely \nimportant that you don't do malloc()/free() all the time.\n\nSo using \"struct tree\" and the general tree-parsing functions is _wrong_. \nReally REALLY wrong.\n\n>From what I can tell, your version doesn't even do the \"free()\". Which \nprobably means that not only is it slower, but I bet that if you have a \nbig repository like the kernel, and you do a slightly more complex \ngit-rev-list with multiple files, you'll use up tons and tons and tons of \nmemory.\n\nJunio, please don't apply this.\n\n\t\tLinus\n"},{"id":"15306","messageId":"Pine.LNX.4.64.0601310905000.7301@g5.osdl.org","threadId":"3179","inReplyTo":"Pine.LNX.4.64.0601291645060.25300@iabervon.org","subject":"Re: [PATCH 0/3] Remove more parsers","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-01-31T17:16:00Z","receivedAt":"2006-01-31T17:16:00Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 29 Jan 2006, Daniel Barkalow wrote:\n> \n> I'll look into discarding the struct trees after use (since we're not \n> keeping flags on them, or storing references to them long-term), so we can \n> use the same parser without worse memory behavior. It does seem to take a \n> bunch more memory (and, oddly, be very slow) as I currently have it.\n\nReally, trying to use \"struct tree\" just is _broken_.\n\nEven if you start freeing the memory, performance will absolutely _suck_. \nYou'll be using a \"malloc()\" (and eventually, a \"free()\") and copying the \ntree entries around for absolutely zero gain. You'll make things follow \npointers and have indirection, instead of just walking the data structure \ndirectly.\n\nIOW, it will be about ten times more expensive in CPU time, in the most \nperformance-critical part of git.\n\nI would actually argue that if you want to use a common structure, try to \nconvert existing users of \"struct tree\" to the \"struct tree_desc\" \niterators. Yes, their use is a little awkward, but there's really no way \nyou can use anything but the fast ones for tree diffing.\n\nThe \"struct tree_desc\" can only be used for traversing a tree linearly in \none order, but I bet that nobody really ever does anything else.\n\nTo make \"struct tree_desc\" more generic, you'd obviously have to export \nthe \"update_tree_entry()\" and \"extract()\" functions (and the latter would \nprobably need to be re-named to \"extract_tree_entry()\").\n\nOh, and to make freeign the tree entry a bit simpler, you'd probably want \nto replace\n\n\tvoid *buf\n\tunsigned int size;\n\nwith a\n\n\tconst void *const tree_base;\n\tconst unsigned int tree_size;\n\tunsigned int offset;\n\nso that you'd just update \"offset\" and leave tree_base/size untouched (to \nmake freeing easier - right now the person who populates the \"struct \ntree_desc\" has to free the thing by hand).\n\n\t\tLinus\n"},{"id":"15330","messageId":"7virs0uma8.fsf@assigned-by-dhcp.cox.net","threadId":"3179","inReplyTo":"Pine.LNX.4.64.0601310846380.7301@g5.osdl.org","subject":"Re: [PATCH 3/3] Use struct tree in diff-tree","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-01-31T21:20:47Z","receivedAt":"2006-01-31T21:20:47Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> On Sun, 29 Jan 2006, Daniel Barkalow wrote:\n>>\n>> It had been open-coding a tree parser. This updates the programs that\n>> call diff_tree() to send it the struct tree instead of a buffer and\n>> size.\n>\n> Please don't.\n> ...\n> Junio, please don't apply this.\n>\n> \t\tLinus\n\nI haven't, and I won't.  From my gut feeling I did not even\nplace it in \"pu\".  After timing it myself and then looking at\nthe code I agree with your analysis.\n\nThe one to git-tar-tree I've already applied, mostly because I\nwas not careful enough and especially I did not care enough\nabout performance of that program.  On my slow machine the tip\nof kernel before you came back takes 9.2 seconds wallclock as\nopposed to 8.7 seconds to tar up, so the patch degrades the\nperformance by about 5%.  Maybe we would want to revert that one\nas well.\n"},{"id":"15333","messageId":"Pine.LNX.4.64.0601311626070.25300@iabervon.org","threadId":"3179","inReplyTo":"7virs0uma8.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 3/3] Use struct tree in diff-tree","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2006-01-31T21:49:38Z","receivedAt":"2006-01-31T21:49:38Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Tue, 31 Jan 2006, Junio C Hamano wrote:\n\n> Linus Torvalds <torvalds@osdl.org> writes:\n> \n> > On Sun, 29 Jan 2006, Daniel Barkalow wrote:\n> >>\n> >> It had been open-coding a tree parser. This updates the programs that\n> >> call diff_tree() to send it the struct tree instead of a buffer and\n> >> size.\n> >\n> > Please don't.\n> > ...\n> > Junio, please don't apply this.\n> >\n> > \t\tLinus\n> \n> I haven't, and I won't.  From my gut feeling I did not even\n> place it in \"pu\".  After timing it myself and then looking at\n> the code I agree with your analysis.\n> \n> The one to git-tar-tree I've already applied, mostly because I\n> was not careful enough and especially I did not care enough\n> about performance of that program.  On my slow machine the tip\n> of kernel before you came back takes 9.2 seconds wallclock as\n> opposed to 8.7 seconds to tar up, so the patch degrades the\n> performance by about 5%.  Maybe we would want to revert that one\n> as well.\n\nProbably a better solution is to move the tree parser from tree-diff.c \ninto tree.c, provide a clear API in tree.h, and use that in tar-tree. \nThere's definitely no need to have another parser beyond the one \ncurrently in tree-diff and the struct tree one.\n\nI think I should be able to change the struct tree API slightly to make it \nan iterator instead of a linked list, and get the efficiency benefits of \nthe tree-diff parser while still having a nice API.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"15337","messageId":"Pine.LNX.4.64.0601311337500.7301@g5.osdl.org","threadId":"3179","inReplyTo":"7virs0uma8.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 3/3] Use struct tree in diff-tree","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-01-31T22:07:30Z","receivedAt":"2006-01-31T22:07:30Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 31 Jan 2006, Junio C Hamano wrote:\n> \n> The one to git-tar-tree I've already applied, mostly because I\n> was not careful enough and especially I did not care enough\n> about performance of that program.  On my slow machine the tip\n> of kernel before you came back takes 9.2 seconds wallclock as\n> opposed to 8.7 seconds to tar up, so the patch degrades the\n> performance by about 5%.  Maybe we would want to revert that one\n> as well.\n\nHmm. Rather than revert it outright, it might be better to make it use the \nnicer parsing functions and \"struct tree_desc\".\n\nIt shouldn't look _that_ different from the \"struct tree\" version: instead \nof doing\n\n\titem = item->next;\n\nit would do\n\n\tupdate_tree_entry(tree);\n\ninstead.\n\nGive me a minute, I'll send you patches.\n\n\t\tLinus\n"}]}