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

[Jeff King <peff@peff.net>]

On Mon, Aug 13, 2018 at 07:15:23PM +0200, René Scharfe wrote:

> Am 11.08.2018 um 22:59 schrieb René Scharfe:
> > 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.
> 
> Here's roughly what I had in mind, only with a free/occupied bitmap (or
> a one-bit payload, if you will).  I tried a variant that encoded empty
> slots as null_oid first, which has lower memory usage, but isn't any
> faster than the current code.

Hmph, I thought I had sent my version out last night, but it looks like
I didn't. I got similarly mediocre results.

Your suggestion can be implemented using khash (my patch below).

> Before:
> Benchmark #1: ./git-cat-file --batch-all-objects --buffer --unordered --batch-check='%(objectname)'
> 
>   Time (mean ± σ):     269.5 ms ±  26.7 ms    [User: 247.7 ms, System: 21.4 ms]
> 
>   Range (min … max):   240.3 ms … 339.3 ms
> 
> After:
> Benchmark #1: ./git-cat-file --batch-all-objects --buffer --unordered --batch-check='%(objectname)'
> 
>   Time (mean ± σ):     224.2 ms ±  18.2 ms    [User: 201.7 ms, System: 22.1 ms]
> 
>   Range (min … max):   205.0 ms … 259.0 ms

Yeah. My best-of-five dropped from 300ms to 247ms. That 300 was using
the memory pool, though khash's deletion strategy isn't all that
different (the wasted memory hangs around until the next hash resize,
but if you're evenly dropping and adding, you likely won't need to
resize).

Applying your patch, I get 337ms, worse than the hashmap with a memory
pool. I'm not sure why.

>  builtin/cat-file.c | 93 +++++++++++++++++++++++++++++++++++++++++++---
>  1 file changed, 88 insertions(+), 5 deletions(-)

By the way, your patch seemed damaged (wouldn't apply, and "am -3"
complained of hand-editing). It looks like maybe there's an extra space
inserted in the context lines?

Anyway, here's the khash patch for reference.

diff --git a/fetch-pack.c b/fetch-pack.c
index 5714bcbddd..5a86b10a5e 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -534,7 +534,7 @@ static int tip_oids_contain(struct oidset *tip_oids,
 	 * add to "newlist" between calls, the additions will always be for
 	 * oids that are already in the set.
 	 */
-	if (!tip_oids->map.map.tablesize) {
+	if (!tip_oids->map) {
 		add_refs_to_oidset(tip_oids, unmatched);
 		add_refs_to_oidset(tip_oids, newlist);
 	}
diff --git a/oidset.c b/oidset.c
index 454c54f933..2964b43b2d 100644
--- a/oidset.c
+++ b/oidset.c
@@ -3,38 +3,44 @@
 
 int oidset_contains(const struct oidset *set, const struct object_id *oid)
 {
-	if (!set->map.map.tablesize)
+	khiter_t pos;
+
+	if (!set->map)
 		return 0;
-	return !!oidmap_get(&set->map, oid);
+
+	pos = kh_get_oid(set->map, *oid);
+	return pos < kh_end(set->map);
 }
 
 int oidset_insert(struct oidset *set, const struct object_id *oid)
 {
-	struct oidmap_entry *entry;
+	int hash_ret;
 
-	if (!set->map.map.tablesize)
-		oidmap_init(&set->map, 0);
-	else if (oidset_contains(set, oid))
-		return 1;
+	if (!set->map)
+		set->map = kh_init_oid();
 
-	entry = xmalloc(sizeof(*entry));
-	oidcpy(&entry->oid, oid);
-
-	oidmap_put(&set->map, entry);
-	return 0;
+	kh_put_oid(set->map, *oid, &hash_ret);
+	return !hash_ret;
 }
 
 int oidset_remove(struct oidset *set, const struct object_id *oid)
 {
-	struct oidmap_entry *entry;
+	khiter_t pos;
 
-	entry = oidmap_remove(&set->map, oid);
-	free(entry);
+	if (!set->map)
+		return 0;
+
+	pos = kh_get_oid(set->map, *oid);
+	if (pos < kh_end(set->map)) {
+		kh_del_oid(set->map, pos);
+		return 1;
+	}
 
-	return (entry != NULL);
+	return 0;
 }
 
 void oidset_clear(struct oidset *set)
 {
-	oidmap_free(&set->map, 1);
+	kh_destroy_oid(set->map);
+	set->map = NULL;
 }
diff --git a/oidset.h b/oidset.h
index 40ec5f87fe..4c4c5a42fe 100644
--- a/oidset.h
+++ b/oidset.h
@@ -2,6 +2,7 @@
 #define OIDSET_H
 
 #include "oidmap.h"
+#include "khash.h"
 
 /**
  * This API is similar to sha1-array, in that it maintains a set of object ids
@@ -15,19 +16,34 @@
  *      table overhead.
  */
 
+static inline unsigned int oid_hash(const struct object_id oid)
+{
+	unsigned int hash;
+	memcpy(&hash, oid.hash, sizeof(hash));
+	return hash;
+}
+
+static inline int oid_equal(const struct object_id a,
+			    const struct object_id b)
+{
+	return !oidcmp(&a, &b);
+}
+
+KHASH_INIT(oid, struct object_id, int, 0, oid_hash, oid_equal)
+
+
 /**
  * A single oidset; should be zero-initialized (or use OIDSET_INIT).
  */
 struct oidset {
-	struct oidmap map;
+	kh_oid_t *map;
 };
 
-#define OIDSET_INIT { OIDMAP_INIT }
-
+#define OIDSET_INIT { NULL }
 
 static inline void oidset_init(struct oidset *set, size_t initial_size)
 {
-	oidmap_init(&set->map, initial_size);
+	set->map = NULL;
 }
 
 /**
@@ -58,19 +74,25 @@ int oidset_remove(struct oidset *set, const struct object_id *oid);
 void oidset_clear(struct oidset *set);
 
 struct oidset_iter {
-	struct oidmap_iter m_iter;
+	kh_oid_t *map;
+	khiter_t iter;
 };
 
 static inline void oidset_iter_init(struct oidset *set,
 				    struct oidset_iter *iter)
 {
-	oidmap_iter_init(&set->map, &iter->m_iter);
+	iter->map = set->map;
+	iter->iter = kh_begin(iter->map);
 }
 
 static inline struct object_id *oidset_iter_next(struct oidset_iter *iter)
 {
-	struct oidmap_entry *e = oidmap_iter_next(&iter->m_iter);
-	return e ? &e->oid : NULL;
+	for (; iter->iter != kh_end(iter->map); iter->iter++) {
+		if (!kh_exist(iter->map, iter->iter))
+			continue;
+		return &kh_key(iter->map, iter->iter);
+	}
+	return NULL;
 }
 
 static inline struct object_id *oidset_iter_first(struct oidset *set,