On 1/2/2021 10:19 AM, René Scharfe wrote:
> Use the name length field of cache entries instead of calculating its
> value anew.
Thanks! I didn't know about this macro.
-Stolee
> Signed-off-by: René Scharfe <l.s.r@xxxxxx>
> ---
> Not sure why it took me so long to spot this.. o_O
>
> cache-tree.c | 10 ++++++----
> 1 file changed, 6 insertions(+), 4 deletions(-)
>
> diff --git a/cache-tree.c b/cache-tree.c
> index a537a806c1..57cacab195 100644
> --- a/cache-tree.c
> +++ b/cache-tree.c
> @@ -185,10 +185,12 @@ static int verify_cache(struct cache_entry **cache,
> * the cache is sorted. Also path can appear only once,
> * which means conflicting one would immediately follow.
> */
> - const char *this_name = cache[i]->name;
> - const char *next_name = cache[i+1]->name;
> - int this_len = strlen(this_name);
> - if (this_len < strlen(next_name) &&
> + const struct cache_entry *this_ce = cache[i];
> + const struct cache_entry *next_ce = cache[i + 1];
> + const char *this_name = this_ce->name;
> + const char *next_name = next_ce->name;
> + int this_len = ce_namelen(this_ce);
> + if (this_len < ce_namelen(next_ce) &&
> strncmp(this_name, next_name, this_len) == 0 &&
> next_name[this_len] == '/') {
> if (10 < ++funny) {
For what it's worth, this caching of the lengths lowers my test
time from 854ms to 833ms. It goes down again to 816ms with the
swapped conditional, so I'll include that patch here:
-- >8 --
>From 8f303000030bd8f9db3466c90eb0d9fea11a7c3b Mon Sep 17 00:00:00 2001
From: Derrick Stolee <dstolee@xxxxxxxxxxxxx>
Date: Sun, 3 Jan 2021 20:20:05 -0500
Subject: [PATCH] cache-tree: speed up consecutive path comparisons
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
The previous change reduced time spent in strlen() while comparing
consecutive paths in verify_cache(), but we can do better. The
conditional checks the existence of a directory separator at the correct
location, but only after doing a string comparison. Swap the order to be
logically equivalent but perform fewer string comparisons.
To test the effect on performance, I used a repository with over three
million paths in the index. I then ran the following command on repeat:
git -c index.threads=1 commit --amend --allow-empty --no-edit
Here are the measurements over 10 runs after a 5-run warmup:
Benchmark #1: v2.30.0
Time (mean ± σ): 854.5 ms ± 18.2 ms
Range (min … max): 825.0 ms … 892.8 ms
Benchmark #2: Previous change
Time (mean ± σ): 833.2 ms ± 10.3 ms
Range (min … max): 815.8 ms … 849.7 ms
Benchmark #3: This change
Time (mean ± σ): 815.5 ms ± 18.1 ms
Range (min … max): 795.4 ms … 849.5 ms
This change is 2% faster than the previous change and 5% faster than
v2.30.0.
Signed-off-by: Derrick Stolee <dstolee@xxxxxxxxxxxxx>
---
cache-tree.c | 4 ++--
1 file changed, 2 insertions(+), 2 deletions(-)
diff --git a/cache-tree.c b/cache-tree.c
index 57cacab195..6eaef21145 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -191,8 +191,8 @@ static int verify_cache(struct cache_entry **cache,
const char *next_name = next_ce->name;
int this_len = ce_namelen(this_ce);
if (this_len < ce_namelen(next_ce) &&
- strncmp(this_name, next_name, this_len) == 0 &&
- next_name[this_len] == '/') {
+ next_name[this_len] == '/' &&
+ strncmp(this_name, next_name, this_len) == 0) {
if (10 < ++funny) {
fprintf(stderr, "...\n");
break;
--
v2.30.0
