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

[Jeff King <peff@peff.net>]

On Sat, Aug 11, 2018 at 05:47:56PM +0200, René Scharfe wrote:

> 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.
> 
> Simplify the code by using an oidset instead.  Memory usage is a bit
> higher, but lookups are done in constant time and there is no need to
> worry about any sort order.
> 
> Embed the oidset into struct fsck_options to make its ownership clear
> (no hidden sharing) and avoid unnecessary pointer indirection.

I actually had a case[1] yesterday where it seems like oidset is a fair
bit slower than oid_array for a large set.

But:

  - loading the skiplist into memory has pretty lousy performance
    anyway. If we really care about performance of large lists, we
    should define a sorted on-disk format that can be mmap'd and
    searched directly.  Or if people are willing to tolerate false
    positives, even a bloom filter.

    I've never really used a big skiplist myself, so I haven't done any
    work towards those things.

  - we could probably improve the speed of oidset. Two things I notice
    about its implementation:

      - it has to malloc for each entry, which I suspect is the main
	bottleneck. We could probably pool-allocate blocks, and when
	entries get removed just leave the allocations in place until we
	clear(). Most callers tend to build up a set and then query it a
	lot, or possibly remove items from the set until it's empty. But
	my guess is that few or none want a long-lived set that they add
	and remove from randomly.

      - insertion lets you do check-and-insert as a single operation
	(something I failed to notice in [1]). But it's not implemented
	as efficiently as it could be, since the "contains" and "put"
	operations do separate lookups. This doesn't matter for a set
	that's queried a lot more, but for something like de-duping
	(like I was doing in [1]) most operations are check-and-insert.

Most of that is just food for thought, but it possibly argues that we
should not care about performance characteristics for swapping out
oid_array and oidset here (i.e., that your patch is fine, and the
simplicity benefit is the most important thing).

[1] https://public-inbox.org/git/20180810232457.GG19875@sigill.intra.peff.net/
    but note that it's buried pretty deep.

> ---
>  fsck.c | 23 ++---------------------
>  fsck.h |  8 +++++---
>  2 files changed, 7 insertions(+), 24 deletions(-)

Again, I didn't see anything wrong with the patch itself.

-Peff