Re: [PATCH] cache-tree: use ce_namelen() instead of strlen()
- From
Derrick Stolee <stolee@gmail.com>
- Date
- Jan 4, 2021, 01:26 UTC
- Message-ID
- <247e3c34-6190-c9e4-2a82-0f4b71249bdb@gmail.com>
- In-Reply-To
- <a8b5bb13-5c88-d744-b47e-7204e12ad05d@web.de>
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
Show 28 quoted lines
> Signed-off-by: René Scharfe <l.s.r@web.de>
> ---
> 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@microsoft.com> 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 msThis change is 2% faster than the previous change and 5% faster than v2.30.0.
Signed-off-by: Derrick Stolee <dstolee@microsoft.com> --- 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