{"thread":{"id":"14429","subject":"[RFC PATCH] Fix quadratic performance in rewrite_one.","startedAt":"2008-07-12T18:00:57Z","lastAt":"2008-07-13T00:37:58Z","messageCount":3,"participants":["Alexander N. Gavrilov","Linus Torvalds","Alexander Gavrilov"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"83098","messageId":"200807122200.58187.angavrilov@gmail.com","threadId":"14429","inReplyTo":null,"subject":"[RFC PATCH] Fix quadratic performance in rewrite_one.","fromName":"Alexander N. Gavrilov","fromEmail":"angavrilov@gmail.com","sentAt":"2008-07-12T18:00:57Z","receivedAt":"2008-07-12T18:00:57Z","isPatch":true,"sender":{"key":"angavrilov@gmail.com","avatar":"https://avatars.githubusercontent.com/u/42666?v=4"},"body":"Parent commits are usually older than their children. Thus,\non each iteration of the loop in rewrite_one, add_parents_to_list\ntraverses all commits previously processed by the loop.\nIt performs very poorly in case of very long rewrite chains.\n\nSigned-off-by: Alexander Gavrilov <angavrilov@gmail.com>\n---\n\t\n\tWhile experimenting with a large Git repository (~10 years of history), I noticed that\n\tgitk (and git-log) is very slow when asked to show history for a recently created directory:\n\n\t$ time git log --no-color --pretty=oneline --parents --boundary -- A_5_Year_Old_Dir | wc\n\t1620    8042  166759\n\n\treal    0m29.969s\n\tuser    0m28.419s\n\tsys     0m0.304s\n\n\t$ time git log --no-color --pretty=oneline --parents --boundary -- A_3_Year_Old_Dir | wc\n\t66     315    6599\n\t\n\treal    1m41.523s\n\tuser    1m38.585s\n\tsys     0m0.549s\n\n\t$ time git log --no-color --pretty=oneline --parents --boundary -- A_1_Year_Old_Dir | wc\n\t18     108    1898\n\t\n\treal    3m33.023s\n\tuser    3m28.817s\n\tsys     0m0.859s\n\t\n\tProfiling showed that most of the time is spent manipulating commit lists:\n\t\n\t%   cumulative   self              self     total           \n\ttime   seconds   seconds    calls   s/call   s/call  name    \n\t98.91    206.21   206.21    76909     0.00     0.00  insert_by_date\n\t0.36    206.97     0.76   409268     0.00     0.00  find_pack_entry_one\n\t0.17    207.33     0.36   258208     0.00     0.00  unpack_object_header_gently\n\t\n\tAfter some research and debugging I narrowed it down to this loop in rewrite_one (revision.c):\n\t\n\t\tfor (;;) {\n\t\t\tstruct commit *p = *pp;\n\t\t\t...\n\t\t\t\tif (add_parents_to_list(revs, p, &revs->commits) < 0)\n\t\t\t...\n\t\t\t*pp = p->parents->item;\n\t\t}\n\t\n\tWhen git-log is called for a recently created directory, all history before its creation ends up\n\tbeing processed in this loop. Since add_parents_to_list traverses the list linearly to find the\n\tpoint of insertion, which in this case is always at the end of the list, it actually works\n\tin quadratical time.\n\t\n\tI made a fix for it by caching a pointer to the farthest added element. The performance gain\n\tis obvious, but as it's my first ever change in Git source code, I believe that there is a better\n\tsolution, or, at least, implementation.\n\t\n\t$ time git log --no-color --pretty=oneline --parents --boundary -- A_1_Year_Old_Dir | wc\n\t18     108    1898\n\t\n\treal    0m4.101s\n\tuser    0m3.897s\n\tsys     0m0.123s\n\t\n\tAlexander.\n\n\n revision.c |   34 ++++++++++++++++++++++++++++------\n 1 files changed, 28 insertions(+), 6 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex fc66755..5bf8039 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -412,11 +412,31 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \tcommit->object.flags |= TREESAME;\n }\n \n-static int add_parents_to_list(struct rev_info *revs, struct commit *commit, struct commit_list **list)\n+static void 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 = insert_by_date(p, &cached_base->next);\n+\t}\n+\telse {\n+\t\tnew_entry = insert_by_date(p, head);\n+\t}\n+\t\n+\tif (cache && (!*cache || p->date < (*cache)->item->date)) {\n+\t\t*cache = new_entry;\n+\t}\n+}\n+\n+static int add_parents_to_list(struct rev_info *revs, struct commit *commit,\n+\t\t    struct commit_list **list, struct commit_list **cache_ptr)\n {\n \tstruct commit_list *parent = commit->parents;\n \tunsigned left_flag;\n \n+\tstruct commit_list *cached_base = cache_ptr ? *cache_ptr : NULL;\n+\n \tif (commit->object.flags & ADDED)\n \t\treturn 0;\n \tcommit->object.flags |= ADDED;\n@@ -445,7 +465,7 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit, str\n \t\t\tif (p->object.flags & SEEN)\n \t\t\t\tcontinue;\n \t\t\tp->object.flags |= SEEN;\n-\t\t\tinsert_by_date(p, list);\n+\t\t\tinsert_by_date_cached(p, list, cached_base, cache_ptr);\n \t\t}\n \t\treturn 0;\n \t}\n@@ -470,7 +490,7 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit, str\n \t\tp->object.flags |= left_flag;\n \t\tif (!(p->object.flags & SEEN)) {\n \t\t\tp->object.flags |= SEEN;\n-\t\t\tinsert_by_date(p, list);\n+\t\t\tinsert_by_date_cached(p, list, cached_base, cache_ptr);\n \t\t}\n \t\tif(revs->first_parent_only)\n \t\t\tbreak;\n@@ -611,7 +631,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 (add_parents_to_list(revs, commit, &list) < 0)\n+\t\tif (add_parents_to_list(revs, commit, &list, NULL) < 0)\n \t\t\treturn -1;\n \t\tif (obj->flags & UNINTERESTING) {\n \t\t\tmark_parents_uninteresting(commit);\n@@ -1458,10 +1478,12 @@ enum rewrite_result {\n \n static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp)\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 (add_parents_to_list(revs, p, &revs->commits) < 0)\n+\t\t\tif (add_parents_to_list(revs, p, &revs->commits, &cache) < 0)\n \t\t\t\treturn rewrite_one_error;\n \t\tif (p->parents && p->parents->next)\n \t\t\treturn rewrite_one_ok;\n@@ -1580,7 +1602,7 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\t\tif (revs->max_age != -1 &&\n \t\t\t    (commit->date < revs->max_age))\n \t\t\t\tcontinue;\n-\t\t\tif (add_parents_to_list(revs, commit, &revs->commits) < 0)\n+\t\t\tif (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0)\n \t\t\t\treturn NULL;\n \t\t}\n \n-- \n1.5.6.2.24.ge09c4\n"},{"id":"83112","messageId":"alpine.LFD.1.10.0807121550320.2959@woody.linux-foundation.org","threadId":"14429","inReplyTo":"200807122200.58187.angavrilov@gmail.com","subject":"Re: [RFC PATCH] Fix quadratic performance in rewrite_one.","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-12T22:55:27Z","receivedAt":"2008-07-12T22:55:27Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 12 Jul 2008, Alexander N. Gavrilov wrote:\n>\n> Parent commits are usually older than their children. Thus,\n> on each iteration of the loop in rewrite_one, add_parents_to_list\n> traverses all commits previously processed by the loop.\n> It performs very poorly in case of very long rewrite chains.\n\nGood call, but you don't seem to invalidate the cache when we remove \nthings from the list.\n\nThe top of the limit_list() loop does that \"get top entry from list, an \nfree it\", and I'm not seeing you invalidating the cache if that entry that \njust got free'd happened to be the cache entry?\n\nOr did I miss some reason why that couldn't happen? \n\n\t\tLinus\n"},{"id":"83116","messageId":"200807130437.59141.angavrilov@gmail.com","threadId":"14429","inReplyTo":"alpine.LFD.1.10.0807121550320.2959@woody.linux-foundation.org","subject":"Re: [RFC PATCH] Fix quadratic performance in rewrite_one.","fromName":"Alexander Gavrilov","fromEmail":"angavrilov@gmail.com","sentAt":"2008-07-13T00:37:58Z","receivedAt":"2008-07-13T00:37:58Z","isPatch":true,"sender":{"key":"angavrilov@gmail.com","avatar":"https://avatars.githubusercontent.com/u/42666?v=4"},"body":"On Sunday 13 July 2008 02:55:27 Linus Torvalds wrote:\n> On Sat, 12 Jul 2008, Alexander N. Gavrilov wrote:\n> > Parent commits are usually older than their children. Thus,\n> > on each iteration of the loop in rewrite_one, add_parents_to_list\n> > traverses all commits previously processed by the loop.\n> > It performs very poorly in case of very long rewrite chains.\n>\n> Good call, but you don't seem to invalidate the cache when we remove\n> things from the list.\n\nThe cache is local to rewrite_one, and is invalidated by exiting from that \nfunction. Other users of add_parents_to_list just pass NULL as cache_ptr, \nthus causing insert_by_date_cached to degenerate into a simple \ninsert_by_date.\n\n> The top of the limit_list() loop does that \"get top entry from list, an\n> free it\", and I'm not seeing you invalidating the cache if that entry that\n> just got free'd happened to be the cache entry?\n\nThis type of workflow can be expected to keep the list relatively short \n(roughly limited by the number of simultaneously existing branches); and if \nit is already long, new entries will probably be added near the beginning \nanyway, so there doesn't seem to be any need to use caching. \n\nrewrite_one() is special in that it can sometimes walk through thousands of \ncommits at once and put them all into the list -- i.e. it is bound not by the \nwidth of the history, but by its length.\n\nAlexander\n"}]}