Am 14.08.2018 um 03:58 schrieb Jeff King:
> 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).
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.
> 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..)
> 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.
>
> 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.
> +#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..
>
> /**
> @@ -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,
>
