{"thread":{"id":"7301","subject":"Set up for better tree diff optimizations","startedAt":"2007-03-18T22:18:30Z","lastAt":"2007-03-22T00:00:27Z","messageCount":8,"participants":["Linus Torvalds","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"37415","messageId":"Pine.LNX.4.64.0703181506570.6730@woody.linux-foundation.org","threadId":"7301","inReplyTo":null,"subject":"Set up for better tree diff optimizations","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-18T22:18:30Z","receivedAt":"2007-03-18T22:18:30Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis is mainly just a cleanup patch, and sets up for later changes where \nthe tree-diff.c \"interesting()\" function can return more than just a \nyes/no value.\n\nIn particular, it should be quite possible to say \"no subsequent entries \nin this tree can possibly be interesting any more\", and thus allow the \ncallers to short-circuit the tree entirely.\n\nIn fact, changing the callers to do so is trivial, and is really all this \npatch really does, because changing \"interesting()\" itself to say that \nnothing further is going to be interesting is definitely more complicated, \nconsidering that we may have arbitrary pathspecs.\n\nBut in cleaning up the callers, this actually fixes a potential small \nperformance issue in diff_tree(): if the second tree has a lot of \nuninterestign crud in it, we would keep on doing the \"is it interesting?\" \ncheck on the first tree for each uninteresting entry in the second one. \n\nThe answer is obviously not going to change, so that was just not helping. \nThe new code is clearer and simpler and avoids this issue entirely.\n\nI also renamed \"interesting()\" to \"tree_entry_interesting()\", because I \ngot frustrated by the fact that \n\n - we actually had *another* function called \"interesting()\" in another \n   file, and I couldn't tell from the profiles which one was the one that \n   mattered more.\n\n - when rewriting it to return a ternary value, you can't just do\n\n\tif (interesting(...))\n\t\t...\n\n   any more, but want to assign the return value to a local variable. The \n   name of choice for that variable would normally be \"interesting\", so \n   I just wanted to make the function name be more specific, and avoid \n   that whole issue (even though I then didn't choose that name for either \n   of the users, just to avoid confusion in the patch itself ;)\n\nIn other words, this doesn't really change anything, but I think it's a \ngood thing to do, and if somebody comes along and writes the logic for \n\"yeah, none of the pathspecs you have are interesting\", we now support \nthat trivially.\n\nIt could easily be a meaningful optimization for things like \"blame\", \nwhere there's just one pathspec, and stopping when you've seen it would \nallow you to avoid about 50% of the tree traversals on average.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n\nJunio, your decision.\n\n tree-diff.c |   44 ++++++++++++++++++++++++++++++++++----------\n 1 files changed, 34 insertions(+), 10 deletions(-)\n\ndiff --git a/tree-diff.c b/tree-diff.c\nindex f89b9d3..2e0a3ae 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -66,7 +66,15 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const\n \treturn 0;\n }\n \n-static int interesting(struct tree_desc *desc, const char *base, int baselen, struct diff_options *opt)\n+/*\n+ * Is a tree entry interesting given the pathspec we have?\n+ *\n+ * Return:\n+ *  - positive for yes\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 {\n \tconst char *path;\n \tconst unsigned char *sha1;\n@@ -123,7 +131,10 @@ static int interesting(struct tree_desc *desc, const char *base, int baselen, st\n static void show_tree(struct diff_options *opt, const char *prefix, struct tree_desc *desc, const char *base, int baselen)\n {\n \twhile (desc->size) {\n-\t\tif (interesting(desc, base, baselen, opt))\n+\t\tint show = tree_entry_interesting(desc, base, baselen, opt);\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\tupdate_tree_entry(desc);\n \t}\n@@ -158,20 +169,33 @@ 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+{\n+\twhile (t->size) {\n+\t\tint show = tree_entry_interesting(t, base, baselen, opt);\n+\t\tif (!show) {\n+\t\t\tupdate_tree_entry(t);\n+\t\t\tcontinue;\n+\t\t}\n+\t\t/* Skip it all? */\n+\t\tif (show < 0)\n+\t\t\tt->size = 0;\n+\t\treturn;\n+\t}\n+}\n+\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 \n-\twhile (t1->size | t2->size) {\n-\t\tif (opt->nr_paths && t1->size && !interesting(t1, base, baselen, opt)) {\n-\t\t\tupdate_tree_entry(t1);\n-\t\t\tcontinue;\n-\t\t}\n-\t\tif (opt->nr_paths && t2->size && !interesting(t2, base, baselen, opt)) {\n-\t\t\tupdate_tree_entry(t2);\n-\t\t\tcontinue;\n+\tfor (;;) {\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}\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\tupdate_tree_entry(t2);\n \t\t\tcontinue;\n"},{"id":"37659","messageId":"7vircv3wfc.fsf@assigned-by-dhcp.cox.net","threadId":"7301","inReplyTo":"Pine.LNX.4.64.0703181506570.6730@woody.linux-foundation.org","subject":"Re: Set up for better tree diff optimizations","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-21T07:09:11Z","receivedAt":"2007-03-21T07:09:11Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> This is mainly just a cleanup patch, and sets up for later changes where \n> the tree-diff.c \"interesting()\" function can return more than just a \n> yes/no value.\n>\n> In particular, it should be quite possible to say \"no subsequent entries \n> in this tree can possibly be interesting any more\", and thus allow the \n> callers to short-circuit the tree entirely.\n>\n> In fact, changing the callers to do so is trivial, and is really all this \n> patch really does, because changing \"interesting()\" itself to say that \n> nothing further is going to be interesting is definitely more complicated, \n> considering that we may have arbitrary pathspecs.\n> ...\n> Junio, your decision.\n\nSorry, as I was sick and spent almost all day in bed, I am\nsomewhat behind going through the mailing list backlog.\n\n>  tree-diff.c |   44 ++++++++++++++++++++++++++++++++++----------\n>  1 files changed, 34 insertions(+), 10 deletions(-)\n>\n> diff --git a/tree-diff.c b/tree-diff.c\n> index f89b9d3..2e0a3ae 100644\n> --- a/tree-diff.c\n> +++ b/tree-diff.c\n> @@ -66,7 +66,15 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const\n>  \treturn 0;\n>  }\n>  \n> -static int interesting(struct tree_desc *desc, const char *base, int baselen, struct diff_options *opt)\n> +/*\n> + * Is a tree entry interesting given the pathspec we have?\n> + *\n> + * Return:\n> + *  - positive for yes\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>  {\n>  \tconst char *path;\n>  \tconst unsigned char *sha1;\n\nI've already applied the patch, but I do not know how much this\ninterface would help, as the only easy case the function\ntree_entry_interesting() can say \"no subsequent entries will be\neither\" without looking ahead is where no pathspecs match the\nbase, but that is already prevented by the way you walk the tree\n(you do not descend into an uninteresting tree).\n\nIf you do:\n\n\t$ git log arch/i386/ include/asm-i386/\n\nand if the traversal is already in arch/i386/crypto, then it is\nunnecessary to check if a path discovered during the traversal\nis interesting, as the base (\"arch/i386/crypto\") for all the\nentries in that subdirectory is already covered by one of the\npathspecs (\"arch/i386\").  It also means checking the other\npathspec \"include/asm-i386/\" is a waste of time, because that\nwill not match the base no matter what path is discovered from\nthe tree object anyway.\n\nI suspect that two possible optimizations are:\n\n (1) instead of, or in addition to, allowing it to say \"no\n     subsequent ones will match\", allow it to say \"everything\n     for this base will be interesting, stop bothering to ask me\n     one path at a time\".\n\n (2) mark include/asm-i386/ pathspec to be N/A while we are\n     already in arch/i386/crypto, as we already know it will\n     never match.  And remove that mark when we come back from\n     that recursion.\n"},{"id":"37674","messageId":"Pine.LNX.4.64.0703210812590.6730@woody.linux-foundation.org","threadId":"7301","inReplyTo":"7vircv3wfc.fsf@assigned-by-dhcp.cox.net","subject":"Re: Set up for better tree diff optimizations","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-21T15:20:50Z","receivedAt":"2007-03-21T15:20:50Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 21 Mar 2007, Junio C Hamano wrote:\n> \n> I've already applied the patch, but I do not know how much this\n> interface would help, as the only easy case the function\n> tree_entry_interesting() can say \"no subsequent entries will be\n> either\" without looking ahead is where no pathspecs match the\n> base, but that is already prevented by the way you walk the tree\n> (you do not descend into an uninteresting tree).\n\nNo. You miss the important case.\n\n> If you do:\n> \n> \t$ git log arch/i386/ include/asm-i386/\n\nRight. Forget about the paths we're *interested* in. \n\nLook at the ones we're *not* interested in!\n\nAt the top level, what's the tree? It looks like this:\n\n\t100644 blob 060a71d41ad7ccc3214065a182e6f67568420071    .gitignore\n\t100644 blob bf62dbea88e613d8a22a6f9977289b4eb2eb968b    .mailmap\n\t100644 blob ca442d313d86dc67e0a2e5d584b465bd382cbf5c    COPYING\n\t100644 blob 6bd8ab86b5bd1b80f2df2ceaf0a4f8d7634639a0    CREDITS\n\t040000 tree 14499497d9d170b046e5cf9aafeec76647ece9a3    Documentation\n\t100644 blob 0451f69353bad4d07de34fd4658f40b805bd467a    Kbuild\n\t100644 blob 6d8d5b917d1fe0f4ff011d738ca9d13947521eb8    MAINTAINERS\n\t100644 blob 1c018c468e153ac85079f90a209a9bb3a09c5671    Makefile\n\t100644 blob 159912cf515549455ed5f579b8825d28962bd22e    README\n\t100644 blob ac02e42a2627f359575ae0e689afca911a75e0ff    REPORTING-BUGS\n\t040000 tree 46262adf3cfb89b4028a2d4beb17d9089e26902f    arch\n\t040000 tree 45d8a2724b4414f7fc3a2dac66929fdf0d032986    block\n\t040000 tree 21696299da054c8ad04c5fc87f21ecc4a7d0e464    crypto\n\t040000 tree ff75402a4a48101c95e9dc820c7c822767ca2ac3    drivers\n\t040000 tree 734d24c7dcfbe8d9b03045aebc2148f92c5f4607    fs\n\t040000 tree e3d0731913e852e7f256af5b6a3cd50bea8d4993    include\n\t040000 tree e39426d7179d961d96e27f7250fb16a483cc17db    init\n\t040000 tree 0438f8748d21ad402d305bf469b27f59bc1300b9    ipc\n\t040000 tree dc33b0bd31bdf49aaa04f3357f20bb1a189bac4a    kernel\n\t040000 tree 7cfb510f6854fe8c51f15fefbedda66773c0f23a    lib\n\t040000 tree cfb673c385e328bbdefb60c3ce59c8f3ba7f215e    mm\n\t040000 tree 30550e7a0676fe13a2e48d5f3c3872112e9634d2    net\n\t040000 tree 5194f3b70deaa7f98cadfeca300fd140b1086409    scripts\n\t040000 tree 164b706596d177b15750eb0da157758397195885    security\n\t040000 tree e5d9e19873759dcccd45dde4d76a0ad75db8fe5c    sound\n\t040000 tree 09109a71d77e211a4253fdde8afec7f119055e3b    usr\n\nAnd with your pathspec, we can tell after we see \"init\", that we're not \ninterested in any of the rest. In other words, we could consistently skip \nand not even parse almost 50% of the top-level tree.\n\nAnd if you only have the first path-spec (\"arch/i386\") you could skip \neverything after you've seen \"block\", because you know that the rest of \nthe tree simply isn't interesting any more.\n\nSimilarly, look at what happens (with your two-entry pathspec) when you \nenter \"arch\". Obviously the \"include\" thing will be totally uninteresting, \nso as far as that one is concerned, you can skip the *whole* thing, but \nbecause we have multiple path-specs we need to skip only when *both* \ndecide that it's uninteresting. So look at the \"arch\" sub-tree, and we \nhave\n\n\talpha\n\tarm\n\tarm26\n\tavr32\n\tcris\n\tfrv\n\th8300\n\ti386\n\tia64\n\tm32r\n\tm68k\n\tm68knommu\n\tmips\n\tparisc\n\tpowerpc\n\tppc\n\ts390\n\tsh\n\tsh64\n\tsparc\n\tsparc64\n\tum\n\tv850\n\tx86_64\n\txtensa\n\nand again, when we hit ia64, we *could* return -1, because \"include\" is \ntotally uninteresting for all of it, and the \"arch/i386/\" pathspec can \ntell that anything below ia64 is uninteresting, because ia64 sorts after \nit, and the tree is alphabetically sorted.\n\nSo you could skip even parsing half of both the top-level tree _and_ more \nthan half of the \"arch\" tree.\n\n\t\tLinus\n"},{"id":"37681","messageId":"7vslby1qvw.fsf@assigned-by-dhcp.cox.net","threadId":"7301","inReplyTo":"Pine.LNX.4.64.0703210812590.6730@woody.linux-foundation.org","subject":"Re: Set up for better tree diff optimizations","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-21T16:51:47Z","receivedAt":"2007-03-21T16:51:47Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> On Wed, 21 Mar 2007, Junio C Hamano wrote:\n>> \n>> I've already applied the patch, but I do not know how much this\n>> interface would help, as the only easy case the function\n>> tree_entry_interesting() can say \"no subsequent entries will be\n>> either\" without looking ahead is where no pathspecs match the\n>> base, but that is already prevented by the way you walk the tree\n>> (you do not descend into an uninteresting tree).\n>\n> No. You miss the important case.\n>\n>> If you do:\n>> \n>> \t$ git log arch/i386/ include/asm-i386/\n>\n> Right. Forget about the paths we're *interested* in. \n>\n> Look at the ones we're *not* interested in!\n\nAs always, you are right and enlightened others with your\nsuperiour intelligence enough to produce code for you so that\nyou do not have to write yourself ;-).\n\nWould something like this suit your taste?\n\nThe \"rev-list org.eclipse.debug.ui/\" test that took 16-17\nseconds takes 9 seconds with this patch.  Running with a\ndiffrent pathspec \"org.apache.ant/\" obviously makes it go a lot\nfaster (15sec vs 7sec).\n\n-- >8 --\n[PATCH] Teach tree_entry_interesting() that the tree entries are sorted.\n\nWhen we are looking at a tree entry with pathspecs, if all the\npathspecs sort strictly earlier than the entry we are currently\nlooking at, there is no way later entries in the same tree would\nmatch out pathspecs, because the entries are sorted.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n\n---\n tree-diff.c |   43 +++++++++++++++++++++++++++++++++++++------\n 1 files changed, 37 insertions(+), 6 deletions(-)\n\ndiff --git a/tree-diff.c b/tree-diff.c\nindex b2f35dc..459a0ff 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -81,6 +81,7 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, int\n \tunsigned mode;\n \tint i;\n \tint pathlen;\n+\tint never_interesting = -1;\n \n \tif (!opt->nr_paths)\n \t\treturn 1;\n@@ -89,9 +90,10 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, int\n \n \tpathlen = tree_entry_len(path, sha1);\n \n-\tfor (i=0; i < opt->nr_paths; i++) {\n+\tfor (i = 0; i < opt->nr_paths; i++) {\n \t\tconst char *match = opt->paths[i];\n \t\tint matchlen = opt->pathlens[i];\n+\t\tint m;\n \n \t\tif (baselen >= matchlen) {\n \t\t\t/* If it doesn't match, move along... */\n@@ -109,6 +111,32 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, int\n \t\tmatch += baselen;\n \t\tmatchlen -= baselen;\n \n+\t\t/*\n+\t\t * Does match sort strictly earlier than path with their\n+\t\t * common parts?\n+\t\t */\n+\t\tm = strncmp(match, path,\n+\t\t\t    (matchlen < pathlen) ? matchlen : pathlen);\n+\t\tif (m < 0)\n+\t\t\tcontinue;\n+\n+\t\t/*\n+\t\t * If we come here even once, that means there is at\n+\t\t * least one pathspec that would sort later than the\n+\t\t * path we are currently looking at (even though this\n+\t\t * particular one we are currently looking at might\n+\t\t * not match).  In other words, if we have never\n+\t\t * reached this point after iterating all pathspecs,\n+\t\t * it means all pathspecs are either outside of base,\n+\t\t * or inside the base but sorts earlier than the\n+\t\t * current one.  In either case, they will never match\n+\t\t * the subsequent entries.  In such a case, we\n+\t\t * initialized the variable to -1 and that is what\n+\t\t * will be returned, allowing the caller to terminate\n+\t\t * early.\n+\t\t */\n+\t\tnever_interesting = 0;\n+\n \t\tif (pathlen > matchlen)\n \t\t\tcontinue;\n \n@@ -119,12 +147,15 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, int\n \t\t\t\tcontinue;\n \t\t}\n \n-\t\tif (strncmp(path, match, pathlen))\n-\t\t\tcontinue;\n-\n-\t\treturn 1;\n+\t\t/*\n+\t\t * If common part matched earlier then it is a hit,\n+\t\t * because we rejected the case where path is not a\n+\t\t * leading directory and is shorter than match.\n+\t\t */\n+\t\tif (!m)\n+\t\t\treturn 1;\n \t}\n-\treturn 0; /* No matches */\n+\treturn never_interesting; /* No matches */\n }\n \n /* A whole sub-tree went away or appeared */\n"},{"id":"37690","messageId":"Pine.LNX.4.64.0703211110050.6730@woody.linux-foundation.org","threadId":"7301","inReplyTo":"7vslby1qvw.fsf@assigned-by-dhcp.cox.net","subject":"Re: Set up for better tree diff optimizations","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-21T18:21:17Z","receivedAt":"2007-03-21T18:21:17Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 21 Mar 2007, Junio C Hamano wrote:\n> \n> As always, you are right and enlightened others with your\n> superiour intelligence enough to produce code for you so that\n> you do not have to write yourself ;-).\n\nWhat can I say? It's a gift. I write _just_ enough code so that others get \nintrigued and encouraged to do the rest. Then I step in, and take all the \nglory.\n\n> Would something like this suit your taste?\n\nThis looks fine, although the reason I didn't get it done myself is that I \nhave this nagging feeling that there must be some clever way to make it \neven faster. I hated having to do the \"strncmp()\" early, when it's not \nalways needed. \n\nBut like your patch, I could never come up with a way to *both* do the \n\"don't strncmp() if you don't have to\" *and* do the \"nothing further will \nbe interesting any more\" optimization..\n\nThat said, your numbers are pretty convincing:\n\n> The \"rev-list org.eclipse.debug.ui/\" test that took 16-17\n> seconds takes 9 seconds with this patch.  Running with a\n> diffrent pathspec \"org.apache.ant/\" obviously makes it go a lot\n> faster (15sec vs 7sec).\n\nYeah, and conversely, a pathspec at the end of the list of paths will make \nit less of an optimization. But in general it shouldn't ever be a loss \nexcept for the rather rare case of asking for a path at the end of a tree, \nand then the loss should be pretty small (ie it's the result of doing a \nfew strncmp's that we used to be able to skip).\n\nConsidering that the win on _average_ is in the 50% range (and your \nnumbers back that up), it's definitely worth it.\n\n\t\tLinus\n"},{"id":"37693","messageId":"7vhcse1kpu.fsf@assigned-by-dhcp.cox.net","threadId":"7301","inReplyTo":"Pine.LNX.4.64.0703211110050.6730@woody.linux-foundation.org","subject":"Re: Set up for better tree diff optimizations","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-21T19:05:01Z","receivedAt":"2007-03-21T19:05:01Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> On Wed, 21 Mar 2007, Junio C Hamano wrote:\n> ...\n>> Would something like this suit your taste?\n>\n> This looks fine, although the reason I didn't get it done myself is that I \n> have this nagging feeling that there must be some clever way to make it \n> even faster. I hated having to do the \"strncmp()\" early, when it's not \n> always needed. \n>\n> But like your patch, I could never come up with a way to *both* do the \n> \"don't strncmp() if you don't have to\" *and* do the \"nothing further will \n> be interesting any more\" optimization..\n\nI briefly tried match[0] < path[0] as a compromise, but it did\nnot fly well with the eclipse example for obvious reasons ;-).\n\n>> The \"rev-list org.eclipse.debug.ui/\" test that took 16-17\n>> seconds takes 9 seconds with this patch.  Running with a\n>> diffrent pathspec \"org.apache.ant/\" obviously makes it go a lot\n>> faster (15sec vs 7sec).\n>\n> Yeah, and conversely, a pathspec at the end of the list of paths will make \n> it less of an optimization. But in general it shouldn't ever be a loss \n> except for the rather rare case of asking for a path at the end of a tree, \n> and then the loss should be pretty small (ie it's the result of doing a \n> few strncmp's that we used to be able to skip).\n\nWe _could_ check never_interesting first and if it is already\ndropped then defer strncmp() and check the pathlen > matchlen\ncomparison first.\n"},{"id":"37694","messageId":"7vslbyz81b.fsf@assigned-by-dhcp.cox.net","threadId":"7301","inReplyTo":"7vhcse1kpu.fsf@assigned-by-dhcp.cox.net","subject":"Re: Set up for better tree diff optimizations","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-21T19:54:56Z","receivedAt":"2007-03-21T19:54:56Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <junkio@cox.net> writes:\n\n> Linus Torvalds <torvalds@linux-foundation.org> writes:\n>\n>> On Wed, 21 Mar 2007, Junio C Hamano wrote:\n>> ...\n>>> Would something like this suit your taste?\n>>\n>> This looks fine, although the reason I didn't get it done myself is that I \n>> have this nagging feeling that there must be some clever way to make it \n>> even faster. I hated having to do the \"strncmp()\" early, when it's not \n>> always needed. \n> ...\n> We _could_ check never_interesting first and if it is already\n> dropped then defer strncmp() and check the pathlen > matchlen\n> comparison first.\n\nSo this is the round #2, as a replacement patch of what I sent\nearlier.  Once we know that there are pathspecs that sort later\nthan the current path, we can defer doing strncmp() and skip\nthat pathspec early by comparing length.  If the path is longer\nthan the spec, we can tell that it would never match without\ncomparing.\n\nBest time for \"git-rev-list HEAD -- arch/i386/ include/asm-i386/\"\nare (ten runs each):\n\nwithout any patch:\t1.17user\nwith the previous:\t1.13user\nwith this patch:\t1.11user\n\n-- >8 --\nTeach tree_entry_interesting() that the tree entries are sorted.\n\nWhen we are looking at a tree entry with pathspecs, if all the\npathspecs sort strictly earlier than the entry we are currently\nlooking at, there is no way later entries in the same tree would\nmatch out pathspecs, because the entries are sorted.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n\n tree-diff.c |   55 +++++++++++++++++++++++++++++++++++++++++++++++++------\n 1 files changed, 49 insertions(+), 6 deletions(-)\n\ndiff --git a/tree-diff.c b/tree-diff.c\nindex 3678805..15fd665 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -81,6 +81,7 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, int\n \tunsigned mode;\n \tint i;\n \tint pathlen;\n+\tint never_interesting = -1;\n \n \tif (!opt->nr_paths)\n \t\treturn 1;\n@@ -89,9 +90,10 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, int\n \n \tpathlen = tree_entry_len(path, sha1);\n \n-\tfor (i=0; i < opt->nr_paths; i++) {\n+\tfor (i = 0; i < opt->nr_paths; i++) {\n \t\tconst char *match = opt->paths[i];\n \t\tint matchlen = opt->pathlens[i];\n+\t\tint m = -1; /* signals that we haven't called strncmp() */\n \n \t\tif (baselen >= matchlen) {\n \t\t\t/* If it doesn't match, move along... */\n@@ -109,6 +111,37 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, int\n \t\tmatch += baselen;\n \t\tmatchlen -= baselen;\n \n+\t\tif (never_interesting) {\n+\t\t\t/*\n+\t\t\t * We have not seen any match that sorts later\n+\t\t\t * than the current path.\n+\t\t\t */\n+\n+\t\t\t/*\n+\t\t\t * Does match sort strictly earlier than path\n+\t\t\t * with their common parts?\n+\t\t\t */\n+\t\t\tm = strncmp(match, path,\n+\t\t\t\t    (matchlen < pathlen) ? matchlen : pathlen);\n+\t\t\tif (m < 0)\n+\t\t\t\tcontinue;\n+\n+\t\t\t/*\n+\t\t\t * If we come here even once, that means there is at\n+\t\t\t * least one pathspec that would sort equal to or\n+\t\t\t * later than the path we are currently looking at.\n+\t\t\t * In other words, if we have never reached this point\n+\t\t\t * after iterating all pathspecs, it means all\n+\t\t\t * pathspecs are either outside of base, or inside the\n+\t\t\t * base but sorts strictly earlier than the current\n+\t\t\t * one.  In either case, they will never match the\n+\t\t\t * subsequent entries.  In such a case, we initialized\n+\t\t\t * the variable to -1 and that is what will be\n+\t\t\t * returned, allowing the caller to terminate early.\n+\t\t\t */\n+\t\t\tnever_interesting = 0;\n+\t\t}\n+\n \t\tif (pathlen > matchlen)\n \t\t\tcontinue;\n \n@@ -119,12 +152,22 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, int\n \t\t\t\tcontinue;\n \t\t}\n \n-\t\tif (strncmp(path, match, pathlen))\n-\t\t\tcontinue;\n-\n-\t\treturn 1;\n+\t\tif (m == -1)\n+\t\t\t/*\n+\t\t\t * we cheated and did not do strncmp(), so we do\n+\t\t\t * that here.\n+\t\t\t */\n+\t\t\tm = strncmp(match, path, pathlen);\n+\n+\t\t/*\n+\t\t * If common part matched earlier then it is a hit,\n+\t\t * because we rejected the case where path is not a\n+\t\t * leading directory and is shorter than match.\n+\t\t */\n+\t\tif (!m)\n+\t\t\treturn 1;\n \t}\n-\treturn 0; /* No matches */\n+\treturn never_interesting; /* No matches */\n }\n \n /* A whole sub-tree went away or appeared */\n"},{"id":"37706","messageId":"7vd532ywo4.fsf@assigned-by-dhcp.cox.net","threadId":"7301","inReplyTo":"7vslbyz81b.fsf@assigned-by-dhcp.cox.net","subject":"Re: Set up for better tree diff optimizations","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-03-22T00:00:27Z","receivedAt":"2007-03-22T00:00:27Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <junkio@cox.net> writes:\n\n> So this is the round #2, as a replacement patch of what I sent\n> earlier.  Once we know that there are pathspecs that sort later\n> than the current path, we can defer doing strncmp() and skip\n> that pathspec early by comparing length.  If the path is longer\n> than the spec, we can tell that it would never match without\n> comparing.\n\nAnd then this comes on top of #2.\n\n-- >8 --\ntree_entry_interesting(): allow it to say \"everything is interesting\"\n\nIn addition to optimizing pathspecs that would never match which\nwas done earlier, this optimizes pathspecs that would always\nmatch (e.g. \"arch/\" while the traversal is already in\n\"arch/i386/\" hierarchy).\n\nWith this, the worst case become slightly more palatable, while\nimproving average case.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n\n---\n\n  For example, best-of-ten user times of\n  \"rev-list HEAD -- $pathspec\" in the eclipse repository for\n  various pathspecs are:\n\n  * .cvsignore (best path, earliest in the tree)\n    11.84 (without any optimization)\n     6.35 (with patch #2)\n     6.35 (with patch #2 and this patch)\n\n  * platform-launcher (worst path, last in the tree)\n    12.20 (without any optimization)\n    12.90 (with patch #2)\n    12.75 (with patch #2 and this patch)\n\n  * org.eclipse.platform.macosx.carbon-feature (middle in the tree)\n    12.02 (without any optimization)\n    10.52 (with patch #2)\n    10.43 (with patch #2 and this patch)\n\n  The kernel archive number is similar.  Limited to arch/i386 and\n  include/asm-i386, the numbers are:\n\n     1.18 (without any optimization)\n     1.11 (with patch #2)\n     1.10 (with patch #2 and this patch).\n\n tree-diff.c |   33 ++++++++++++++++++++++++++++-----\n 1 files changed, 28 insertions(+), 5 deletions(-)\n\ndiff --git a/tree-diff.c b/tree-diff.c\nindex 15fd665..852498e 100644\n--- a/tree-diff.c\n+++ b/tree-diff.c\n@@ -70,7 +70,8 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const\n  * Is a tree entry interesting given the pathspec we have?\n  *\n  * Return:\n- *  - positive for yes\n+ *  - 2 for \"yes, and all subsequent entries will be\"\n+ *  - 1 for yes\n  *  - zero for no\n  *  - negative for \"no, and no subsequent entries will be either\"\n  */\n@@ -100,8 +101,11 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, int\n \t\t\tif (strncmp(base, match, matchlen))\n \t\t\t\tcontinue;\n \n-\t\t\t/* The base is a subdirectory of a path which was specified. */\n-\t\t\treturn 1;\n+\t\t\t/*\n+\t\t\t * The base is a subdirectory of a path which\n+\t\t\t * was specified, so all of them are interesting.\n+\t\t\t */\n+\t\t\treturn 2;\n \t\t}\n \n \t\t/* Does the base match? */\n@@ -173,8 +177,18 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, int\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 {\n+\tint all_interesting = 0;\n \twhile (desc->size) {\n-\t\tint show = tree_entry_interesting(desc, base, baselen, opt);\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(desc, base, baselen,\n+\t\t\t\t\t\t      opt);\n+\t\t\tif (show == 2)\n+\t\t\t\tall_interesting = 1;\n+\t\t}\n \t\tif (show < 0)\n \t\t\tbreak;\n \t\tif (show)\n@@ -215,8 +229,17 @@ static void show_entry(struct diff_options *opt, const char *prefix, struct tree\n \n static void skip_uninteresting(struct tree_desc *t, const char *base, int baselen, struct diff_options *opt)\n {\n+\tint all_interesting = 0;\n \twhile (t->size) {\n-\t\tint show = tree_entry_interesting(t, base, baselen, opt);\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\tif (!show) {\n \t\t\tupdate_tree_entry(t);\n \t\t\tcontinue;\n"}]}