)]}'
{
  "commit": "b6e8a3b5404606f156a14bac262d7e9adf620990",
  "tree": "9765b289ea0ac238812d6b3b88081f780ad9cf52",
  "parents": [
    "282616c72d1d08a77ca4fe1186cb708c38408d87"
  ],
  "author": {
    "name": "Jeff King",
    "email": "peff@peff.net",
    "time": "Fri Apr 17 18:11:04 2015 -0400"
  },
  "committer": {
    "name": "Junio C Hamano",
    "email": "gitster@pobox.com",
    "time": "Fri Apr 17 15:22:05 2015 -0700"
  },
  "message": "limit_list: avoid quadratic behavior from still_interesting\n\nWhen 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\u0027ll 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\u0027t a problem.\nThey aren\u0027t UNINTERESTING, so they don\u0027t incur the\nstill_interesting check.  It also isn\u0027t 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 \u003einput\n\n    # huge number of more recent negative refs\n    git rev-list --all | head -$n | sed s/^/^/ \u003e\u003einput\n\n    time git rev-list --stdin \u003cinput\n\nHere are timings for various `n` on the linux.git\nrepository. The `n\u003d1` 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 \u003cpeff@peff.net\u003e\nSigned-off-by: Junio C Hamano \u003cgitster@pobox.com\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "2571ada6bf66ce6e945c539be4b0123e5b9648a9",
      "old_mode": 33188,
      "old_path": "revision.c",
      "new_id": "06f31d6fb5632c6d89f581f8d9282348cb6f743a",
      "new_mode": 33188,
      "new_path": "revision.c"
    }
  ]
}