{"thread":{"id":"24865","subject":"[PATCHv2 0/8] Make rev-list --objects work with pathspecs; minor optimizations","startedAt":"2010-08-26T06:21:43Z","lastAt":"2010-08-27T17:28:24Z","messageCount":10,"participants":["Elijah Newren","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"149041","messageId":"1282803711-10253-1-git-send-email-newren@gmail.com","threadId":"24865","inReplyTo":null,"subject":"[PATCHv2 0/8] Make rev-list --objects work with pathspecs; minor optimizations","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2010-08-26T06:21:43Z","receivedAt":"2010-08-26T06:21:43Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series enables rev-list to produce a list of objects that is path\nlimited, when the user requests it.  It also provides a few small code\ncleanups and some small optimizations.\n\nChanges since last round:\n  * Patch 1 has two new testcase; one that triggered a bug I found,\n    and an interesting case Junio mentioned needed to work.\n  * Patch 2 will have fewer mallocs/frees in some cases (a suggestion\n    from Nguyen Thai Ngoc Duy), and corrects an issue from the first\n    series with how it calls tree_entry_interesting.\n  * Patch 3 is new; it adds a simple code comment that would have\n    alerted me to avoiding the bug in the first round of the series.\n  * Patches 4-8 are unchanged.\n\nAs before, the last two patches are weatherballons.  They can be\nsilently dropped.\n\nUpdated timings, for the curious:\n A git rev-list --quiet HEAD\n B git rev-list --quiet HEAD -- Documentation/\n C git rev-list --quiet HEAD -- t/\n D git rev-list --objects HEAD > /dev/null\n E git rev-list --objects HEAD -- Documentation/ > /dev/null\n F git rev-list --objects HEAD -- t/t9350-fast-export.sh > /dev/null\nResults:\n             A      B      C      D      E      F\nmaint       0.34   0.68   1.33   1.90   1.39   0.65\nPatch-1     0.34   0.68   1.33   1.90   1.38   0.65\nPatch-2     0.34   0.68   1.33   1.88   0.97   0.66\nPatch-3     0.34   0.68   1.33   1.88   0.97   0.65\nPatch-4     0.34   0.67   1.33   1.87   0.97   0.65\nPatch-5     0.34   0.68   1.33   1.88   0.97   0.65\nPatch-6     0.34   0.65   1.28   1.87   0.93   0.65\nPatch-7     0.34   0.65   1.29   1.86   0.94   0.65\nPatch-8     0.34   0.65   1.28   1.85   0.93   0.65\n\n\n\nElijah Newren (8):\n  Add testcases showing how pathspecs are ignored with rev-list\n    --objects\n  Make rev-list --objects work together with pathspecs\n  Document pre-condition for tree_entry_interesting\n  tree-walk: Correct bitrotted comment about tree_entry()\n  tree_entry_interesting(): Make return value more specific\n  diff_tree(): Skip skip_uninteresting() when all remaining paths\n    interesting\n  list-objects.c: Avoid recomputing interesting-ness for subtrees when\n    possible\n  tree-diff.c: Avoid recomputing interesting-ness for subtrees when\n    possible\n\n diff.h                   |    1 +\n list-objects.c           |   34 +++++++++++++++++++++++---\n revision.c               |    8 ++++-\n revision.h               |    3 +-\n t/t6000-rev-list-misc.sh |   51 +++++++++++++++++++++++++++++++++++++++\n tree-diff.c              |   60 +++++++++++++++++++++++----------------------\n tree-walk.h              |    4 ++-\n 7 files changed, 124 insertions(+), 37 deletions(-)\n create mode 100755 t/t6000-rev-list-misc.sh\n\n-- \n1.7.2.2.45.ga60f\n"},{"id":"149042","messageId":"1282803711-10253-2-git-send-email-newren@gmail.com","threadId":"24865","inReplyTo":"1282803711-10253-1-git-send-email-newren@gmail.com","subject":"[PATCHv2 1/8] Add testcases showing how pathspecs are ignored with rev-list --objects","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2010-08-26T06:21:44Z","receivedAt":"2010-08-26T06:21:44Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"\nSigned-off-by: Elijah Newren <newren@gmail.com>\n---\n t/t6000-rev-list-misc.sh |   51 ++++++++++++++++++++++++++++++++++++++++++++++\n 1 files changed, 51 insertions(+), 0 deletions(-)\n create mode 100755 t/t6000-rev-list-misc.sh\n\ndiff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh\nnew file mode 100755\nindex 0000000..a298f0d\n--- /dev/null\n+++ b/t/t6000-rev-list-misc.sh\n@@ -0,0 +1,51 @@\n+#!/bin/sh\n+\n+test_description='miscellaneous rev-list tests'\n+\n+. ./test-lib.sh\n+\n+test_expect_success setup '\n+\techo content1 > wanted_file &&\n+\techo content2 > unwanted_file &&\n+\tgit add wanted_file unwanted_file &&\n+\tgit commit -mone\n+'\n+\n+test_expect_failure 'rev-list --objects heeds pathspecs' '\n+\tgit rev-list --objects HEAD -- wanted_file >output &&\n+\tgrep wanted_file output &&\n+\t! grep unwanted_file output\n+'\n+\n+test_expect_failure 'rev-list --objects with pathspecs and deeper paths' '\n+\tmkdir foo &&\n+\t> foo/file &&\n+\tgit add foo/file &&\n+\tgit commit -mtwo &&\n+\n+\tgit rev-list --objects HEAD -- foo >output &&\n+\tgrep foo/file output &&\n+\n+\tgit rev-list --objects HEAD -- foo/file >output &&\n+\tgrep foo/file output &&\n+\t! grep unwanted_file output\n+'\n+\n+test_expect_failure 'rev-list --objects with pathspecs and copied files' '\n+\tgit checkout --orphan junio-testcase &&\n+\tgit rm -rf . &&\n+\n+\tmkdir two &&\n+\techo frotz >one &&\n+\tcp one two/three &&\n+\tgit add one two/three &&\n+\ttest_tick &&\n+\tgit commit -m that &&\n+\n+\tONE=$(git rev-parse HEAD:one)\n+\tgit rev-list --objects HEAD two >output &&\n+\tgrep \"$ONE two/three\" output &&\n+\t! grep one output\n+'\n+\n+test_done\n-- \n1.7.2.2.45.ga60f\n"},{"id":"149043","messageId":"1282803711-10253-3-git-send-email-newren@gmail.com","threadId":"24865","inReplyTo":"1282803711-10253-1-git-send-email-newren@gmail.com","subject":"[PATCHv2 2/8] Make rev-list --objects work together with pathspecs","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2010-08-26T06:21:45Z","receivedAt":"2010-08-26T06:21:45Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"When traversing commits, the selection of commits would heed the list of\npathspecs passed, but subsequent walking of the trees of those commits\nwould not.  This resulted in 'rev-list --objects HEAD -- <paths>'\ndisplaying objects at unwanted paths.\n\nHave process_tree() call tree_entry_interesting() to determine which paths\nare interesting and should be walked.\n\nNaturally, this change can provide a large speedup when paths are specified\ntogether with --objects, since many tree entries are now correctly ignored.\nInterestingly, though, this change also gives me a small (~1%) but\nrepeatable speedup even when no paths are specified with --objects.\n\nSigned-off-by: Elijah Newren <newren@gmail.com>\n---\n diff.h                   |    1 +\n list-objects.c           |   27 ++++++++++++++++++++++++++-\n revision.c               |    8 ++++++--\n revision.h               |    3 ++-\n t/t6000-rev-list-misc.sh |    6 +++---\n tree-diff.c              |    2 +-\n 6 files changed, 39 insertions(+), 8 deletions(-)\n\ndiff --git a/diff.h b/diff.h\nindex 6fff024..35130b8 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -169,6 +169,7 @@ extern int diff_tree_sha1(const unsigned char *old, const unsigned char *new,\n \t\t\t  const char *base, struct diff_options *opt);\n extern int diff_root_tree_sha1(const unsigned char *new, const char *base,\n                                struct diff_options *opt);\n+extern int tree_entry_interesting(struct tree_desc *desc, const char *base, int baselen, struct diff_options *opt);\n \n struct combine_diff_path {\n \tstruct combine_diff_path *next;\ndiff --git a/list-objects.c b/list-objects.c\nindex 8953548..bb95962 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -67,6 +67,9 @@ static void process_tree(struct rev_info *revs,\n \tstruct tree_desc desc;\n \tstruct name_entry entry;\n \tstruct name_path me;\n+\tint all_interesting = (revs->diffopt.nr_paths == 0);\n+\tchar *full_prefix = NULL;\n+\tint full_prefix_len = 0;\n \n \tif (!revs->tree_objects)\n \t\treturn;\n@@ -82,9 +85,30 @@ static void process_tree(struct rev_info *revs,\n \tme.elem = name;\n \tme.elem_len = strlen(name);\n \n+\tif (!all_interesting) {\n+\t\tfull_prefix = path_name_impl(path, name, 1);\n+\t\tfull_prefix_len = strlen(full_prefix);\n+\t}\n+\n \tinit_tree_desc(&desc, tree->buffer, tree->size);\n \n-\twhile (tree_entry(&desc, &entry)) {\n+\tfor (; desc.size; update_tree_entry(&desc)) {\n+\t\tentry = desc.entry;\n+\n+\t\tif (!all_interesting) {\n+\t\t\tint showit = tree_entry_interesting(&desc,\n+\t\t\t\t\t\t\t    full_prefix,\n+\t\t\t\t\t\t\t    full_prefix_len,\n+\t\t\t\t\t\t\t    &revs->diffopt);\n+\n+\t\t\tif (showit < 0)\n+\t\t\t\tbreak;\n+\t\t\telse if (!showit)\n+\t\t\t\tcontinue;\n+\t\t\telse if (showit == 2)\n+\t\t\t\tall_interesting = 1;\n+\t\t}\n+\n \t\tif (S_ISDIR(entry.mode))\n \t\t\tprocess_tree(revs,\n \t\t\t\t     lookup_tree(entry.sha1),\n@@ -97,6 +121,7 @@ static void process_tree(struct rev_info *revs,\n \t\t\t\t     lookup_blob(entry.sha1),\n \t\t\t\t     show, &me, entry.path);\n \t}\n+\tfree(full_prefix);\n \tfree(tree->buffer);\n \ttree->buffer = NULL;\n }\ndiff --git a/revision.c b/revision.c\nindex 7e82efd..64d8316 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -16,7 +16,7 @@\n \n volatile show_early_output_fn_t show_early_output;\n \n-char *path_name(const struct name_path *path, const char *name)\n+char *path_name_impl(const struct name_path *path, const char *name, int isdir)\n {\n \tconst struct name_path *p;\n \tchar *n, *m;\n@@ -27,7 +27,7 @@ char *path_name(const struct name_path *path, const char *name)\n \t\tif (p->elem_len)\n \t\t\tlen += p->elem_len + 1;\n \t}\n-\tn = xmalloc(len);\n+\tn = xmalloc(len + !!isdir);\n \tm = n + len - (nlen + 1);\n \tstrcpy(m, name);\n \tfor (p = path; p; p = p->up) {\n@@ -37,6 +37,10 @@ char *path_name(const struct name_path *path, const char *name)\n \t\t\tm[p->elem_len] = '/';\n \t\t}\n \t}\n+\tif (isdir && len > 1) {\n+\t\tn[len-1] = '/';\n+\t\tn[len] = '\\0';\n+\t}\n \treturn n;\n }\n \ndiff --git a/revision.h b/revision.h\nindex 36fdf22..5ecbeb0 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -172,7 +172,8 @@ struct name_path {\n \tconst char *elem;\n };\n \n-char *path_name(const struct name_path *path, const char *name);\n+char *path_name_impl(const struct name_path *path, const char *name, int isdir);\n+#define path_name(path, name) path_name_impl(path, name, 0)\n \n extern void add_object(struct object *obj,\n \t\t       struct object_array *p,\ndiff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh\nindex a298f0d..b6a7c9c 100755\n--- a/t/t6000-rev-list-misc.sh\n+++ b/t/t6000-rev-list-misc.sh\n@@ -11,13 +11,13 @@ test_expect_success setup '\n \tgit commit -mone\n '\n \n-test_expect_failure 'rev-list --objects heeds pathspecs' '\n+test_expect_success 'rev-list --objects heeds pathspecs' '\n \tgit rev-list --objects HEAD -- wanted_file >output &&\n \tgrep wanted_file output &&\n \t! grep unwanted_file output\n '\n \n-test_expect_failure 'rev-list --objects with pathspecs and deeper paths' '\n+test_expect_success 'rev-list --objects with pathspecs and deeper paths' '\n \tmkdir foo &&\n \t> foo/file &&\n \tgit add foo/file &&\n@@ -31,7 +31,7 @@ test_expect_failure 'rev-list --objects with pathspecs and deeper paths' '\n \t! grep unwanted_file output\n '\n \n-test_expect_failure 'rev-list --objects with pathspecs and copied files' '\n+test_expect_success 'rev-list --objects with pathspecs and copied files' '\n \tgit checkout --orphan junio-testcase &&\n \tgit rm -rf . &&\n \ndiff --git a/tree-diff.c b/tree-diff.c\nindex cd659c6..2fb670b 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -91,7 +91,7 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const\n  *  - zero for no\n  *  - negative for \"no, and no subsequent entries will be either\"\n  */\n-static int tree_entry_interesting(struct tree_desc *desc, const char *base, int baselen, struct diff_options *opt)\n+int tree_entry_interesting(struct tree_desc *desc, const char *base, int baselen, struct diff_options *opt)\n {\n \tconst char *path;\n \tconst unsigned char *sha1;\n-- \n1.7.2.2.45.ga60f\n"},{"id":"149044","messageId":"1282803711-10253-4-git-send-email-newren@gmail.com","threadId":"24865","inReplyTo":"1282803711-10253-1-git-send-email-newren@gmail.com","subject":"[PATCHv2 3/8] Document pre-condition for tree_entry_interesting","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2010-08-26T06:21:46Z","receivedAt":"2010-08-26T06:21:46Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"tree_entry_interesting will fail to find appropriate matches if the base\ndirectory path is not terminated with a slash.  Knowing this earlier would\nhave saved me some debugging time.\n\nSigned-off-by: Elijah Newren <newren@gmail.com>\n---\n tree-diff.c |    2 ++\n 1 files changed, 2 insertions(+), 0 deletions(-)\n\ndiff --git a/tree-diff.c b/tree-diff.c\nindex 2fb670b..75b1480 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -85,6 +85,8 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const\n /*\n  * Is a tree entry interesting given the pathspec we have?\n  *\n+ * Pre-condition: baselen == 0 || base[baselen-1] == '/'\n+ *\n  * Return:\n  *  - 2 for \"yes, and all subsequent entries will be\"\n  *  - 1 for yes\n-- \n1.7.2.2.45.ga60f\n"},{"id":"149047","messageId":"1282803711-10253-5-git-send-email-newren@gmail.com","threadId":"24865","inReplyTo":"1282803711-10253-1-git-send-email-newren@gmail.com","subject":"[PATCHv2 4/8] tree-walk: Correct bitrotted comment about tree_entry()","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2010-08-26T06:21:47Z","receivedAt":"2010-08-26T06:21:47Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"There was a code comment that referred to the \"above two functions\" but\nover time the functions immediately preceding the comment have changed.\nJust mention the relevant functions by name.\n\nSigned-off-by: Elijah Newren <newren@gmail.com>\n---\n tree-walk.h |    4 +++-\n 1 files changed, 3 insertions(+), 1 deletions(-)\n\ndiff --git a/tree-walk.h b/tree-walk.h\nindex 42110a4..a5175fa 100644\n--- a/tree-walk.h\n+++ b/tree-walk.h\n@@ -28,7 +28,9 @@ static inline int tree_entry_len(const char *name, const unsigned char *sha1)\n void update_tree_entry(struct tree_desc *);\n void init_tree_desc(struct tree_desc *desc, const void *buf, unsigned long size);\n \n-/* Helper function that does both of the above and returns true for success */\n+/* Helper function that does both tree_entry_extract() and update_tree_entry()\n+ * and returns true for success\n+ */\n int tree_entry(struct tree_desc *, struct name_entry *);\n \n void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1);\n-- \n1.7.2.2.45.ga60f\n"},{"id":"149046","messageId":"1282803711-10253-6-git-send-email-newren@gmail.com","threadId":"24865","inReplyTo":"1282803711-10253-1-git-send-email-newren@gmail.com","subject":"[PATCHv2 5/8] tree_entry_interesting(): Make return value more specific","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2010-08-26T06:21:48Z","receivedAt":"2010-08-26T06:21:48Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"tree_entry_interesting() can signal to its callers not only if the given\nentry matches one of the specified paths, but whether all remaining paths\nwill (or will not) match.  When no paths are specified, all paths are\nconsidered interesting, so intead of returning 1 (this path is interesting)\nreturn 2 (all paths are interesting).\n\nThis will allow the caller to avoid calling tree_entry_interesting() again,\nwhich theoretically should speed up tree walking.  I am not able to measure\nany actual gains in practice, but it certainly can not hurt and seems to\nmake the code more readable to me.\n\nSigned-off-by: Elijah Newren <newren@gmail.com>\n---\n tree-diff.c |    2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/tree-diff.c b/tree-diff.c\nindex 75b1480..bac5008 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -103,7 +103,7 @@ int tree_entry_interesting(struct tree_desc *desc, const char *base, int baselen\n \tint never_interesting = -1;\n \n \tif (!opt->nr_paths)\n-\t\treturn 1;\n+\t\treturn 2;\n \n \tsha1 = tree_entry_extract(desc, &path, &mode);\n \n-- \n1.7.2.2.45.ga60f\n"},{"id":"149045","messageId":"1282803711-10253-7-git-send-email-newren@gmail.com","threadId":"24865","inReplyTo":"1282803711-10253-1-git-send-email-newren@gmail.com","subject":"[PATCHv2 6/8] diff_tree(): Skip skip_uninteresting() when all remaining paths interesting","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2010-08-26T06:21:49Z","receivedAt":"2010-08-26T06:21:49Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"In 1d848f6 (tree_entry_interesting(): allow it to say \"everything is\ninteresting\" 2007-03-21), both show_tree() and skip_uninteresting() were\nmodified to determine if all remaining tree entries were interesting.\nHowever, the latter returns as soon as it finds the first interesting path,\nwithout any way to signal to its caller (namely, diff_tree()) that all\nremaining paths are interesting, making these extra checks useless.\n\nPass whether all remaining entries are interesting back to diff_tree(), and\nwhenever they are, have diff_tree() skip subsequent calls to\nskip_uninteresting().\n\nWith this change, I measure speedups of 3-4% for the commands\n  git rev-list --quiet HEAD -- Documentation/\n  git rev-list --quiet HEAD -- t/\nin git.git.\n\nSigned-off-by: Elijah Newren <newren@gmail.com>\n---\n tree-diff.c |   25 ++++++++++++-------------\n 1 files changed, 12 insertions(+), 13 deletions(-)\n\ndiff --git a/tree-diff.c b/tree-diff.c\nindex bac5008..d976bdf 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -259,19 +259,12 @@ static void show_entry(struct diff_options *opt, const char *prefix, struct tree\n \t}\n }\n \n-static void skip_uninteresting(struct tree_desc *t, const char *base, int baselen, struct diff_options *opt)\n+static void skip_uninteresting(struct tree_desc *t, const char *base, int baselen, struct diff_options *opt, int *all_interesting)\n {\n-\tint all_interesting = 0;\n \twhile (t->size) {\n-\t\tint show;\n-\n-\t\tif (all_interesting)\n-\t\t\tshow = 1;\n-\t\telse {\n-\t\t\tshow = tree_entry_interesting(t, base, baselen, opt);\n-\t\t\tif (show == 2)\n-\t\t\t\tall_interesting = 1;\n-\t\t}\n+\t\tint show = tree_entry_interesting(t, base, baselen, opt);\n+\t\tif (show == 2)\n+\t\t\t*all_interesting = 1;\n \t\tif (!show) {\n \t\t\tupdate_tree_entry(t);\n \t\t\tcontinue;\n@@ -286,14 +279,20 @@ static void skip_uninteresting(struct tree_desc *t, const char *base, int basele\n int diff_tree(struct tree_desc *t1, struct tree_desc *t2, const char *base, struct diff_options *opt)\n {\n \tint baselen = strlen(base);\n+\tint all_t1_interesting = 0;\n+\tint all_t2_interesting = 0;\n \n \tfor (;;) {\n \t\tif (DIFF_OPT_TST(opt, QUICK) &&\n \t\t    DIFF_OPT_TST(opt, HAS_CHANGES))\n \t\t\tbreak;\n \t\tif (opt->nr_paths) {\n-\t\t\tskip_uninteresting(t1, base, baselen, opt);\n-\t\t\tskip_uninteresting(t2, base, baselen, opt);\n+\t\t\tif (!all_t1_interesting)\n+\t\t\t\tskip_uninteresting(t1, base, baselen, opt,\n+\t\t\t\t\t\t   &all_t1_interesting);\n+\t\t\tif (!all_t2_interesting)\n+\t\t\t\tskip_uninteresting(t2, base, baselen, opt,\n+\t\t\t\t\t\t   &all_t2_interesting);\n \t\t}\n \t\tif (!t1->size) {\n \t\t\tif (!t2->size)\n-- \n1.7.2.2.45.ga60f\n"},{"id":"149048","messageId":"1282803711-10253-8-git-send-email-newren@gmail.com","threadId":"24865","inReplyTo":"1282803711-10253-1-git-send-email-newren@gmail.com","subject":"[PATCHv2 7/8] list-objects.c: Avoid recomputing interesting-ness for subtrees when possible","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2010-08-26T06:21:50Z","receivedAt":"2010-08-26T06:21:50Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Weather balloon patch.  Doesn't seem to help much in benchmarks; in fact\nI think it sometimes hurts a bit.  Is it worthwhile just in case someone\ncomes up with a ginormous tree that is really deep with few entries per\ntree?  I'm leaning against it, but am sending the patch to at least show\nothers that it has been considered.\n\n---\nNo signed-off-by, since I'm not sold on this patch and am somewhat leaning\nagainst it.  It would need a better commit message anyway.  :-)\n\n list-objects.c |    9 +++++----\n 1 files changed, 5 insertions(+), 4 deletions(-)\n\ndiff --git a/list-objects.c b/list-objects.c\nindex bb95962..488428b 100644\n--- a/list-objects.c\n+++ b/list-objects.c\n@@ -61,13 +61,13 @@ static void process_tree(struct rev_info *revs,\n \t\t\t struct tree *tree,\n \t\t\t show_object_fn show,\n \t\t\t struct name_path *path,\n-\t\t\t const char *name)\n+\t\t\t const char *name,\n+\t\t\t int all_interesting)\n {\n \tstruct object *obj = &tree->object;\n \tstruct tree_desc desc;\n \tstruct name_entry entry;\n \tstruct name_path me;\n-\tint all_interesting = (revs->diffopt.nr_paths == 0);\n \tchar *full_prefix = NULL;\n \tint full_prefix_len = 0;\n \n@@ -112,7 +112,8 @@ static void process_tree(struct rev_info *revs,\n \t\tif (S_ISDIR(entry.mode))\n \t\t\tprocess_tree(revs,\n \t\t\t\t     lookup_tree(entry.sha1),\n-\t\t\t\t     show, &me, entry.path);\n+\t\t\t\t     show, &me, entry.path,\n+\t\t\t\t     all_interesting);\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@@ -189,7 +190,7 @@ void traverse_commit_list(struct rev_info *revs,\n \t\t}\n \t\tif (obj->type == OBJ_TREE) {\n \t\t\tprocess_tree(revs, (struct tree *)obj, show_object,\n-\t\t\t\t     NULL, name);\n+\t\t\t\t     NULL, name, revs->diffopt.nr_paths == 0);\n \t\t\tcontinue;\n \t\t}\n \t\tif (obj->type == OBJ_BLOB) {\n-- \n1.7.2.2.45.ga60f\n"},{"id":"149049","messageId":"1282803711-10253-9-git-send-email-newren@gmail.com","threadId":"24865","inReplyTo":"1282803711-10253-1-git-send-email-newren@gmail.com","subject":"[PATCHv2 8/8] tree-diff.c: Avoid recomputing interesting-ness for subtrees when possible","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2010-08-26T06:21:51Z","receivedAt":"2010-08-26T06:21:51Z","isPatch":false,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Weather balloon patch.  Doesn't seem to help much in benchmarks, and after\nmany runs I think it might occasionally hurt slightly.  It ought to help\nin the case of a ginormous tree that is really deep with few entries per\ntree, but that case seems kind of contrived.\n\nKind of makes the code look icky too.\n\n---\nNo signed-off-by, since I'm not sold on this patch and am somewhat leaning\nagainst it.  It would need a better commit message anyway.  :-)\n\n tree-diff.c |   29 +++++++++++++++--------------\n 1 files changed, 15 insertions(+), 14 deletions(-)\n\ndiff --git a/tree-diff.c b/tree-diff.c\nindex d976bdf..ecae15e 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -25,9 +25,9 @@ static char *malloc_fullname(const char *base, int baselen, const char *path, in\n }\n \n static void show_entry(struct diff_options *opt, const char *prefix, struct tree_desc *desc,\n-\t\t       const char *base, int baselen);\n+\t\t       const char *base, int baselen, int all_interesting);\n \n-static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const char *base, int baselen, struct diff_options *opt)\n+static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const char *base, int baselen, struct diff_options *opt, int all_t1_interesting, int all_t2_interesting)\n {\n \tunsigned mode1, mode2;\n \tconst char *path1, *path2;\n@@ -42,11 +42,11 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const\n \tpathlen2 = tree_entry_len(path2, sha2);\n \tcmp = base_name_compare(path1, pathlen1, mode1, path2, pathlen2, mode2);\n \tif (cmp < 0) {\n-\t\tshow_entry(opt, \"-\", t1, base, baselen);\n+\t\tshow_entry(opt, \"-\", t1, base, baselen, all_t1_interesting);\n \t\treturn -1;\n \t}\n \tif (cmp > 0) {\n-\t\tshow_entry(opt, \"+\", t2, base, baselen);\n+\t\tshow_entry(opt, \"+\", t2, base, baselen, all_t2_interesting);\n \t\treturn 1;\n \t}\n \tif (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(sha1, sha2) && mode1 == mode2)\n@@ -57,8 +57,8 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const\n \t * file, we need to consider it a remove and an add.\n \t */\n \tif (S_ISDIR(mode1) != S_ISDIR(mode2)) {\n-\t\tshow_entry(opt, \"-\", t1, base, baselen);\n-\t\tshow_entry(opt, \"+\", t2, base, baselen);\n+\t\tshow_entry(opt, \"-\", t1, base, baselen, all_t1_interesting);\n+\t\tshow_entry(opt, \"+\", t2, base, baselen, all_t2_interesting);\n \t\treturn 0;\n \t}\n \n@@ -199,9 +199,8 @@ int tree_entry_interesting(struct tree_desc *desc, const char *base, int baselen\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, int baselen)\n+static void show_tree(struct diff_options *opt, const char *prefix, struct tree_desc *desc, const char *base, int baselen, int all_interesting)\n {\n-\tint all_interesting = 0;\n \twhile (desc->size) {\n \t\tint show;\n \n@@ -216,14 +215,14 @@ static void show_tree(struct diff_options *opt, const char *prefix, struct tree_\n \t\tif (show < 0)\n \t\t\tbreak;\n \t\tif (show)\n-\t\t\tshow_entry(opt, prefix, desc, base, baselen);\n+\t\t\tshow_entry(opt, prefix, desc, base, baselen, all_interesting);\n \t\tupdate_tree_entry(desc);\n \t}\n }\n \n /* A file entry went away or appeared */\n static void show_entry(struct diff_options *opt, const char *prefix, struct tree_desc *desc,\n-\t\t       const char *base, int baselen)\n+\t\t       const char *base, int baselen, int all_interesting)\n {\n \tunsigned mode;\n \tconst char *path;\n@@ -248,7 +247,7 @@ static void show_entry(struct diff_options *opt, const char *prefix, struct tree\n \t\t}\n \n \t\tinit_tree_desc(&inner, tree, size);\n-\t\tshow_tree(opt, prefix, &inner, newbase, baselen + 1 + pathlen);\n+\t\tshow_tree(opt, prefix, &inner, newbase, baselen + 1 + pathlen, all_interesting);\n \n \t\tfree(tree);\n \t\tfree(newbase);\n@@ -297,16 +296,18 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2, const char *base, stru\n \t\tif (!t1->size) {\n \t\t\tif (!t2->size)\n \t\t\t\tbreak;\n-\t\t\tshow_entry(opt, \"+\", t2, base, baselen);\n+\t\t\tshow_entry(opt, \"+\", t2, base, baselen, all_t2_interesting);\n \t\t\tupdate_tree_entry(t2);\n \t\t\tcontinue;\n \t\t}\n \t\tif (!t2->size) {\n-\t\t\tshow_entry(opt, \"-\", t1, base, baselen);\n+\t\t\tshow_entry(opt, \"-\", t1, base, baselen, all_t1_interesting);\n \t\t\tupdate_tree_entry(t1);\n \t\t\tcontinue;\n \t\t}\n-\t\tswitch (compare_tree_entry(t1, t2, base, baselen, opt)) {\n+\t\tswitch (compare_tree_entry(t1, t2, base, baselen, opt,\n+\t\t\t\t\t   all_t1_interesting,\n+\t\t\t\t\t   all_t2_interesting)) {\n \t\tcase -1:\n \t\t\tupdate_tree_entry(t1);\n \t\t\tcontinue;\n-- \n1.7.2.2.45.ga60f\n"},{"id":"149129","messageId":"7vr5hkhsnb.fsf@alter.siamese.dyndns.org","threadId":"24865","inReplyTo":"1282803711-10253-1-git-send-email-newren@gmail.com","subject":"Re: [PATCHv2 0/8] Make rev-list --objects work with pathspecs; minor optimizations","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-08-27T17:28:24Z","receivedAt":"2010-08-27T17:28:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Newren <newren@gmail.com> writes:\n\n> This series enables rev-list to produce a list of objects that is path\n> limited, when the user requests it.  It also provides a few small code\n> cleanups and some small optimizations.\n\nA cursory look didn't spot anything glaringly wrong ;-)\n\nI'd split 3-6 into a separate \"tree-walk-optim\" topic and keep the first\ntwo as \"object-list-with-pathspec\" topic.  They really look independent.\n\nThanks.\n"}]}