{"thread":{"id":"18668","subject":"[PATCH 0/2] speed up reflog unreachability pruning","startedAt":"2009-03-31T17:03:43Z","lastAt":"2009-03-31T17:58:52Z","messageCount":6,"participants":["Linus Torvalds","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"110036","messageId":"alpine.LFD.2.00.0903310958000.4093@localhost.localdomain","threadId":"18668","inReplyTo":null,"subject":"[PATCH 0/2] speed up reflog unreachability pruning","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-03-31T17:03:43Z","receivedAt":"2009-03-31T17:03:43Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nOk, this is a two-patch series that first tries to clean things up a bit, \nand then applies Junio's approach to speed up the reachability test.\n\nThe reason I did it this way is that I think we can improve on the \nreachability logic a bit more, but in order to do that I refuse to work \nwith the crazy duplicated complex logic inside 'expire_reflog_ent()', and \nI wanted to abstract it out.\n\nThen, the first cut at speedup is just Junio's approach. Which is fairly \nhacky, but works.\n\nI'd _like_ to do more of a \"dynamically do 'mark_reachable()' only when \nnecessary\" thing, but that's a separate cleanup thing.\n\nAs is, this improves the reflog expire quite enormously for me:\n\n - before:\n\n\t[torvalds@nehalem linux]$ time git reflog expire --all\n\treal\t0m37.193s\n\tuser\t0m37.174s\n\tsys\t0m0.020s\n\n - after:\n\n\t[torvalds@nehalem linux]$ time ~/git/git reflog expire --all\n\treal\t0m1.693s\n\tuser\t0m1.672s\n\tsys\t0m0.020s\n\nalthough I do suspect that the 'mark_reachable()' could slow things down \nin some less extreme cases. But probably never by a huge amount.\n\nTotal diffstat:\n\n builtin-reflog.c |   75 +++++++++++++++++++++++++++++++++++++++++++++++++----\n 1 files changed, 69 insertions(+), 6 deletions(-)\n\nwith the two individual patches coming up next.\n\n\t\t\tLinus\n"},{"id":"110038","messageId":"alpine.LFD.2.00.0903311003490.4093@localhost.localdomain","threadId":"18668","inReplyTo":"alpine.LFD.2.00.0903310958000.4093@localhost.localdomain","subject":"[PATCH 1/2] Clean up reflog unreachability pruning decision","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-03-31T17:09:55Z","receivedAt":"2009-03-31T17:09:55Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFrom: Linus Torvalds <torvalds@linux-foundation.org>\nDate: Tue, 31 Mar 2009 09:45:22 -0700\n\nThis clarifies the pruning rules for unreachable commits by having a \nseparate helpder function for the unreachability decision.\n\nIt's preparation for actual bigger changes to come to speed up the\ndecision when the reachability calculations become a bottleneck.\n\nIn the process it also _does_ change behavior, although in a way that I \nthink is much saner than the old behavior (which was in my opinion not \ndesigned, just a result of how the tests were written). It now will prune \nreflog entries that are older than that 'prune_unreacable' time _and_ that \nhave commit references that can't be even looked up.\n\nOf course, \"--stale-fix\" also does that, and does it regardless of the age \nof the reflog entry is, but I really think this is the right thing to do. \nIf we can't even look it up, we should consider it to be unreachable.\n\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n builtin-reflog.c |   32 ++++++++++++++++++++++++++------\n 1 files changed, 26 insertions(+), 6 deletions(-)\n\nNote the behavioural change. I think it's sane and \"ObviouslyCorrect(tm)\", \nbut maybe somebody disagrees.\n\ndiff --git a/builtin-reflog.c b/builtin-reflog.c\nindex d95f515..0355ce6 100644\n--- a/builtin-reflog.c\n+++ b/builtin-reflog.c\n@@ -209,6 +209,31 @@ static int keep_entry(struct commit **it, unsigned char *sha1)\n \treturn 1;\n }\n \n+static int unreachable(struct expire_reflog_cb *cb, struct commit *commit, unsigned char *sha1)\n+{\n+\t/*\n+\t * We may or may not have the commit yet - if not, look it\n+\t * up using the supplied sha1.\n+\t */\n+\tif (!commit) {\n+\t\tif (is_null_sha1(sha1))\n+\t\t\treturn 0;\n+\n+\t\tcommit = lookup_commit_reference_gently(sha1, 1);\n+\n+\t\t/* We can't even look it up - consider it unreachable */\n+\t\tif (!commit)\n+\t\t\treturn 1;\n+\t}\n+\n+\t/* Reachable from the current reflog top? Don't prune */\n+\tif (in_merge_bases(commit, &cb->ref_commit, 1))\n+\t\treturn 0;\n+\n+\t/* We can't reach it - prune it. */\n+\treturn 1;\n+}\n+\n static int expire_reflog_ent(unsigned char *osha1, unsigned char *nsha1,\n \t\tconst char *email, unsigned long timestamp, int tz,\n \t\tconst char *message, void *cb_data)\n@@ -230,12 +255,7 @@ static int expire_reflog_ent(unsigned char *osha1, unsigned char *nsha1,\n \tif (timestamp < cb->cmd->expire_unreachable) {\n \t\tif (!cb->ref_commit)\n \t\t\tgoto prune;\n-\t\tif (!old && !is_null_sha1(osha1))\n-\t\t\told = lookup_commit_reference_gently(osha1, 1);\n-\t\tif (!new && !is_null_sha1(nsha1))\n-\t\t\tnew = lookup_commit_reference_gently(nsha1, 1);\n-\t\tif ((old && !in_merge_bases(old, &cb->ref_commit, 1)) ||\n-\t\t    (new && !in_merge_bases(new, &cb->ref_commit, 1)))\n+\t\tif (unreachable(cb, old, osha1) || unreachable(cb, new, nsha1))\n \t\t\tgoto prune;\n \t}\n \n-- \n1.6.2.1.404.gb0085.dirty\n"},{"id":"110039","messageId":"alpine.LFD.2.00.0903311010050.4093@localhost.localdomain","threadId":"18668","inReplyTo":"alpine.LFD.2.00.0903311003490.4093@localhost.localdomain","subject":"[PATCH 2/2] Speed up reflog pruning of unreachable commits","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-03-31T17:11:56Z","receivedAt":"2009-03-31T17:11:56Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nFrom: Junio Hamano <gitster@pobox.com>\nDate: Mon, 30 Mar 2009 21:34:14 -0700\n\nInstead of doing the (potentially very expensive) \"in_merge_base()\"\ncheck for each commit that might be pruned if it is unreachable, do a\npreparatory reachability graph of the commit space, so that the common\ncase of being reachable can be tested directly.\n\n[ Cleaned up a bit and tweaked to actually work.  - Linus ]\nSigned-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n---\n builtin-reflog.c |   43 +++++++++++++++++++++++++++++++++++++++++++\n 1 files changed, 43 insertions(+), 0 deletions(-)\n\ndiff --git a/builtin-reflog.c b/builtin-reflog.c\nindex 0355ce6..f29ab2f 100644\n--- a/builtin-reflog.c\n+++ b/builtin-reflog.c\n@@ -52,6 +52,7 @@ struct collect_reflog_cb {\n \n #define INCOMPLETE\t(1u<<10)\n #define STUDYING\t(1u<<11)\n+#define REACHABLE\t(1u<<12)\n \n static int tree_is_complete(const unsigned char *sha1)\n {\n@@ -209,6 +210,43 @@ static int keep_entry(struct commit **it, unsigned char *sha1)\n \treturn 1;\n }\n \n+static void mark_reachable(struct commit *commit, unsigned long expire_limit)\n+{\n+\t/*\n+\t * We need to compute if commit on either side of an reflog\n+\t * entry is reachable from the tip of the ref for all entries.\n+\t * Mark commits that are reachable from the tip down to the\n+\t * time threashold first; we know a commit marked thusly is\n+\t * reachable from the tip without running in_merge_bases()\n+\t * at all.\n+\t */\n+\tstruct commit_list *pending = NULL;\n+\n+\tcommit_list_insert(commit, &pending);\n+\twhile (pending) {\n+\t\tstruct commit_list *entry = pending;\n+\t\tstruct commit_list *parent;\n+\t\tpending = entry->next;\n+\t\tcommit = entry->item;\n+\t\tfree(entry);\n+\t\tif (commit->object.flags & REACHABLE)\n+\t\t\tcontinue;\n+\t\tif (parse_commit(commit))\n+\t\t\tcontinue;\n+\t\tcommit->object.flags |= REACHABLE;\n+\t\tif (commit->date < expire_limit)\n+\t\t\tcontinue;\n+\t\tparent = commit->parents;\n+\t\twhile (parent) {\n+\t\t\tcommit = parent->item;\n+\t\t\tparent = parent->next;\n+\t\t\tif (commit->object.flags & REACHABLE)\n+\t\t\t\tcontinue;\n+\t\t\tcommit_list_insert(commit, &pending);\n+\t\t}\n+\t}\n+}\n+\n static int unreachable(struct expire_reflog_cb *cb, struct commit *commit, unsigned char *sha1)\n {\n \t/*\n@@ -227,6 +265,8 @@ static int unreachable(struct expire_reflog_cb *cb, struct commit *commit, unsig\n \t}\n \n \t/* Reachable from the current reflog top? Don't prune */\n+\tif (commit->object.flags & REACHABLE)\n+\t\treturn 0;\n \tif (in_merge_bases(commit, &cb->ref_commit, 1))\n \t\treturn 0;\n \n@@ -308,7 +348,10 @@ static int expire_reflog(const char *ref, const unsigned char *sha1, int unused,\n \tcb.ref_commit = lookup_commit_reference_gently(sha1, 1);\n \tcb.ref = ref;\n \tcb.cmd = cmd;\n+\n+\tmark_reachable(cb.ref_commit, cmd->expire_total);\n \tfor_each_reflog_ent(ref, expire_reflog_ent, &cb);\n+\tclear_commit_marks(cb.ref_commit, REACHABLE);\n  finish:\n \tif (cb.newlog) {\n \t\tif (fclose(cb.newlog)) {\n-- \n1.6.2.1.404.gb0085.dirty\n"},{"id":"110041","messageId":"7vab7160yt.fsf@gitster.siamese.dyndns.org","threadId":"18668","inReplyTo":"alpine.LFD.2.00.0903311003490.4093@localhost.localdomain","subject":"Re: [PATCH 1/2] Clean up reflog unreachability pruning decision","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-03-31T17:44:58Z","receivedAt":"2009-03-31T17:44:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> From: Linus Torvalds <torvalds@linux-foundation.org>\n> Date: Tue, 31 Mar 2009 09:45:22 -0700\n>\n> This clarifies the pruning rules for unreachable commits by having a \n> separate helpder function for the unreachability decision.\n>\n> It's preparation for actual bigger changes to come to speed up the\n> decision when the reachability calculations become a bottleneck.\n>\n> In the process it also _does_ change behavior, although in a way that I \n> think is much saner than the old behavior (which was in my opinion not \n> designed, just a result of how the tests were written). It now will prune \n> reflog entries that are older than that 'prune_unreacable' time _and_ that \n> have commit references that can't be even looked up.\n\n> Of course, \"--stale-fix\" also does that, and does it regardless of the age \n> of the reflog entry is, but I really think this is the right thing to do. \n> If we can't even look it up, we should consider it to be unreachable.\n>\n> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n> ---\n>  builtin-reflog.c |   32 ++++++++++++++++++++++++++------\n>  1 files changed, 26 insertions(+), 6 deletions(-)\n>\n> Note the behavioural change. I think it's sane and \"ObviouslyCorrect(tm)\", \n> but maybe somebody disagrees.\n\nI did not recall initially when I was discussing this with you last night\nbut I think this \"no commit? not prune\" is intentional.  The codepath is\nnot about logs/heads but logs/*anything*, and we allow pointers to non\ncommit objects (like v2.6.11-tree).\n\nAlso even if we limit ourselves to commits, @{-N} notation can be used to\nsee the history of branch switching, and that does not need any underlying\nobjects.  I do not think it is interesting to be able to see which branch\nyou were on 30 days abo, though ;-)\n\n\n> diff --git a/builtin-reflog.c b/builtin-reflog.c\n> index d95f515..0355ce6 100644\n> --- a/builtin-reflog.c\n> +++ b/builtin-reflog.c\n> @@ -209,6 +209,31 @@ static int keep_entry(struct commit **it, unsigned char *sha1)\n>  \treturn 1;\n>  }\n>  \n> +static int unreachable(struct expire_reflog_cb *cb, struct commit *commit, unsigned char *sha1)\n> +{\n> +\t/*\n> +\t * We may or may not have the commit yet - if not, look it\n> +\t * up using the supplied sha1.\n> +\t */\n> +\tif (!commit) {\n> +\t\tif (is_null_sha1(sha1))\n> +\t\t\treturn 0;\n> +\n> +\t\tcommit = lookup_commit_reference_gently(sha1, 1);\n> +\n> +\t\t/* We can't even look it up - consider it unreachable */\n> +\t\tif (!commit)\n> +\t\t\treturn 1;\n\n\t/* If it is not a commit, keep it. */\n        if (!commit)\n        \treturn 0;\n\n> +\t}\n> +\n> +\t/* Reachable from the current reflog top? Don't prune */\n\nThat's \"tip of the ref\", not necessarily \"reflog top\".\n\n> +\tif (in_merge_bases(commit, &cb->ref_commit, 1))\n> +\t\treturn 0;\n> +\n> +\t/* We can't reach it - prune it. */\n> +\treturn 1;\n> +}\n> +\n>  static int expire_reflog_ent(unsigned char *osha1, unsigned char *nsha1,\n>  \t\tconst char *email, unsigned long timestamp, int tz,\n>  \t\tconst char *message, void *cb_data)\n> @@ -230,12 +255,7 @@ static int expire_reflog_ent(unsigned char *osha1, unsigned char *nsha1,\n>  \tif (timestamp < cb->cmd->expire_unreachable) {\n>  \t\tif (!cb->ref_commit)\n>  \t\t\tgoto prune;\n> -\t\tif (!old && !is_null_sha1(osha1))\n> -\t\t\told = lookup_commit_reference_gently(osha1, 1);\n> -\t\tif (!new && !is_null_sha1(nsha1))\n> -\t\t\tnew = lookup_commit_reference_gently(nsha1, 1);\n> -\t\tif ((old && !in_merge_bases(old, &cb->ref_commit, 1)) ||\n> -\t\t    (new && !in_merge_bases(new, &cb->ref_commit, 1)))\n> +\t\tif (unreachable(cb, old, osha1) || unreachable(cb, new, nsha1))\n>  \t\t\tgoto prune;\n>  \t}\n>  \n> -- \n> 1.6.2.1.404.gb0085.dirty\n"},{"id":"110042","messageId":"7v63hp60vi.fsf@gitster.siamese.dyndns.org","threadId":"18668","inReplyTo":"alpine.LFD.2.00.0903311010050.4093@localhost.localdomain","subject":"Re: [PATCH 2/2] Speed up reflog pruning of unreachable commits","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-03-31T17:46:57Z","receivedAt":"2009-03-31T17:46:57Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> writes:\n\n> From: Junio Hamano <gitster@pobox.com>\n> Date: Mon, 30 Mar 2009 21:34:14 -0700\n>\n> Instead of doing the (potentially very expensive) \"in_merge_base()\"\n> check for each commit that might be pruned if it is unreachable, do a\n> preparatory reachability graph of the commit space, so that the common\n> case of being reachable can be tested directly.\n>\n> [ Cleaned up a bit and tweaked to actually work.  - Linus ]\n> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>\n> ---\n>  builtin-reflog.c |   43 +++++++++++++++++++++++++++++++++++++++++++\n>  1 files changed, 43 insertions(+), 0 deletions(-)\n>\n> diff --git a/builtin-reflog.c b/builtin-reflog.c\n> index 0355ce6..f29ab2f 100644\n> --- a/builtin-reflog.c\n> +++ b/builtin-reflog.c\n> @@ -52,6 +52,7 @@ struct collect_reflog_cb {\n>  \n>  #define INCOMPLETE\t(1u<<10)\n>  #define STUDYING\t(1u<<11)\n> +#define REACHABLE\t(1u<<12)\n>  \n>  static int tree_is_complete(const unsigned char *sha1)\n>  {\n> @@ -209,6 +210,43 @@ static int keep_entry(struct commit **it, unsigned char *sha1)\n>  \treturn 1;\n>  }\n>  \n> +static void mark_reachable(struct commit *commit, unsigned long expire_limit)\n> +{\n> +\t/*\n> +\t * We need to compute if commit on either side of an reflog\n> +\t * entry is reachable from the tip of the ref for all entries.\n> +\t * Mark commits that are reachable from the tip down to the\n> +\t * time threashold first; we know a commit marked thusly is\n> +\t * reachable from the tip without running in_merge_bases()\n> +\t * at all.\n> +\t */\n> +\tstruct commit_list *pending = NULL;\n> +\n> +\tcommit_list_insert(commit, &pending);\n> +\twhile (pending) {\n> +\t\tstruct commit_list *entry = pending;\n> +\t\tstruct commit_list *parent;\n> +\t\tpending = entry->next;\n> +\t\tcommit = entry->item;\n> +\t\tfree(entry);\n> +\t\tif (commit->object.flags & REACHABLE)\n> +\t\t\tcontinue;\n> +\t\tif (parse_commit(commit))\n> +\t\t\tcontinue;\n> +\t\tcommit->object.flags |= REACHABLE;\n> +\t\tif (commit->date < expire_limit)\n> +\t\t\tcontinue;\n> +\t\tparent = commit->parents;\n> +\t\twhile (parent) {\n> +\t\t\tcommit = parent->item;\n> +\t\t\tparent = parent->next;\n> +\t\t\tif (commit->object.flags & REACHABLE)\n> +\t\t\t\tcontinue;\n> +\t\t\tcommit_list_insert(commit, &pending);\n> +\t\t}\n> +\t}\n> +}\n> +\n>  static int unreachable(struct expire_reflog_cb *cb, struct commit *commit, unsigned char *sha1)\n>  {\n>  \t/*\n> @@ -227,6 +265,8 @@ static int unreachable(struct expire_reflog_cb *cb, struct commit *commit, unsig\n>  \t}\n>  \n>  \t/* Reachable from the current reflog top? Don't prune */\n> +\tif (commit->object.flags & REACHABLE)\n> +\t\treturn 0;\n>  \tif (in_merge_bases(commit, &cb->ref_commit, 1))\n>  \t\treturn 0;\n>  \n> @@ -308,7 +348,10 @@ static int expire_reflog(const char *ref, const unsigned char *sha1, int unused,\n>  \tcb.ref_commit = lookup_commit_reference_gently(sha1, 1);\n>  \tcb.ref = ref;\n>  \tcb.cmd = cmd;\n> +\n\nYou seem to have lost \"if (cb.ref_commit)\" from the last round to protect\nmark_rechable().  It can be NULL.\n\n> +\tmark_reachable(cb.ref_commit, cmd->expire_total);\n>  \tfor_each_reflog_ent(ref, expire_reflog_ent, &cb);\n> +\tclear_commit_marks(cb.ref_commit, REACHABLE);\n>   finish:\n>  \tif (cb.newlog) {\n>  \t\tif (fclose(cb.newlog)) {\n> -- \n> 1.6.2.1.404.gb0085.dirty\n"},{"id":"110044","messageId":"alpine.LFD.2.00.0903311056000.4093@localhost.localdomain","threadId":"18668","inReplyTo":"7v63hp60vi.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 2/2] Speed up reflog pruning of unreachable commits","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-03-31T17:58:52Z","receivedAt":"2009-03-31T17:58:52Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 31 Mar 2009, Junio C Hamano wrote:\n> \n> You seem to have lost \"if (cb.ref_commit)\" from the last round to protect\n> mark_rechable().  It can be NULL.\n\nI based it on your original patch, so yeah, it's missing all your updates \nsince.\n\n\t\t\tLinus\n"}]}