Re: Set up for better tree diff optimizations
From: Junio C Hamano <hidden>
Date: 2016-06-15 22:43:00
Subsystem:
the rest · Maintainer:
Linus Torvalds
Possibly related (same subject, not in this thread)
- 2016-06-15 · Set up for better tree diff optimizations · Linus Torvalds <torvalds@linux-foundation.org>
- 2016-06-15 · Re: Set up for better tree diff optimizations · Junio C Hamano <hidden>
- 2016-06-15 · Re: Set up for better tree diff optimizations · Linus Torvalds <torvalds@linux-foundation.org>
- 2016-06-15 · Re: Set up for better tree diff optimizations · Junio C Hamano <hidden>
- 2016-06-15 · Re: Set up for better tree diff optimizations · Linus Torvalds <torvalds@linux-foundation.org>
Junio C Hamano [off-list ref] 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 <redacted>
---
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;