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

[Jeff King <peff@peff.net>]

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

Some notes on this, based on the cat-file patch that I linked to.

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.

Applying this patch:

diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index 45992c9be9..04b5cda191 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -443,9 +443,8 @@ static int batch_unordered_object(const struct object_id *oid, void *vdata)
 {
 	struct object_cb_data *data = vdata;
 
-	if (oidset_contains(data->seen, oid))
+	if (oidset_insert(data->seen, oid))
 		return 0;
-	oidset_insert(data->seen, oid);
 
 	return batch_object_cb(oid, data);
 }

to use the single-call set-and-replace doesn't seem to help (any
improvement is within the run-to-run noise). 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:

diff --git a/oidset.c b/oidset.c
index 454c54f933..504929f177 100644
--- a/oidset.c
+++ b/oidset.c
@@ -17,7 +17,10 @@ int oidset_insert(struct oidset *set, const struct object_id *oid)
 	else if (oidset_contains(set, oid))
 		return 1;
 
-	entry = xmalloc(sizeof(*entry));
+	if (!set->pool)
+		mem_pool_init(&set->pool, 0);
+
+	entry = mem_pool_alloc(set->pool, sizeof(*entry));
 	oidcpy(&entry->oid, oid);
 
 	oidmap_put(&set->map, entry);
@@ -29,12 +32,13 @@ int oidset_remove(struct oidset *set, const struct object_id *oid)
 	struct oidmap_entry *entry;
 
 	entry = oidmap_remove(&set->map, oid);
-	free(entry);
+	/* abandon pool memory for "entry" */
 
 	return (entry != NULL);
 }
 
 void oidset_clear(struct oidset *set)
 {
-	oidmap_free(&set->map, 1);
+	oidmap_free(&set->map, 0);
+	mem_pool_discard(set->pool, 0);
 }
diff --git a/oidset.h b/oidset.h
index 40ec5f87fe..6b8b802987 100644
--- a/oidset.h
+++ b/oidset.h
@@ -20,6 +20,7 @@
  */
 struct oidset {
 	struct oidmap map;
+	struct mem_pool *pool;
 };
 
 #define OIDSET_INIT { OIDMAP_INIT }

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.

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

-Peff