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

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

From
René Scharfe <l.s.r@web.de>
Date
Aug 26, 2018, 11:37 UTC
Message-ID
<030bac66-eeb4-7bc9-8f27-1e6b4124fd76@web.de>
In-Reply-To
<20180814015842.GA27055@sigill.intra.peff.net>
Am 14.08.2018 um 03:58 schrieb Jeff King:
Show 21 quoted lines
> 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.
Show 15 quoted 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);
>  	}

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

Show 39 quoted lines
> 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.

Show 35 quoted lines
>  
>  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.
Show 20 quoted lines
> +#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.

Show 19 quoted lines
> +
> +
>  /**
>   * 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..

Show 18 quoted lines
>  
>  /**
> @@ -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...

Show 12 quoted lines
>  
>  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,
>
Previous: Jeff KingNext: Jeff King
Message 9 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.