{"thread":{"id":"36715","subject":"Why is --graph --max-count=n so much slower than --graph HEAD~n..?","startedAt":"2014-05-20T22:17:01Z","lastAt":"2014-05-21T00:24:19Z","messageCount":4,"participants":["Mitchel Humpherys","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"242335","messageId":"vnkwd2f8ayea.fsf@mitchelh-linux.qualcomm.com","threadId":"36715","inReplyTo":null,"subject":"Why is --graph --max-count=n so much slower than --graph HEAD~n..?","fromName":"Mitchel Humpherys","fromEmail":"mitch.special@gmail.com","sentAt":"2014-05-20T22:17:01Z","receivedAt":"2014-05-20T22:17:01Z","isPatch":false,"sender":{"key":"mitch.special@gmail.com","avatar":null},"body":"I've noticed that --max-count doesn't seem to speed up `git log --graph'\ncomputation time. Here are some numbers using the linux kernel\nrepository:\n\n | command | time* |\n |----------------------------------+-------|\n | git log --graph --max-count=5000 | 4.11s |\n | git log --graph --max-count=1000 | 4.05s |\n | git log --graph --max-count=500 | 3.95s |\n | git log --graph --max-count=50 | 3.95s |\n | git log --graph --max-count=10 | 3.97s |\n | git log --graph --max-count=1 | 3.96s |\n\nHowever, specifying a manual revision range results in a much more\ndramatic speedup as `n' decreases:\n\n | command | time* |\n |----------------------------------+-------|\n | git log --graph HEAD~5000.. | 6.69s |\n | git log --graph HEAD~1000.. | 1.89s |\n | git log --graph HEAD~500.. | 0.03s |\n | git log --graph HEAD~50.. | 0.02s |\n | git log --graph HEAD~10.. | 0.02s |\n | git log --graph HEAD~1.. | 0.00s |\n\n* All times are \"steady state\" measurements after warming up the disk\n cache by running the command a few times.\n\nI see that the manual revision range doesn't seem to go back as far in\nhistory when I diff the output of the two commands. However, if I add\n`--max-count=50' to the `HEAD~50..' command I get the exact same commits\nbut with fewer \"dangling\" lines at the bottom of the graph in the\n`HEAD~50..' approach.\n\nAnyone care to provide any insight about what's going on here? Is this\nexpected behavior? Is there any low-hanging fruit for optimizing\n--max-count --graph?\n\n-- \nMitch\n"},{"id":"242339","messageId":"xmqq61l0rrng.fsf@gitster.dls.corp.google.com","threadId":"36715","inReplyTo":"vnkwd2f8ayea.fsf@mitchelh-linux.qualcomm.com","subject":"Re: Why is --graph --max-count=n so much slower than --graph HEAD~n..?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-05-20T22:50:43Z","receivedAt":"2014-05-20T22:50:43Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Mitchel Humpherys writes:\n\n> I've noticed that --max-count doesn't seem to speed up `git log --graph'\n> computation time.\n\nAFAIK, --graph wants to compute the whole history and the max-count\nonly affects the output phase after --graph does its computation.\n\nBesides, \"log --max-count=n\" and \"log HEAD~n..\" compute completely\ndifferent things, so the comparison is apples and oranges.\n"},{"id":"242343","messageId":"vnkw4n0kat01.fsf@mitchelh-linux.qualcomm.com","threadId":"36715","inReplyTo":"xmqq61l0rrng.fsf@gitster.dls.corp.google.com","subject":"Re: Why is --graph --max-count=n so much slower than --graph HEAD~n..?","fromName":"Mitchel Humpherys","fromEmail":"mitch.special@gmail.com","sentAt":"2014-05-21T00:13:34Z","receivedAt":"2014-05-21T00:13:34Z","isPatch":false,"sender":{"key":"mitch.special@gmail.com","avatar":null},"body":"On Tue, May 20 2014 at 03:50:43 PM, Junio C Hamano wrote:\n> Mitchel Humpherys writes:\n>\n>> I've noticed that --max-count doesn't seem to speed up `git log --graph'\n>> computation time.\n>\n> AFAIK, --graph wants to compute the whole history and the max-count\n> only affects the output phase after --graph does its computation.\n>\n> Besides, \"log --max-count=n\" and \"log HEAD~n..\" compute completely\n> different things, so the comparison is apples and oranges.\n\nYes, apples and oranges in a black box :). I provided the\nHEAD~n.. measurements just to show that we can get (almost) the exact\nsame output another way and it's much faster. It just \"seems like\"\n--max-count=n should speed things up as n decreases...\n\n\n-- \nMitch\n"},{"id":"242344","messageId":"CAPc5daWBKa2kTe6jEcNk2=Xqh+R-mMFqL2tTpHERtPjPkAAvGg@mail.gmail.com","threadId":"36715","inReplyTo":"vnkw4n0kat01.fsf@mitchelh-linux.qualcomm.com","subject":"Re: Why is --graph --max-count=n so much slower than --graph HEAD~n..?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-05-21T00:24:19Z","receivedAt":"2014-05-21T00:24:19Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Surely. I am on a bus with terrible WiFi that does not let me use the\nusual terminal,\nbut you would find a code in revision.c that sets revs->topo_order = 1\nwhen it parses\n\"--graph\" option. If you disable it, that would stop \"--graph\" from\nwanting to compute\nthe whole history before starting to emit stuff (and then stop at nth\none with --max-count).\n\nI do not know what other side effects such a change would have, though.\n\nOn Tue, May 20, 2014 at 5:13 PM, Mitchel Humpherys\n wrote:\n> On Tue, May 20 2014 at 03:50:43 PM, Junio C Hamano wrote:\n>> Mitchel Humpherys writes:\n>>\n>>> I've noticed that --max-count doesn't seem to speed up `git log --graph'\n>>> computation time.\n>>\n>> AFAIK, --graph wants to compute the whole history and the max-count\n>> only affects the output phase after --graph does its computation.\n>>\n>> Besides, \"log --max-count=n\" and \"log HEAD~n..\" compute completely\n>> different things, so the comparison is apples and oranges.\n>\n> Yes, apples and oranges in a black box :). I provided the\n> HEAD~n.. measurements just to show that we can get (almost) the exact\n> same output another way and it's much faster. It just \"seems like\"\n> --max-count=n should speed things up as n decreases...\n>\n>\n> --\n> Mitch\n"}]}