{"thread":{"id":"41971","subject":"git log with ordering option and --first-parent is unnecessarily slow","startedAt":"2016-04-09T03:55:54Z","lastAt":"2016-04-09T05:42:15Z","messageCount":3,"participants":["Josiah Boning","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"283002","messageId":"CAKdicq8MnZMBV97K5O8Oa1T=PT9DsutmBS+P-bFYitATHH3s+Q@mail.gmail.com","threadId":"41971","inReplyTo":null,"subject":"git log with ordering option and --first-parent is unnecessarily slow","fromName":"Josiah Boning","fromEmail":"jboning@gmail.com","sentAt":"2016-04-09T03:55:54Z","receivedAt":"2016-04-09T03:55:54Z","isPatch":false,"sender":{"key":"jboning@gmail.com","avatar":null},"body":"As measured on linux.git, adding --date-order to a log command can\nresult in a significant slowdown (~25x here; I've seen ~100x on other\nrepositories):\n\n    $ time git log --first-parent --max-count=51 master > /dev/null\n    real    0m0.024s\n    user    0m0.006s\n    sys    0m0.016s\n    $ time git log --date-order --first-parent --max-count=51 master > /dev/null\n    real    0m0.652s\n    user    0m0.570s\n    sys    0m0.074s\n\nIn combination with --first-parent, --date-order (or any other\nordering option) should be a no-op, since --first-parent selects a\nlinear history. So it seems like there's a significant performance win\navailable by ignoring ordering options when --first-parent is present.\nWould this change be desirable? If so, I'll see about submitting a\npatch.\n\nMore generally, it seems like it might be possible to identify when\nthe selected commits are linear and avoid the cost of sorting.\n\nJosiah\n"},{"id":"283004","messageId":"20160409050116.GB25151@sigill.intra.peff.net","threadId":"41971","inReplyTo":"CAKdicq8MnZMBV97K5O8Oa1T=PT9DsutmBS+P-bFYitATHH3s+Q@mail.gmail.com","subject":"Re: git log with ordering option and --first-parent is unnecessarily slow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2016-04-09T05:01:16Z","receivedAt":"2016-04-09T05:01:16Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Apr 08, 2016 at 08:55:54PM -0700, Josiah Boning wrote:\n\n> As measured on linux.git, adding --date-order to a log command can\n> result in a significant slowdown (~25x here; I've seen ~100x on other\n> repositories):\n> \n>     $ time git log --first-parent --max-count=51 master > /dev/null\n>     real    0m0.024s\n>     user    0m0.006s\n>     sys    0m0.016s\n>     $ time git log --date-order --first-parent --max-count=51 master > /dev/null\n>     real    0m0.652s\n>     user    0m0.570s\n>     sys    0m0.074s\n\nTry timing \"git log --first-parent master >/dev/null\". It should be\nabout the same as the latter, which gives a hint about what is going on.\n\nIt's the \"--max-count\" which is interesting here. It is applied _after_\nthe sorting. So in the non-sorted case, git can stream out commits and\nstop after printing 51. In the sorted case, we have to access every\ncommit to get its date (well, every commit on the first-parent path),\nthen sort them, and then return the first 51.\n\n> In combination with --first-parent, --date-order (or any other\n> ordering option) should be a no-op, since --first-parent selects a\n> linear history. So it seems like there's a significant performance win\n> available by ignoring ordering options when --first-parent is present.\n> Would this change be desirable? If so, I'll see about submitting a\n> patch.\n\nI do agree that --date-order on a linear parent walk cannot change the\nordering (which guarantees child-before-parent), and is a noop.  But\nnote that not all first-parent invocations are strictly linear. For\nexample:\n\n  git log --first-parent --date-order master next\n\nwhich starts from two tips. We'd still want to order commits from the\ntwo lists according to --date-order.\n\nI suppose we could catch the single-tip, first-parent case and ignore\nany ordering options which imply child-before-parent (which is currently\nall of them). But I did not think too hard if there are any other corner\ncases. This sounds like a case of \"doctor, it hurts when I do this\". Why\ndo you want to add --date-order in such a case, when it is a noop?\n\n> More generally, it seems like it might be possible to identify when\n> the selected commits are linear and avoid the cost of sorting.\n\nIt's not the cost of sorting. It's the cost of accessing the commits (if\nyou profile, you should see most time spent in zlib). So figuring out\nthat the case is linear will require roughly the same expense.\n\n-Peff\n"},{"id":"283005","messageId":"CAKdicq_uNFcy0_SPephHX9KhEouYdk0ddj4g0y4nAiD90+eH3A@mail.gmail.com","threadId":"41971","inReplyTo":"20160409050116.GB25151@sigill.intra.peff.net","subject":"Re: git log with ordering option and --first-parent is unnecessarily slow","fromName":"Josiah Boning","fromEmail":"jboning@gmail.com","sentAt":"2016-04-09T05:42:15Z","receivedAt":"2016-04-09T05:42:15Z","isPatch":false,"sender":{"key":"jboning@gmail.com","avatar":null},"body":"On Fri, Apr 8, 2016 at 10:01 PM, Jeff King wrote:\n> I do agree that --date-order on a linear parent walk cannot change the\n> ordering (which guarantees child-before-parent), and is a noop.  But\n> note that not all first-parent invocations are strictly linear. For\n> example:\n>\n>   git log --first-parent --date-order master next\n>\n> which starts from two tips. We'd still want to order commits from the\n> two lists according to --date-order.\n\nAh, indeed; multiple tips certainly count as a nonlinearity.\n\n> I suppose we could catch the single-tip, first-parent case and ignore\n> any ordering options which imply child-before-parent (which is currently\n> all of them). But I did not think too hard if there are any other corner\n> cases. This sounds like a case of \"doctor, it hurts when I do this\". Why\n> do you want to add --date-order in such a case, when it is a noop?\n\nIt hurt when I did that, so I stopped. In my case, the git log command\nwas written when the repositories involved were much smaller, so the\ndelay was not so noticeable. Today I found and fixed the\ninvocation--but it still seems nice to fix at the git level, if that's\npossible without adding much complexity.\n\n> It's not the cost of sorting. It's the cost of accessing the commits (if\n> you profile, you should see most time spent in zlib). So figuring out\n> that the case is linear will require roughly the same expense.\n\nI'm imagining that while traversing the commit graph, one could keep\nan is_linear flag, which is set initially if starting from a single\ntip, and becomes unset when a merge commit is encountered. If\nis_linear is still true when the entire requested range or the desired\nnumber of commit sare accumulated, then there's no need to sort.\n\nThis is, as a disclaimer, the guesswork of someone not familiar with\nthe codebase. I'll go read the source before imagining further :)\n\nJosiah\n"}]}