{"thread":{"id":"26824","subject":"[RFH] git cherry vs. git rev-list --cherry, or: Why does \"...\" suck?","startedAt":"2011-03-22T12:07:53Z","lastAt":"2011-03-24T07:38:48Z","messageCount":5,"participants":["Michael J Gruber","Jeff King","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"164038","messageId":"4D889119.3020009@drmicha.warpmail.net","threadId":"26824","inReplyTo":null,"subject":"[RFH] git cherry vs. git rev-list --cherry, or: Why does \"...\" suck?","fromName":"Michael J Gruber","fromEmail":"git@drmicha.warpmail.net","sentAt":"2011-03-22T12:07:53Z","receivedAt":"2011-03-22T12:07:53Z","isPatch":false,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"In the process of converting \"git cherry\" and \"git format patch\" to use\nthe new rev-list options (the saner way according to d7a17ca (git-log\n--cherry-pick A...B, 2007-04-09) already!), I have a simple question and\na hard one which I both ask help for:\n\nrun_command\n===========\n\nI could use either run_command_v_opt(args, RUN_GIT_CMD) or setup the\nwalker, call it etc. For the former I have to check how to treat the\nthird argument to \"git cherry\", the latter seems to be more code (and I\nwould need to call the rev-list/log output loop somehow).\n\nIs there a general preference for using or avoiding run_command?\n\n(There's also the question of what details of git cherry's output I need\nto preserve.)\n\n\nPerformance\n===========\n\nI don't get this:\n\ngit cherry A B: 0.4s\ngit rev-list --cherry A...B: 1.7s\n(more details below)\n\nThis makes \"rev-list --cherry\" almost unacceptable as a replacement. But\nI'd like to understand this difference (and maybe do something about\nit). I'm lost with gprof, but here are more details on the timing:\n\nA is pu at 0f169fc\nB is next at 5ddab49 plus three commits which are not upstream\n\nrev-list --count 5ddab49..A is 166 (117 without merges), for B it is 3\n\nNow the timings (rev-list done with --count):\n\ncherry A B: 0.4s\ncherry B A: 0.4s\nrev-list --cherry A...B: 1.7s\n\nThe latter computes merge bases (there are 25), the former does not. How\nmuch is it:\n\nmerge-base A B: 0.95s\nmerge-base --all A B: 0.95s\nrev-parse A...B: 0.95s\n\nSo this accounts for much of the difference (and we need to do something\nabout get_merge_bases()), but not all. How much is the patch-id computation:\n\nrev-list --no-merges --right-only --cherry-pick A...B: 1.7s\n(the above is --cherry)\nrev-list --no-merges --right-only A...B: 1.0s\nrev-list --no-merges --left-right A...B: 1.0s\n\nWhy does it take rev-list 0.7s to do the same patch-id computations that\ncherry does in less than 0.4s? (More details on what they do below.)\n\nrev-list --no-merges A..B: 0.04s (counting to 3, yeah)\nrev-list --no-merges A..B: 0.6s (counting to 117)\n\nThe latter has no patch-id nor merge computation. Should this really\ntake 0.6s?\n\nI'm stomped. Help, please!\n\nMichael\n\nWhat the commands roughly do:\n\ncherry A B [limit]:\n===================\nadd pending B ^A\nwalk B..A (on temp rev_info) and\nadd_commit_patch_id() on these\nclear_commit_marks()\nadd pending ^limit if specified\nwalk A..B and\nreverse that list and\nhas_commit_patch_id() on these\n\nrev-list --cherry A...B:\n========================\nget_merge_bases for A,B\nadd pending --not merge bases\nadd pending A B\nadd_commit_patch_id() on smaller side\nhas_commit_patch_id() on other side (&& mark id seen)\nrecheck smaller side (based on id->seen)\n\nThis seems to enumerate A..B and B..A more often, but is iterating\nthrough a commit list that time consuming? The number of patch-id\ncomputations is the same as far as I can see.\n"},{"id":"164163","messageId":"4D8A23CD.9030203@drmicha.warpmail.net","threadId":"26824","inReplyTo":"4D889119.3020009@drmicha.warpmail.net","subject":"Re: [RFH] git cherry vs. git rev-list --cherry, or: Why does \"...\" suck?","fromName":"Michael J Gruber","fromEmail":"git@drmicha.warpmail.net","sentAt":"2011-03-23T16:46:05Z","receivedAt":"2011-03-23T16:46:05Z","isPatch":false,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"Adding some recent insight:\n\nMichael J Gruber venit, vidit, dixit 22.03.2011 13:07:\n> Performance\n> ===========\n> \n> I don't get this:\n> \n> git cherry A B: 0.4s\n> git rev-list --cherry A...B: 1.7s\n> (more details below)\n\nI can get the latter down to 0.95s and this\n\n> merge-base A B: 0.95s\n> merge-base --all A B: 0.95s\n> rev-parse A...B: 0.95s\n\nto 0.16s each. The downside is that merge-base may give a few\nunneccessary candidates (commits which are ancestors of other commits it\nreturns), but this does not change the results for rev-list, of course.\n\nI get this dramatic speedup by removing the check for duplicates from\nget_merge_bases_many() in commit.c. After a first merge_bases_many()\nrun, returning N commits, that check calls merge_bases_many() again for\neach pair (N choose 2) to check whether one is contained in the other.\nQuite a bottleneck. Removing it works great. But can we live with a few\nadditional merge bases?\n\nMichael\n"},{"id":"164169","messageId":"20110323171912.GD30337@sigill.intra.peff.net","threadId":"26824","inReplyTo":"4D889119.3020009@drmicha.warpmail.net","subject":"Re: [RFH] git cherry vs. git rev-list --cherry, or: Why does \"...\" suck?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-03-23T17:19:12Z","receivedAt":"2011-03-23T17:19:12Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Mar 22, 2011 at 01:07:53PM +0100, Michael J Gruber wrote:\n\n> I don't get this:\n> \n> git cherry A B: 0.4s\n> git rev-list --cherry A...B: 1.7s\n> (more details below)\n> \n> This makes \"rev-list --cherry\" almost unacceptable as a replacement. But\n> I'd like to understand this difference (and maybe do something about\n> it). I'm lost with gprof, but here are more details on the timing:\n\nI don't have much to say on the problem at hand, but have you tried\nusing the \"perf\" tool from the kernel to measure? These days it ships in\nlinux-tools-2.6.x in Debian unstable; I don't know about other distros.\n\nYou can do this:\n\n  perf record git cherry $A $B >/dev/null\n  perf record git rev-list --cherry $A...$B >/dev/null\n  perf diff\n\nto get a list of the hot-spots with the time differences between the two\nruns (along with \"perf report\" and \"perf annotate\" to get more\ninformation).\n\nDisclaimer: I am very new to perf, so I may be misleading you about how\nuseful the \"diff\" would be. In particular, it seems to be based on a\npercentages of time spent between two runs. Which is great for two runs\nof the same program calling very similar functions. But for two programs\ncalling _mostly_ the same functions, I don't know how misleading it is.\n\n-Peff\n"},{"id":"164178","messageId":"7vfwqdem0p.fsf@alter.siamese.dyndns.org","threadId":"26824","inReplyTo":"4D8A23CD.9030203@drmicha.warpmail.net","subject":"Re: [RFH] git cherry vs. git rev-list --cherry, or: Why does \"...\" suck?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-03-23T18:20:54Z","receivedAt":"2011-03-23T18:20:54Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael J Gruber <git@drmicha.warpmail.net> writes:\n\n> Adding some recent insight:\n>\n> Michael J Gruber venit, vidit, dixit 22.03.2011 13:07:\n>> Performance\n>> ===========\n>> \n>> I don't get this:\n>> \n>> git cherry A B: 0.4s\n>> git rev-list --cherry A...B: 1.7s\n>> (more details below)\n>\n> I can get the latter down to 0.95s and this\n>\n>> merge-base A B: 0.95s\n>> merge-base --all A B: 0.95s\n>> rev-parse A...B: 0.95s\n>\n> to 0.16s each. The downside is that merge-base may give a few\n> unneccessary candidates (commits which are ancestors of other commits it\n> returns), but this does not change the results for rev-list, of course.\n>\n> I get this dramatic speedup by removing the check for duplicates from\n> get_merge_bases_many() in commit.c. After a first merge_bases_many()\n> run, returning N commits, that check calls merge_bases_many() again for\n> each pair (N choose 2) to check whether one is contained in the other.\n> Quite a bottleneck. Removing it works great. But can we live with a few\n> additional merge bases?\n\nWhen we run merge-base as the top-level command (this includes\nreduce_heads() that is used by \"git merge\"), we have to cull unnecessary\nphantom bases that can be reached by other bases, so you are not allowed\nto make such a change unconditionally.\n\nPassing down a parameter from a caller that is prepared to handle phantom\nmerge bases correctly is probably the right approach.  Existing callers\ncan make \"safer\" calls for now; you can later examine them and turn them\ninto \"faster\" calls if they operate correctly given a result that contain\nphantom bases.\n"},{"id":"164212","messageId":"4D8AF508.7070709@drmicha.warpmail.net","threadId":"26824","inReplyTo":"7vfwqdem0p.fsf@alter.siamese.dyndns.org","subject":"Re: [RFH] git cherry vs. git rev-list --cherry, or: Why does \"...\" suck?","fromName":"Michael J Gruber","fromEmail":"git@drmicha.warpmail.net","sentAt":"2011-03-24T07:38:48Z","receivedAt":"2011-03-24T07:38:48Z","isPatch":false,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"Junio C Hamano venit, vidit, dixit 23.03.2011 19:20:\n> Michael J Gruber <git@drmicha.warpmail.net> writes:\n> \n>> Adding some recent insight:\n>>\n>> Michael J Gruber venit, vidit, dixit 22.03.2011 13:07:\n>>> Performance\n>>> ===========\n>>>\n>>> I don't get this:\n>>>\n>>> git cherry A B: 0.4s\n>>> git rev-list --cherry A...B: 1.7s\n>>> (more details below)\n>>\n>> I can get the latter down to 0.95s and this\n>>\n>>> merge-base A B: 0.95s\n>>> merge-base --all A B: 0.95s\n>>> rev-parse A...B: 0.95s\n>>\n>> to 0.16s each. The downside is that merge-base may give a few\n>> unneccessary candidates (commits which are ancestors of other commits it\n>> returns), but this does not change the results for rev-list, of course.\n>>\n>> I get this dramatic speedup by removing the check for duplicates from\n>> get_merge_bases_many() in commit.c. After a first merge_bases_many()\n>> run, returning N commits, that check calls merge_bases_many() again for\n>> each pair (N choose 2) to check whether one is contained in the other.\n>> Quite a bottleneck. Removing it works great. But can we live with a few\n>> additional merge bases?\n> \n> When we run merge-base as the top-level command (this includes\n> reduce_heads() that is used by \"git merge\"), we have to cull unnecessary\n> phantom bases that can be reached by other bases, so you are not allowed\n> to make such a change unconditionally.\n> \n> Passing down a parameter from a caller that is prepared to handle phantom\n> merge bases correctly is probably the right approach.  Existing callers\n> can make \"safer\" calls for now; you can later examine them and turn them\n> into \"faster\" calls if they operate correctly given a result that contain\n> phantom bases.\n\nYes, I was thinking of having thorough vs. fast mode, but I'll dig more\ninto merge_bases_many().\n\nMy current impression is that those phantom merge bases appear only\n(mainly?) when there are severe date ordering problems in the dag.\nmerge_bases_many() uses commit_list_insert_by_date(), and given the way\nit walks, later merge bases which are ancestors of another one get\nmarked STALE automatically.\n\nFor callers which are interested in one base only, the check makes a\ndifference only if there are date ordering problems.\n\nIn my A B example, merge_bases_many() comes up with the correct 25 ones\nduring its first run, and then gets called 300 times again (25*24/2) to\ncheck each pair of them, without any reduction. (Clearly, it's a non\nissue in the case of unique merge base.)\n\nWhat I'm mainly interested in is the A...B case. And for a revision walk\nwith one A...B range and revs->limited, one could even embed the whole\nmb-logic into the walk! But I don't see how to do this for multiple\nsymmetric ranges.\n\nMichael\n"}]}