GitHub PushEvent at 2014-11-27 05:45:08
Repository: git
Actor: peff
Payload: {"shas":[["a2b450d6fd8ad94881b257cda86cf90c1ec55385","e9ae0fa8a6ea1c4a34faf6d3356cfe5d659ec9d4@xiplink.com","RelNotes: spelling & grammar tweaks\n\nSigned-off-by: Marc Branchaud <marcnarc@xiplink.com>\nSigned-off-by: Junio C Hamano <gitster@pobox.com>","Marc Branchaud",false],["b260d265e189728b26e50506ac6ffab6a7d588da","a6723cc3f76163bf7adb636a73ac3b0ceb3e6b9b@pobox.com","Git 2.2\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>","Junio C Hamano",false],["1f97027d82aa08cfda1a2cb55376350a434934d2","696e3fbcf235d40b6ea1ebd61c87cbea79d444e7@peff.net","tag: allow --sort with -n\n\nWhen we are listing tags, we print each one as it is\nprocessed by for_each_ref. We can't do that with --sort, of\ncourse, as we need to see the whole list to sort. For the\n--sort code path, we store each tag in a string_list, and\nthen print them all at the end.\n\nThis interacts badly with \"-n\", which needs not only the\nname of the tag, but also the object itself. We simply\npunted on handling this, and disallowed the combination.\n\nThis patch remedies that by storing the sha1 of each object\nin the \"util\" field of the string list. We can then factor\nout the printing to a helper function and call that function\neither when we first see each tag, or after we have sorted.","Jeff King",false],["996f86bc7305bf52fb5824ca782ce44a3998a2c5","696e3fbcf235d40b6ea1ebd61c87cbea79d444e7@peff.net","tag: factor out decision to stream tags\n\nRight now we stream tags if we are not sorting. If we are\nsorting, we save them in a list and print them at the end.\nLet's abstract this decision into a function to make it\neasier to add more cases where we use the list.","Jeff King",false],["f74612f83c1c29798a4233d7339035f5ce190d9a","696e3fbcf235d40b6ea1ebd61c87cbea79d444e7@peff.net","add functions for memory-efficient bitmaps\n\nWe already have a nice-to-use bitmap implementation in\newah/bitmap.c. It pretends to be infinitely long when asking\nfor a bit (and just returns 0 for bits that haven't been\nallocated or set), and dynamically resizes as appropriate\nwhen you set bits.\n\nThe cost to this is that each bitmap must store its own\npointer and length, using up to 16 bytes per bitmap on top\nof the actual bit storage. This is a lot of storage (not to\nmention an extra level of pointer indirection) if you are\ngoing to store one bitmap per commit in a traversal.\n\nThese functions provide an alternative bitmap implementation\nthat can be used when you have a large number of fixed-size\nbitmaps. See the documentation in the header file for\ndetails and examples.","Jeff King",false],["b044eded7626c807e0dfff27a3f6a1220c11f49c","696e3fbcf235d40b6ea1ebd61c87cbea79d444e7@peff.net","commit: provide a fast multi-tip contains function\n\nWhen commands like \"git branch --contains\" want to know\nwhich branches contain a particular commit, they run a\nseries of merge-base calculations, one per branch. This can\nbe very slow if you have a large number of branches.\n\nWe made \"tag --contains\" faster in ffc4b80 (tag: speed up\n--contains calculation, 2011-06-11) by switching to a\ndifferent algorithm that caches intermediate \"contains\"\ninformation from each tag we check. The downside of the new\nalgorithm is that it moves depth-first through the graph. So\nit tends to go all the way to the roots, even if the\ncontained commit is near the top of history. That works OK\nfor tags, because repositories tend to have tags near the\nroots anyway (e.g., a v0.1 or similar). The number of\ncommits we look at increased a little bit, but since we\navoid traversing over the same parts of history repeatedly,\nit was a huge net win.\n\nFor \"branch --contains\", it is less clear that this is a\nwin. Most branches stay up to date, so we can bound a search\nfor a recent commit when we hit the merge base between the\ncommit and the branches.\n\nThe ideal would be to use the merge-base-style breadth-first\ntraversal, but to perform a single traversal for all tips.\nThe problem is that we need one bit of storage per tip in\neach commit, and \"struct commit\" has only a fixed number of\nbits. We can solve that by using a process similar to\npaint_down_to_common, but instead of storing PARENT1 and\nPARENT2 flags, using a commit slab to store one bit per tip.","Jeff King",false],["830eb33b11f8a20e96f9ae02ff25a2d6b8efaa68","696e3fbcf235d40b6ea1ebd61c87cbea79d444e7@peff.net","tag: use commit_contains\n\nThe newly added commit_contains function should do a better\njob than our custom depth-first traversal. It should be the\nsame speed when going close to the roots, but much faster\nwhen all tags are close to the searched-for commit (this\nusually isn't the case, but could be if you limit the tags\nwith a pattern).\n\nIt also cleans up some of the more egregious pitfalls of the\noriginal implementation, including an abuse of the\nUNINTERESTING and TMP_MARK flags, an utterly confusing\ncalling convention (it silently caches the bits between\ncalls, with no checks that our \"with_commit\" was the same\nfor each call), and a failure to clean up after itself\n(tainting any further traversals).","Jeff King",false],["f13302c0007bf51a4ed7dbf00a9f027a7e5edbf9","696e3fbcf235d40b6ea1ebd61c87cbea79d444e7@peff.net","perf: add tests for tag --contains\n\nThese tests can demonstrate the changes in \"tag --contains\"\nspeed over time. The interesting points in history are:\n\n  - pre-ffc4b80, where we used a series of N merge-base\n    traversals\n\n  - ffc4b80 up to the current master, where we moved to a\n    single depth-first traversal\n\n  - the previous commit, where we moved from depth-first to\n    a multi-tip merge-base\n\nThe interesting cases to measure are:\n\n  - checking which tags contain a recent commit (we use\n    HEAD~100 here)\n\n  - checking which tags contain a very ancient commit (we\n    use the last commit output by rev-list)\n\n  - checking which tags contain a commit in the middle (we\n    use HEAD~5000, which goes back 5 years in git.git)\n\n  - all of the above, but instead of looking at all commits,\n    considering only recent ones (we pick the most recent\n    tag by its tagger date)\n\nHere are the timings for git.git:\n\n    Test                              ffc4b80^          origin/master             HEAD\n    ----------------------------------------------------------------------------------------------------\n    7000.3: contains recent/all       1.99(1.97+0.01)   0.25(0.24+0.00) -87.4%    0.27(0.26+0.00) -86.4%\n    7000.4: contains recent/v2.0.1    0.03(0.03+0.00)   0.00(0.00+0.00) -100.0%   0.03(0.02+0.00) +0.0%\n    7000.5: contains old/all          0.90(0.89+0.00)   0.18(0.17+0.00) -80.0%    0.27(0.26+0.00) -70.0%\n    7000.6: contains old/v2.0.1       0.25(0.24+0.00)   0.03(0.03+0.00) -88.0%    0.25(0.24+0.00) +0.0%\n    7000.7: contains ancient/all      0.82(0.80+0.01)   0.13(0.12+0.00) -84.1%    0.27(0.26+0.01) -67.1%\n    7000.8: contains ancient/v2.0.1   0.26(0.26+0.00)   0.09(0.08+0.00) -65.4%    0.25(0.24+0.00) -3.8%\n\nYou can see that ffc4b80 vastly improved the normal case of\nchecking all tags. This is because we avoid walking over the\nsame parts of history over and over. However, when looking\nonly for a recent tag (v2.0.1 in these tests), it sometimes\nperforms much worse than the original. This is not\nsurprising. For a merge-base solution, we can quit when we\nhit history shared between the contained commit and the tag.\nFor ffc4b80's depth-first approach, we typically go all the\nway to the roots before backtracking. For the ancient/v2.0.1\ncase, that's not a big deal, because the merge base requires\nus doing that anyway. But for recent/v2.0.1, the merge-base\nanswer should involve only recent history.\n\nThe new traversal code performs about as well as the\ndepth-first code in the normal case, but fixes the\nregression in the recent/v2.0.1 case.","Jeff King",false]],"size":8,"ref":"refs/heads/jk/contains-merge-base","head":"f13302c0007bf51a4ed7dbf00a9f027a7e5edbf9"}