)]}'
{
  "commit": "6cc017431c1c48f80d1c6512fdcc9866cf4b7f55",
  "tree": "2884e5eb4406ddd5e3d3e395a7ceab84dd73f3e4",
  "parents": [
    "4fbcca4effc1c6f8431120f88f5a4bd1c8e38ca3"
  ],
  "author": {
    "name": "Derrick Stolee",
    "email": "dstolee@microsoft.com",
    "time": "Fri Jul 20 16:33:30 2018 +0000"
  },
  "committer": {
    "name": "Junio C Hamano",
    "email": "gitster@pobox.com",
    "time": "Fri Jul 20 15:38:56 2018 -0700"
  },
  "message": "commit-reach: use can_all_from_reach\n\nThe is_descendant_of method previously used in_merge_bases() to check if\nthe commit can reach any of the commits in the provided list. This had\ntwo performance problems:\n\n1. The performance is quadratic in worst-case.\n\n2. A single in_merge_bases() call requires walking beyond the target\n   commit in order to find the full set of boundary commits that may be\n   merge-bases.\n\nThe can_all_from_reach method avoids this quadratic behavior and can\nlimit the search beyond the target commits using generation numbers. It\nrequires a small prototype adjustment to stop using commit-date as a\ncutoff, as that optimization is no longer appropriate here.\n\nSince in_merge_bases() uses paint_down_to_common(), is_descendant_of()\nnaturally found cutoffs to avoid walking the entire commit graph. Since\nwe want to always return the correct result, we cannot use the\nmin_commit_date cutoff in can_all_from_reach. We then rely on generation\nnumbers to provide the cutoff.\n\nSince not all repos will have a commit-graph file, nor will we always\nhave generation numbers computed for a commit-graph file, create a new\nmethod, generation_numbers_enabled(), that checks for a commit-graph\nfile and sees if the first commit in the file has a non-zero generation\nnumber. In the case that we do not have generation numbers, use the old\nlogic for is_descendant_of().\n\nPerformance was meausured on a copy of the Linux repository using the\n\u0027test-tool reach is_descendant_of\u0027 command using this input:\n\nA:v4.9\nX:v4.10\nX:v4.11\nX:v4.12\nX:v4.13\nX:v4.14\nX:v4.15\nX:v4.16\nX:v4.17\nX.v3.0\n\nNote that this input is tailored to demonstrate the quadratic nature of\nthe previous method, as it will compute merge-bases for v4.9 versus all\nof the later versions before checking against v4.1.\n\nBefore: 0.26 s\n After: 0.21 s\n\nSince we previously used the is_descendant_of method in the ref_newer\nmethod, we also measured performance there using\n\u0027test-tool reach ref_newer\u0027 with this input:\n\nA:v4.9\nB:v3.19\n\nBefore: 0.10 s\n After: 0.08 s\n\nBy adding a new commit with parent v3.19, we test the non-reachable case\nof ref_newer:\n\nBefore: 0.09 s\n After: 0.08 s\n\nSigned-off-by: Derrick Stolee \u003cdstolee@microsoft.com\u003e\nSigned-off-by: Junio C Hamano \u003cgitster@pobox.com\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "b0a55ad128fbcaa2e34c25b8487856d20d0ad3d5",
      "old_mode": 33188,
      "old_path": "commit-graph.c",
      "new_id": "e9786fa8640ec4ccab570b4f902d1f039ceb08d7",
      "new_mode": 33188,
      "new_path": "commit-graph.c"
    },
    {
      "type": "modify",
      "old_id": "76e098934a7f6740b52a479baa5c68fe605d1ea6",
      "old_mode": 33188,
      "old_path": "commit-graph.h",
      "new_id": "0de8f88316fd465b4bb08bfb4ac40559d615c161",
      "new_mode": 33188,
      "new_path": "commit-graph.h"
    },
    {
      "type": "modify",
      "old_id": "bc522d6840f3c9fc4ae79adb0f2fc339fe37df38",
      "old_mode": 33188,
      "old_path": "commit-reach.c",
      "new_id": "c9965240323633fa1e6145290cc56596cfb1c3bb",
      "new_mode": 33188,
      "new_path": "commit-reach.c"
    }
  ]
}