summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@osdl.org>2005-08-10 23:26:32 (GMT)
committerJunio C Hamano <junkio@cox.net>2005-08-12 01:26:12 (GMT)
commit0b9442d618bedd5bef7ec4ef5829b82df57e89eb (patch)
tree765f2585e8b9def58562331d6003b71f82557825
parent2b64f88f09ae2169ec85652b46897574e352936d (diff)
downloadgit-0b9442d618bedd5bef7ec4ef5829b82df57e89eb.zip
git-0b9442d618bedd5bef7ec4ef5829b82df57e89eb.tar.gz
git-0b9442d618bedd5bef7ec4ef5829b82df57e89eb.tar.bz2
[PATCH] Speed up git-merge-base a lot
In commit 4f7eb2e5a351e0d1f19fd4eab7e92834cc4528c2 I fixed git-merge-base getting confused by datestamps that caused it to traverse things in a non-obvious order. However, my fix was a very brute-force one, and it had some really horrible implications for more complex trees with lots of parallell development. It might end up traversing all the way to the root commit. Now, normally that isn't that horrible: it's used mainly for merging, and the bad cases really tend to happen fairly rarely, so if it takes a few seconds, we're not in too bad shape. However, gitk will also do the git-merge-base for every merge it shows, because it basically re-does the trivial merge in order to show the "interesting" parts. And there we'd really like the result to be instantaneous. This patch does that by walking the tree more completely, and using the same heuristic as git-rev-list to decide "ok, the rest is uninteresting". In one - hopefully fairly extreme - case, it made a git-merge-base go from just under five seconds(!) to a tenth of a second on my machine. Signed-off-by: Linus Torvalds <torvalds@osdl.org> Signed-off-by: Junio C Hamano <junkio@cox.net>
-rw-r--r--merge-base.c29
1 files changed, 22 insertions, 7 deletions
diff --git a/merge-base.c b/merge-base.c
index 5919566..18d81d0 100644
--- a/merge-base.c
+++ b/merge-base.c
@@ -2,6 +2,22 @@
#include "cache.h"
#include "commit.h"
+#define PARENT1 1
+#define PARENT2 2
+#define UNINTERESTING 4
+
+static int interesting(struct commit_list *list)
+{
+ while (list) {
+ struct commit *commit = list->item;
+ list = list->next;
+ if (commit->object.flags & UNINTERESTING)
+ continue;
+ return 1;
+ }
+ return 0;
+}
+
static struct commit *common_ancestor(struct commit *rev1, struct commit *rev2)
{
struct commit_list *list = NULL;
@@ -18,19 +34,18 @@ static struct commit *common_ancestor(struct commit *rev1, struct commit *rev2)
insert_by_date(rev1, &list);
insert_by_date(rev2, &list);
- while (list) {
+ while (interesting(list)) {
struct commit *commit = list->item;
struct commit_list *tmp = list, *parents;
- int flags = commit->object.flags & 3;
+ int flags = commit->object.flags & 7;
list = list->next;
free(tmp);
- switch (flags) {
- case 3:
+ if (flags == 3) {
insert_by_date(commit, &result);
- continue;
- case 0:
- die("git-merge-base: commit without either parent?");
+
+ /* Mark children of a found merge uninteresting */
+ flags |= UNINTERESTING;
}
parents = commit->parents;
while (parents) {