Re: [PATCH v1] read_index_from(): Skip verification of the cache entry order to speed index loading

From: Ben Peart <peartben@gmail.com>
Date: Oct 19, 2017, 15:12 UTC
Message-ID: <db8da340-f8f5-0114-392d-e415b5564993@gmail.com>
In-Reply-To: <xmqq4lqvk8ze.fsf@gitster.mtv.corp.google.com>

On 10/19/2017 1:22 AM, Junio C Hamano wrote:

Show 10 quoted lines

> Ben Peart <benpeart@microsoft.com> writes:
> 
>> There is code in post_read_index_from() to catch out of order entries
>> when reading an index file.  This order verification is ~13% of the cost
>> of every call to read_index_from().
> 
> I find this a bit over-generalized claim---wouldn't the overhead
> depend on various conditions, e.g. the size of the index and if
> split-index is in effect?
>

I tested it against 10K, 100K and 1,000K files and the absolute time varies with different sized indexes, but the percentage is relatively consistent (after doing multiple runs and averaging the results to reduce noise). I didn't measure it with split index so can't say how that would impact performance.

Show 11 quoted lines

> In general, I get very skeptical towards any change that makes the
> integrity of the data less certain based only on microbenchmarks,
> and prefer to see a solution that can absorb the overhead in some
> other way.
> 
> When we are using split-index, the current code is not validating
> the two input files from the disk. Because merge_base_index()
> depends on the base to be properly sorted before the overriding
> entries are added into it, if the input from disk is in a wrong
> order, we are screwed already, and the order check in post
> processing is pointless.

The original commit message doesn't say *why* this test was added so I have to make some educated guesses. Given no attempt is made to recover or continue and instead we just die when an out-of-order entry is detected, I'm assuming check_ce_order() is protecting against buggy code that incorrectly wrote out an invalid index (the sha check would have detected file corruption or torn writes).

If we are guarding against "git" writing out an invalid index, we can move this into an assert so that only git developers pay the cost of validating they haven't created a new bug. I think this is better than just adding a new test case as a new test case would not achieve the same coverage. This is my preferred solution.

If we are guarding against "some other application" writing out an invalid index, then everyone will have to pay the cost as we can't insert the test into "some other applications." Without user reports of it happening or any telemetry saying it has happened I really have no idea if it every actually happens in the wild anymore and whether the cost on every index load is still justified.

Show 13 quoted lines

> If we want to do this order validation, I
> think we should be doing it in do_read_index() where it does
> create_from_disk() and the set_index_entry(), instead of having it
> as a separate phase that scans a potentially large index array one
> more time.  And doing so will not penalize the case where we do not
> use split-index, either.
> 
> So, I think I like the direction of getting rid of the order
> validation in post_read_index_from(), not only during the normal
> operation but also in fsck.  I think it makes more sense to do so
> incrementally inside do_read_index() all the time and see how fast
> we can make it do so.
>

Unfortunately, all the cost is in the strcmp() - the other tests are negligible so moving it to be done incrementally inside do_read_index() won't reduce the cost, it just moves it and makes it harder to identify.

The only idea I could come up with for reducing the cost to our end users is to keep it separate and split the test across multiple threads with some minimum index size threshold as we have done elsewhere. This adds code and complexity that we'll have to maintain forever so is less preferred than making it an assert.