git.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Duy Nguyen <pclouds@gmail.com>
To: Kirill Smelkov <kirr@mns.spb.ru>
Cc: Junio C Hamano <gitster@pobox.com>,
	Git Mailing List <git@vger.kernel.org>
Subject: Re: [PATCH v2 00/19] Multiparent diff tree-walker + combine-diff speedup
Date: Tue, 25 Feb 2014 06:43:24 +0700	[thread overview]
Message-ID: <CACsJy8BXMVNVAyqPEbHTkGxSSEJ6DpYUVwZqthiMQfO7Tj9T8A@mail.gmail.com> (raw)
In-Reply-To: <cover.1393257006.git.kirr@mns.spb.ru>

On Mon, Feb 24, 2014 at 11:21 PM, Kirill Smelkov <kirr@mns.spb.ru> wrote:
> 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.

I think there is another use case for this n-tree walker (but I'm not
entirely sure yet as I haven't really read the series). In git-log
(either with pathspec or --patch) we basically do this

diff HEAD^ HEAD
diff HEAD^^ HEAD^
diff HEAD^^^ HEAD^^
diff HEAD^^^^ HEAD^^^
...

so except HEAD (and the last commit), all commits' tree will be
read/diff'd twice. With n-tree walker I think we may be able to diff
them in batch to reduce extra processing: commit lists are split into
16-commit blocks where 16 trees are fed to the new tree walker at the
same time. I hope it would make git-log a bit faster (especially for
-S). Maybe not much.
-- 
Duy

  parent reply	other threads:[~2014-02-24 23:44 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
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 ` Duy Nguyen [this message]
2014-02-25 10:38   ` [PATCH v2 00/19] Multiparent diff tree-walker + combine-diff speedup 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=CACsJy8BXMVNVAyqPEbHTkGxSSEJ6DpYUVwZqthiMQfO7Tj9T8A@mail.gmail.com \
    --to=pclouds@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=kirr@mns.spb.ru \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
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;
as well as URLs for NNTP newsgroup(s).