Kirill Smelkov <kirr@xxxxxxxxxx> writes:
> ---- 8< ----
> From: Kirill Smelkov <kirr@xxxxxxxxxx>
> Subject: [PATCH v2 1/2] tree-diff: rework diff_tree() to generate diffs for
> multiparent cases as well
> MIME-Version: 1.0
> Content-Type: text/plain; charset=UTF-8
> Content-Transfer-Encoding: 8bit
The last three do not belong here. Only From, Date and Subject are
relevant and taken as in-body headers.
For that matter, as the From and Subject above are exactly the same
as what you have on the e-mail header, you do not want any of them.
I'll strip them out here, so no need to resend. Thanks.
> Previously diff_tree(), which is now named __diff_tree_sha1(), was
That name with two leading underscores is a rather unfortunate,
especially for a function that is not a file scope static. No way
to rename this to something more sensible?
> That impedance mismatch *hurts* *performance* *badly* for generating
> combined diffs - in c839f1bd (combine-diff: optimize combine_diff_path
Please avoid referring to a commit that is not in 'master' by its
object name. It can be reworked later and get a different name.
> That slowness comes from the fact that currently, while generating
> combined diff, a lot of time is spent computing diff(commit,commit^2)
> just to only then intersect that huge diff to almost small set of files
> from diff(commit,commit^1).
Good observation.
> |a| |b| a < b -> a ∉ B -> D(A,B) += +a a↓
> |-| |-| a > b -> b ∉ A -> D(A,B) += -b b↓
> | | | | a = b -> investigate δ(a,b) a↓ b↓
In both the "n-parallel" and "diff-tree", when an entry 'a' is a
tree, I take this "D(A,B) += +a" to mean (recursively) adding all
the paths within 'a' to the result as addition. Sounds sensible.
> D(A,B)
>
> is by definition the same as combined diff
>
> D(A,[B]),
>
> so if we could rework the code for common case and make it be not slower
> for nparent=1 case, usual diff(t1,t2) generation will not be slower, and
> multiparent diff tree-walker would greatly benefit generating
> combine-diff.
OK.
> What we do is as follows:
>
> 1) diff tree-walker __diff_tree_sha1() is internally reworked to be
> a paths generator (new name diff_tree_paths()), with each generated path
> being `struct combine_diff_path` with info for path, new sha1,mode and for
> every parent which sha1,mode it was in it.
>
> 2) From that info, we can still generate usual diff queue with
> struct diff_filepairs, via "exporting" generated
> combine_diff_path, if we know we run for nparent=1 case.
> (see emit_diff() which is now named emit_diff_p0only())
s/p0/first_parent_/; perhaps?
> 3) In order for diff_can_quit_early(), which checks
>
> DIFF_OPT_TST(opt, HAS_CHANGES))
>
> to work, that exporting have to be happening not in bulk, but
> incrementally, one diff path at a time.
Good thinking.
> Some notes(*):
>
> 1) For loops,
>
> i = 0; do { ... } while (++i < nparent);
>
> is used instead of
>
> for (i = 0; i < nparent; ++i)
> ...
>
> because for the former case, the compiler have to emit additional
> prologue code which checks for i >= nparent case before entering the
> loop.
>
> As we require nparent must be >0, that additional overhead
> conflicts with the "runs not slower for nparent=1 case than before"
> goal.
Unfortunate. I'd rather see us stick to more readable and familiar
form for maintainability if this were not measurable.
> 2) alloca(), for small arrays, is used for the same reason - if we change
> it to xmalloc()/free() the timings get worse
Do you see any use of it outside compat/?
I thought we specifically avoid alloca() for portability. Also we
do not use variable-length-arrays on the stack either, I think.
> 3) For every parent tree, we need to keep a tag, whether entry from that
> parent equals to entry from minimal parent. For performance reasons I'm
> keeping that tag in entry's mode field in unused bit - see S_IFXMIN_NEQ.
Unfortunate, but I do not see another place to keep this
information offhand (nor implement this approach without keeping
that piece of information).
> P.S. and combined diff is not some exotic/for-play-only stuff - for
No need to convince us about that ;-)
> example for a program I write to represent Git archives as readonly
> filesystem, there is initial scan with
>
> `git log --reverse --raw --no-abbrev --no-renames -c`
>
> to extract log of what was created/changed when, as a result building a
> map
>
> {} sha1 -> in which commit (and date) a content was added
>
> that `-c` means also show combined diff for merges, and without them, if
> a merge is non-trivial (merges changes from two parents with both having
> separate changes to a file), or an evil one, the map will not be full,
> i.e. some valid sha1 would be absent from it.
>
> That case was my initial motivation for combined diffs speedup.
I wonder if this machinery can be reused for "log -m" as well (or
perhaps you do that already?). After all, by performing a single
parallel scan, you are gathering all the necessary information to
let you pretend that you did N pairwise diff-tree.
> diff --git a/tree-diff.c b/tree-diff.c
> index ab61a0a..2b7c991 100644
> --- a/tree-diff.c
> +++ b/tree-diff.c
> @@ -7,6 +7,25 @@
> #include "tree.h"
>
> /*
> + * internal mode marker, saying a tree entry != entry of tp[imin]
> + * (see __diff_tree_paths for what it means there)
> + *
> + * it *must* not overlap with any valid modes, and we will update/use/emit
> + * entry for diff only with it unset. Only non-overlapping to valid modes is
> + * required, because mode in tree_desc, comes here canonicalized via
> + * canon_mode().
> + *
> + * the definition assumes unsigned is at least 32 bits.
> + */
> +#define S_IFXMIN_NEQ 0x80000000
To allow better coordination across multiple codepaths that deal
with modes, I am wondering if this should be defined in cache.h
where made-up S_FIGITLINK and S_IFINVALID are defined (note the
comment that is there, as well).
> +static struct combine_diff_path *__diff_tree_paths(
> + struct combine_diff_path *p, const unsigned char *sha1,
> + const unsigned char **parents_sha1, int nparent,
> + struct strbuf *base, struct diff_options *opt);
Most of our code do not name private helper functions with leading
underscores.
I do like the direction this is going, but it looks to me that
"struct combine_diff" is now misnamed, because it no longer is about
combined diff. You are introducing a good framework for n-way diff,
and producing combined diff (i.e. -c or --cc) is now merely one way
to use that framework. We may want to clean these names up after
this series settles---perhaps "struct nway_diff" or something.
> +
> +/*
> * Compare two tree entries, taking into account only path/S_ISDIR(mode),
> * but not their sha1's.
> *
> @@ -33,72 +52,152 @@ static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2)
> }
>
>
> -/* convert path, t1/t2 -> opt->diff_*() callbacks */
> -static void emit_diff(struct diff_options *opt, struct strbuf *path,
> - struct tree_desc *t1, struct tree_desc *t2)
> +/*
> + * convert path -> opt->diff_*() callbacks
> + *
> + * emits diff to parent0 only.
Please call that "first parent".
> + */
"Returns 0 to tell the caller that we are done with p and it can be
freed" or something?
> +static int emit_diff_p0only(struct diff_options *opt, struct combine_diff_path *p)
> {
> ...
> +
> + return 0; /* = no need to keep allocated combine_diff_path */
Curious; what is that equal sign in the comment?
--
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