git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Jeff King <peff@peff.net>
Date
Aug 14, 2018, 01:58 UTC
Message-ID
<20180814015842.GA27055@sigill.intra.peff.net>
In-Reply-To
<6065f3e5-f831-802f-9adc-099de99405fc@web.de>
On Mon, Aug 13, 2018 at 07:15:23PM +0200, René Scharfe wrote:
Show 15 quoted lines
> 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).
Show 13 quoted lines
> 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,
Previous: René ScharfeNext: Jeff King
Message 7 of 31 in “fsck: use strbuf_getline() to read skiplist file”
  1. 1/2 fsck: use strbuf_getline() to read skiplist fileRené Scharfe, Aug 11, 2018
  2. 2/2 fsck: use oidset for skiplistRené Scharfe, Aug 11, 2018
  3. Jeff KingAug 11, 2018
  4. Jeff KingAug 11, 2018
  5. René ScharfeAug 11, 2018
  6. René ScharfeAug 13, 2018
  7. Jeff KingAug 14, 2018
  8. Jeff KingAug 14, 2018
  9. René ScharfeAug 26, 2018
  10. Jeff KingAug 27, 2018
  11. René ScharfeOct 1, 2018
  12. Jeff KingOct 1, 2018
  13. René ScharfeOct 2, 2018
  14. Jeff KingOct 2, 2018
  15. René ScharfeAug 13, 2018
  16. Jeff KingAug 14, 2018
  17. Ævar Arnfjörð BjarmasonAug 11, 2018
  18. René ScharfeAug 25, 2018
  19. Ramsay JonesAug 11, 2018
  20. René ScharfeAug 25, 2018
  21. Junio C HamanoAug 13, 2018
  22. René ScharfeAug 13, 2018
  23. Junio C HamanoAug 13, 2018
  24. René ScharfeAug 13, 2018
  25. Jeff KingAug 11, 2018
  26. René ScharfeAug 11, 2018
  27. 2/2 fsck: use oidset for skiplistRené Scharfe, Aug 25, 2018
  28. Ævar Arnfjörð BjarmasonAug 27, 2018
  29. René ScharfeAug 27, 2018
  30. 1/2 fsck: use strbuf_getline() to read skiplist fileRené Scharfe, Aug 25, 2018
  31. Jeff KingAug 27, 2018

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.