From: "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com>
To: git@vger.kernel.org
Cc: peff@peff.net, johannes.schindelin@gmx.net,
Derrick Stolee <dstolee@microsoft.com>
Subject: [PATCH] unpack-trees: correctly compute result count
Date: Fri, 10 Jan 2020 01:59:30 +0000 [thread overview]
Message-ID: <pull.520.git.1578621570180.gitgitgadget@gmail.com> (raw)
The clear_ce_flags_dir() method processes the cache entries within
a common directory. The returned int is the number of cache entries
processed by that directory. When using the sparse-checkout feature
in cone mode, we can skip the pattern matching for entries in the
directories that are entirely included or entirely excluded.
eb42feca (unpack-trees: hash less in cone mode, 2019-11-21)
introduced this performance feature. The old mechanism relied on
the counts returned by calling clear_ce_flags_1(), but the new
mechanism calculated the number of rows by subtracting "cache_end"
from "cache" to find the size of the range. However, the equation
is wrong because it divides by sizeof(struct cache_entry *). This
is not how pointer arithmetic works!
A coverity build of Git for Windows in preparation for the 2.25.0
release found this issue with the warning, "Pointer differences,
such as cache_end - cache, are automatically scaled down by the
size (8 bytes) of the pointed-to type (struct cache_entry *).
Most likely, the division by sizeof(struct cache_entry *) is
extraneous and should be eliminated." This warning is correct.
This leaves us with the question "how did this even work?" The
problem that occurs with this incorrect pointer arithmetic is
a performance-only bug, and a very slight one at that. Since
the entry count returned by clear_ce_flags_dir() is reduced by
a factor of 8, the loop in clear_ce_flags_1() will re-process
entries from those directories.
By inserting global counters into unpack-tree.c and tracing
them with trace2_data_intmax() (in a private change, for
testing), I was able to see count how many times the loop inside
clear_ce_flags_1() processed an entry and how many times
clear_ce_flags_dir() was called. Each of these are reduced by at
least a factor of 8 with the current change. A factor larger
than 8 happens when multiple levels of directories are repeated.
Specifically, in the Linux kernel repo, the command
git sparse-checkout set LICENSES
restricts the working directory to only the files at root and
in the LICENSES directory. Here are the measured counts:
clear_ce_flags_1 loop blocks:
Before: 11,520
After: 1,621
clear_ce_flags_dir calls:
Before: 7,048
After: 606
While these are dramatic counts, the time spent in
clear_ce_flags_1() is under one millisecond in each case, so
the improvement is not measurable as an end-to-end time.
Reported-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
unpack-trees: correctly compute result count
Here is a very small fix to the cone-mode pattern-matching in
unpack-trees.c. Johannes found this while running a Coverity scan for
other issues. He alerted me to the problem and I could immediately see
my error here. In creating this patch, most of my time was spent asking
"how did this work before?" and "why didn't this hurt performance?"
Hopefully my commit message explains this thoroughly enough.
As for making it into the release, I don't know. The change is small, it
has a very limited scope, but this flaw is also not really hurting
anything in a major way.
Thanks, -Stolee
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-520%2Fderrickstolee%2Funpack-trees-division-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-520/derrickstolee/unpack-trees-division-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/520
unpack-trees.c | 4 ++--
1 file changed, 2 insertions(+), 2 deletions(-)
diff --git a/unpack-trees.c b/unpack-trees.c
index 2399b6818b..3dba7f9f09 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -1305,14 +1305,14 @@ static int clear_ce_flags_dir(struct index_state *istate,
if (pl->use_cone_patterns && orig_ret == MATCHED_RECURSIVE) {
struct cache_entry **ce = cache;
- rc = (cache_end - cache) / sizeof(struct cache_entry *);
+ rc = cache_end - cache;
while (ce < cache_end) {
(*ce)->ce_flags &= ~clear_mask;
ce++;
}
} else if (pl->use_cone_patterns && orig_ret == NOT_MATCHED) {
- rc = (cache_end - cache) / sizeof(struct cache_entry *);
+ rc = cache_end - cache;
} else {
rc = clear_ce_flags_1(istate, cache, cache_end - cache,
prefix,
base-commit: 7a6a90c6ec48fc78c83d7090d6c1b95d8f3739c0
--
gitgitgadget
next reply other threads:[~2020-01-10 1:59 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-01-10 1:59 Derrick Stolee via GitGitGadget [this message]
2020-01-10 10:37 ` [PATCH] unpack-trees: correctly compute result count Jeff King
2020-01-10 11:24 ` Derrick Stolee
2020-01-10 11:30 ` Derrick Stolee
2020-01-10 19:33 ` Junio C Hamano
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=pull.520.git.1578621570180.gitgitgadget@gmail.com \
--to=gitgitgadget@gmail.com \
--cc=dstolee@microsoft.com \
--cc=git@vger.kernel.org \
--cc=johannes.schindelin@gmx.net \
--cc=peff@peff.net \
/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).