{"thread":{"id":"15097","subject":"[JGIT PATCH 15/14] Micro-optimize the combineDF part of NameConflictTreeWalk","startedAt":"2008-08-19T23:17:13Z","lastAt":"2008-08-19T23:17:13Z","messageCount":1,"participants":["Shawn O. Pearce"],"isPatch":true,"patchVersion":1,"patchTotal":14},"messages":[{"id":"87766","messageId":"1219187833-26568-1-git-send-email-spearce@spearce.org","threadId":"15097","inReplyTo":null,"subject":"[JGIT PATCH 15/14] Micro-optimize the combineDF part of NameConflictTreeWalk","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-19T23:17:13Z","receivedAt":"2008-08-19T23:17:13Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"We can do the common case of combineDF (which requires no lookahead)\nduring the search for the minimum entry by keeping track of the type\nof each entry and using the single entry lookahead inherent in the\ndata structure.\n\nSince this catches the most common case of \"a\" and \"a/\" with no\nintervening \"a.foo\" we can typically avoid the much more costly\ncombineDF and skipEntry routines.\n\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n\n This adds onto the end of my 14 patch D/F conflict series.  Last night\n it was bugging me that the common cases of all paths matching, or of\n the D/F pair being just one item apart required two loops through the\n iterators to identify the match (once in super.min, again in combineDF).\n\n .../jgit/treewalk/NameConflictTreeWalk.java        |   75 +++++++++++++++++++-\n 1 files changed, 72 insertions(+), 3 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java\nindex fdfba4e..dc854d8 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java\n@@ -78,6 +78,8 @@\n public class NameConflictTreeWalk extends TreeWalk {\n \tprivate static final int TREE_MODE = FileMode.TREE.getBits();\n \n+\tprivate boolean fastMinHasMatch;\n+\n \t/**\n \t * Create a new tree walker for a given repository.\n \t * \n@@ -91,11 +93,11 @@ public NameConflictTreeWalk(final Repository repo) {\n \t@Override\n \tAbstractTreeIterator min() throws CorruptObjectException {\n \t\tfor (;;) {\n-\t\t\tfinal AbstractTreeIterator minRef = super.min();\n-\t\t\tif (minRef.eof())\n+\t\t\tfinal AbstractTreeIterator minRef = fastMin();\n+\t\t\tif (fastMinHasMatch)\n \t\t\t\treturn minRef;\n \n-\t\t\tif (FileMode.TREE.equals(minRef.mode)) {\n+\t\t\tif (isTree(minRef)) {\n \t\t\t\tif (skipEntry(minRef)) {\n \t\t\t\t\tfor (final AbstractTreeIterator t : trees) {\n \t\t\t\t\t\tif (t.matches == minRef) {\n@@ -112,6 +114,73 @@ AbstractTreeIterator min() throws CorruptObjectException {\n \t\t}\n \t}\n \n+\tprivate AbstractTreeIterator fastMin() {\n+\t\tfastMinHasMatch = true;\n+\n+\t\tint i = 0;\n+\t\tAbstractTreeIterator minRef = trees[i];\n+\t\twhile (minRef.eof() && ++i < trees.length)\n+\t\t\tminRef = trees[i];\n+\t\tif (minRef.eof())\n+\t\t\treturn minRef;\n+\n+\t\tminRef.matches = minRef;\n+\t\twhile (++i < trees.length) {\n+\t\t\tfinal AbstractTreeIterator t = trees[i];\n+\t\t\tif (t.eof())\n+\t\t\t\tcontinue;\n+\n+\t\t\tfinal int cmp = t.pathCompare(minRef);\n+\t\t\tif (cmp < 0) {\n+\t\t\t\tif (fastMinHasMatch && isTree(minRef) && !isTree(t)\n+\t\t\t\t\t\t&& nameEqual(minRef, t)) {\n+\t\t\t\t\t// We used to be at a tree, but now we are at a file\n+\t\t\t\t\t// with the same name. Allow the file to match the\n+\t\t\t\t\t// tree anyway.\n+\t\t\t\t\t//\n+\t\t\t\t\tt.matches = minRef;\n+\t\t\t\t} else {\n+\t\t\t\t\tfastMinHasMatch = false;\n+\t\t\t\t\tt.matches = t;\n+\t\t\t\t\tminRef = t;\n+\t\t\t\t}\n+\t\t\t} else if (cmp == 0) {\n+\t\t\t\t// Exact name/mode match is best.\n+\t\t\t\t//\n+\t\t\t\tt.matches = minRef;\n+\t\t\t} else if (fastMinHasMatch && isTree(t) && !isTree(minRef)\n+\t\t\t\t\t&& nameEqual(t, minRef)) {\n+\t\t\t\t// The minimum is a file (non-tree) but the next entry\n+\t\t\t\t// of this iterator is a tree whose name matches our file.\n+\t\t\t\t// This is a classic D/F conflict and commonly occurs like\n+\t\t\t\t// this, with no gaps in between the file and directory.\n+\t\t\t\t//\n+\t\t\t\t// Use the tree as the minimum instead (see combineDF).\n+\t\t\t\t//\n+\n+\t\t\t\tfor (int k = 0; k < i; k++) {\n+\t\t\t\t\tfinal AbstractTreeIterator p = trees[k];\n+\t\t\t\t\tif (p.matches == minRef)\n+\t\t\t\t\t\tp.matches = t;\n+\t\t\t\t}\n+\t\t\t\tt.matches = t;\n+\t\t\t\tminRef = t;\n+\t\t\t} else\n+\t\t\t\tfastMinHasMatch = false;\n+\t\t}\n+\n+\t\treturn minRef;\n+\t}\n+\n+\tprivate static boolean nameEqual(final AbstractTreeIterator a,\n+\t\t\tfinal AbstractTreeIterator b) {\n+\t\treturn a.pathCompare(b, TREE_MODE) == 0;\n+\t}\n+\n+\tprivate static boolean isTree(final AbstractTreeIterator p) {\n+\t\treturn FileMode.TREE.equals(p.mode);\n+\t}\n+\n \tprivate boolean skipEntry(final AbstractTreeIterator minRef)\n \t\t\tthrows CorruptObjectException {\n \t\t// A tree D/F may have been handled earlier. We need to\n-- \n1.6.0.96.g2fad1.dirty\n"}]}