{"thread":{"id":"39106","subject":"[PATCH] limit_list: avoid quadratic behavior from still_interesting","startedAt":"2015-04-17T22:11:04Z","lastAt":"2015-04-17T22:21:30Z","messageCount":2,"participants":["Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"259602","messageId":"20150417221104.GA8806@peff.net","threadId":"39106","inReplyTo":null,"subject":"[PATCH] limit_list: avoid quadratic behavior from still_interesting","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-04-17T22:11:04Z","receivedAt":"2015-04-17T22:11:04Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When we are limiting a rev-list traversal due to\nUNINTERESTING refs, we have to walk down the tips (both\ninteresting and uninteresting) to find where they intersect.\nWe keep a queue of commits to examine, pop commits off\nthe queue one by one, and potentially add their parents.  The\nsize of the queue will naturally fluctuate based on the\n\"width\" of the history graph; i.e., the number of\nsimultaneous lines of development. But for the most part it\nwill stay in the same ballpark as the initial number of tips\nwe fed, shrinking over time (as we hit common ancestors of\nthe tips). So roughly speaking, if we start with `N` tips,\nwe'll spend much of the time with a queue around `N` items.\n\nFor each UNINTERESTING commit we pop, we call\nstill_interesting to check whether marking its parents as\nUNINTERESTING has made the whole queue uninteresting (in\nwhich case we can quit early).  Because the queue is stored\nas a linked list, this is `O(N)`, where `N` is the number of\nitems in the queue. So processing a queue with `N` commits\nmarked UNINTERESTING (and one or more interesting commits)\nwill take `O(N^2)`.\n\nIf you feed a lot of positive tips, this isn't a problem.\nThey aren't UNINTERESTING, so they don't incur the\nstill_interesting check.  It also isn't a problem if you\ntraverse from an interesting tip to some UNINTERESTING\nbases. We order the queue by recency, so the interesting\ncommits stay at the front of the queue as we walk down them.\nThe linear check can exit early as soon as it sees one\ninteresting commit left in the queue.\n\nBut if you want to know whether an older commit is reachable\nfrom a set of newer tips, we end up processing in the\nopposite direction: from the UNINTERESTING ones down to the\ninteresting one. This may happen when we call:\n\n  git rev-list $commits --not --all\n\nin check_everything_connected after a fetch. If we fetched\nsomething much older than most of our refs, and if we have a\nlarge number of refs, the traversal cost is dominated by the\nquadratic behavior.\n\nThese commands simulate the connectivity check of such a\nfetch, when you have `$n` distinct refs in the receiver:\n\n    # positive ref is 100,000 commits deep\n    git rev-list --all | head -100000 | tail -1 >input\n\n    # huge number of more recent negative refs\n    git rev-list --all | head -$n | sed s/^/^/ >>input\n\n    time git rev-list --stdin <input\n\nHere are timings for various `n` on the linux.git\nrepository. The `n=1` case provides a baseline for just\nwalking the commits, which lets us see the still_interesting\noverhead. The times marked with `+` subtract that baseline\nto show just the extra time growth due to the large number\nof refs. The `x` numbers show the slowdown of the adjusted\ntime versus the prior trial.\n\n       n  | before                 | after\n    --------------------------------------------------------\n        1 | 0.991s                 | 0.848s\n    10000 | 1.120s (+0.129s)       | 0.885s (+0.037s)\n    20000 | 1.451s (+0.460s, 3.5x) | 0.923s (+0.075s, 2.0x)\n    40000 | 2.731s (+1.740s, 3.8x) | 0.994s (+0.146s, 1.9x)\n    80000 | 8.235s (+7.244s, 4.2x) | 1.123s (+0.275s, 1.9x)\n\nEach trial doubles `n`, so you can see the quadratic (`4x`)\nbehavior before this patch. Afterwards, we have a roughly\nlinear relationship.\n\nThe implementation is fairly straightforward. Whenever we do\nthe linear search, we cache the interesting commit we find,\nand next time check it before doing another linear search.\nIf that commit is removed from the list or becomes\nUNINTERESTING itself, then we fall back to the linear\nsearch. This is very similar to the trick used by fce87ae\n(Fix quadratic performance in rewrite_one., 2008-07-12).\n\nI considered and rejected several possible alternatives:\n\n  1. Keep a count of UNINTERESTING commits in the queue.\n     This requires managing the count not only when removing\n     an item from the queue, but also when marking an item\n     as UNINTERESTING. That requires touching the other\n     functions which mark commits, and would require knowing\n     quickly which commits are in the queue (lookup in the\n     queue is linear, so we would need an auxiliary\n     structure or to also maintain an IN_QUEUE flag in each\n     commit object).\n\n  2. Keep a separate list of interesting commits. Drop items\n     from it when they are dropped from the queue, or if\n     they become UNINTERESTING. This again suffers from\n     extra complexity to maintain the list, not to mention\n     CPU and memory.\n\n  3. Use a better data structure for the queue. This is\n     something that could help the fix in fce87ae, because\n     we order the queue by recency, and it is about\n     inserting quickly in recency order. So a normal\n     priority queue would help there. But here, we cannot\n     disturb the order of the queue, which makes things\n     harder. We really do need an auxiliary index to track\n     the flag we care about, which is basically option (2)\n     above.\n\nThe \"cache\" trick is simple, and the numbers above show that\nit works well in practice. This is because the length of\ntime it takes to find an interesting commit is proportional\nto the length of time it will remain cached (i.e., if we\nhave to walk a long way to find it, it also means we have to\npop a lot of elements in the queue until we get rid of it\nand have to find another interesting commit).\n\nThe worst case is still quadratic, though. We could have `N`\nuninteresting commits at the front of the queue, followed by\n`N` interesting commits, where commit `i` has parent `i+N`.\nWhen we pop commit `i`, we will notice that the parent of\nthe next commit, `i+1+N` is still interesting and cache it.\nBut then handling commit `i+1`, we will mark its parent\n`i+1+N` uninteresting, and immediately invalidate our cache.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nI think this should help me retain my crown for average number of\ncommit-message lines per commit.\n\nTo solve the quadratic case at the bottom, we could re-start the linear\nsearch right after the cached commit, and then wrap around. It's not too\nhard to do (we'd just have to cache the commit_list instead of the\ncommit), but I'm not convinced it doesn't just open up new pathological\ncases.  Since the case I described above seems rather ridiculous in\npractice, and because it would introduce complexity, I decided not to\npursue it.\n\n revision.c | 23 +++++++++++++++++++----\n 1 file changed, 19 insertions(+), 4 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 6399a04..7ddbaa0 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -345,14 +345,24 @@ static struct commit *handle_commit(struct rev_info *revs,\n \tdie(\"%s is unknown object\", name);\n }\n \n-static int everybody_uninteresting(struct commit_list *orig)\n+static int everybody_uninteresting(struct commit_list *orig,\n+\t\t\t\t   struct commit **interesting_cache)\n {\n \tstruct commit_list *list = orig;\n+\n+\tif (*interesting_cache) {\n+\t\tstruct commit *commit = *interesting_cache;\n+\t\tif (!(commit->object.flags & UNINTERESTING))\n+\t\t\treturn 0;\n+\t}\n+\n \twhile (list) {\n \t\tstruct commit *commit = list->item;\n \t\tlist = list->next;\n \t\tif (commit->object.flags & UNINTERESTING)\n \t\t\tcontinue;\n+\t\tif (interesting_cache)\n+\t\t\t*interesting_cache = commit;\n \t\treturn 0;\n \t}\n \treturn 1;\n@@ -940,7 +950,8 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)\n /* How many extra uninteresting commits we want to see.. */\n #define SLOP 5\n \n-static int still_interesting(struct commit_list *src, unsigned long date, int slop)\n+static int still_interesting(struct commit_list *src, unsigned long date, int slop,\n+\t\t\t     struct commit **interesting_cache)\n {\n \t/*\n \t * No source list at all? We're definitely done..\n@@ -959,7 +970,7 @@ static int still_interesting(struct commit_list *src, unsigned long date, int sl\n \t * Does the source list still have interesting commits in\n \t * it? Definitely not done..\n \t */\n-\tif (!everybody_uninteresting(src))\n+\tif (!everybody_uninteresting(src, interesting_cache))\n \t\treturn SLOP;\n \n \t/* Ok, we're closing in.. */\n@@ -1078,6 +1089,7 @@ static int limit_list(struct rev_info *revs)\n \tstruct commit_list *newlist = NULL;\n \tstruct commit_list **p = &newlist;\n \tstruct commit_list *bottom = NULL;\n+\tstruct commit *interesting_cache = NULL;\n \n \tif (revs->ancestry_path) {\n \t\tbottom = collect_bottom_commits(list);\n@@ -1094,6 +1106,9 @@ static int limit_list(struct rev_info *revs)\n \t\tlist = list->next;\n \t\tfree(entry);\n \n+\t\tif (commit == interesting_cache)\n+\t\t\tinteresting_cache = NULL;\n+\n \t\tif (revs->max_age != -1 && (commit->date < revs->max_age))\n \t\t\tobj->flags |= UNINTERESTING;\n \t\tif (add_parents_to_list(revs, commit, &list, NULL) < 0)\n@@ -1102,7 +1117,7 @@ static int limit_list(struct rev_info *revs)\n \t\t\tmark_parents_uninteresting(commit);\n \t\t\tif (revs->show_all)\n \t\t\t\tp = &commit_list_insert(commit, p)->next;\n-\t\t\tslop = still_interesting(list, date, slop);\n+\t\t\tslop = still_interesting(list, date, slop, &interesting_cache);\n \t\t\tif (slop)\n \t\t\t\tcontinue;\n \t\t\t/* If showing all, add the whole pending list to the end */\n-- \n2.4.0.rc2.384.g7297a4a\n"},{"id":"259605","messageId":"xmqqoammo0ph.fsf@gitster.dls.corp.google.com","threadId":"39106","inReplyTo":"20150417221104.GA8806@peff.net","subject":"Re: [PATCH] limit_list: avoid quadratic behavior from still_interesting","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-04-17T22:21:30Z","receivedAt":"2015-04-17T22:21:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> The implementation is fairly straightforward. Whenever we do\n> the linear search, we cache the interesting commit we find,\n> and next time check it before doing another linear search.\n> If that commit is removed from the list or becomes\n> UNINTERESTING itself, then we fall back to the linear\n> search.\n\nNicely done, clever, simple and effective.\n\nThanks.\n"}]}