From: Linus Torvalds <torvalds@linux-foundation.org>
To: Junio C Hamano <gitster@pobox.com>,
Git Mailing List <git@vger.kernel.org>
Subject: [PATCH 2/2] Speed up reflog pruning of unreachable commits
Date: Tue, 31 Mar 2009 10:11:56 -0700 (PDT) [thread overview]
Message-ID: <alpine.LFD.2.00.0903311010050.4093@localhost.localdomain> (raw)
In-Reply-To: <alpine.LFD.2.00.0903311003490.4093@localhost.localdomain>
From: Junio Hamano <gitster@pobox.com>
Date: Mon, 30 Mar 2009 21:34:14 -0700
Instead of doing the (potentially very expensive) "in_merge_base()"
check for each commit that might be pruned if it is unreachable, do a
preparatory reachability graph of the commit space, so that the common
case of being reachable can be tested directly.
[ Cleaned up a bit and tweaked to actually work. - Linus ]
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
builtin-reflog.c | 43 +++++++++++++++++++++++++++++++++++++++++++
1 files changed, 43 insertions(+), 0 deletions(-)
diff --git a/builtin-reflog.c b/builtin-reflog.c
index 0355ce6..f29ab2f 100644
--- a/builtin-reflog.c
+++ b/builtin-reflog.c
@@ -52,6 +52,7 @@ struct collect_reflog_cb {
#define INCOMPLETE (1u<<10)
#define STUDYING (1u<<11)
+#define REACHABLE (1u<<12)
static int tree_is_complete(const unsigned char *sha1)
{
@@ -209,6 +210,43 @@ static int keep_entry(struct commit **it, unsigned char *sha1)
return 1;
}
+static void mark_reachable(struct commit *commit, unsigned long expire_limit)
+{
+ /*
+ * We need to compute if commit on either side of an reflog
+ * entry is reachable from the tip of the ref for all entries.
+ * Mark commits that are reachable from the tip down to the
+ * time threashold first; we know a commit marked thusly is
+ * reachable from the tip without running in_merge_bases()
+ * at all.
+ */
+ struct commit_list *pending = NULL;
+
+ commit_list_insert(commit, &pending);
+ while (pending) {
+ struct commit_list *entry = pending;
+ struct commit_list *parent;
+ pending = entry->next;
+ commit = entry->item;
+ free(entry);
+ if (commit->object.flags & REACHABLE)
+ continue;
+ if (parse_commit(commit))
+ continue;
+ commit->object.flags |= REACHABLE;
+ if (commit->date < expire_limit)
+ continue;
+ parent = commit->parents;
+ while (parent) {
+ commit = parent->item;
+ parent = parent->next;
+ if (commit->object.flags & REACHABLE)
+ continue;
+ commit_list_insert(commit, &pending);
+ }
+ }
+}
+
static int unreachable(struct expire_reflog_cb *cb, struct commit *commit, unsigned char *sha1)
{
/*
@@ -227,6 +265,8 @@ static int unreachable(struct expire_reflog_cb *cb, struct commit *commit, unsig
}
/* Reachable from the current reflog top? Don't prune */
+ if (commit->object.flags & REACHABLE)
+ return 0;
if (in_merge_bases(commit, &cb->ref_commit, 1))
return 0;
@@ -308,7 +348,10 @@ static int expire_reflog(const char *ref, const unsigned char *sha1, int unused,
cb.ref_commit = lookup_commit_reference_gently(sha1, 1);
cb.ref = ref;
cb.cmd = cmd;
+
+ mark_reachable(cb.ref_commit, cmd->expire_total);
for_each_reflog_ent(ref, expire_reflog_ent, &cb);
+ clear_commit_marks(cb.ref_commit, REACHABLE);
finish:
if (cb.newlog) {
if (fclose(cb.newlog)) {
--
1.6.2.1.404.gb0085.dirty
next prev parent reply other threads:[~2009-03-31 17:15 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
2009-03-31 17:03 [PATCH 0/2] speed up reflog unreachability pruning Linus Torvalds
2009-03-31 17:09 ` [PATCH 1/2] Clean up reflog unreachability pruning decision Linus Torvalds
2009-03-31 17:11 ` Linus Torvalds [this message]
2009-03-31 17:46 ` [PATCH 2/2] Speed up reflog pruning of unreachable commits Junio C Hamano
2009-03-31 17:58 ` Linus Torvalds
2009-03-31 17:44 ` [PATCH 1/2] Clean up reflog unreachability pruning decision Junio C Hamano
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=alpine.LFD.2.00.0903311010050.4093@localhost.localdomain \
--to=torvalds@linux-foundation.org \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.