Re: [PATCH v3 6/7] fsck: use oidset for skiplist

From: René Scharfe <l.s.r@web.de>
Date: Aug 28, 2018, 14:29 UTC
Message-ID: <c356f239-f3f4-242b-fb75-95a4ccbe374b@web.de>
In-Reply-To: <87lg8refcr.fsf@evledraar.gmail.com>

Am 27.08.2018 um 22:15 schrieb Ævar Arnfjörð Bjarmason:

Show 26 quoted lines

> 
> On Mon, Aug 27 2018, Ævar Arnfjörð Bjarmason wrote:
> 
>> From: René Scharfe <l.s.r@web.de>
>>
>> Object IDs to skip are stored in a shared static oid_array.  Lookups do
>> a binary search on the sorted array.  The code checks if the object IDs
>> are already in the correct order while loading and skips sorting in that
>> case.  Lookups are done before reporting a (non-fatal) corruption and
>> before checking .gitmodules files.
>>
>> Simplify the code by using an oidset instead.  Memory usage is a bit
>> higher, but we don't need to worry about any sort order anymore.  Embed
>> the oidset into struct fsck_options to make its ownership clear (no
>> hidden sharing) and avoid unnecessary pointer indirection.
>>
>> Performance on repositories with a low number of reported issues and
>> .gitmodules files (i.e. the usual case) won't be affected much.  The
>> oidset should be a bit quicker with higher numbers of bad objects in
>> the skipList.
> 
> I didn't change this commit message at all, but FWIW this still has me
> somewhat confused. What is the interaction with .gitmodules being
> described here? You also mentioned it in
> https://public-inbox.org/git/113aa2d7-6f66-8d03-dda4-7337cda9b2df@web.de/
> (but I don't get that either)

The skipList is consulted before checking .gitmodules blobs, since fb16287719 (fsck: check skiplist for object in fsck_blob()).

> Does that just mean that when cloning with --recursive with
> transfer.fsckObjects=true we'll re-read the file for each "clone"
> invocation, both for the main project and everything listed in
> .gitmodules?

That is probably true, but I didn't mean that. I was only talking about when an object is looked up in the skiplist (oid_array/oidset).

Show 10 quoted lines

> If so, I think something like this commit message would be clearer:
> 
>     fsck: use oidset instead of oid_array for skipList
> 
>     Change the implementation of the skipList feature to use oidset
>     instead of oid_array to store SHA-1s for later lookup.
> 
>     This list is parsed once on startup by fsck, fetch-pack or
>     receive-pack depending on the *.skipList config in use, so for fetch
>     it's currently re-parsed for each submodule fetch.

OK; the patch doesn't change that, though. Mentioning it sound like a good idea if the load takes a significant amount of time -- I didn't measure this separately, so perhaps this needs to be explored further if people use big skipLists.

Show 8 quoted lines

>     Memory usage is a bit higher, but we don't need to keep track of the
>     sort order anymore. Embed the oidset into struct fsck_options to
>     make its ownership clear (no hidden sharing) and avoid unnecessary
>     pointer indirection.
> 
> Then let's just attach the test program you wrote in
> https://public-inbox.org/git/113aa2d7-6f66-8d03-dda4-7337cda9b2df@web.de/
> and note the results and let them speak for themselves.

I was surprised that such a big repo can be mocked up relatively quickly, but the numbers are a bit underwhelming -- there is not a lot of change. The script is not too expensive, so I don't mind adding it.

> I can do all that if that seems fine to you. I also notice that the test
> case only sets up a case where all the items on the skip list are bad
> commits in the repo, it would be interesting to test with a few needles
> in a large haystack (I can modify it to do that...).

I tried something like this first, and its results are even more boring. Since skipList lookups are done only for bad objects (and .gitmodules) you won't see any difference at all. Having only bad objects is the edge case, this test being designed to highlight the performance of the skipList implementation.

René