From: Junio C Hamano <gitster@pobox•com>
To: Kirill Smelkov <kirr@navytux•spb.ru>
Cc: kirr@mns•spb.ru, git@vger•kernel.org
Subject: Re: [PATCH v2 18/19] tree-diff: rework diff_tree() to generate diffs for multiparent cases as well
Date: Mon, 07 Apr 2014 10:29:46 -0700 [thread overview]
Message-ID: <xmqqr459m4j9.fsf@gitster.dls.corp.google.com> (raw)
In-Reply-To: <20140406214626.GA3843@mini.zxlink> (Kirill Smelkov's message of "Mon, 7 Apr 2014 01:46:26 +0400")
Kirill Smelkov <kirr@navytux•spb.ru> writes:
> The following
> ...
> maybe looks a bit simpler, but calls tree_entry_pathcmp twice more times.
>
> Besides for important nparent=1 case we were not calling
> tree_entry_pathcmp at all and here we'll call it once, which would slow
> execution down a bit, as base_name_compare shows measurable enough in profile.
> To avoid that we'll need to add 'if (i==imin) continue' and this won't
> be so simple then. And for general nparent case, as I've said, we'll be
> calling tree_entry_pathcmp twice more times...
>
> Because of all that I'd suggest to go with my original version.
OK.
> ... After some break on the topic,
> with a fresh eye I see a lot of confusion goes from the notation I've
> chosen initially (because of how I was reasoning about it on paper, when
> it was in flux) - i.e. xi for x[imin] and also using i as looping
> variable. And also because xi was already used for x[imin] I've used
> another letter 'k' denoting all other x'es, which leads to confusion...
>
>
> I propose we do the following renaming to clarify things:
>
> A/a -> T/t (to match resulting tree t name in the code)
> X/x -> P/p (to match parents trees tp in the code)
> i -> imin (so that i would be free for other tasks)
>
> then the above (with a prologue) would look like
>
> ---- 8< ----
> * T P1 Pn
> * - - -
> * |t| |p1| |pn|
> * |-| |--| ... |--| imin = argmin(p1...pn)
> * | | | | | |
> * |-| |--| |--|
> * |.| |. | |. |
> * . . .
> * . . .
> *
> * at any time there could be 3 cases:
> *
> * 1) t < p[imin];
> * 2) t > p[imin];
> * 3) t = p[imin].
> *
> * Schematic deduction of what every case means, and what to do, follows:
> *
> * 1) t < p[imin] -> ∀j t ∉ Pj -> "+t" ∈ D(T,Pj) -> D += "+t"; t↓
> *
> * 2) t > p[imin]
> *
> * 2.1) ∃j: pj > p[imin] -> "-p[imin]" ∉ D(T,Pj) -> D += ø; ∀ pi=p[imin] pi↓
> * 2.2) ∀i pi = p[imin] -> pi ∉ T -> "-pi" ∈ D(T,Pi) -> D += "-p[imin]"; ∀i pi↓
> *
> * 3) t = p[imin]
> *
> * 3.1) ∃j: pj > p[imin] -> "+t" ∈ D(T,Pj) -> only pi=p[imin] remains to investigate
> * 3.2) pi = p[imin] -> investigate δ(t,pi)
> * |
> * |
> * v
> *
> * 3.1+3.2) looking at δ(t,pi) ∀i: pi=p[imin] - if all != ø ->
> *
> * ⎧δ(t,pi) - if pi=p[imin]
> * -> D += ⎨
> * ⎩"+t" - if pi>p[imin]
> *
> *
> * in any case t↓ ∀ pi=p[imin] pi↓
> ...
> now xk is gone and i matches p[i] (= pi) etc so variable names correlate
> to algorithm description better.
>
> Does that maybe clarify things?
That sounds more consistent (modulo perhaps s/argmin/min/ at the
beginning?).
> P.S. Sorry for maybe some crept-in mistakes - I've tried to verify it
> thoroughly, but am too sleepy to be completely sure. On the other hand I
> think and hope the patch should be ok.
Thanks and do not be sorry for "mistakes"---we have the review
process exactly for catching them.
next prev parent reply other threads:[~2014-04-07 17:29 UTC|newest]
Thread overview: 64+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-02-24 16:21 [PATCH v2 00/19] Multiparent diff tree-walker + combine-diff speedup Kirill Smelkov
2014-02-24 16:21 ` [PATCH 01/19] combine-diff: move show_log_first logic/action out of paths scanning Kirill Smelkov
2014-02-24 16:21 ` [PATCH 02/19] combine-diff: move changed-paths scanning logic into its own function Kirill Smelkov
2014-02-24 16:21 ` [PATCH 03/19] tree-diff: no need to manually verify that there is no mode change for a path Kirill Smelkov
2014-02-24 16:21 ` [PATCH 04/19] tree-diff: no need to pass match to skip_uninteresting() Kirill Smelkov
2014-02-24 16:21 ` [PATCH 05/19] tree-diff: show_tree() is not needed Kirill Smelkov
2014-02-24 16:21 ` [PATCH 06/19] tree-diff: consolidate code for emitting diffs and recursion in one place Kirill Smelkov
2014-02-24 16:21 ` [PATCH 07/19] tree-diff: don't assume compare_tree_entry() returns -1,0,1 Kirill Smelkov
2014-02-24 16:21 ` [PATCH 08/19] tree-diff: move all action-taking code out of compare_tree_entry() Kirill Smelkov
2014-02-24 16:21 ` [PATCH 09/19] tree-diff: rename compare_tree_entry -> tree_entry_pathcmp Kirill Smelkov
2014-02-24 16:21 ` [PATCH 10/19] tree-diff: show_path prototype is not needed anymore Kirill Smelkov
2014-02-24 16:21 ` [PATCH 11/19] tree-diff: simplify tree_entry_pathcmp Kirill Smelkov
2014-03-24 21:25 ` Junio C Hamano
2014-03-25 9:23 ` Kirill Smelkov
2014-02-24 16:21 ` [PATCH 12/19] tree-diff: remove special-case diff-emitting code for empty-tree cases Kirill Smelkov
2014-03-24 21:18 ` Junio C Hamano
2014-03-25 9:20 ` Kirill Smelkov
2014-03-25 17:45 ` Junio C Hamano
2014-03-26 18:32 ` Kirill Smelkov
2014-03-25 22:07 ` Junio C Hamano
2014-02-24 16:21 ` [PATCH 13/19] tree-diff: diff_tree() should now be static Kirill Smelkov
2014-02-24 16:21 ` [PATCH v2 14/19] tree-diff: rework diff_tree interface to be sha1 based Kirill Smelkov
2014-03-24 21:36 ` Junio C Hamano
2014-03-25 9:22 ` Kirill Smelkov
2014-03-25 17:46 ` Junio C Hamano
2014-03-26 19:52 ` Kirill Smelkov
2014-03-26 21:34 ` Junio C Hamano
2014-03-27 14:24 ` Kirill Smelkov
2014-03-27 18:48 ` Junio C Hamano
2014-03-27 19:43 ` Kirill Smelkov
2014-03-28 6:52 ` Johannes Sixt
2014-03-28 17:06 ` Junio C Hamano
2014-03-28 17:46 ` Johannes Sixt
2014-03-28 18:36 ` Junio C Hamano
2014-03-28 19:08 ` Johannes Sixt
2014-03-28 19:27 ` Junio C Hamano
2014-02-24 16:21 ` [PATCH 15/19] tree-diff: no need to call "full" diff_tree_sha1 from show_path() Kirill Smelkov
2014-03-27 14:21 ` Kirill Smelkov
2014-02-24 16:21 ` [PATCH v2 16/19] tree-diff: reuse base str(buf) memory on sub-tree recursion Kirill Smelkov
2014-03-24 21:43 ` Junio C Hamano
2014-03-25 9:23 ` Kirill Smelkov
2014-03-27 14:22 ` Kirill Smelkov
2014-02-24 16:21 ` [PATCH 17/19] Portable alloca for Git Kirill Smelkov
2014-02-28 10:58 ` Thomas Schwinge
2014-02-28 13:44 ` Erik Faye-Lund
2014-02-28 13:50 ` Erik Faye-Lund
2014-02-28 17:00 ` Kirill Smelkov
2014-02-28 17:19 ` Erik Faye-Lund
2014-03-05 9:31 ` Kirill Smelkov
2014-03-24 21:47 ` Junio C Hamano
2014-03-27 14:22 ` Kirill Smelkov
2014-04-09 12:48 ` Kirill Smelkov
2014-04-09 13:01 ` Erik Faye-Lund
2014-04-10 17:30 ` Junio C Hamano
2014-02-24 16:21 ` [PATCH v2 18/19] tree-diff: rework diff_tree() to generate diffs for multiparent cases as well Kirill Smelkov
2014-03-27 14:23 ` Kirill Smelkov
2014-04-04 18:42 ` Junio C Hamano
2014-04-06 21:46 ` Kirill Smelkov
2014-04-07 17:29 ` Junio C Hamano [this message]
2014-04-07 20:26 ` Kirill Smelkov
2014-04-07 18:07 ` Junio C Hamano
2014-02-24 16:21 ` [PATCH 19/19] combine-diff: speed it up, by using multiparent diff tree-walker directly Kirill Smelkov
2014-02-24 23:43 ` [PATCH v2 00/19] Multiparent diff tree-walker + combine-diff speedup Duy Nguyen
2014-02-25 10:38 ` Kirill Smelkov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=xmqqr459m4j9.fsf@gitster.dls.corp.google.com \
--to=gitster@pobox$(echo .)com \
--cc=git@vger$(echo .)kernel.org \
--cc=kirr@mns$(echo .)spb.ru \
--cc=kirr@navytux$(echo .)spb.ru \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox