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

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

On Mon, Aug 27 2018, Ævar Arnfjörð Bjarmason wrote:

quoted

From: René Scharfe <redacted>

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).

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.

    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é