All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH v2 00/19] Multiparent diff tree-walker + combine-diff speedup
@ 2014-02-24 16:21 Kirill Smelkov
  2014-02-24 16:21 ` [PATCH 01/19] combine-diff: move show_log_first logic/action out of paths scanning Kirill Smelkov
                   ` (19 more replies)
  0 siblings, 20 replies; 64+ messages in thread
From: Kirill Smelkov @ 2014-02-24 16:21 UTC (permalink / raw)
  To: Junio C Hamano; +Cc: git, Kirill Smelkov

Hello up there.

Here go combine-diff speedup patches in form of first reworking diff
tree-walker to work in general case - when a commit have several parents, not
only one - we are traversing all 1+nparent trees in parallel.

Then we are taking advantage of the new diff tree-walker for speeding up
combine-diff, which for linux.git results in ~14 times speedup.

This is the second posting for the whole series - sent here patches should go
instead of already-in-pu ks/diff-tree-more and ks/tree-diff-nway into
ks/tree-diff-nway - patches are related and seeing them all at once is more
logical to me.

I've tried to do my homework based on review feedback and the changes compared
to v1 are:

- fixed last-minute thinko/bug last time introduced on my side (sorry) with
  opt->pathchange manipulation in __diff_tree_sha1() - we were forgetting to
  restore opt->pathchange, which led to incorrect log -c (merges _and_ plain
  diff-tree) output;

  This time, I've verified several times, log output stays really the same.

- direct use of alloca() changed to portability wrappers xalloca/xalloca_free
  which gracefully degrade to xmalloc/free on systems, where alloca is not
  available (see new patch 17).

- "i = 0; do { ... } while (++i < nparent)" is back to usual looping
  "for (i = 0; i < nparent; ++)", as I've re-measured timings and the
  difference is negligible.

  ( Initially, when I was fighting for every cycle it made sense, but real
    no-slowdown turned out to be related to avoiding mallocs, load trees in correct
    order and reducing register pressure. )

- S_IFXMIN_NEQ definition moved out to cache.h, to have all modes registry in one place;


- diff_tree() becomes static (new patch 13), as nobody is using it outside
  tree-diff.c (and is later renamed to __diff_tree_sha1);

- p0 -> first_parent; corrected comments about how emit_diff_first_parent_only
  behaves;


not changed:

- low-level helpers are still named with "__" prefix as, imho, that is the best
  convention to name such helpers, without sacrificing signal/noise ratio. All
  of them are now static though.


Signoffs were left intact, if a patch was already applied to pu with one, and
had not changed.

Please apply and thanks,
Kirill

P.S. Sorry for the delay - I was very busy.


Kirill Smelkov (19):
  combine-diff: move show_log_first logic/action out of paths scanning
  combine-diff: move changed-paths scanning logic into its own function
  tree-diff: no need to manually verify that there is no mode change for a path
  tree-diff: no need to pass match to skip_uninteresting()
  tree-diff: show_tree() is not needed
  tree-diff: consolidate code for emitting diffs and recursion in one place
  tree-diff: don't assume compare_tree_entry() returns -1,0,1
  tree-diff: move all action-taking code out of compare_tree_entry()
  tree-diff: rename compare_tree_entry -> tree_entry_pathcmp
  tree-diff: show_path prototype is not needed anymore
  tree-diff: simplify tree_entry_pathcmp
  tree-diff: remove special-case diff-emitting code for empty-tree cases
  tree-diff: diff_tree() should now be static
  tree-diff: rework diff_tree interface to be sha1 based
  tree-diff: no need to call "full" diff_tree_sha1 from show_path()
  tree-diff: reuse base str(buf) memory on sub-tree recursion
  Portable alloca for Git
  tree-diff: rework diff_tree() to generate diffs for multiparent cases as well
  combine-diff: speed it up, by using multiparent diff tree-walker directly

 Makefile          |   6 +
 cache.h           |  15 ++
 combine-diff.c    | 170 +++++++++++---
 config.mak.uname  |  10 +-
 configure.ac      |   8 +
 diff.c            |   2 +
 diff.h            |  12 +-
 git-compat-util.h |   8 +
 tree-diff.c       | 666 +++++++++++++++++++++++++++++++++++++++++++-----------
 9 files changed, 724 insertions(+), 173 deletions(-)

-- 
1.9.rc1.181.g641f458

^ permalink raw reply	[flat|nested] 64+ messages in thread

end of thread, other threads:[~2014-04-10 17:30 UTC | newest]

Thread overview: 64+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
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
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

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.