From 24cb1bb1984be60addeecaf0bf5d16cd9688e6a7 Mon Sep 17 00:00:00 2001 From: Junio Hamano Date: Mon, 30 Mar 2009 21:34:14 -0700 Subject: [PATCH] Speed up reflog pruning of unreachable commits 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 Signed-off-by: Junio C Hamano --- builtin-reflog.c | 44 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 44 insertions(+) diff --git a/builtin-reflog.c b/builtin-reflog.c index a07960ff5..249ad2a31 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) { @@ -227,6 +228,8 @@ static int unreachable(struct expire_reflog_cb *cb, struct commit *commit, unsig } /* Reachable from the current ref? Don't prune. */ + if (commit->object.flags & REACHABLE) + return 0; if (in_merge_bases(commit, &cb->ref_commit, 1)) return 0; @@ -234,6 +237,43 @@ static int unreachable(struct expire_reflog_cb *cb, struct commit *commit, unsig 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 expire_reflog_ent(unsigned char *osha1, unsigned char *nsha1, const char *email, unsigned long timestamp, int tz, const char *message, void *cb_data) @@ -308,7 +348,11 @@ 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; + if (cb.ref_commit) + mark_reachable(cb.ref_commit, cmd->expire_total); for_each_reflog_ent(ref, expire_reflog_ent, &cb); + if (cb.ref_commit) + clear_commit_marks(cb.ref_commit, REACHABLE); finish: if (cb.newlog) { if (fclose(cb.newlog)) { -- 2.30.2