{"thread":{"id":"18653","subject":"\"git reflog expire --all\" very slow","startedAt":"2009-03-31T01:43:59Z","lastAt":"2009-04-02T15:30:52Z","messageCount":13,"participants":["Linus Torvalds","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"109955","messageId":"alpine.LFD.2.00.0903301803190.4093@localhost.localdomain","threadId":"18653","inReplyTo":null,"subject":"\"git reflog expire --all\" very slow","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-03-31T01:43:59Z","receivedAt":"2009-03-31T01:43:59Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nI haven't checked in detail what is up, but I just did a \"git gc --prune\", \nand it was quiet for about half a minute before anything seemed to happen.\n\nVery irritating, as normally the expensive stuff at least gives you some \nkind of indication of what it's doing.\n\nIt turns out that it's the reflog expiration. On my crazy beefy \nNehalem machine:\n\n\t[torvalds@nehalem linux]$ time git reflog expire --all\n\n\treal\t0m37.596s\n\tuser\t0m37.554s\n\tsys\t0m0.040s\n\nand that really isn't good. 37 cpu-seconds on this machine is like half a \ndecade on some laptops I could name.\n\nThe flat pgprof for this thing (user-land oprofile isn't doing Nehalem \nyet) looks like this:\n\n % cumulative self self total \n time seconds seconds calls s/call s/call name \n 60.94 30.24 30.24 301120211 0.00 0.00 interesting\n 12.37 36.38 6.14 301338513 0.00 0.00 insert_by_date\n 11.35 42.01 5.63 8776 0.00 0.00 clear_commit_marks\n 9.96 46.95 4.94 4388 0.00 0.01 merge_bases_many\n 2.16 48.02 1.07 301486366 0.00 0.00 commit_list_insert\n 1.21 48.62 0.60 301329737 0.00 0.00 parse_commit\n 0.87 49.05 0.43 301637945 0.00 0.00 xmalloc\n 0.34 49.22 0.17 24 0.01 0.01 xstrdup\n ...\n\nOk, so my reflog on this thing has 1583 entries on HEAD (yes, in the last \n90 days, the problem is _not_ that I have a long reflog and am pruning it, \nit _is_ already pruned). Add to that the reflogs for the branches (mainly \nmaster: 1294), and you end up with apparently a nice total of 4388 reflog \nentries.\n\nAnd then it looks like for _each_ reflog entry we have:\n\n expire_reflog_ent()\n in_merge_bases()\n\nwhich then calls \n\n get_merge_bases()\n get_merge_bases_many()\n ..\n\neach of which probably often traverses an appreciable part of the kernel \ntree, since my reflog entries are often merges, and the merge bases need \neasily thousands of commits to look up.\n\nWhich explains how you end up with 301 _million_ commits inserted into the \nlists and checked if they are interesting. Since the whole kernel tree has \nonly something like 140k commits, and my revlog doesn't even go back more \nthan three months, I guess that means that we'll be traversing the same \ncommits tens of thousands of times each.\n\nEven on this machine, that whole cluster-f*ck takes a little while. Oops.\n\nI have not checked if there is anything really obvious going on that could \nchange that whole logic that causes us to do merge-bases into something \nsaner, since the reflog code is not a part of git I'm familiar with. \n\nInstead, I'm just sending this to Junio, Brandon, and Dscho, who are \ngetting the main blame for 'builtin-reflog.c'. Although I'm pretty sure \nthis is all Junio, but just in case..\n\n\t\t\tLinus\n"},{"id":"109958","messageId":"7vk5668g55.fsf@gitster.siamese.dyndns.org","threadId":"18653","inReplyTo":"alpine.LFD.2.00.0903301803190.4093@localhost.localdomain","subject":"Re: \"git reflog expire --all\" very slow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-03-31T04:34:14Z","receivedAt":"2009-03-31T04:34:14Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> I have not checked if there is anything really obvious going on that could \n> change that whole logic that causes us to do merge-bases into something \n> saner, since the reflog code is not a part of git I'm familiar with. \n\nWhen we look at one reflog entry with old and new commit, we decide to\nprune an old entry if either side is unreachable from the tip of the\nbranch:\n\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\t\tgoto prune;\n\t}\n\nMost of your reflog entries are expected to be reachable from the tip, so\none optimization would be to mark all commits reachable from the tip\nupfront, and omit the in_merge_bases() computation for the ones that are\nalready marked. Perhaps something like this...\n\n builtin-reflog.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++--\n 1 files changed, 47 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin-reflog.c b/builtin-reflog.c\nindex d95f515..f0d61bd 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\tcommit->object.flags |= REACHABLE;\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\tif (parse_commit(commit))\n+\t\t\t\tcontinue;\n+\t\t\tif (commit->date < expire_limit)\n+\t\t\t\tcontinue;\n+\t\t\tcommit_list_insert(commit, &pending);\n+\t\t}\n+\t}\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@@ -234,8 +272,12 @@ static int expire_reflog_ent(unsigned char *osha1, unsigned char *nsha1,\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 ((old &&\n+\t\t !(old->object.flags & REACHABLE) &&\n+\t\t !in_merge_bases(old, &cb->ref_commit, 1)) ||\n+\t\t (new &&\n+\t\t !(new->object.flags & REACHABLE) &&\n+\t\t !in_merge_bases(new, &cb->ref_commit, 1)))\n \t\t\tgoto prune;\n \t}\n \n@@ -288,7 +330,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_unreachable);\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"},{"id":"109962","messageId":"alpine.LFD.2.00.0903302154000.4093@localhost.localdomain","threadId":"18653","inReplyTo":"7vk5668g55.fsf@gitster.siamese.dyndns.org","subject":"Re: \"git reflog expire --all\" very slow","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-03-31T05:09:25Z","receivedAt":"2009-03-31T05:09:25Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 30 Mar 2009, Junio C Hamano wrote:\n> \n> Most of your reflog entries are expected to be reachable from the tip, so\n> one optimization would be to mark all commits reachable from the tip\n> upfront, and omit the in_merge_bases() computation for the ones that are\n> already marked. Perhaps something like this...\n\nThis if anything makes things just go slower.\n\nNot much, but some. It went from 36.566s to 38.070s. That may be in the \nnoise, I've not done any sensitivity analysis.\n\nI thought you perhaps had a missing \"parse_commit()\" making the \nreachability thing not work (look_up_gently parses the object, but if it's \na tag deref_tag() will dereference it until it hits a commit, but never \nparse the commit). But that wasn't it.\n\n\t\t\tLinus\n"},{"id":"109964","messageId":"7vy6um6z9m.fsf@gitster.siamese.dyndns.org","threadId":"18653","inReplyTo":"alpine.LFD.2.00.0903302154000.4093@localhost.localdomain","subject":"Re: \"git reflog expire --all\" very slow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-03-31T05:24:05Z","receivedAt":"2009-03-31T05:24:05Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Mon, 30 Mar 2009, Junio C Hamano wrote:\n>> \n>> Most of your reflog entries are expected to be reachable from the tip, so\n>> one optimization would be to mark all commits reachable from the tip\n>> upfront, and omit the in_merge_bases() computation for the ones that are\n>> already marked. Perhaps something like this...\n>\n> This if anything makes things just go slower.\n>\n> Not much, but some. It went from 36.566s to 38.070s. That may be in the \n> noise, I've not done any sensitivity analysis.\n\nI actually think that the cutoff for history traversal is bogus. You may\nhave a 30-day old reflog entry that pulled in a 45-day old commit, and\ngiving up the smudging at the expiry cutoff timestamp does not make much\nsense.\n\nI do have a lot of reflog entries kept around, as my main repository has\nthese:\n\n [gc]\n reflogexpire = '2005-01-01 00:00:00 +0000'\n reflogexpireunreachable = '2005-01-01 00:00:00 +0000'\n\nso let me experiment a bit more.\n\n builtin-reflog.c | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 files changed, 59 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin-reflog.c b/builtin-reflog.c\nindex d95f515..ef02b5a 100644\n--- a/builtin-reflog.c\n+++ b/builtin-reflog.c\n@@ -36,6 +36,7 @@ struct expire_reflog_cb {\n \tFILE *newlog;\n \tconst char *ref;\n \tstruct commit *ref_commit;\n+\tint commit_marked;\n \tstruct cmd_reflog_expire_cb *cmd;\n \tunsigned char last_kept_sha1[20];\n };\n@@ -52,6 +53,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 +211,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\tcommit->object.flags |= REACHABLE;\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\tif (parse_commit(commit))\n+\t\t\t\tcontinue;\n+\t\t\tif (commit->date < expire_limit)\n+\t\t\t\tcontinue;\n+\t\t\tcommit_list_insert(commit, &pending);\n+\t\t}\n+\t}\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 +269,28 @@ 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+\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+\n+\t\tif (!cb->commit_marked) {\n+\t\t\tif (old) {\n+\t\t\t\tmark_reachable(cb->ref_commit, old->date);\n+\t\t\t\tcb->commit_marked = 1;\n+\t\t\t} else if (new) {\n+\t\t\t\tmark_reachable(cb->ref_commit, new->date);\n+\t\t\t\tcb->commit_marked = 1;\n+\t\t\t}\n+\t\t}\n+\n+\t\tif ((old &&\n+\t\t !(old->object.flags & REACHABLE) &&\n+\t\t !in_merge_bases(old, &cb->ref_commit, 1)) ||\n+\t\t (new &&\n+\t\t !(new->object.flags & REACHABLE) &&\n+\t\t !in_merge_bases(new, &cb->ref_commit, 1)))\n \t\t\tgoto prune;\n \t}\n \n@@ -289,6 +344,8 @@ static int expire_reflog(const char *ref, const unsigned char *sha1, int unused,\n \tcb.ref = ref;\n \tcb.cmd = cmd;\n \tfor_each_reflog_ent(ref, expire_reflog_ent, &cb);\n+\tif (cb.ref_commit && cb.commit_marked)\n+\t\tclear_commit_marks(cb.ref_commit, REACHABLE);\n finish:\n \tif (cb.newlog) {\n \t\tif (fclose(cb.newlog)) {\n"},{"id":"109967","messageId":"alpine.LFD.2.00.0903302231370.4093@localhost.localdomain","threadId":"18653","inReplyTo":"alpine.LFD.2.00.0903302154000.4093@localhost.localdomain","subject":"Re: \"git reflog expire --all\" very slow","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-03-31T05:38:24Z","receivedAt":"2009-03-31T05:38:24Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 30 Mar 2009, Linus Torvalds wrote:\n> \n> This if anything makes things just go slower.\n> \n> Not much, but some. It went from 36.566s to 38.070s. That may be in the \n> noise, I've not done any sensitivity analysis.\n> \n> I thought you perhaps had a missing \"parse_commit()\" making the \n> reachability thing not work (look_up_gently parses the object, but if it's \n> a tag deref_tag() will dereference it until it hits a commit, but never \n> parse the commit). But that wasn't it.\n\nAhhah.\n\nI know why it makes things slower.\n\nThe slow case is already inside that whole:\n\n\tif (timestamp < cb->cmd->expire_unreachable) {\n\nif-statement, so the thing that slows down is if we hit a commit that is \n_older_ than the expire limit.\n\nBut your whole \"mark_reachable()\" thing only marks things _younger_ than \nthat reachable. So you mark exactly the wrong things reachable - you mark \nthe ones that we don't even care about.\n\nIf I do\n\n\tmark_reachable(cb.ref_commit, 0);\n\ninstead (to traverse the _whole_ tree, with no regards to date), the time \nshrinks to 1.7s. But of course, that's also wrong.\n\nQutie frankly, I don't really understand why the logic isn't just\n\n\tif (timestamp < cb->cmd->expire_unreachable)\n\t\tgoto prune; \n\nwhy is that reachability so important?\n\n\t\t\tLinus\n"},{"id":"109968","messageId":"alpine.LFD.2.00.0903302239040.4093@localhost.localdomain","threadId":"18653","inReplyTo":"7vy6um6z9m.fsf@gitster.siamese.dyndns.org","subject":"Re: \"git reflog expire --all\" very slow","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-03-31T05:42:50Z","receivedAt":"2009-03-31T05:42:50Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 30 Mar 2009, Junio C Hamano wrote:\n> \n> I do have a lot of reflog entries kept around, as my main repository has\n> these:\n> \n> [gc]\n> reflogexpire = '2005-01-01 00:00:00 +0000'\n> reflogexpireunreachable = '2005-01-01 00:00:00 +0000'\n\nI think that actually _hides_ the problem. You'll never have anything at \nall that triggers that\n\n\tif (timestamp < cb->cmd->expire_unreachable) {\n\nbecause your \"expire_unreachable\" timestamp is already very old (== small \nvalue), so 'timestamp' will _not_ be older (smaller value) than that.\n\nI dunno. As mentioned, I don't really understand why we'd want to save \nsome of those reflog entries at all in the first place, so I'm probably \nmissing something.\n\nIf we've asked for reflog entries past a certain age to be expired, why do \nwhen then look at the details of those reflog entries and only expire them \nunder certain circumstances? Just expire them, and get rid of the \n'unreachable' part.\n\n\t\t\tLinus\n"},{"id":"109970","messageId":"alpine.LFD.2.00.0903302244580.4093@localhost.localdomain","threadId":"18653","inReplyTo":"alpine.LFD.2.00.0903302231370.4093@localhost.localdomain","subject":"Re: \"git reflog expire --all\" very slow","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-03-31T05:50:17Z","receivedAt":"2009-03-31T05:50:17Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 30 Mar 2009, Linus Torvalds wrote:\n> \n> If I do\n> \n> \tmark_reachable(cb.ref_commit, 0);\n\nOk, I think I got it.\n\nYou had\n\n\tmark_reachable(cb.ref_commit, cmd->expire_unreachable);\n\nbut we care about the commits that are younger than 'expire_total' (older \nthan that, and they are pruned unconditionally), but older than \n'expire_unreachable' (younger than that and the date doesn't matter).\n\nSo making it do\n\n\tmark_reachable(cb.ref_commit, cmd->expire_total);\n\nmarks the right parts reachable. Not the whole tree, but also not just the \ncommits we're not going to expire regardless.\n\nWith that change, it's all basically instantaneous. We don't need to \ntraverse the whole kernel history, and with that change to your patch, I \nget\n\n\t[torvalds@nehalem linux]$ time ~/git/git reflog expire --all\n\n\treal\t0m1.715s\n\tuser\t0m1.676s\n\tsys\t0m0.040s\n\nwhich is still slower than I'd wish for, but is a whole lot faster than \nover half a minute.\n\n\t\tLinus\n"},{"id":"109969","messageId":"7vr60e6y1v.fsf@gitster.siamese.dyndns.org","threadId":"18653","inReplyTo":"7vy6um6z9m.fsf@gitster.siamese.dyndns.org","subject":"Re: \"git reflog expire --all\" very slow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-03-31T05:50:20Z","receivedAt":"2009-03-31T05:50:20Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Linus Torvalds writes:\n>> ...\n>> This if anything makes things just go slower.\n>> \n>> Not much, but some. It went from 36.566s to 38.070s. That may be in the \n>> noise, I've not done any sensitivity analysis.\n>\n> I actually think that the cutoff for history traversal is bogus. You may\n> have a 30-day old reflog entry that pulled in a 45-day old commit, and\n> giving up the smudging at the expiry cutoff timestamp does not make much\n> sense.\n>\n> I do have a lot of reflog entries kept around, as my main repository has\n> these:\n>\n> [gc]\n> reflogexpire = '2005-01-01 00:00:00 +0000'\n> reflogexpireunreachable = '2005-01-01 00:00:00 +0000'\n>\n> so let me experiment a bit more.\n\nTo initially prune a copy of my git repository that was never pruned\nbefore, it takes a lot of time with or without the patch to prune from the\noriginal 73476 reflog entries.\n\n(without patch)\n23.46user 0.23system 0:23.70elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+5464outputs (0major+6045minor)pagefaults 0swaps\n\n(with patch, but with a bit of fprintf's for counting)\n21.99user 0.40system 0:22.56elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+5472outputs (0major+6040minor)pagefaults 0swaps\n\nAfter the initial pruning, with 13780 reflog entries still left (and no\nfurther pruning expected), I am seeing these:\n\n(without patch)\n2.09user 0.22system 0:02.32elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+5464outputs (0major+4956minor)pagefaults 0swaps\n\n(with patch, but again with a bit of fprintf's for counting)\n0.76user 0.25system 0:01.05elapsed 96%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+5464outputs (0major+4918minor)pagefaults 0swaps\n\nI might be better off traversing down all the way and do away with\nin_merge_bases(), but that might hold true only for something small like\ngit.git and the kernel.\n"},{"id":"109971","messageId":"alpine.LFD.2.00.0903302250500.4093@localhost.localdomain","threadId":"18653","inReplyTo":"alpine.LFD.2.00.0903302244580.4093@localhost.localdomain","subject":"Re: \"git reflog expire --all\" very slow","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-03-31T05:51:34Z","receivedAt":"2009-03-31T05:51:34Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThat made no sense. It should have been:\n\nOn Mon, 30 Mar 2009, Linus Torvalds wrote:\n> \n> but we care about the commits that are younger than 'expire_total' (older \n> than that, and they are pruned unconditionally), but older than \n> 'expire_unreachable' (younger than that and the date doesn't matter).\n ^^^^\n reachability\n\nbut other than that the commentary stands.\n\n\t\tLinus\n"},{"id":"109973","messageId":"7vmyb26xp4.fsf@gitster.siamese.dyndns.org","threadId":"18653","inReplyTo":"alpine.LFD.2.00.0903302239040.4093@localhost.localdomain","subject":"Re: \"git reflog expire --all\" very slow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-03-31T05:57:59Z","receivedAt":"2009-03-31T05:57:59Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Mon, 30 Mar 2009, Junio C Hamano wrote:\n>> \n>> I do have a lot of reflog entries kept around, as my main repository has\n>> these:\n>> \n>> [gc]\n>> reflogexpire = '2005-01-01 00:00:00 +0000'\n>> reflogexpireunreachable = '2005-01-01 00:00:00 +0000'\n>\n> I think that actually _hides_ the problem. You'll never have anything at \n> all that triggers that\n>\n> \tif (timestamp < cb->cmd->expire_unreachable) {\n>\n> because your \"expire_unreachable\" timestamp is already very old (== small \n> value), so 'timestamp' will _not_ be older (smaller value) than that.\n>\n> I dunno. As mentioned, I don't really understand why we'd want to save \n> some of those reflog entries at all in the first place, so I'm probably \n> missing something.\n>\n> If we've asked for reflog entries past a certain age to be expired, why do \n> when then look at the details of those reflog entries and only expire them \n> under certain circumstances? Just expire them, and get rid of the \n> 'unreachable' part.\n\nI know. My test repository does not have them. I only quoted them to\ntell you that I have a lot of entries to play with.\n"},{"id":"109974","messageId":"7vd4by6x8d.fsf@gitster.siamese.dyndns.org","threadId":"18653","inReplyTo":"alpine.LFD.2.00.0903302244580.4093@localhost.localdomain","subject":"Re: \"git reflog expire --all\" very slow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-03-31T06:08:02Z","receivedAt":"2009-03-31T06:08:02Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Mon, 30 Mar 2009, Linus Torvalds wrote:\n>> \n>> If I do\n>> \n>> \tmark_reachable(cb.ref_commit, 0);\n>\n> Ok, I think I got it.\n>\n> You had\n>\n> \tmark_reachable(cb.ref_commit, cmd->expire_unreachable);\n>\n> but we care about the commits that are younger than 'expire_total' (older \n> than that, and they are pruned unconditionally), but older than \n> 'expire_unreachable' (younger than that and the date doesn't matter).\n>\n> So making it do\n>\n> \tmark_reachable(cb.ref_commit, cmd->expire_total);\n>\n> marks the right parts reachable. Not the whole tree, but also not just the \n> commits we're not going to expire regardless.\n>\n> With that change, it's all basically instantaneous. We don't need to \n> traverse the whole kernel history, and with that change to your patch, I \n> get\n>\n> \t[torvalds@nehalem linux]$ time ~/git/git reflog expire --all\n>\n> \treal\t0m1.715s\n> \tuser\t0m1.676s\n> \tsys\t0m0.040s\n>\n> which is still slower than I'd wish for, but is a whole lot faster than \n> over half a minute.\n\nActually, the initial pruning I showed (around 23 seconds) is not helped\nwith the expire_total change at all, but if I mark everything and get rid\nof in_merge_bases(), it goes down to 1.15 seconds.\n\nBut subsequent pruning, which is what we should be optimizing for, gets\nmuch faster with your approach of not traversing down the history all the\nway.\n\nBy the way, I suspect I might be making the same mistake of traversing\nboth sides of the merge twice while marking, but I am tired already, so\nI'll throw out the final patch for tonight and go to bed.\n\n builtin-reflog.c | 48 ++++++++++++++++++++++++++++++++++++++++++++++--\n 1 files changed, 46 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin-reflog.c b/builtin-reflog.c\nindex d95f515..b67272a 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\tcommit->object.flags |= REACHABLE;\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\tif (parse_commit(commit))\n+\t\t\t\tcontinue;\n+\t\t\tif (expire_limit && commit->date < expire_limit)\n+\t\t\t\tcontinue;\n+\t\t\tcommit_list_insert(commit, &pending);\n+\t\t}\n+\t}\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@@ -234,8 +272,10 @@ static int expire_reflog_ent(unsigned char *osha1, unsigned char *nsha1,\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 ((old && !(old->object.flags & REACHABLE) &&\n+\t\t !in_merge_bases(old, &cb->ref_commit, 1)) ||\n+\t\t (new && !(new->object.flags & REACHABLE) &&\n+\t\t !in_merge_bases(new, &cb->ref_commit, 1)))\n \t\t\tgoto prune;\n \t}\n \n@@ -288,7 +328,11 @@ 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+\tif (cb.ref_commit)\n+\t\tmark_reachable(cb.ref_commit, cmd->expire_total);\n \tfor_each_reflog_ent(ref, expire_reflog_ent, &cb);\n+\tif (cb.ref_commit)\n+\t\tclear_commit_marks(cb.ref_commit, REACHABLE);\n finish:\n \tif (cb.newlog) {\n \t\tif (fclose(cb.newlog)) {\n"},{"id":"110196","messageId":"7vmyazimds.fsf@gitster.siamese.dyndns.org","threadId":"18653","inReplyTo":"alpine.LFD.2.00.0903302250500.4093@localhost.localdomain","subject":"Re: \"git reflog expire --all\" very slow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-04-02T06:46:07Z","receivedAt":"2009-04-02T06:46:07Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> That made no sense. It should have been:\n>\n> On Mon, 30 Mar 2009, Linus Torvalds wrote:\n>> \n>> but we care about the commits that are younger than 'expire_total' (older \n>> than that, and they are pruned unconditionally), but older than \n>> 'expire_unreachable' (younger than that and the date doesn't matter).\n> ^^^^\n> reachability\n>\n> but other than that the commentary stands.\n\nCorrect. But after thinking about this a bit more, I am starting to suspect\nthe \"of course\" in your earlier\n\n If I do\n\n mark_reachable(cb.ref_commit, 0);\n\n instead (to traverse the _whole_ tree, with no regards to date), the time \n shrinks to 1.7s. But of course, that's also wrong.\n\nmay not be such a clearly obvious thing.\n\nSuppose you do not do \"mark_reachable(cb.ref_commit, 0)\" but use the\nexpire_total as the cut-off value (which is what I've queued). If you\nhave one unreachable entry that you end up running in_merge_bases() for,\nyou will traverse all the history down _anyway_, and at that point, you\nwould be better off if you actually marked everything upfront, and\ndiscarded anything unmarked as unreachable without falling back to\nin_merge_bases() at all.\n\nThe above reasoning of course assumes that \"keep reflog entries if they\nare reachable from the tip, otherwise drop them if they are more than 30\ndays old\" is a good medium level semantics to cull what the other rule\n\"drop any reflog entry older than 90 days\" may not.\n\nA hacky alternative would be to use total_expire as the cut-off and do not\nfall back on in_merge_bases(). We might incorrectly prune away an entry\nthat records that you pulled a commit that is still reachable from the tip\nlast week, if that commit happens to be 4 months old if we did so, so I am\nnot convinced myself it is a reasonable hack, though.\n"},{"id":"110223","messageId":"alpine.LFD.2.00.0904020759180.4130@localhost.localdomain","threadId":"18653","inReplyTo":"7vmyazimds.fsf@gitster.siamese.dyndns.org","subject":"Re: \"git reflog expire --all\" very slow","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-04-02T15:30:52Z","receivedAt":"2009-04-02T15:30:52Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 1 Apr 2009, Junio C Hamano wrote:\n> \n> Correct. But after thinking about this a bit more, I am starting to suspect\n> the \"of course\" in your earlier\n> \n> If I do\n> \n> mark_reachable(cb.ref_commit, 0);\n> \n> instead (to traverse the _whole_ tree, with no regards to date), the time \n> shrinks to 1.7s. But of course, that's also wrong.\n> \n> may not be such a clearly obvious thing.\n\nI think we should never do it up-front, because for nicely behaved people \nwho just pull other peoples work (which are also the people most likely to \nnot have beefy machines), the normal reflog is going to be entirely \nreachable, and we don't have to traverse the whole thing.\n\nSo what I'd suggest is something like:\n\n - start off with the time limit, possibly with some extra fudging\n\n - but never bother calling \"in_merge_bases()\"\n\n - if we ever get to a commit that doesn't look reachable in that \n situation, we now have two choices:\n\n (a) just use the dang 'object->flags & REACHABLE' flag as-is.\n Why even bother to be clever? We did the reachability by time \n already, it's done, it's there, just use it. In other words, the \n reachability simply works like \"--since='.\n\n (b) Try to do the \"exact\" thing, and waste lots of time on it, and \n maybe find an odd commit or two where the date had been wrong. Do \n we really care? \n\nI'd actually go for 'a', with a slight modification: try to convert the \n\"reflog date\" (the date of a local action) into a \"commit date\" (the date \nof a commit in the repository). Because those two are different \"time \nspaces\", and comparing a \"commit date\" to a \"in my repo\" date is fairly \nwrong.\n\nBut in general, I don't think this is something that needs any extra \nprecision. We're not talking about \"theoretically reachable\" here. We're \ntalking about reflog entries that are already older than the \nunreachability limit, and that point to commits that are older than the \nreachability limit. Yes, yes, clocks aren't synchronized, but do we really \ncare?\n\nIOW, I'd suggest just removing the in_merge_base() tests entirely. Make \nthe semantics even simpler:\n\n\thave_done_reachability = 0;\n\treachability_date = 0;\n\n\tfor_each_reflog_oldest_first() {\n\t\t/* Older than unconditional expire? */\n\t\tif (really_old(entry)) {\n\t\t\treachability_date = entry->commit->date;\n\t\t\tgoto prune;\n\t\t}\n\n\t\t/* Younger than the reflog reachability? */\n\t\tif (really_young(entry) && !fix_stale)\n\t\t\tgoto save;\n\n\t\t/*\n\t\t * Ok, not an unconditional expire entry.\n\t\t * Do the reachability - once\n\t\t */\n\t\tif (!have_done_reachability) {\n\t\t\thave_done_reachability = 1;\n\t\t\tif (fix_stale)\n\t\t\t\treachability_date = 0;\n\t\t\tmark_reachabile(top, reachability_date);\n\t\t}\n\n\t\tif (!(entry->commit->flags & REACHABLE))\n\t\t\tgoto prune;\n\n\tsave:\n\t\tsave(entry);\n\t\tcontinue;\n\tprune:\n\t\tprune(entry);\n\t\tcontinue;\n\t}\n\nDoes that change semantics? Yes, absolutely. But it sounds very practical.\n\n\t\tLinus\n"}]}