Junio C Hamano <junkio@xxxxxxx> writes:
> So this is the round #2, as a replacement patch of what I sent
> earlier. Once we know that there are pathspecs that sort later
> than the current path, we can defer doing strncmp() and skip
> that pathspec early by comparing length. If the path is longer
> than the spec, we can tell that it would never match without
> comparing.
And then this comes on top of #2.
-- >8 --
tree_entry_interesting(): allow it to say "everything is interesting"
In addition to optimizing pathspecs that would never match which
was done earlier, this optimizes pathspecs that would always
match (e.g. "arch/" while the traversal is already in
"arch/i386/" hierarchy).
With this, the worst case become slightly more palatable, while
improving average case.
Signed-off-by: Junio C Hamano <junkio@xxxxxxx>
---
For example, best-of-ten user times of
"rev-list HEAD -- $pathspec" in the eclipse repository for
various pathspecs are:
* .cvsignore (best path, earliest in the tree)
11.84 (without any optimization)
6.35 (with patch #2)
6.35 (with patch #2 and this patch)
* platform-launcher (worst path, last in the tree)
12.20 (without any optimization)
12.90 (with patch #2)
12.75 (with patch #2 and this patch)
* org.eclipse.platform.macosx.carbon-feature (middle in the tree)
12.02 (without any optimization)
10.52 (with patch #2)
10.43 (with patch #2 and this patch)
The kernel archive number is similar. Limited to arch/i386 and
include/asm-i386, the numbers are:
1.18 (without any optimization)
1.11 (with patch #2)
1.10 (with patch #2 and this patch).
tree-diff.c | 33 ++++++++++++++++++++++++++++-----
1 files changed, 28 insertions(+), 5 deletions(-)
diff --git a/tree-diff.c b/tree-diff.c
index 15fd665..852498e 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -70,7 +70,8 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const
* Is a tree entry interesting given the pathspec we have?
*
* Return:
- * - positive for yes
+ * - 2 for "yes, and all subsequent entries will be"
+ * - 1 for yes
* - zero for no
* - negative for "no, and no subsequent entries will be either"
*/
@@ -100,8 +101,11 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, int
if (strncmp(base, match, matchlen))
continue;
- /* The base is a subdirectory of a path which was specified. */
- return 1;
+ /*
+ * The base is a subdirectory of a path which
+ * was specified, so all of them are interesting.
+ */
+ return 2;
}
/* Does the base match? */
@@ -173,8 +177,18 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, int
/* A whole sub-tree went away or appeared */
static void show_tree(struct diff_options *opt, const char *prefix, struct tree_desc *desc, const char *base, int baselen)
{
+ int all_interesting = 0;
while (desc->size) {
- int show = tree_entry_interesting(desc, base, baselen, opt);
+ int show;
+
+ if (all_interesting)
+ show = 1;
+ else {
+ show = tree_entry_interesting(desc, base, baselen,
+ opt);
+ if (show == 2)
+ all_interesting = 1;
+ }
if (show < 0)
break;
if (show)
@@ -215,8 +229,17 @@ static void show_entry(struct diff_options *opt, const char *prefix, struct tree
static void skip_uninteresting(struct tree_desc *t, const char *base, int baselen, struct diff_options *opt)
{
+ int all_interesting = 0;
while (t->size) {
- int show = tree_entry_interesting(t, base, baselen, opt);
+ int show;
+
+ if (all_interesting)
+ show = 1;
+ else {
+ show = tree_entry_interesting(t, base, baselen, opt);
+ if (show == 2)
+ all_interesting = 1;
+ }
if (!show) {
update_tree_entry(t);
continue;
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html