{"thread":{"id":"18377","subject":"[JGIT PATCH 1/2] Fix long running merge base computations","startedAt":"2009-03-18T18:01:48Z","lastAt":"2009-03-18T18:01:49Z","messageCount":2,"participants":["Shawn O. Pearce"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"108399","messageId":"1237399309-29493-1-git-send-email-spearce@spearce.org","threadId":"18377","inReplyTo":null,"subject":"[JGIT PATCH 1/2] Fix long running merge base computations","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-03-18T18:01:48Z","receivedAt":"2009-03-18T18:01:48Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"If a part of the project history is reachable by more than one\npath through the revision graph, we only need to traverse down\nit once through the first detected path when marking parents\nas reachable from an input branch.\n\nPreviously, JGit recomputed the entire project history for each\npath it was reachable through.  On linux-2.6 based histories we\ngot stuck for hours computing a merge base, as we kept passing\nback through the same sections of the revision graph.\n\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n .../spearce/jgit/revwalk/MergeBaseGenerator.java   |    9 ++++++++-\n 1 files changed, 8 insertions(+), 1 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java\nindex 1676caa..2eb9688 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java\n@@ -184,7 +184,9 @@ private void carryOntoHistory(RevCommit c, final int carry) {\n \t}\n \n \tprivate boolean carryOntoOne(final RevCommit p, final int carry) {\n+\t\tfinal boolean haveAll = (p.flags & carry) == carry;\n \t\tp.flags |= carry;\n+\n \t\tif ((p.flags & POPPED) != 0 && (carry & MERGE_BASE) == 0\n \t\t\t\t&& (p.flags & branchMask) == branchMask) {\n \t\t\t// We were popped without being a merge base, but we just got\n@@ -197,6 +199,11 @@ private boolean carryOntoOne(final RevCommit p, final int carry) {\n \t\t\tcarryOntoHistory(p, branchMask | MERGE_BASE);\n \t\t\treturn true;\n \t\t}\n-\t\treturn false;\n+\n+\t\t// If we already had all carried flags, our parents do too.\n+\t\t// Return true to stop the caller from running down this leg\n+\t\t// of the revision graph any further.\n+\t\t//\n+\t\treturn haveAll;\n \t}\n }\n-- \n1.6.2.1.337.g6270ba\n"},{"id":"108400","messageId":"1237399309-29493-2-git-send-email-spearce@spearce.org","threadId":"18377","inReplyTo":"1237399309-29493-1-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 2/2] Micro-optimize the merge base generator","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-03-18T18:01:49Z","receivedAt":"2009-03-18T18:01:49Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Instead of doing 3 bit-wise and operations followed by 3 compares\nand two boolean and conditions on every commit we evaluate in the\nhistory, we can fold all of the tests into a pair of fields and\ndo one bit mask and compare.\n\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n .../spearce/jgit/revwalk/MergeBaseGenerator.java   |   13 +++++++++++--\n 1 files changed, 11 insertions(+), 2 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java\nindex 2eb9688..8694e4c 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/MergeBaseGenerator.java\n@@ -73,6 +73,10 @@\n \n \tprivate int branchMask;\n \n+\tprivate int recarryTest;\n+\n+\tprivate int recarryMask;\n+\n \tMergeBaseGenerator(final RevWalk w) {\n \t\twalker = w;\n \t\tpending = new DateRevQueue();\n@@ -91,6 +95,12 @@ void init(final AbstractRevQueue p) {\n \t\t\t// will be available for reuse when the walk resets.\n \t\t\t//\n \t\t\twalker.freeFlag(branchMask);\n+\n+\t\t\t// Setup the condition used by carryOntoOne to detect a late\n+\t\t\t// merge base and produce it on the next round.\n+\t\t\t//\n+\t\t\trecarryTest = branchMask | POPPED;\n+\t\t\trecarryMask = branchMask | POPPED | MERGE_BASE;\n \t\t}\n \t}\n \n@@ -187,8 +197,7 @@ private boolean carryOntoOne(final RevCommit p, final int carry) {\n \t\tfinal boolean haveAll = (p.flags & carry) == carry;\n \t\tp.flags |= carry;\n \n-\t\tif ((p.flags & POPPED) != 0 && (carry & MERGE_BASE) == 0\n-\t\t\t\t&& (p.flags & branchMask) == branchMask) {\n+\t\tif ((p.flags & recarryMask) == recarryTest) {\n \t\t\t// We were popped without being a merge base, but we just got\n \t\t\t// voted to be one. Inject ourselves back at the front of the\n \t\t\t// pending queue and tell all of our ancestors they are within\n-- \n1.6.2.1.337.g6270ba\n"}]}