Re: [PATCH 8/8] cache-tree: avoid path comparison loop when silent

[Derrick Stolee <stolee@gmail.com>]

On 12/31/2020 7:34 AM, René Scharfe wrote:
> Am 30.12.20 um 20:26 schrieb Derrick Stolee via GitGitGadget:
>> From: Derrick Stolee <dstolee@microsoft.com>
>>
>> The verify_cache() method is used both for debugging issues with the
>> cached tree extension but also to avoid using the extension when there
>> are unmerged entries. It also checks for cache entries out of order with
>> respect to file-versus-directory sorting.
>>
>> In 996277c (Refactor cache_tree_update idiom from commit, 2011-12-06),
>> the silent option was added to remove the progress indicators from the
>> initial loop looking for unmerged entries. This was changed to be a flag
>> in e859c69 (cache-tree: update API to take abitrary flags, 2012-01-16).
>>
>> In both cases, the silent option is ignored for the second loop that
>> checks for file-versus-directory sorting. It must be that this loop is
>> intended only for debugging purposes and is not actually helpful in
>> practice.
> 
> So you're saying that the directory/file conflict check not honoring the
> WRITE_TREE_SILENT flag would have been noticed as a bug and therefore
> doesn't happen?
> 
> I'm not sure I can follow that logic.  I don't know how important that
> check is, how often it found a conflict and how likely such a find is
> overlooked or ignored, but disabling a check in silent mode that
> affects the return code instead of only suppressing its messages seems
> risky.
> 
> If we are sure that the check cannot trigger then we should remove it.
> If we are not so sure, but a conflict would be Git's fault (and not the
> user's) then we should always do the check and BUG out.  And otherwise
> we should keep it.

I think this method was originally designed for debugging issues with
the index, and it still serves that purpose when someone is working on
it. The check for out-of-order directory/file conflicts probably exists
only for that case.

However, this method also got repurposed to (silently) check for the
real scenario of unmerged entries. Perhaps it would be better to split
these into two cases and move the silent case into a new method,
"has_unmerged_entries()".

>> Since verify_cache() is called in cache_tree_update(), which is run
>> during 'git commit', we could speed up 'git commit' operations by not
>> iterating through this loop another time. Of course, noticing this loop
>> requires an incredibly large index.
>>
>> To get a measurable difference, I needed to run this test on the
>> Microsoft Office monorepo, which has over three million entries in its
>> index. I used 'git commit --amend --no-edit' as my command and saw the
>> performance go from 752ms to 739ms with this change.>> Could you please check the performance impact of the following code
> simplification?

Thank you for sending this. I started comparing the performance and
discovered that the performance difference I had measured before was
NOT consistent! I went back and debugged and found that 'git commit'
doesn't actually pass the silent flag, and my performance tests were
skewed by the filesystem cache. (A warmup of 3 runs was not sufficient
to get consistent numbers, it seemed. Perhaps the threaded index reads
are too inconsistent.)

> diff --git a/cache-tree.c b/cache-tree.c
> index a537a806c1..1105cfe6b7 100644
> --- a/cache-tree.c
> +++ b/cache-tree.c
> @@ -187,10 +187,8 @@ static int verify_cache(struct cache_entry **cache,
>  		 */
>  		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) &&
> -		    strncmp(this_name, next_name, this_len) == 0 &&
> -		    next_name[this_len] == '/') {
> +		const char *p;
> +		if (skip_prefix(next_name, this_name, &p) && *p == '/') {
>  			if (10 < ++funny) {
>  				fprintf(stderr, "...\n");
>  				break;
 
This performs consistently worse than both cases (see performance test
later in this message). I think the strlen is saving us some time here.

In fact, I think the compiler is doing some magic to save our strlen
results, as I get identical performance results when doing this:

diff --git a/cache-tree.c b/cache-tree.c
index c6c084463b..a076e7cec5 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -156,6 +156,8 @@ static int verify_cache(struct cache_entry **cache,
 {
        int i, funny;
        int silent = flags & WRITE_TREE_SILENT;
+       const char *this_name;
+       size_t this_len;
 
        /* Verify that the tree is merged */
        funny = 0;
@@ -182,18 +184,21 @@ static int verify_cache(struct cache_entry **cache,
         * and they should not exist unless a bug was introduced along
         * the way.
         */
-       if (silent)
-               return 0;
        funny = 0;
-       for (i = 0; i < entries - 1; i++) {
+
+       if (!entries)
+               return 0;
+       this_name = cache[0]->name;
+       this_len = strlen(this_name);
+
+       for (i = 1; i < entries; i++) {
                /* path/file always comes after path because of the way
                 * 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 char *next_name = cache[i]->name;
+               size_t next_len = strlen(next_name);
+               if (this_len < next_len &&
                    strncmp(this_name, next_name, this_len) == 0 &&
                    next_name[this_len] == '/') {
                        if (10 < ++funny) {
@@ -203,6 +208,8 @@ static int verify_cache(struct cache_entry **cache,
                        fprintf(stderr, "You have both %s and %s\n",
                                this_name, next_name);
                }
+               this_name = next_name;
+               this_len = next_len;
        }
        if (funny)
                return -1;

To get more consistent results, I modified my benchmark to be the following:

	git -c index.threads=1 commit --amend --allow-empty --no-edit

I also adjusted the test suite to use 5 warmup rounds. Here are the numbers:

  Benchmark #1: v2.30.0
    Time (mean ± σ):     856.6 ms ±  18.0 ms    [User: 807.9 ms, System: 198.4 ms]
    Range (min … max):   832.1 ms … 882.2 ms    10 runs
 
So, 756.5ms average for v2.30.0.

  Benchmark #2: skipping the second loop
    Time (mean ± σ):     805.5 ms ±  15.8 ms    [User: 758.0 ms, System: 197.1 ms]
    Range (min … max):   783.4 ms … 835.2 ms    10 runs
 
Here, I just deleted the second loop to see what is the potential minimum.

  Benchmark #3: storing this_name during second loop
    Time (mean ± σ):     855.6 ms ±  14.1 ms    [User: 804.5 ms, System: 194.6 ms]
    Range (min … max):   835.9 ms … 875.2 ms    10 runs

The diff I provided earlier reduces the number of strlen() computations
by storing them across the loop iterations. There is no effect, which
makes me think the compiler is being smart.

  Benchmark #4: check for '/' before strncmp()
    Time (mean ± σ):     834.1 ms ±  18.0 ms    [User: 786.6 ms, System: 196.7 ms]
    Range (min … max):   803.5 ms … 860.4 ms    10 runs 

HOWEVER, if we swap the order of the conditionals to be

		if (this_len < next_len &&
		    strncmp(this_name, next_name, this_len) == 0 &&
		    next_name[this_len] == '/') {

then we _do_ get a measurable, consistent speedup.

  Benchmark #5: using skip_prefix
    Time (mean ± σ):     877.3 ms ±  16.1 ms    [User: 839.1 ms, System: 187.5 ms]
    Range (min … max):   847.7 ms … 900.4 ms    10 runs

This final benchmark stores the results for your skip_prefix diff.

Including the full ranges of the 10 runs hopefully assists in demonstrating
that the performance changes are (mostly) consistent.

To wrap up, I'm going to eject this patch from my v2 since more investigation
must be done to see if this second loop _can_ be dropped. At minimum, it isn't
properly silent when requested and there _is_ a performance boost possible,
even if we keep the check.

Thanks,
-Stolee