Re: [PATCH 2/2] fsck: use oidset for skiplist
From: René Scharfe <hidden>
Date: 2018-08-26 11:47:54
Am 14.08.2018 um 03:58 schrieb Jeff King:
Your suggestion can be implemented using khash (my patch below).quoted
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 msYeah. 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).
With your khash patch: Benchmark #1: ./git-cat-file --batch-all-objects --buffer --unordered --batch-check='%(objectname)' Time (mean ± σ): 159.1 ms ± 20.5 ms [User: 140.3 ms, System: 18.5 ms] Range (min … max): 140.0 ms … 214.0 ms So it seems worth it.
quoted hunk ↗ jump to hunk
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); }
The caller shouldn't look at the private parts of the implementation like this. tablesize is the allocation count, which becomes non-zero if at least one entry was added. tip_oids is only inserted into, never deleted from, so a count or size function could be used instead as a cleaner interface. (In a separate patch..)
quoted hunk ↗ jump to hunk
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; }
So initialization is deferred to the first insert, and the empty set can be represented in two ways -- map == NULL and map->size == 0. I wondered about the performance impact of all those NULL checks at insert and lookup and converted it to stack storage, with a dirty hand-rolled oidset_clear() implementation. It wasn't any faster.
quoted hunk ↗ jump to hunk
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"
This can go.
quoted hunk ↗ jump to hunk
+#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); +}
Look, it's oideq() from that other series in disguise! :)
+ +KHASH_INIT(oid, struct object_id, int, 0, oid_hash, oid_equal)
Note to self: The 0 is for kh_is_map, which means that no values are kept and the given value type (int) doesn't matter.
+
+
/**
* 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;
}This ignores initial_size, which is misleading. We should probably call kh_resize_oid() here and move the function to oidset.c. Or get rid of the second parameter..
quoted hunk ↗ jump to hunk
/**@@ -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); }
This is fine even if map == NULL, because kh_begin() can handle any parameter value, as it ignores them...
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;
}... but kh_end() dereferences map, so iterating a fresh oidset will segfault here.
static inline struct object_id *oidset_iter_first(struct oidset *set,