Re: [PATCH 2/2] fsck: use oidset for skiplist

From: René Scharfe <l.s.r@web.de>
Date: Aug 11, 2018, 20:59 UTC
Message-ID: <f69e08d7-b29d-a9b7-b6d4-5294c4379133@web.de>
In-Reply-To: <20180811172350.GA2689@sigill.intra.peff.net>

Am 11.08.2018 um 19:23 schrieb Jeff King:

> On Sat, Aug 11, 2018 at 01:02:48PM -0400, Jeff King wrote:
> 
>>    - we could probably improve the speed of oidset. Two things I notice
>>      about its implementation:

Show 13 quoted lines

> Before any optimizations, my best-of-five timing for:
> 
>    git cat-file --batch-all-objects --unordered --buffer \
>                 --batch-check='%(objectname)' >/dev/null
> 
> in git.git was:
> 
>    real	0m0.434s
>    user	0m0.414s
>    sys	0m0.020s
> 
> That's enumerating every object in the repo but not doing much more than
> de-duping the names and printing them.

> So a single hash lookup per
> object does not seem to be measurable. And thus teaching oidset_insert()
> to do a single hash lookup for check-and-insert is unlikely to help us.

> On top of that, I tried using a pool to store the set entries:

Show 7 quoted lines

> That drops my best-of-five to:
> 
>    real	0m0.300s
>    user	0m0.288s
>    sys	0m0.012s
> 
> which is over a 25% speedup. So that does seem worth pursuing.

Show 12 quoted lines

> For reference, the oid_array code path for cat-file is still:
> 
>    real	0m0.161s
>    user	0m0.157s
>    sys	0m0.004s
> 
> but that's not completely apples to apples. The oidset code is also
> iterating the packfiles in a different order and generating a revidx
> (which I know is about 25ms in this repo). So a better test would
> actually swap one data structure out for the other with no other changes
> (I just happened to have this test handy, and really wanted to know
> whether the mem_pool stuff would help).

If the current oidset implementation is so bad, why not replace it with one based on oid_array? ;-)

Intuitively I'd try a hashmap with no payload and open addressing via sha1hash(), which should reduce memory allocations quite a bit -- no need to store hash codes and next pointers, only an array of object IDs with a fill rate of 50% or so. Deletions are a bit awkward with that scheme, though; they could perhaps be implemented as insertions into a second hashmap.

Balancing might become a problem. Your cat-file example should be fine, but someone could decide to add only hashes with a certain prefix to their skiplist, and lookups would lopsided.

But first we'd need something like test-sha1-array for oidset and some kind of performance tests based on these helpers, right?

René