Re: [PATCH 1/2] tree-diff: rework diff_tree() to generate diffs for multiparent cases as well

[Junio C Hamano <gitster@pobox.com>]

Kirill Smelkov <kirr@mns.spb.ru> writes:

> ---- 8< ----
> From: Kirill Smelkov <kirr@mns.spb.ru>
> 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?