{"thread":{"id":"50861","subject":"Bad performance when using git log --parents (used by gitk)","startedAt":"2019-04-02T11:32:45Z","lastAt":"2019-04-04T01:54:37Z","messageCount":7,"participants":["Björn Pettersson A","Jeff King","Johannes Schindelin"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"372974","messageId":"HE1PR0702MB3788FCDAB764252D9CBB42E5B0560@HE1PR0702MB3788.eurprd07.prod.outlook.com","threadId":"50861","inReplyTo":null,"subject":"Bad performance when using git log --parents (used by gitk)","fromName":"Björn Pettersson A","fromEmail":"bjorn.a.pettersson@ericsson.com","sentAt":"2019-04-02T11:31:59Z","receivedAt":"2019-04-02T11:32:45Z","isPatch":false,"sender":{"key":"bjorn.a.pettersson@ericsson.com","avatar":null},"body":"Hi!\n\nThe LLVM project is moving from SVN to git, creating a single repo on github for several LLVM sub-projects.\nIn the past we have had one git repo mirror for each sub-project (mirroring the SVN projects).\n\nUnfortunately, I've seen some performance problems with git (or rather gitk) when starting to use the new llvm-project git repo.\n\nIt seems like gitk is using \"git log --no-color -z --pretty=raw --show-notes --parents --boundary HEAD -- <file>\" when loading the history. So it seems to be the performance of \"git log --parents . -- <file>\" that is causing the performance problem afaict.\n\n\nExample:\n\nRun \"git log --parents\" for an old file (bswap.ll), and a brand new file (dummy).\n\nFirst we try it using the new \"llvm-project\" repository.\n\n--------------------------------------------------------------------------------\nbash-4.1$ git clone https://github.com/llvm/llvm-project.git && cd llvm-project\nCloning into 'llvm-project'...\nremote: Enumerating objects: 130, done.\nremote: Counting objects: 100% (130/130), done.\nremote: Compressing objects: 100% (98/98), done.\nremote: Total 3361980 (delta 39), reused 58 (delta 26), pack-reused 3361850\nReceiving objects: 100% (3361980/3361980), 605.50 MiB | 15.63 MiB/s, done.\nResolving deltas: 100% (2755544/2755544), done.\nChecking out files: 100% (82618/82618), done.\n\nbash-4.1$ /usr/bin/time git log --parents -- llvm/test/CodeGen/Generic/bswap.ll >> /dev/null\n190.63user 0.43system 3:11.01elapsed 100%CPU (0avgtext+0avgdata 702756maxresident)k\n232inputs+0outputs (2major+177913minor)pagefaults 0swaps\n\nbash-4.1$ touch dummy\nbash-4.1$ git add dummy\nbash-4.1$ git commit -m \"test\"\n[master ce43ac2e487] test\n 1 file changed, 0 insertions(+), 0 deletions(-)\n create mode 100644 dummy\nbash-4.1$ /usr/bin/time git log --parents -- dummy >> /dev/null\n205.54user 0.37system 3:25.83elapsed 100%CPU (0avgtext+0avgdata 644576maxresident)k\n0inputs+0outputs (0major+163134minor)pagefaults 0swaps\n--------------------------------------------------------------------------------\n\n\nNow do the same for the old \"llvm\" repository.\n\n--------------------------------------------------------------------------------\nbash-4.1$ git clone https://github.com/llvm-mirror/llvm.git llvm && cd llvm\nCloning into 'llvm'...\nremote: Enumerating objects: 84, done.\nremote: Counting objects: 100% (84/84), done.\nremote: Compressing objects: 100% (61/61), done.\nremote: Total 1673859 (delta 25), reused 35 (delta 23), pack-reused 1673775\nReceiving objects: 100% (1673859/1673859), 373.08 MiB | 12.72 MiB/s, done.\nResolving deltas: 100% (1369306/1369306), done.\nChecking out files: 100% (36477/36477), done.\nbash-4.1$ /usr/bin/time git log --parents -- test/CodeGen/Generic/bswap.ll >> /dev/null\n4.89user 0.27system 0:05.19elapsed 99%CPU (0avgtext+0avgdata 468072maxresident)k\n0inputs+0outputs (0major+120244minor)pagefaults 0swaps\n\nbash-4.1$ touch dummy\nbash-4.1$ git add dummy\nbash-4.1$ git commit -m \"test\"\n[master 1db81b43a30] test\n 1 file changed, 0 insertions(+), 0 deletions(-)\n create mode 100644 dummy\nbash-4.1$ /usr/bin/time git log --parents -- dummy >> /dev/null\n4.05user 0.24system 0:04.32elapsed 99%CPU (0avgtext+0avgdata 437920maxresident)k\n0inputs+0outputs (0major+112503minor)pagefaults 0swaps\n--------------------------------------------------------------------------------\n\n\nSo for bswap.ll it takes about 190/5 = 38 times longer time to run \"git log --parents\",\nand for the new dummy file it takes 205/4 = 51 times longer time, when using the new repo.\n\nThe size of the llvm-project repo is a little bit larger (since we have merged\nseveral project, so the number of commits increases from ~180000 to ~310000, but I doubt\nthat such an increase should affect the time for git log --parents by a factor of 50.\n\n\nFrom what I understand --parents can take some time, but I see huge degradation when using our new repo compared to the old.\nNot sure if just the repo is too large (or poorly packed?), or if this is a git problem.\n\nAny help understanding this is welcome.\n\nI used git version 2.20.0 in the tests above.\n\n\nPS. I also think that the problem can be seen for files with longer history, for example CODE_OWNERS.txt (llvm/CODE_OWNERS.txt in llvm-project). But then the git log command starts printing commits much sooner. So with gitk I actually get to see some history just after a few seconds also when using llvm-project (even though it takes some time to load the full history). For the files with a very short history (like the dummy file example) the printout won't happen until at the end (after 200 seconds) so git log (and gitk) just appears to be stuck. Is git log caching the result somehow, not printing anything until it has more than one commit to print?\n\nRegards,\nBjörn Pettersson A    \n\nEricsson\nDatalinjen 4 (Hus K)\n58330, Linköping\nSweden\n"},{"id":"372979","messageId":"20190402132756.GB13141@sigill.intra.peff.net","threadId":"50861","inReplyTo":"HE1PR0702MB3788FCDAB764252D9CBB42E5B0560@HE1PR0702MB3788.eurprd07.prod.outlook.com","subject":"Re: Bad performance when using git log --parents (used by gitk)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-04-02T13:27:56Z","receivedAt":"2019-04-02T13:28:00Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Apr 02, 2019 at 11:31:59AM +0000, Björn Pettersson A wrote:\n\n> Example:\n> \n> Run \"git log --parents\" for an old file (bswap.ll), and a brand new file (dummy).\n\nInteresting case. I was able to reproduce it here pretty easily, and I\nhave a start on a solution below.\n\n> So for bswap.ll it takes about 190/5 = 38 times longer time to run \"git log --parents\",\n> and for the new dummy file it takes 205/4 = 51 times longer time, when using the new repo.\n> \n> The size of the llvm-project repo is a little bit larger (since we have merged\n> several project, so the number of commits increases from ~180000 to ~310000, but I doubt\n> that such an increase should affect the time for git log --parents by a factor of 50.\n\nYeah, I'd expect it to take about twice as long (having to sort through\nabout twice as much tree data), which is what I see without --parents.\n\n> From what I understand --parents can take some time, but I see huge\n> degradation when using our new repo compared to the old.\n\nI wouldn't normally expect --parents to take a long time. Most of the\ntime for your command should be going to opening up trees to see if they\ntouched the file in question.\n\nI don't think there's anything wrong with the new repo compared to the\nold. They just happen to have different access patterns.\n\nPoking at your case in perf and gdb, it looks like a resurgence of our\nold friend, the accidentally-quadratic commit_list_insert_by_date. The\nbacktrace where we spend most of our time looks like this:\n\n  #0  commit_list_insert_by_date_cached (...) at revision.c:919\n  #1  0x000055555572c860 in process_parents (...) at revision.c:1009\n  #2  0x0000555555733cc6 in rewrite_one (...) at revision.c:3351\n  #3  0x0000555555733d98 in rewrite_parents (...) at revision.c:3371\n  #4  0x0000555555734906 in simplify_commit (...) at revision.c:3625\n  #5  0x0000555555734c17 in get_revision_1 (...) at revision.c:3691\n\nAnd that explains your observation that you don't see any output.\nNormally Git tries to stream the commits as it finds them, but it\nliterally spends all of its time trying to find the next viable parent\nof that first commit before it can print it. And there are a ton of such\ncommits in your examples, because they each are touched by only one\ncommit relatively near the tip of our traversal (so basically we end up\ngoing through the entire history looking for another parent before\ndeciding there isn't one).\n\nThe root of the issue is that we keep the queue of commits to be shown\nin a linked list, and then insert new ones by date. Naively, this is\nquadratic in the number of commits. We tried to deal with that long ago\nin fce87ae538 (Fix quadratic performance in rewrite_one., 2008-07-12).\n\nThat commit caches the oldest item we've added, which makes a good\nheuristic starting point for inserting the next one, as time tends to go\nbackwards as we traverse.\n\nBut that heuristic seems to behave poorly for your case, presumably\nbecause you have merges which jump around a lot in time (I'm guessing\nthere, based on the fact that you said you merged several projects\ntogether).\n\nIf I tweak the heuristic to just always cache the last-added item,\nrather than the oldest, like so:\n\ndiff --git a/revision.c b/revision.c\nindex eb8e51bc63..492c4247c4 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -921,7 +921,7 @@ static void commit_list_insert_by_date_cached(struct commit *p, struct commit_li\n \telse\n \t\tnew_entry = commit_list_insert_by_date(p, head);\n \n-\tif (cache && (!*cache || p->date < (*cache)->item->date))\n+\tif (cache)\n \t\t*cache = new_entry;\n }\n \n\nI get much better performance:\n\n  $ time git log --parents -- llvm/test/CodeGen/Generic/bswap.ll >/dev/null\n  real\t0m5.674s\n  user\t0m5.546s\n  sys\t0m0.128s\n\nBut there are two issues, still. One is that I'm not sure if that might\nbe hurting other cases. It works for your case because hitting one old\ncommit doesn't permanently adjust our cache into a useless position.\n\nAnd two, 5.6s is still not as cheap as it is without --parents:\n\n  $ time git log -- llvm/test/CodeGen/Generic/bswap.ll >/dev/null\n  real\t0m4.200s\n  user\t0m4.043s\n  sys\t0m0.156s\n\nI think the right solution is scrap this heuristic hackery and use a\nreal priority queue (which we didn't have readily available back in\n2008). The patch below does that, and gives me similar performance to\nthe non-parents case:\n\n  $ time git log --parents -- llvm/test/CodeGen/Generic/bswap.ll >/dev/null\n  real\t0m4.356s\n  user\t0m4.208s\n  sys\t0m0.148s\n\nIt's a little hacky because other parts of the code use lists, so:\n\n  - the underlying process_parents() handles either case, since there's\n    another caller which wants its results in a list\n\n  - we can't convert &revs->commits to prio_queue, because that would\n    have huge fallouts all over the code base (and in particular, it\n    sometimes does want to do in-order traversal, so something like a\n    skip-list would actually be a better data structure). So we end up\n    doing our local computation using the queue, and then dumping the\n    results back into the list. I don't _think_ anybody needs to see\n    those commits in &revs->commits while we're walking the parents.\n\nAs an aside, I notice that the parent-rewriting always uses commit\ntimestamps for ordering (even before my patch). I suspect this may\ninteract in a funny way with --topo-order or --date-order, but any such\nbugs would be the same before or after this patch.\n\n---\ndiff --git a/revision.c b/revision.c\nindex eb8e51bc63..96bac876a6 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -911,26 +911,11 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\tcommit->object.flags |= TREESAME;\n }\n \n-static void commit_list_insert_by_date_cached(struct commit *p, struct commit_list **head,\n-\t\t    struct commit_list *cached_base, struct commit_list **cache)\n-{\n-\tstruct commit_list *new_entry;\n-\n-\tif (cached_base && p->date < cached_base->item->date)\n-\t\tnew_entry = commit_list_insert_by_date(p, &cached_base->next);\n-\telse\n-\t\tnew_entry = commit_list_insert_by_date(p, head);\n-\n-\tif (cache && (!*cache || p->date < (*cache)->item->date))\n-\t\t*cache = new_entry;\n-}\n-\n static int process_parents(struct rev_info *revs, struct commit *commit,\n-\t\t\t   struct commit_list **list, struct commit_list **cache_ptr)\n+\t\t\t   struct commit_list **list, struct prio_queue *queue)\n {\n \tstruct commit_list *parent = commit->parents;\n \tunsigned left_flag;\n-\tstruct commit_list *cached_base = cache_ptr ? *cache_ptr : NULL;\n \n \tif (commit->object.flags & ADDED)\n \t\treturn 0;\n@@ -966,7 +951,9 @@ static int process_parents(struct rev_info *revs, struct commit *commit,\n \t\t\t\tcontinue;\n \t\t\tp->object.flags |= SEEN;\n \t\t\tif (list)\n-\t\t\t\tcommit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);\n+\t\t\t\tcommit_list_insert_by_date(p, list);\n+\t\t\tif (queue)\n+\t\t\t\tprio_queue_put(queue, p);\n \t\t}\n \t\treturn 0;\n \t}\n@@ -1006,7 +993,9 @@ static int process_parents(struct rev_info *revs, struct commit *commit,\n \t\tif (!(p->object.flags & SEEN)) {\n \t\t\tp->object.flags |= SEEN;\n \t\t\tif (list)\n-\t\t\t\tcommit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);\n+\t\t\t\tcommit_list_insert_by_date(p, list);\n+\t\t\tif (queue)\n+\t\t\t\tprio_queue_put(queue, p);\n \t\t}\n \t\tif (revs->first_parent_only)\n \t\t\tbreak;\n@@ -3341,14 +3330,14 @@ int prepare_revision_walk(struct rev_info *revs)\n \treturn 0;\n }\n \n-static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp)\n+static enum rewrite_result rewrite_one_1(struct rev_info *revs,\n+\t\t\t\t\t struct commit **pp,\n+\t\t\t\t\t struct prio_queue *queue)\n {\n-\tstruct commit_list *cache = NULL;\n-\n \tfor (;;) {\n \t\tstruct commit *p = *pp;\n \t\tif (!revs->limited)\n-\t\t\tif (process_parents(revs, p, &revs->commits, &cache) < 0)\n+\t\t\tif (process_parents(revs, p, NULL, queue) < 0)\n \t\t\t\treturn rewrite_one_error;\n \t\tif (p->object.flags & UNINTERESTING)\n \t\t\treturn rewrite_one_ok;\n@@ -3362,6 +3351,31 @@ static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp\n \t}\n }\n \n+static void merge_queue_into_list(struct prio_queue *q, struct commit_list **list)\n+{\n+\twhile (q->nr) {\n+\t\tstruct commit *item = prio_queue_peek(q);\n+\t\tstruct commit_list *p = *list;\n+\n+\t\tif (p && p->item->date > item->date)\n+\t\t\tlist = &p->next;\n+\t\telse {\n+\t\t\tp = commit_list_insert(item, list);\n+\t\t\tlist = &p->next; /* skip newly added item */\n+\t\t\tprio_queue_get(q); /* pop item */\n+\t\t}\n+\t}\n+}\n+\n+static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp)\n+{\n+\tstruct prio_queue queue = { compare_commits_by_commit_date };\n+\tenum rewrite_result ret = rewrite_one_1(revs, pp, &queue);\n+\tmerge_queue_into_list(&queue, &revs->commits);\n+\tclear_prio_queue(&queue);\n+\treturn ret;\n+}\n+\n int rewrite_parents(struct rev_info *revs, struct commit *commit,\n \trewrite_parent_fn_t rewrite_parent)\n {\n"},{"id":"372984","messageId":"HE1PR0702MB378867A3A8F81CB475882A28B0560@HE1PR0702MB3788.eurprd07.prod.outlook.com","threadId":"50861","inReplyTo":"20190402132756.GB13141@sigill.intra.peff.net","subject":"RE: Bad performance when using git log --parents (used by gitk)","fromName":"Björn Pettersson A","fromEmail":"bjorn.a.pettersson@ericsson.com","sentAt":"2019-04-02T15:07:15Z","receivedAt":"2019-04-02T15:07:22Z","isPatch":false,"sender":{"key":"bjorn.a.pettersson@ericsson.com","avatar":null},"body":"Hello Jeff!\n\nThanks for a quick reply (with lots of details).\n\nHitting some quadratic complexity algorithm explains why the \"degradation\"\nis so huge. And if I understand it correctly we are more or less \"unlucky\"\nto hit such access patterns more often in the new repo.\n\nAnyway, nice to see that you already have some ideas regarding how to\nimprove this.\n\nRegards,\nBjörn\n\n> -----Original Message-----\n> From: Jeff King <peff@peff.net>\n> Sent: den 2 april 2019 15:28\n> To: Björn Pettersson A <bjorn.a.pettersson@ericsson.com>\n> Cc: git@vger.kernel.org\n> Subject: Re: Bad performance when using git log --parents (used by gitk)\n> \n> On Tue, Apr 02, 2019 at 11:31:59AM +0000, Björn Pettersson A wrote:\n> \n> > Example:\n> >\n> > Run \"git log --parents\" for an old file (bswap.ll), and a brand new file\n> (dummy).\n> \n> Interesting case. I was able to reproduce it here pretty easily, and I\n> have a start on a solution below.\n> \n> > So for bswap.ll it takes about 190/5 = 38 times longer time to run \"git\n> log --parents\",\n> > and for the new dummy file it takes 205/4 = 51 times longer time, when\n> using the new repo.\n> >\n> > The size of the llvm-project repo is a little bit larger (since we have\n> merged\n> > several project, so the number of commits increases from ~180000 to\n> ~310000, but I doubt\n> > that such an increase should affect the time for git log --parents by a\n> factor of 50.\n> \n> Yeah, I'd expect it to take about twice as long (having to sort through\n> about twice as much tree data), which is what I see without --parents.\n> \n> > From what I understand --parents can take some time, but I see huge\n> > degradation when using our new repo compared to the old.\n> \n> I wouldn't normally expect --parents to take a long time. Most of the\n> time for your command should be going to opening up trees to see if they\n> touched the file in question.\n> \n> I don't think there's anything wrong with the new repo compared to the\n> old. They just happen to have different access patterns.\n> \n> Poking at your case in perf and gdb, it looks like a resurgence of our\n> old friend, the accidentally-quadratic commit_list_insert_by_date. The\n> backtrace where we spend most of our time looks like this:\n> \n>   #0  commit_list_insert_by_date_cached (...) at revision.c:919\n>   #1  0x000055555572c860 in process_parents (...) at revision.c:1009\n>   #2  0x0000555555733cc6 in rewrite_one (...) at revision.c:3351\n>   #3  0x0000555555733d98 in rewrite_parents (...) at revision.c:3371\n>   #4  0x0000555555734906 in simplify_commit (...) at revision.c:3625\n>   #5  0x0000555555734c17 in get_revision_1 (...) at revision.c:3691\n> \n> And that explains your observation that you don't see any output.\n> Normally Git tries to stream the commits as it finds them, but it\n> literally spends all of its time trying to find the next viable parent\n> of that first commit before it can print it. And there are a ton of such\n> commits in your examples, because they each are touched by only one\n> commit relatively near the tip of our traversal (so basically we end up\n> going through the entire history looking for another parent before\n> deciding there isn't one).\n> \n> The root of the issue is that we keep the queue of commits to be shown\n> in a linked list, and then insert new ones by date. Naively, this is\n> quadratic in the number of commits. We tried to deal with that long ago\n> in fce87ae538 (Fix quadratic performance in rewrite_one., 2008-07-12).\n> \n> That commit caches the oldest item we've added, which makes a good\n> heuristic starting point for inserting the next one, as time tends to go\n> backwards as we traverse.\n> \n> But that heuristic seems to behave poorly for your case, presumably\n> because you have merges which jump around a lot in time (I'm guessing\n> there, based on the fact that you said you merged several projects\n> together).\n> \n> If I tweak the heuristic to just always cache the last-added item,\n> rather than the oldest, like so:\n> \n> diff --git a/revision.c b/revision.c\n> index eb8e51bc63..492c4247c4 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -921,7 +921,7 @@ static void commit_list_insert_by_date_cached(struct\n> commit *p, struct commit_li\n>  \telse\n>  \t\tnew_entry = commit_list_insert_by_date(p, head);\n> \n> -\tif (cache && (!*cache || p->date < (*cache)->item->date))\n> +\tif (cache)\n>  \t\t*cache = new_entry;\n>  }\n> \n> \n> I get much better performance:\n> \n>   $ time git log --parents -- llvm/test/CodeGen/Generic/bswap.ll >/dev/null\n>   real\t0m5.674s\n>   user\t0m5.546s\n>   sys\t0m0.128s\n> \n> But there are two issues, still. One is that I'm not sure if that might\n> be hurting other cases. It works for your case because hitting one old\n> commit doesn't permanently adjust our cache into a useless position.\n> \n> And two, 5.6s is still not as cheap as it is without --parents:\n> \n>   $ time git log -- llvm/test/CodeGen/Generic/bswap.ll >/dev/null\n>   real\t0m4.200s\n>   user\t0m4.043s\n>   sys\t0m0.156s\n> \n> I think the right solution is scrap this heuristic hackery and use a\n> real priority queue (which we didn't have readily available back in\n> 2008). The patch below does that, and gives me similar performance to\n> the non-parents case:\n> \n>   $ time git log --parents -- llvm/test/CodeGen/Generic/bswap.ll >/dev/null\n>   real\t0m4.356s\n>   user\t0m4.208s\n>   sys\t0m0.148s\n> \n> It's a little hacky because other parts of the code use lists, so:\n> \n>   - the underlying process_parents() handles either case, since there's\n>     another caller which wants its results in a list\n> \n>   - we can't convert &revs->commits to prio_queue, because that would\n>     have huge fallouts all over the code base (and in particular, it\n>     sometimes does want to do in-order traversal, so something like a\n>     skip-list would actually be a better data structure). So we end up\n>     doing our local computation using the queue, and then dumping the\n>     results back into the list. I don't _think_ anybody needs to see\n>     those commits in &revs->commits while we're walking the parents.\n> \n> As an aside, I notice that the parent-rewriting always uses commit\n> timestamps for ordering (even before my patch). I suspect this may\n> interact in a funny way with --topo-order or --date-order, but any such\n> bugs would be the same before or after this patch.\n> \n> ---\n> diff --git a/revision.c b/revision.c\n> index eb8e51bc63..96bac876a6 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -911,26 +911,11 @@ static void try_to_simplify_commit(struct rev_info\n> *revs, struct commit *commit)\n>  \t\tcommit->object.flags |= TREESAME;\n>  }\n> \n> -static void commit_list_insert_by_date_cached(struct commit *p, struct\n> commit_list **head,\n> -\t\t    struct commit_list *cached_base, struct commit_list **cache)\n> -{\n> -\tstruct commit_list *new_entry;\n> -\n> -\tif (cached_base && p->date < cached_base->item->date)\n> -\t\tnew_entry = commit_list_insert_by_date(p, &cached_base->next);\n> -\telse\n> -\t\tnew_entry = commit_list_insert_by_date(p, head);\n> -\n> -\tif (cache && (!*cache || p->date < (*cache)->item->date))\n> -\t\t*cache = new_entry;\n> -}\n> -\n>  static int process_parents(struct rev_info *revs, struct commit *commit,\n> -\t\t\t   struct commit_list **list, struct commit_list\n> **cache_ptr)\n> +\t\t\t   struct commit_list **list, struct prio_queue *queue)\n>  {\n>  \tstruct commit_list *parent = commit->parents;\n>  \tunsigned left_flag;\n> -\tstruct commit_list *cached_base = cache_ptr ? *cache_ptr : NULL;\n> \n>  \tif (commit->object.flags & ADDED)\n>  \t\treturn 0;\n> @@ -966,7 +951,9 @@ static int process_parents(struct rev_info *revs,\n> struct commit *commit,\n>  \t\t\t\tcontinue;\n>  \t\t\tp->object.flags |= SEEN;\n>  \t\t\tif (list)\n> -\t\t\t\tcommit_list_insert_by_date_cached(p, list,\n> cached_base, cache_ptr);\n> +\t\t\t\tcommit_list_insert_by_date(p, list);\n> +\t\t\tif (queue)\n> +\t\t\t\tprio_queue_put(queue, p);\n>  \t\t}\n>  \t\treturn 0;\n>  \t}\n> @@ -1006,7 +993,9 @@ static int process_parents(struct rev_info *revs,\n> struct commit *commit,\n>  \t\tif (!(p->object.flags & SEEN)) {\n>  \t\t\tp->object.flags |= SEEN;\n>  \t\t\tif (list)\n> -\t\t\t\tcommit_list_insert_by_date_cached(p, list,\n> cached_base, cache_ptr);\n> +\t\t\t\tcommit_list_insert_by_date(p, list);\n> +\t\t\tif (queue)\n> +\t\t\t\tprio_queue_put(queue, p);\n>  \t\t}\n>  \t\tif (revs->first_parent_only)\n>  \t\t\tbreak;\n> @@ -3341,14 +3330,14 @@ int prepare_revision_walk(struct rev_info *revs)\n>  \treturn 0;\n>  }\n> \n> -static enum rewrite_result rewrite_one(struct rev_info *revs, struct\n> commit **pp)\n> +static enum rewrite_result rewrite_one_1(struct rev_info *revs,\n> +\t\t\t\t\t struct commit **pp,\n> +\t\t\t\t\t struct prio_queue *queue)\n>  {\n> -\tstruct commit_list *cache = NULL;\n> -\n>  \tfor (;;) {\n>  \t\tstruct commit *p = *pp;\n>  \t\tif (!revs->limited)\n> -\t\t\tif (process_parents(revs, p, &revs->commits, &cache) < 0)\n> +\t\t\tif (process_parents(revs, p, NULL, queue) < 0)\n>  \t\t\t\treturn rewrite_one_error;\n>  \t\tif (p->object.flags & UNINTERESTING)\n>  \t\t\treturn rewrite_one_ok;\n> @@ -3362,6 +3351,31 @@ static enum rewrite_result rewrite_one(struct\n> rev_info *revs, struct commit **pp\n>  \t}\n>  }\n> \n> +static void merge_queue_into_list(struct prio_queue *q, struct commit_list\n> **list)\n> +{\n> +\twhile (q->nr) {\n> +\t\tstruct commit *item = prio_queue_peek(q);\n> +\t\tstruct commit_list *p = *list;\n> +\n> +\t\tif (p && p->item->date > item->date)\n> +\t\t\tlist = &p->next;\n> +\t\telse {\n> +\t\t\tp = commit_list_insert(item, list);\n> +\t\t\tlist = &p->next; /* skip newly added item */\n> +\t\t\tprio_queue_get(q); /* pop item */\n> +\t\t}\n> +\t}\n> +}\n> +\n> +static enum rewrite_result rewrite_one(struct rev_info *revs, struct\n> commit **pp)\n> +{\n> +\tstruct prio_queue queue = { compare_commits_by_commit_date };\n> +\tenum rewrite_result ret = rewrite_one_1(revs, pp, &queue);\n> +\tmerge_queue_into_list(&queue, &revs->commits);\n> +\tclear_prio_queue(&queue);\n> +\treturn ret;\n> +}\n> +\n>  int rewrite_parents(struct rev_info *revs, struct commit *commit,\n>  \trewrite_parent_fn_t rewrite_parent)\n>  {\n"},{"id":"372987","messageId":"nycvar.QRO.7.76.6.1904022017510.41@tvgsbejvaqbjf.bet","threadId":"50861","inReplyTo":"HE1PR0702MB378867A3A8F81CB475882A28B0560@HE1PR0702MB3788.eurprd07.prod.outlook.com","subject":"RE: Bad performance when using git log --parents (used by gitk)","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2019-04-02T18:20:05Z","receivedAt":"2019-04-02T18:20:12Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Björn,\n\nOn Tue, 2 Apr 2019, Björn Pettersson A wrote:\n\n> Thanks for a quick reply (with lots of details).\n>\n> Hitting some quadratic complexity algorithm explains why the \"degradation\"\n> is so huge. And if I understand it correctly we are more or less \"unlucky\"\n> to hit such access patterns more often in the new repo.\n>\n> Anyway, nice to see that you already have some ideas regarding how to\n> improve this.\n\nIn the meantime, maybe the commit graph feature can help you?\n\n\tgit config --global core.commitGraph true\n\tgit config --global gc.writeCommitGraph true\n\tgit commit-graph write --reachable\n\nThe idea being that the commit graph extracts a lot of information\npre-emptively and makes the lookup of those bits faster than unpacking the\ncommits all the time.\n\nCiao,\nJohannes\n"},{"id":"373083","messageId":"20190404013606.GB4409@sigill.intra.peff.net","threadId":"50861","inReplyTo":"nycvar.QRO.7.76.6.1904022017510.41@tvgsbejvaqbjf.bet","subject":"Re: Bad performance when using git log --parents (used by gitk)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-04-04T01:36:07Z","receivedAt":"2019-04-04T01:36:10Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Apr 02, 2019 at 08:20:05PM +0200, Johannes Schindelin wrote:\n\n> > Hitting some quadratic complexity algorithm explains why the \"degradation\"\n> > is so huge. And if I understand it correctly we are more or less \"unlucky\"\n> > to hit such access patterns more often in the new repo.\n> >\n> > Anyway, nice to see that you already have some ideas regarding how to\n> > improve this.\n> \n> In the meantime, maybe the commit graph feature can help you?\n> \n> \tgit config --global core.commitGraph true\n> \tgit config --global gc.writeCommitGraph true\n> \tgit commit-graph write --reachable\n> \n> The idea being that the commit graph extracts a lot of information\n> pre-emptively and makes the lookup of those bits faster than unpacking the\n> commits all the time.\n\nI'd definitely encourage Björn (or anybody with a biggish repo) to check\nout the commit-graph work, because it's really cool. But it won't help\nmuch here, because the quadratic loop is just on linked-list insertion.\nWe're literally spending all of our time chasing pointers in memory.\n\n-Peff\n"},{"id":"373084","messageId":"20190404014108.GC4409@sigill.intra.peff.net","threadId":"50861","inReplyTo":"20190402132756.GB13141@sigill.intra.peff.net","subject":"[PATCH] revision: use a prio_queue to hold rewritten parents","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-04-04T01:41:09Z","receivedAt":"2019-04-04T01:41:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Apr 02, 2019 at 09:27:56AM -0400, Jeff King wrote:\n\n> On Tue, Apr 02, 2019 at 11:31:59AM +0000, Björn Pettersson A wrote:\n> \n> > Example:\n> > \n> > Run \"git log --parents\" for an old file (bswap.ll), and a brand new file (dummy).\n> \n> Interesting case. I was able to reproduce it here pretty easily, and I\n> have a start on a solution below.\n\nAfter a bit of pondering and some experimentation, I think this is the\nright direction. Here's that patch again (with a few minor tweaks), and\nan excessively long commit message which I hope explains everything.\n\nThanks for a very interesting case (and with an easy reproduction\nrecipe!).\n\n-- >8 --\nSubject: [PATCH] revision: use a prio_queue to hold rewritten parents\n\nThis patch fixes a quadratic list insertion in rewrite_one() when\npathspec limiting is combined with --parents. What happens is something\nlike this:\n\n  1. We see that some commit X touches the path, so we try to rewrite\n     its parents.\n\n  2. rewrite_one() loops forever, rewriting parents, until it finds a\n     relevant parent (or hits the root and decides there are none). The\n     heavy lifting is done by process_parent(), which uses\n     try_to_simplify_commit() to drop parents.\n\n  3. process_parent() puts any intermediate parents into the\n     &revs->commits list, inserting by commit date as usual.\n\nSo if commit X is recent, and then there's a large chunk of history that\ndoesn't touch the path, we may add a lot of commits to &revs->commits.\nAnd insertion by commit date is O(n) in the worst case, making the whole\nthing quadratic.\n\nWe tried to deal with this long ago in fce87ae538 (Fix quadratic\nperformance in rewrite_one., 2008-07-12). In that scheme, we cache the\noldest commit in the list; if the new commit to be added is older, we\ncan start our linear traversal there. This often works well in practice\nbecause parents are older than their descendants, and thus we tend to\nadd older and older commits as we traverse.\n\nBut this isn't guaranteed, and in fact there's a simple case where it is\nnot: merges. Imagine we look at the first parent of a merge and see a\nvery old commit (let's say 3 years old). And on the second parent, as we\ngo back 3 years in history, we might have many commits. That one\nfirst-parent commit has polluted our oldest-commit cache; it will remain\nthe oldest while we traverse a huge chunk of history, during which we\nhave to fall back to the slow, linear method of adding to the list.\n\nNaively, one might imagine that instead of caching the oldest commit,\nwe'd start at the last-added one. But that just makes some cases faster\nwhile making others slower (and indeed, while it made a real-world test\ncase much faster, it does quite poorly in the perf test include here).\nFundamentally, these are just heuristics; our worst case is still\nquadratic, and some cases will approach that.\n\nInstead, let's use a data structure with better worst-case performance.\nSwapping out revs->commits for something else would have repercussions\nall over the code base, but we can take advantage of one fact: for the\nrewrite_one() case, nobody actually needs to see those commits in\nrevs->commits until we've finished generating the whole list.\n\nThat leaves us with two obvious options:\n\n  1. We can generate the list _unordered_, which should be O(n), and\n     then sort it afterwards, which would be O(n log n) total. This is\n     \"sort-after\" below.\n\n  2. We can insert the commits into a separate data structure, like a\n     priority queue. This is \"prio-queue\" below.\n\nI expected that sort-after would be the fastest (since it saves us the\nextra step of copying the items into the linked list), but surprisingly\nthe prio-queue seems to be a bit faster.\n\nHere are timings for the new p0001.6 for all three techniques across a\nfew repositories, as compared to master:\n\nmaster              cache-last                sort-after              prio-queue\n--------------------------------------------------------------------------------------------\nGIT_PERF_REPO=git.git\n0.52(0.50+0.02)      0.53(0.51+0.02)  +1.9%   0.37(0.33+0.03) -28.8%  0.37(0.32+0.04) -28.8%\n\nGIT_PERF_REPO=linux.git\n20.81(20.74+0.07)   20.31(20.24+0.07) -2.4%   0.94(0.86+0.07) -95.5%  0.91(0.82+0.09) -95.6%\n\nGIT_PERF_REPO=llvm-project.git\n83.67(83.57+0.09)    4.23(4.15+0.08) -94.9%   3.21(3.15+0.06) -96.2%  2.98(2.91+0.07) -96.4%\n\nA few items to note:\n\n  - the cache-list tweak does improve the bad case for llvm-project.git\n    that started my digging into this problem. But it performs terribly\n    on linux.git, barely helping at all.\n\n  - the sort-after and prio-queue techniques work well. They approach\n    the timing for running without --parents at all, which is what you'd\n    expect (see below for more data).\n\n  - prio-queue just barely outperforms sort-after. As I said, I'm not\n    really sure why this is the case, but it is. You can see it even\n    more prominently in this real-world case on llvm-project.git:\n\n      git rev-list --parents 07ef786652e7 -- llvm/test/CodeGen/Generic/bswap.ll\n\n    where prio-queue routinely outperforms sort-after by about 7%. One\n    guess is that the prio-queue may just be more efficient because it\n    uses a compact array.\n\nThere are three new perf tests:\n\n  - \"rev-list --parents\" gives us a baseline for running with --parents.\n    This isn't sped up meaningfully here, because the bad case is\n    triggered only with simplification. But it's good to make sure we\n    don't screw it up (now, or in the future).\n\n  - \"rev-list -- dummy\" gives us a baseline for just traversing with\n    pathspec limiting. This gives a lower bound for the next test (and\n    it's also a good thing for us to be checking in general for\n    regressions, since we don't seem to have any existing tests).\n\n  - \"rev-list --parents -- dummy\" shows off the problem (and our fix)\n\nHere are the timings for those three on llvm-project.git, before and\nafter the fix:\n\nTest                                 master              prio-queue\n------------------------------------------------------------------------------\n0001.3: rev-list --parents           2.24(2.12+0.12)     2.22(2.11+0.11) -0.9%\n0001.5: rev-list -- dummy            2.89(2.82+0.07)     2.92(2.89+0.03) +1.0%\n0001.6: rev-list --parents -- dummy  83.67(83.57+0.09)   2.98(2.91+0.07) -96.4%\n\nChanges in the first two are basically noise, and you can see we\napproach our lower bound in the final one.\n\nNote that we can't fully get rid of the list argument from\nprocess_parents(). Other callers do have lists, and it would be hard to\nconvert them. They also don't seem to have this problem (probably\nbecause they actually remove items from the list as they loop, meaning\nit doesn't grow so large in the first place). So this basically just\ndrops the \"cache_ptr\" parameter (which was used only by the one caller\nwe're fixing here) and replaces it with a prio_queue. Callers are free\nto use either data structure, depending on what they're prepared to\nhandle.\n\nReported-by: Björn Pettersson A <bjorn.a.pettersson@ericsson.com>\nSigned-off-by: Jeff King <peff@peff.net>\n---\n revision.c               | 58 +++++++++++++++++++++++++---------------\n t/perf/p0001-rev-list.sh | 18 +++++++++++++\n 2 files changed, 54 insertions(+), 22 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex eb8e51bc63..8e500441d9 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -911,26 +911,11 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\tcommit->object.flags |= TREESAME;\n }\n \n-static void commit_list_insert_by_date_cached(struct commit *p, struct commit_list **head,\n-\t\t    struct commit_list *cached_base, struct commit_list **cache)\n-{\n-\tstruct commit_list *new_entry;\n-\n-\tif (cached_base && p->date < cached_base->item->date)\n-\t\tnew_entry = commit_list_insert_by_date(p, &cached_base->next);\n-\telse\n-\t\tnew_entry = commit_list_insert_by_date(p, head);\n-\n-\tif (cache && (!*cache || p->date < (*cache)->item->date))\n-\t\t*cache = new_entry;\n-}\n-\n static int process_parents(struct rev_info *revs, struct commit *commit,\n-\t\t\t   struct commit_list **list, struct commit_list **cache_ptr)\n+\t\t\t   struct commit_list **list, struct prio_queue *queue)\n {\n \tstruct commit_list *parent = commit->parents;\n \tunsigned left_flag;\n-\tstruct commit_list *cached_base = cache_ptr ? *cache_ptr : NULL;\n \n \tif (commit->object.flags & ADDED)\n \t\treturn 0;\n@@ -966,7 +951,9 @@ static int process_parents(struct rev_info *revs, struct commit *commit,\n \t\t\t\tcontinue;\n \t\t\tp->object.flags |= SEEN;\n \t\t\tif (list)\n-\t\t\t\tcommit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);\n+\t\t\t\tcommit_list_insert_by_date(p, list);\n+\t\t\tif (queue)\n+\t\t\t\tprio_queue_put(queue, p);\n \t\t}\n \t\treturn 0;\n \t}\n@@ -1006,7 +993,9 @@ static int process_parents(struct rev_info *revs, struct commit *commit,\n \t\tif (!(p->object.flags & SEEN)) {\n \t\t\tp->object.flags |= SEEN;\n \t\t\tif (list)\n-\t\t\t\tcommit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);\n+\t\t\t\tcommit_list_insert_by_date(p, list);\n+\t\t\tif (queue)\n+\t\t\t\tprio_queue_put(queue, p);\n \t\t}\n \t\tif (revs->first_parent_only)\n \t\t\tbreak;\n@@ -3341,14 +3330,14 @@ int prepare_revision_walk(struct rev_info *revs)\n \treturn 0;\n }\n \n-static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp)\n+static enum rewrite_result rewrite_one_1(struct rev_info *revs,\n+\t\t\t\t\t struct commit **pp,\n+\t\t\t\t\t struct prio_queue *queue)\n {\n-\tstruct commit_list *cache = NULL;\n-\n \tfor (;;) {\n \t\tstruct commit *p = *pp;\n \t\tif (!revs->limited)\n-\t\t\tif (process_parents(revs, p, &revs->commits, &cache) < 0)\n+\t\t\tif (process_parents(revs, p, NULL, queue) < 0)\n \t\t\t\treturn rewrite_one_error;\n \t\tif (p->object.flags & UNINTERESTING)\n \t\t\treturn rewrite_one_ok;\n@@ -3362,6 +3351,31 @@ static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp\n \t}\n }\n \n+static void merge_queue_into_list(struct prio_queue *q, struct commit_list **list)\n+{\n+\twhile (q->nr) {\n+\t\tstruct commit *item = prio_queue_peek(q);\n+\t\tstruct commit_list *p = *list;\n+\n+\t\tif (p && p->item->date >= item->date)\n+\t\t\tlist = &p->next;\n+\t\telse {\n+\t\t\tp = commit_list_insert(item, list);\n+\t\t\tlist = &p->next; /* skip newly added item */\n+\t\t\tprio_queue_get(q); /* pop item */\n+\t\t}\n+\t}\n+}\n+\n+static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp)\n+{\n+\tstruct prio_queue queue = { compare_commits_by_commit_date };\n+\tenum rewrite_result ret = rewrite_one_1(revs, pp, &queue);\n+\tmerge_queue_into_list(&queue, &revs->commits);\n+\tclear_prio_queue(&queue);\n+\treturn ret;\n+}\n+\n int rewrite_parents(struct rev_info *revs, struct commit *commit,\n \trewrite_parent_fn_t rewrite_parent)\n {\ndiff --git a/t/perf/p0001-rev-list.sh b/t/perf/p0001-rev-list.sh\nindex ebf172401b..3042a85666 100755\n--- a/t/perf/p0001-rev-list.sh\n+++ b/t/perf/p0001-rev-list.sh\n@@ -14,6 +14,24 @@ test_perf 'rev-list --all --objects' '\n \tgit rev-list --all --objects >/dev/null\n '\n \n+test_perf 'rev-list --parents' '\n+\tgit rev-list --parents HEAD >/dev/null\n+'\n+\n+test_expect_success 'create dummy file' '\n+\techo unlikely-to-already-be-there >dummy &&\n+\tgit add dummy &&\n+\tgit commit -m dummy\n+'\n+\n+test_perf 'rev-list -- dummy' '\n+\tgit rev-list HEAD -- dummy\n+'\n+\n+test_perf 'rev-list --parents -- dummy' '\n+\tgit rev-list --parents HEAD -- dummy\n+'\n+\n test_expect_success 'create new unreferenced commit' '\n \tcommit=$(git commit-tree HEAD^{tree} -p HEAD) &&\n \ttest_export commit\n-- \n2.21.0.714.gd1be1d035b\n\n"},{"id":"373085","messageId":"20190404015432.GD4409@sigill.intra.peff.net","threadId":"50861","inReplyTo":"20190404014108.GC4409@sigill.intra.peff.net","subject":"Re: [PATCH] revision: use a prio_queue to hold rewritten parents","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-04-04T01:54:33Z","receivedAt":"2019-04-04T01:54:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Apr 03, 2019 at 09:41:09PM -0400, Jeff King wrote:\n\n> A few items to note:\n> \n>   - the cache-list tweak does improve the bad case for llvm-project.git\n>     that started my digging into this problem. But it performs terribly\n>     on linux.git, barely helping at all.\n\nOops, that should be cache-last of course.  Just for completeness,\nhere's the patch for that (which I also showed earlier in the thread):\n\n  diff --git a/revision.c b/revision.c\n  index eb8e51bc63..492c4247c4 100644\n  --- a/revision.c\n  +++ b/revision.c\n  @@ -921,7 +921,7 @@ static void commit_list_insert_by_date_cached(struct commit *p, struct commit_li\n   \telse\n   \t\tnew_entry = commit_list_insert_by_date(p, head);\n   \n  -\tif (cache && (!*cache || p->date < (*cache)->item->date))\n  +\tif (cache)\n   \t\t*cache = new_entry;\n   }\n\n>   - prio-queue just barely outperforms sort-after. As I said, I'm not\n>     really sure why this is the case, but it is. You can see it even\n>     more prominently in this real-world case on llvm-project.git:\n> \n>       git rev-list --parents 07ef786652e7 -- llvm/test/CodeGen/Generic/bswap.ll\n> \n>     where prio-queue routinely outperforms sort-after by about 7%. One\n>     guess is that the prio-queue may just be more efficient because it\n>     uses a compact array.\n\nAnd much more interesting, here's the patch for sort-after. It's\npossible I simply screwed something up, and that's why prio-queue is\nfaster.\n\nTwo things to note:\n\n  - it sorts the new list, and then merges it in O(n) into the existing\n    list. This should have identical behavior to the existing\n    insert_by_date if the existing list is not sorted in the same way.\n    I'm not sure if that's possible or not (e.g., due to topo order or\n    similar). If it's not, then it might be slightly faster to just\n    insert into the final list in the first place, and then sort the\n    whole thing as one unit.\n\n  - curiously, this seems to racily fail t6001. That script creates some\n    new commits without using test_tick, so it may end up with several\n    commits with the same timestamp. When this happens, it fails because\n    two of the commits get reordered in the log output.\n\n    That points to the sort not being stable. But generally mergesort\n    _is_ stable (and I'm relying on the existing sort here). And I think\n    my merge operation is stable, too. If anything, I'd have thought I'd\n    screw something up with the prio-queue merge, but that one does\n    behave reliably (heap queues are not inherently stable, but our\n    prio_queue uses a counter to address that).\n\n    So I dunno. Again, it's possible I simply screwed something up.\n\n---\ndiff --git a/revision.c b/revision.c\nindex eb8e51bc63..a8cbe80636 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -911,26 +911,11 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\tcommit->object.flags |= TREESAME;\n }\n \n-static void commit_list_insert_by_date_cached(struct commit *p, struct commit_list **head,\n-\t\t    struct commit_list *cached_base, struct commit_list **cache)\n-{\n-\tstruct commit_list *new_entry;\n-\n-\tif (cached_base && p->date < cached_base->item->date)\n-\t\tnew_entry = commit_list_insert_by_date(p, &cached_base->next);\n-\telse\n-\t\tnew_entry = commit_list_insert_by_date(p, head);\n-\n-\tif (cache && (!*cache || p->date < (*cache)->item->date))\n-\t\t*cache = new_entry;\n-}\n-\n static int process_parents(struct rev_info *revs, struct commit *commit,\n-\t\t\t   struct commit_list **list, struct commit_list **cache_ptr)\n+\t\t\t   struct commit_list **list, int insert_by_date)\n {\n \tstruct commit_list *parent = commit->parents;\n \tunsigned left_flag;\n-\tstruct commit_list *cached_base = cache_ptr ? *cache_ptr : NULL;\n \n \tif (commit->object.flags & ADDED)\n \t\treturn 0;\n@@ -965,8 +950,13 @@ static int process_parents(struct rev_info *revs, struct commit *commit,\n \t\t\tif (p->object.flags & SEEN)\n \t\t\t\tcontinue;\n \t\t\tp->object.flags |= SEEN;\n-\t\t\tif (list)\n-\t\t\t\tcommit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);\n+\t\t\tif (list) {\n+\t\t\t\tif (insert_by_date)\n+\t\t\t\t\tcommit_list_insert_by_date(p, list);\n+\t\t\t\telse\n+\t\t\t\t\tcommit_list_insert(p, list);\n+\t\t\t}\n+\n \t\t}\n \t\treturn 0;\n \t}\n@@ -1005,8 +995,12 @@ static int process_parents(struct rev_info *revs, struct commit *commit,\n \t\tp->object.flags |= left_flag;\n \t\tif (!(p->object.flags & SEEN)) {\n \t\t\tp->object.flags |= SEEN;\n-\t\t\tif (list)\n-\t\t\t\tcommit_list_insert_by_date_cached(p, list, cached_base, cache_ptr);\n+\t\t\tif (list) {\n+\t\t\t\tif (insert_by_date)\n+\t\t\t\t\tcommit_list_insert_by_date(p, list);\n+\t\t\t\telse\n+\t\t\t\t\tcommit_list_insert(p, list);\n+\t\t\t}\n \t\t}\n \t\tif (revs->first_parent_only)\n \t\t\tbreak;\n@@ -1250,7 +1244,7 @@ static int limit_list(struct rev_info *revs)\n \n \t\tif (revs->max_age != -1 && (commit->date < revs->max_age))\n \t\t\tobj->flags |= UNINTERESTING;\n-\t\tif (process_parents(revs, commit, &list, NULL) < 0)\n+\t\tif (process_parents(revs, commit, &list, 1) < 0)\n \t\t\treturn -1;\n \t\tif (obj->flags & UNINTERESTING) {\n \t\t\tmark_parents_uninteresting(commit);\n@@ -3117,7 +3111,7 @@ static void explore_walk_step(struct rev_info *revs)\n \tif (revs->max_age != -1 && (c->date < revs->max_age))\n \t\tc->object.flags |= UNINTERESTING;\n \n-\tif (process_parents(revs, c, NULL, NULL) < 0)\n+\tif (process_parents(revs, c, NULL, 0) < 0)\n \t\treturn;\n \n \tif (c->object.flags & UNINTERESTING)\n@@ -3260,7 +3254,7 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)\n {\n \tstruct commit_list *p;\n \tstruct topo_walk_info *info = revs->topo_walk_info;\n-\tif (process_parents(revs, commit, NULL, NULL) < 0) {\n+\tif (process_parents(revs, commit, NULL, 0) < 0) {\n \t\tif (!revs->ignore_missing_links)\n \t\t\tdie(\"Failed to traverse parents of commit %s\",\n \t\t\t    oid_to_hex(&commit->object.oid));\n@@ -3341,14 +3335,14 @@ int prepare_revision_walk(struct rev_info *revs)\n \treturn 0;\n }\n \n-static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp)\n+static enum rewrite_result rewrite_one_1(struct rev_info *revs,\n+\t\t\t\t\t struct commit **pp,\n+\t\t\t\t\t struct commit_list **list)\n {\n-\tstruct commit_list *cache = NULL;\n-\n \tfor (;;) {\n \t\tstruct commit *p = *pp;\n \t\tif (!revs->limited)\n-\t\t\tif (process_parents(revs, p, &revs->commits, &cache) < 0)\n+\t\t\tif (process_parents(revs, p, list, 0) < 0)\n \t\t\t\treturn rewrite_one_error;\n \t\tif (p->object.flags & UNINTERESTING)\n \t\t\treturn rewrite_one_ok;\n@@ -3362,6 +3356,39 @@ static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp\n \t}\n }\n \n+static struct commit_list *commit_list_merge_by_date(struct commit_list *a,\n+\t\t\t\t\t\t     struct commit_list *b)\n+{\n+\tstruct commit_list *ret = NULL, **tail = &ret;\n+\twhile (a && b) {\n+\t\tif (a->item->date >= b->item->date) {\n+\t\t\t*tail = a;\n+\t\t\ttail = &a->next;\n+\t\t\ta = a->next;\n+\t\t} else {\n+\t\t\t*tail = b;\n+\t\t\ttail = &b->next;\n+\t\t\tb = b->next;\n+\t\t}\n+\t}\n+\tif (a)\n+\t\t*tail = a;\n+\telse\n+\t\t*tail = b;\n+\n+\treturn ret;\n+}\n+\n+static enum rewrite_result rewrite_one(struct rev_info *revs,\n+\t\t\t\t       struct commit **pp)\n+{\n+\tstruct commit_list *list = NULL;\n+\tenum rewrite_result ret = rewrite_one_1(revs, pp, &list);\n+\tcommit_list_sort_by_date(&list);\n+\trevs->commits = commit_list_merge_by_date(revs->commits, list);\n+\treturn ret;\n+}\n+\n int rewrite_parents(struct rev_info *revs, struct commit *commit,\n \trewrite_parent_fn_t rewrite_parent)\n {\n@@ -3681,7 +3708,7 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\t\t\ttry_to_simplify_commit(revs, commit);\n \t\t\telse if (revs->topo_walk_info)\n \t\t\t\texpand_topo_walk(revs, commit);\n-\t\t\telse if (process_parents(revs, commit, &revs->commits, NULL) < 0) {\n+\t\t\telse if (process_parents(revs, commit, &revs->commits, 1) < 0) {\n \t\t\t\tif (!revs->ignore_missing_links)\n \t\t\t\t\tdie(\"Failed to traverse parents of commit %s\",\n \t\t\t\t\t\toid_to_hex(&commit->object.oid));\n"}]}