From: "SZEDER Gábor" <szeder.dev@gmail.com>
To: git@vger.kernel.org
Cc: "Junio C Hamano" <gitster@pobox.com>,
"Thomas Rast" <tr@thomasrast.ch>,
"Derrick Stolee" <stolee@gmail.com>,
"SZEDER Gábor" <szeder.dev@gmail.com>
Subject: [RFC PATCH 5/5] line-log: try to use generation number-based topo-ordering
Date: Sun, 18 Aug 2019 20:28:01 +0200 [thread overview]
Message-ID: <20190818182801.7580-6-szeder.dev@gmail.com> (raw)
In-Reply-To: <20190818182801.7580-1-szeder.dev@gmail.com>
The previous patch made it possible to perform line-level filtering
during history traversal instead of in an expensive preprocessing
step, but it still requires some simpler preprocessing steps, notably
topo-ordering. However, nowadays we have commit-graphs storing
generation numbers, which make it possible to incrementally traverse
the history in topological order, without the preparatory limit_list()
and sort_in_topological_order() steps; see b45424181e (revision.c:
generation-based topo-order algorithm, 2018-11-01).
This patch combines the two, so we can do both the topo-ordering and
the line-level filtering during history traversal, eliminating even
those simpler preprocessing steps, and thus further reducing the delay
before showing the first commit modifying the given line range.
The 'revs->limited' flag plays the central role in this, because, due
to limitations of the current implementation, the generation
number-based topo-ordering is only enabled when this flag remains
unset. Line-level log, however, always sets this flag in
setup_revisions() ever since the feature was introduced in 12da1d1f6f
(Implement line-history search (git log -L), 2013-03-28). The reason
for setting 'limited' is unclear, though, because the line-level log
itself doesn't directly depend on it, and it doesn't affect how the
limit_list() function limits the revision range. However, there is an
indirect dependency: the line-level log requires topo-ordering, and
the "traditional" sort_in_topological_order() requires an already
limited commit list since e6c3505b44 (Make sure we generate the whole
commit list before trying to sort it topologically, 2005-07-06). The
new, generation numbers-based topo-ordering doesn't require a limited
commit list anymore.
So don't set 'revs->limited' for line-level log, unless it is really
necessary, namely:
- The user explicitly requested parent rewriting, because that is
still done in the line_log_filter() preprocessing step (see
previous patch), which requires sort_in_topological_order() and in
turn limit_list() as well.
- A commit-graph file is not available or it doesn't yet contain
generation numbers. In these cases we had to fall back on
sort_in_topological_order() and in turn limit_list(). The
existing condition with generation_numbers_enabled() has already
ensured that the 'limited' flag is set in these cases; this patch
just makes sure that the line-level log sets 'revs->topo_order'
before that condition.
While the reduced delay before showing the first commit is measurable
in git.git, it takes a bigger repository to make it clearly noticable.
In both cases below the line ranges were chosen so that they were
modified rather close to the starting revisions, so the effect of this
change is most noticable.
# git.git
$ time git --no-pager log -L:read_alternate_refs:sha1-file.c -1 v2.23.0
Before:
real 0m0.107s
user 0m0.091s
sys 0m0.013s
After:
real 0m0.058s
user 0m0.050s
sys 0m0.005s
# linux.git
$ time git --no-pager log \
-L:build_restore_work_registers:arch/mips/mm/tlbex.c -1 v5.2
Before:
real 0m1.129s
user 0m1.061s
sys 0m0.069s
After:
real 0m0.096s
user 0m0.087s
sys 0m0.009s
Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
---
Notes:
FWIW, that line-level log sets 'limited' in addition to 'topo_order'
thing was already part of the first submitted iteration of the
line-level log patch series:
https://public-inbox.org/git/1277558857-23103-4-git-send-email-struggleyb.nku@gmail.com/#Z30revision.c
But it was never discussed during review.
revision.c | 11 ++++++-----
1 file changed, 6 insertions(+), 5 deletions(-)
diff --git a/revision.c b/revision.c
index 6bdfcb38cd..7a9dc54771 100644
--- a/revision.c
+++ b/revision.c
@@ -2658,6 +2658,12 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s
if (revs->diffopt.objfind)
revs->simplify_history = 0;
+ if (revs->line_level_traverse) {
+ if (want_ancestry(revs))
+ revs->limited = 1;
+ revs->topo_order = 1;
+ }
+
if (revs->topo_order && !generation_numbers_enabled(the_repository))
revs->limited = 1;
@@ -2677,11 +2683,6 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s
revs->diffopt.abbrev = revs->abbrev;
- if (revs->line_level_traverse) {
- revs->limited = 1;
- revs->topo_order = 1;
- }
-
diff_setup_done(&revs->diffopt);
grep_commit_pattern_type(GREP_PATTERN_TYPE_UNSPECIFIED,
--
2.23.0.349.g73f10e387d
next prev parent reply other threads:[~2019-08-18 18:28 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-08-18 18:27 [RFC PATCH 0/5] line-log: towards a more responsive, incremental 'git log -L' SZEDER Gábor
2019-08-18 18:27 ` [RFC PATCH 1/5] completion: offer '--(no-)patch' among 'git log' options SZEDER Gábor
2019-08-18 18:27 ` [RFC PATCH 2/5] line-log: remove unused fields from 'struct line_log_data' SZEDER Gábor
2019-08-19 11:53 ` Derrick Stolee
2019-08-18 18:27 ` [RFC PATCH 3/5] t4211-line-log: add tests for parent oids SZEDER Gábor
2019-08-18 18:28 ` [RFC PATCH 4/5] line-log: more responsive, incremental 'git log -L' SZEDER Gábor
2019-08-19 12:34 ` SZEDER Gábor
2019-08-19 12:43 ` Derrick Stolee
2019-08-18 18:28 ` SZEDER Gábor [this message]
2019-08-19 12:00 ` [RFC PATCH 0/5] line-log: towards a " Derrick Stolee
2019-08-19 13:03 ` SZEDER Gábor
2019-08-19 14:50 ` Derrick Stolee
2019-08-19 15:02 ` SZEDER Gábor
2019-08-19 16:12 ` Derrick Stolee
2019-08-21 11:07 ` SZEDER Gábor
2020-04-09 12:17 ` Derrick Stolee
2020-04-24 9:02 ` SZEDER Gábor
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
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20190818182801.7580-6-szeder.dev@gmail.com \
--to=szeder.dev@gmail.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=stolee@gmail.com \
--cc=tr@thomasrast.ch \
/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.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
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 read-only IMAP folder(s) and NNTP newsgroup(s).