Re: [PATCH v3 10/21] pack-bitmap: add support for bitmap indexes

Jeff King [off-list ref] writes:

 khash.h       | 338 ++++++++++++++++++++

[...]

[...]

+static inline khint_t __kh_oid_hash(const unsigned char *oid)
+{
+	khint_t hash;
+	memcpy(&hash, oid, sizeof(hash));
+	return hash;
+}
+
+#define __kh_oid_cmp(a, b) (hashcmp(a, b) == 0)
+
+KHASH_INIT(sha1, const unsigned char *, void *, 1, __kh_oid_hash, __kh_oid_cmp)
+typedef kh_sha1_t khash_sha1;
+
+KHASH_INIT(sha1_pos, const unsigned char *, int, 1, __kh_oid_hash, __kh_oid_cmp)
+typedef kh_sha1_pos_t khash_sha1_pos;
+
+#endif /* __AC_KHASH_H */

AFAICS, the part after the [...] are additions specific to git.  Is that
right?

Can we store them in a separate khash-sha1.h or some such, to make it
clearer what's what?  As things stand, one has to look for an identifier
that is built from macros at the far end of a file that looks like it
was imported verbatim from klib(?).  I don't know about you, but that
just took me far too long to get right.

I think I'll also lend you a hand writing Documentation/technical/api-khash.txt
(expect it tomorrow) so that we also have documentation in the git
style, where gitters can be expected to find it on their own.

All that could then nicely fit into a commit that actually says where
you conjured khash.h from and such.  This information seems
conspicuously absent from this commit's message :-)

Furthermore, would it be a problem to name the second hash sha1_int
instead?  I have another use for such a hash, and I can't imagine I'm
the only one.  (That's not critical however, I can do the required
editing in that other series.)

-- 
Thomas Rast
tr@thomasrast.ch

For squashing into a commit that adds khash.h.

Signed-off-by: Thomas Rast <redacted>
---

I think I'll also lend you a hand writing Documentation/technical/api-khash.txt
(expect it tomorrow) so that we also have documentation in the git
style, where gitters can be expected to find it on their own.

Here goes.

Furthermore, would it be a problem to name the second hash sha1_int
instead?  I have another use for such a hash, and I can't imagine I'm
the only one.  (That's not critical however, I can do the required
editing in that other series.)

Actually, let's not do that.  Since everything is 'static inline'
anyway, there's no cost to simply instantiating more hashes as needed.


 Documentation/technical/api-khash.txt | 109 ++++++++++++++++++++++++++++++++++
 1 file changed, 109 insertions(+)
 create mode 100644 Documentation/technical/api-khash.txt

diff --git a/Documentation/technical/api-khash.txt b/Documentation/technical/api-khash.txt
new file mode 100644
index 0000000..e7ca883
--- /dev/null
+++ b/Documentation/technical/api-khash.txt

@@ -0,0 +1,109 @@
+khash
+=====
+
+The khash API is a collection of macros that instantiate hash table
+routines for arbitrary key/value types.
+
+It lives in 'khash.h', which we imported from
+  https://github.com/attractivechaos/klib/blob/master/khash.h
+and then gitified somewhat.
+
+Usage
+-----
+
+------------
+#import "khash.h"
+KHASH_INIT(NAME, key_t, value_t, is_map, key_hash_fn, key_equal_fn)
+------------
+
+The arguments are as follows:
+
+`NAME`::
+	Used to give your hash and its API a unique name.  Spelled
+	`NAME` here to set it apart from the rest of the names, but
+	generally should be a lowercase C identifier.
+
+`key_t`::
+	Type of the keys for your hashes.  Generally should be
+	`const`.
+
+`value_t`::
+	Type of the values of your hashes.
+
+`is_map`::
+	Whether the hash holds values.  Set to 0 to create a hash for
+	use as a set.
+
+`khint_t key_hash_fn(key_t)`::
+	Hash function.
+
+`int key_equal_fn(key_t a, key_t b)`::
+	Comparison function.  Return 1 if the two keys are the same, 0
+	otherwise.
+
+These two functions may also be macros.
+
+
+API
+---
+
+The above instantiation defines a single type:
+
+`kh_NAME_t`::
+	A struct that holds your hash.  You should only ever use
+	pointers to it.
+
+After the above instantiation, the following functions and
+function-like macros are defined:
+
+`kh_NAME_t *kh_init_NAME(void)`::
+	Allocate and initialize a new hash table.
+
+`void kh_destroy_NAME(kh_NAME_t *)`::
+	Free the hash table.
+
+`void kh_clear_NAME(kh_NAME_t *)`::
+	Clear (but do not free) the hash table.
+
+`khint_t kh_get_NAME(const kh_NAME_t *hash, key_t key)`::
+	Find the given key in the hash table.  The returned khint_t
+	should be treated as an opaque iterator token that indexes
+	into the hash.  Use `kh_value` to get the value from the
+	token.  If the key does not exist, returns kh_end(hash).
+
+`khint_t kh_put_NAME(const kh_NAME_t *hash, key_t key, int *ret)`::
+	Put the given key in the hash table.  The returned khint_t
+	should be treated as an opaque iterator token that indexes
+	into the hash.  Use `kh_value(hash, token) = value` to assign
+	a value after putting the key.
++
+'ret' tells you whether the key already existed: it is -1 if the
+operation failed; 0 if the key was already present; 1 if the bucket is
+empty; 2 if the bucket has been deleted.
+
+`kh_key(kh_NAME_t *, khint_t)`::
+	The key slot for the given iterator token.  This can be used
+	as an lvalue, but you must not change the key!
+
+`kh_value(kh_NAME_t *, khint_t)`::
+`kh_val(kh_NAME_t *, khint_t)`::
+	The value slot for the given iterator token.  This can be used
+	as an lvalue.
+
+`int kh_exist(const kh_NAME_t *, key_t)`::
+	Tests if the given bucket contains data.
+
+`khint_t kh_begin(const kh_NAME_t *)`::
+	The smallest iterator token.
+
+`khint_t kh_end(const kh_NAME_t *)`::
+	The beyond-the-hash iterator token; it is one larger than the
+	largest token that points to a hash member.
+
+`khint_t kh_size(const kh_NAME_t *)`::
+	The number of elements in the hash.
+
+`kh_foreach(const kh_NAME_t *, keyvar, valuevar, { ... loop body ... })`::
+	Iterate over every key-value pair in the hash.  This is a
+	macro, and keyvar and valuevar must be pre-declared of type
+	key_t and value_t, respectively.

-- 
1.8.5.rc3.397.g2a3acd5

Am 24.11.2013 22:36, schrieb Thomas Rast:

Jeff King [off-list ref] writes:

[...]

I think I'll also lend you a hand writing Documentation/technical/api-khash.txt
(expect it tomorrow) so that we also have documentation in the git
style, where gitters can be expected to find it on their own.

Khash is OK for sha1 keys, but I don't think it should be advertised as a second general purpose hash table implementation. Its far too easy to shoot yourself in the foot by using 'straightforward' hash- and comparison functions. Khash doesn't store the hash codes of the keys, so you have to take care of that yourself or live with the performance penalties (see [1]).

[1] http://article.gmane.org/gmane.comp.version-control.git/237876

On Mon, Nov 25, 2013 at 04:04:48PM +0100, Thomas Rast wrote:

quoted

I think I'll also lend you a hand writing Documentation/technical/api-khash.txt
(expect it tomorrow) so that we also have documentation in the git
style, where gitters can be expected to find it on their own.

Here goes.

Thanks. Some comments below.

quoted

Furthermore, would it be a problem to name the second hash sha1_int
instead?  I have another use for such a hash, and I can't imagine I'm
the only one.  (That's not critical however, I can do the required
editing in that other series.)

Actually, let's not do that.  Since everything is 'static inline'
anyway, there's no cost to simply instantiating more hashes as needed.

Yeah. If we cared about code duplication, we'd have to split it into
declaration and definition macros, and then collect the definitions in
one .c file (khash does support this, but we don't use it). I don't
think we are using enough repeated ones to make it matter, and most of
the functions benefit from inlining anyway.

+------------
+#import "khash.h"
+KHASH_INIT(NAME, key_t, value_t, is_map, key_hash_fn, key_equal_fn)
+------------

#import?

+The arguments are as follows:
[...]
+`khint_t key_hash_fn(key_t)`::
+	Hash function.

It is true that this is a khint_t, but I do not think knowing that helps
the caller. They need to design a hash function, so knowing the size and
type of the hint helps. Maybe:

  Return a hash value for a key. The khint_t is a 32-bit unsigned value.
  Git provides __kh_oid_hash, which converts a sha1 into a hash value.

+`int key_equal_fn(key_t a, key_t b)`::
+	Comparison function.  Return 1 if the two keys are the same, 0
+	otherwise.

Here we provide __kh_oid_cmp, and we should mention it. Based on recent
discussions, this should probably be __kh_oid_equal, since it is not a
"cmp" function in the ordering sense.

+`khint_t kh_get_NAME(const kh_NAME_t *hash, key_t key)`::
+	Find the given key in the hash table.  The returned khint_t
+	should be treated as an opaque iterator token that indexes
+	into the hash.  Use `kh_value` to get the value from the
+	token.  If the key does not exist, returns kh_end(hash).

I do not know of the khash author's intention, but in the bitmap code we
prefer khiter_t to represent an iterator. It is the same as a khint_t,
but I think that is an implementation detail (and the khash functions
should probably be returning a khiter_t).

[...]

The rest of it looks correct to me.

-Peff

On Wed, Nov 27, 2013 at 10:08:56AM +0100, Karsten Blees wrote:

Khash is OK for sha1 keys, but I don't think it should be advertised
as a second general purpose hash table implementation. Its far too
easy to shoot yourself in the foot by using 'straightforward' hash-
and comparison functions. Khash doesn't store the hash codes of the
keys, so you have to take care of that yourself or live with the
performance penalties (see [1]).

[1] http://article.gmane.org/gmane.comp.version-control.git/237876

Yes. I wonder if we should improve it in that respect. I haven't looked
carefully at the hash code you posted elsewhere, but I feel like many
uses will want a macro implementation to let them store arbitrary types
smaller or larger than a pointer.

-Peff

Am 28.11.2013 11:38, schrieb Jeff King:

On Wed, Nov 27, 2013 at 10:08:56AM +0100, Karsten Blees wrote:

quoted

Khash is OK for sha1 keys, but I don't think it should be advertised
as a second general purpose hash table implementation. Its far too
easy to shoot yourself in the foot by using 'straightforward' hash-
and comparison functions. Khash doesn't store the hash codes of the
keys, so you have to take care of that yourself or live with the
performance penalties (see [1]).

[1] http://article.gmane.org/gmane.comp.version-control.git/237876

Yes. I wonder if we should improve it in that respect. I haven't looked
carefully at the hash code you posted elsewhere, but I feel like many
uses will want a macro implementation to let them store arbitrary types
smaller or larger than a pointer.

-Peff

IMO, trying to improve khash isn't worth the trouble.

With smaller-than-pointer types, khash _may_ actually save a few bytes compared to hash.[ch] or hashmap.[ch]. E.g. a set of 'int's would be a perfect use case for khash. However, you're using bitmaps for that, and khash's predefined macros for int sets and maps have been removed from the git version.

Using khash with pointers and larger-than-pointer types is just a waste of memory and performance, though. Hash tables are sparsely filled by design, and using large types means lots of large empty buckets. E.g. kh_resize requires almost four times the size or your data, and copies everything at least three times.

Additionally, there are the obvious problems with khash's macro design (hard to read, impossible to debug, and each named instance increases executable size by ~4k).


Below is a patch that converts pack-bitmap.c to hashmap. Its not even longer than the khash version, and the hashmap API forces you to think about no-brainer improvements such as specifying an expected size or skipping duplicates checks where they aren't needed. I could do the same for pack-bitmap-write.c if you like.

Karsten

-----------8<----------
Subject: [PATCH] pack-bitmap.c: convert to new hashmap implementation

Preallocates bitmap_index.bitmaps with the expected size to prevent
rehashing.

Combines the five arrays of ext_index ('objects', 'hashes' and khash's
'keys', 'flags' and 'vals') into a single structure for better locality.

Removes two unnecessary duplicates checks:
 - we don't expect a pack index file to contain duplicate sha1's
 - ext_index_add_object is only called after bitmap_position returned -1,
   so it is impossible that the entry is already there

Signed-off-by: Karsten Blees <redacted>
---
 pack-bitmap.c | 166 ++++++++++++++++++++++++++++------------------------------
 1 file changed, 81 insertions(+), 85 deletions(-)

diff --git a/pack-bitmap.c b/pack-bitmap.c
index 078f7c6..115caed 100644
--- a/pack-bitmap.c
+++ b/pack-bitmap.c

@@ -15,6 +15,7 @@
  * commit.
  */
 struct stored_bitmap {
+	struct hashmap_entry ent;
 	unsigned char sha1[20];
 	struct ewah_bitmap *root;
 	struct stored_bitmap *xor;

@@ -22,6 +23,16 @@ struct stored_bitmap {
 };
 
 /*
+ * An entry in the extended index.
+ */
+struct ext_entry {
+	struct hashmap_entry ent;
+	uint32_t name_hash;
+	struct object *object;
+	unsigned int nr;
+};
+
+/*
  * The currently active bitmap index. By design, repositories only have
  * a single bitmap index available (the index for the biggest packfile in
  * the repository), since bitmap indexes need full closure.

@@ -61,7 +72,7 @@ static struct bitmap_index {
 	struct ewah_bitmap *tags;
 
 	/* Map from SHA1 -> `stored_bitmap` for all the bitmapped comits */
-	khash_sha1 *bitmaps;
+	struct hashmap bitmaps;
 
 	/* Number of bitmapped commits */
 	uint32_t entry_count;

@@ -76,12 +87,7 @@ static struct bitmap_index {
 	 * packed in `pack`, these objects are added to this "fake index" and
 	 * are assumed to appear at the end of the packfile for all operations
 	 */
-	struct eindex {
-		struct object **objects;
-		uint32_t *hashes;
-		uint32_t count, alloc;
-		khash_sha1_pos *positions;
-	} ext_index;
+	struct hashmap ext_index;
 
 	/* Bitmap result of the last performed walk */
 	struct bitmap *result;

@@ -93,6 +99,21 @@ static struct bitmap_index {
 
 } bitmap_git;
 
+static int stored_bitmap_cmp(const struct stored_bitmap *entry,
+		const struct stored_bitmap *entry_or_key,
+		const unsigned char *sha1)
+{
+	return hashcmp(entry->sha1, sha1 ? sha1 : entry_or_key->sha1);
+}
+
+static int ext_entry_cmp(const struct ext_entry *entry,
+		const struct ext_entry *entry_or_key,
+		const unsigned char *sha1)
+{
+	return hashcmp(entry->object->sha1,
+		       sha1 ? sha1 : entry_or_key->object->sha1);
+}
+
 static struct ewah_bitmap *lookup_stored_bitmap(struct stored_bitmap *st)
 {
 	struct ewah_bitmap *parent;

@@ -112,6 +133,16 @@ static struct ewah_bitmap *lookup_stored_bitmap(struct stored_bitmap *st)
 	return composed;
 }
 
+static struct ewah_bitmap *lookup_stored_bitmap_sha1(const unsigned char *sha1)
+{
+	struct stored_bitmap key, *st;
+	hashmap_entry_init(&key, __kh_oid_hash(sha1));
+	st = hashmap_get(&bitmap_git.bitmaps, &key, sha1);
+	if (st)
+		return lookup_stored_bitmap(st);
+	return NULL;
+}
+
 /*
  * Read a bitmap from the current read position on the mmaped
  * index, and increase the read position accordingly

@@ -174,26 +205,15 @@ static struct stored_bitmap *store_bitmap(struct bitmap_index *index,
 					  int flags)
 {
 	struct stored_bitmap *stored;
-	khiter_t hash_pos;
-	int ret;
 
 	stored = xmalloc(sizeof(struct stored_bitmap));
+	hashmap_entry_init(stored, __kh_oid_hash(sha1));
 	stored->root = root;
 	stored->xor = xor_with;
 	stored->flags = flags;
 	hashcpy(stored->sha1, sha1);
 
-	hash_pos = kh_put_sha1(index->bitmaps, stored->sha1, &ret);
-
-	/* a 0 return code means the insertion succeeded with no changes,
-	 * because the SHA1 already existed on the map. this is bad, there
-	 * shouldn't be duplicated commits in the index */
-	if (ret == 0) {
-		error("Duplicate entry in bitmap index: %s", sha1_to_hex(sha1));
-		return NULL;
-	}
-
-	kh_value(index->bitmaps, hash_pos) = stored;
+	hashmap_add(&index->bitmaps, stored);
 	return stored;
 }
 

@@ -291,8 +311,9 @@ static int load_pack_bitmap(void)
 {
 	assert(bitmap_git.map && !bitmap_git.loaded);
 
-	bitmap_git.bitmaps = kh_init_sha1();
-	bitmap_git.ext_index.positions = kh_init_sha1_pos();
+	hashmap_init(&bitmap_git.bitmaps, (hashmap_cmp_fn) stored_bitmap_cmp,
+			bitmap_git.entry_count);
+	hashmap_init(&bitmap_git.ext_index, (hashmap_cmp_fn) ext_entry_cmp, 0);
 	bitmap_git.reverse_index = revindex_for_pack(bitmap_git.pack);
 
 	if (!(bitmap_git.commits = read_bitmap_1(&bitmap_git)) ||

@@ -362,13 +383,12 @@ struct include_data {
 
 static inline int bitmap_position_extended(const unsigned char *sha1)
 {
-	khash_sha1_pos *positions = bitmap_git.ext_index.positions;
-	khiter_t pos = kh_get_sha1_pos(positions, sha1);
+	struct ext_entry key, *e;
+	hashmap_entry_init(&key, __kh_oid_hash(sha1));
+	e = hashmap_get(&bitmap_git.bitmaps, &key, sha1);
 
-	if (pos < kh_end(positions)) {
-		int bitmap_pos = kh_value(positions, pos);
-		return bitmap_pos + bitmap_git.pack->num_objects;
-	}
+	if (e)
+		return e->nr + bitmap_git.pack->num_objects;
 
 	return -1;
 }

@@ -390,32 +410,13 @@ static int bitmap_position(const unsigned char *sha1)
 
 static int ext_index_add_object(struct object *object, const char *name)
 {
-	struct eindex *eindex = &bitmap_git.ext_index;
-
-	khiter_t hash_pos;
-	int hash_ret;
-	int bitmap_pos;
-
-	hash_pos = kh_put_sha1_pos(eindex->positions, object->sha1, &hash_ret);
-	if (hash_ret > 0) {
-		if (eindex->count >= eindex->alloc) {
-			eindex->alloc = (eindex->alloc + 16) * 3 / 2;
-			eindex->objects = xrealloc(eindex->objects,
-				eindex->alloc * sizeof(struct object *));
-			eindex->hashes = xrealloc(eindex->hashes,
-				eindex->alloc * sizeof(uint32_t));
-		}
-
-		bitmap_pos = eindex->count;
-		eindex->objects[eindex->count] = object;
-		eindex->hashes[eindex->count] = pack_name_hash(name);
-		kh_value(eindex->positions, hash_pos) = bitmap_pos;
-		eindex->count++;
-	} else {
-		bitmap_pos = kh_value(eindex->positions, hash_pos);
-	}
-
-	return bitmap_pos + bitmap_git.pack->num_objects;
+	struct ext_entry *e = xmalloc(sizeof(struct ext_entry));
+	hashmap_entry_init(e, __kh_oid_hash(object->sha1));
+	e->object = object;
+	e->name_hash = pack_name_hash(name);
+	e->nr = bitmap_git.ext_index.size;
+	hashmap_add(&bitmap_git.ext_index, e);
+	return e->nr + bitmap_git.pack->num_objects;
 }
 
 static void show_object(struct object *object, const struct name_path *path,

@@ -443,7 +444,7 @@ static int add_to_include_set(struct include_data *data,
 			      const unsigned char *sha1,
 			      int bitmap_pos)
 {
-	khiter_t hash_pos;
+	struct ewah_bitmap *bm;
 
 	if (data->seen && bitmap_get(data->seen, bitmap_pos))
 		return 0;

@@ -451,10 +452,9 @@ static int add_to_include_set(struct include_data *data,
 	if (bitmap_get(data->base, bitmap_pos))
 		return 0;
 
-	hash_pos = kh_get_sha1(bitmap_git.bitmaps, sha1);
-	if (hash_pos < kh_end(bitmap_git.bitmaps)) {
-		struct stored_bitmap *st = kh_value(bitmap_git.bitmaps, hash_pos);
-		bitmap_or_ewah(data->base, lookup_stored_bitmap(st));
+	bm = lookup_stored_bitmap_sha1(sha1);
+	if (bm) {
+		bitmap_or_ewah(data->base, bm);
 		return 0;
 	}
 

@@ -507,12 +507,9 @@ static struct bitmap *find_objects(struct rev_info *revs,
 		roots = roots->next;
 
 		if (object->type == OBJ_COMMIT) {
-			khiter_t pos = kh_get_sha1(bitmap_git.bitmaps, object->sha1);
-
-			if (pos < kh_end(bitmap_git.bitmaps)) {
-				struct stored_bitmap *st = kh_value(bitmap_git.bitmaps, pos);
-				struct ewah_bitmap *or_with = lookup_stored_bitmap(st);
-
+			struct ewah_bitmap *or_with =
+				lookup_stored_bitmap_sha1(object->sha1);
+			if (or_with) {
 				if (base == NULL)
 					base = ewah_to_bitmap(or_with);
 				else

@@ -584,17 +581,15 @@ static struct bitmap *find_objects(struct rev_info *revs,
 static void show_extended_objects(struct bitmap *objects,
 				  show_reachable_fn show_reach)
 {
-	struct eindex *eindex = &bitmap_git.ext_index;
-	uint32_t i;
-
-	for (i = 0; i < eindex->count; ++i) {
-		struct object *obj;
+	struct ext_entry *e;
+	struct hashmap_iter iter;
 
-		if (!bitmap_get(objects, bitmap_git.pack->num_objects + i))
+	for (e = hashmap_iter_first(&bitmap_git.ext_index, &iter); e;
+	     e = hashmap_iter_next(&iter)) {
+		if (!bitmap_get(objects, bitmap_git.pack->num_objects + e->nr))
 			continue;
 
-		obj = eindex->objects[i];
-		show_reach(obj->sha1, obj->type, 0, eindex->hashes[i], NULL, 0);
+		show_reach(e->object->sha1, e->object->type, 0, e->name_hash, NULL, 0);
 	}
 }
 

@@ -831,7 +826,8 @@ void traverse_bitmap_commit_list(show_reachable_fn show_reachable)
 static uint32_t count_object_type(struct bitmap *objects,
 				  enum object_type type)
 {
-	struct eindex *eindex = &bitmap_git.ext_index;
+	struct ext_entry *e;
+	struct hashmap_iter iter;
 
 	uint32_t i = 0, count = 0;
 	struct ewah_iterator it;

@@ -863,9 +859,10 @@ static uint32_t count_object_type(struct bitmap *objects,
 		count += ewah_bit_popcount64(word);
 	}
 
-	for (i = 0; i < eindex->count; ++i) {
-		if (eindex->objects[i]->type == type &&
-			bitmap_get(objects, bitmap_git.pack->num_objects + i))
+	for (e = hashmap_iter_first(&bitmap_git.ext_index, &iter); e;
+	     e = hashmap_iter_next(&iter)) {
+		if (e->object->type == type &&
+			bitmap_get(objects, bitmap_git.pack->num_objects + e->nr))
 			count++;
 	}
 

@@ -928,7 +925,7 @@ void test_bitmap_walk(struct rev_info *revs)
 {
 	struct object *root;
 	struct bitmap *result = NULL;
-	khiter_t pos;
+	struct ewah_bitmap *bm;
 	size_t result_popcnt;
 	struct bitmap_test_data tdata;
 

@@ -942,12 +939,9 @@ void test_bitmap_walk(struct rev_info *revs)
 		bitmap_git.version, bitmap_git.entry_count);
 
 	root = revs->pending.objects[0].item;
-	pos = kh_get_sha1(bitmap_git.bitmaps, root->sha1);
-
-	if (pos < kh_end(bitmap_git.bitmaps)) {
-		struct stored_bitmap *st = kh_value(bitmap_git.bitmaps, pos);
-		struct ewah_bitmap *bm = lookup_stored_bitmap(st);
 
+	bm = lookup_stored_bitmap_sha1(root->sha1);
+	if (bm) {
 		fprintf(stderr, "Found bitmap for %s. %d bits / %08x checksum\n",
 			sha1_to_hex(root->sha1), (int)bm->bit_size, ewah_checksum(bm));
 

@@ -1020,6 +1014,7 @@ int rebuild_existing_bitmaps(struct packing_data *mapping,
 	struct bitmap *rebuild;
 	struct stored_bitmap *stored;
 	struct progress *progress = NULL;
+	struct hashmap_iter iter;
 
 	khiter_t hash_pos;
 	int hash_ret;

@@ -1049,7 +1044,8 @@ int rebuild_existing_bitmaps(struct packing_data *mapping,
 	if (show_progress)
 		progress = start_progress("Reusing bitmaps", 0);
 
-	kh_foreach_value(bitmap_git.bitmaps, stored, {
+	for (stored = hashmap_iter_first(&bitmap_git.bitmaps, &iter); stored;
+	     stored = hashmap_iter_next(&iter)) {
 		if (stored->flags & BITMAP_FLAG_REUSE) {
 			if (!rebuild_bitmap(reposition,
 					    lookup_stored_bitmap(stored),

@@ -1063,7 +1059,7 @@ int rebuild_existing_bitmaps(struct packing_data *mapping,
 			bitmap_reset(rebuild);
 			display_progress(progress, ++i);
 		}
-	});
+	}
 
 	stop_progress(&progress);
 

-- 

On Tue, Dec 03, 2013 at 03:40:41PM +0100, Karsten Blees wrote:

IMO, trying to improve khash isn't worth the trouble.

With smaller-than-pointer types, khash _may_ actually save a few bytes
compared to hash.[ch] or hashmap.[ch]. E.g. a set of 'int's would be a
perfect use case for khash. However, you're using bitmaps for that,
and khash's predefined macros for int sets and maps have been removed
from the git version.

True, we are not using it for smaller-than-pointer sizes here. So it may
not be worth thinking about (I was considering more for the general
case). In most instances, though, we can shove the int bits into a
pointer with the right casting. So it probably isn't worth worrying
about (you may waste a few bytes, but probably not more than one word
per entry).

Using khash with pointers and larger-than-pointer types is just a
waste of memory and performance, though. Hash tables are sparsely
filled by design, and using large types means lots of large empty
buckets. E.g. kh_resize requires almost four times the size or your
data, and copies everything at least three times.

I think the analysis is more complicated than that, and depends on what
you are storing. If you are storing something that is 1.5 times the size
of a pointer, it is more space efficient to just stick it in the hash
table than it is to have a separate pointer in the hash table (you pay
the load factor penalty only on the single pointer, but you've almost
doubled your total storage).

But again, that's a more general argument. We're not storing anything of
that size here, and in fact I think we are just storing pointers
everywhere.

Additionally, there are the obvious problems with khash's macro design
(hard to read, impossible to debug, and each named instance increases
executable size by ~4k).

Yes, those are all downsides to macros. Type safety is one of the
upsides, though.

Besides macros, I think the major difference between the two
implementations is open-addressing versus chaining. Especially for sets,
we've had good experiences with open-addressing by keeping the load
factor low (e.g., the one in object.c). As you note, the resizing
operation pays some penalty, but in most of our workloads it's largely
irrelevant compared to lookup times.

Chaining typically adds an extra layer of pointer-following to the
lookup, and I'd be worried about that loss of locality. It's true that
when you are storing a pointer you are already hurting locality to
follow the pointer to the key, but I don't know whether that means an
_extra_ layer doesn't still hurt more (and I really mean I don't know --
I'd be interested to see measurements).

In your implementation, it looks like you break even there because you
store the hash directly in the entry, and do a single-word compare (so
you avoid having to follow a pointer to the key in the common case
during lookup). But that also means you're paying extra to store the
hash. That probably makes sense for things like strings, where it takes
some effort to calculate the hash. But not necessarily for sha1s, where
looking at the hash is the same thing as looking at the key bytes (so
you are storing extra bytes, and when you do have a hit on the stored
hash, which is just the first bytes of the sha1, you end up comparing
them again as part of the hashcmp. The tradeoff is that in the
non-matching cases, you avoid an extra level of indirection).

All of these are things I could see helping or hurting, depending on the
case. I'd really love to see more numbers. I tried timing your patch
below, but there was no interesting change. Mostly because the code path
you changed is not heavily exercised (the "ext_index" is for objects
that are not in the pack, and frequent packing keeps that number low).

I'd be really interested to see if you could make the hash in object.c
faster. That one is a prominent lookup bottle-neck (e.g., for "git
rev-list --objects --all"); if you can make that faster, I would be very
convinced that your implementation is fast (note that I am not implying
the converse; if you cannot make it faster, that does not necessarily
mean your implementation sucks, but perhaps only that the existing one
has lots of type-specific optimizations which add up).

Khash also has a lot of bloat (e.g., flags) that the one in object.c
does not have. If you do not care about deletion and are storing
something with a sentinel value (e.g., NULL for pointers), you can trim
quite a bit of fat.

Below is a patch that converts pack-bitmap.c to hashmap. Its not even
longer than the khash version, and the hashmap API forces you to think
about no-brainer improvements such as specifying an expected size or
skipping duplicates checks where they aren't needed. I could do the
same for pack-bitmap-write.c if you like.

If it's not too much trouble, I'd be curious to measure the performance
impact on pack-bitmap-write.

Removes two unnecessary duplicates checks:
 - we don't expect a pack index file to contain duplicate sha1's

We don't expect them to, but it has happened (and caused bugs not too
long ago). What happens after your patch when there are duplicates?

+static struct ewah_bitmap *lookup_stored_bitmap_sha1(const unsigned char *sha1)
+{
+	struct stored_bitmap key, *st;
+	hashmap_entry_init(&key, __kh_oid_hash(sha1));
+	st = hashmap_get(&bitmap_git.bitmaps, &key, sha1);
+	if (st)
+		return lookup_stored_bitmap(st);
+	return NULL;
+}

This interface looks odd to me. You create a fake stored_bitmap for the
hashmap_entry part of it, and then fill in the "hash" field by hashing
the sha1. And then pass the same sha1 in. I guess you are trying to
avoid the hash table knowing about the hash function at all, since it
just stores the hash for each entry already.

I guess that makes sense, but would not work for a system where you
wanted to get rid of the extra hash storage (but as I implied above, I
am not sure if it is helping or hurting for the sha1 case).

-	hash_pos = kh_put_sha1_pos(eindex->positions, object->sha1, &hash_ret);
-	if (hash_ret > 0) {
-		if (eindex->count >= eindex->alloc) {
-			eindex->alloc = (eindex->alloc + 16) * 3 / 2;
-			eindex->objects = xrealloc(eindex->objects,
-				eindex->alloc * sizeof(struct object *));
-			eindex->hashes = xrealloc(eindex->hashes,
-				eindex->alloc * sizeof(uint32_t));
-		}
-
-		bitmap_pos = eindex->count;
-		eindex->objects[eindex->count] = object;
-		eindex->hashes[eindex->count] = pack_name_hash(name);
-		kh_value(eindex->positions, hash_pos) = bitmap_pos;
-		eindex->count++;
-	} else {
-		bitmap_pos = kh_value(eindex->positions, hash_pos);
-	}
-
-	return bitmap_pos + bitmap_git.pack->num_objects;
+	struct ext_entry *e = xmalloc(sizeof(struct ext_entry));
+	hashmap_entry_init(e, __kh_oid_hash(object->sha1));
+	e->object = object;
+	e->name_hash = pack_name_hash(name);
+	e->nr = bitmap_git.ext_index.size;
+	hashmap_add(&bitmap_git.ext_index, e);
+	return e->nr + bitmap_git.pack->num_objects;

One of the side effects of the current system is that the array
effectively works as a custom allocator, and we do not pay per-entry
malloc overhead. As I mentioned above, this is not that
heavily-exercised a code path, so it may not matter (and you can convert
it by explicitly using a custom allocator, at which point you could drop
the e->nr field entirely, I'd think).

Before we were iterating in eindex order. Now we are iterating in
hashmap order. That effects our traversal order, and ultimately our
output for something like "rev-list". We'd want to sort on e->nr (or
again, a custom allocator would make this go away because we would
iterate over the array).

-	for (i = 0; i < eindex->count; ++i) {
-		if (eindex->objects[i]->type == type &&
-			bitmap_get(objects, bitmap_git.pack->num_objects + i))
+	for (e = hashmap_iter_first(&bitmap_git.ext_index, &iter); e;
+	     e = hashmap_iter_next(&iter)) {
+		if (e->object->type == type &&
+			bitmap_get(objects, bitmap_git.pack->num_objects + e->nr))
 			count++;

Ditto here, but I do not think the order matters in this instance.

-Peff

Am 03.12.2013 19:21, schrieb Jeff King:

On Tue, Dec 03, 2013 at 03:40:41PM +0100, Karsten Blees wrote:

quoted

IMO, trying to improve khash isn't worth the trouble.

With smaller-than-pointer types, khash _may_ actually save a few bytes
compared to hash.[ch] or hashmap.[ch]. E.g. a set of 'int's would be a
perfect use case for khash. However, you're using bitmaps for that,
and khash's predefined macros for int sets and maps have been removed
from the git version.

True, we are not using it for smaller-than-pointer sizes here. So it may
not be worth thinking about (I was considering more for the general
case). In most instances, though, we can shove the int bits into a
pointer with the right casting. So it probably isn't worth worrying
about (you may waste a few bytes, but probably not more than one word
per entry).

quoted

Using khash with pointers and larger-than-pointer types is just a
waste of memory and performance, though. Hash tables are sparsely
filled by design, and using large types means lots of large empty
buckets. E.g. kh_resize requires almost four times the size or your
data, and copies everything at least three times.

I think the analysis is more complicated than that, and depends on what
you are storing. If you are storing something that is 1.5 times the size
of a pointer, it is more space efficient to just stick it in the hash
table than it is to have a separate pointer in the hash table (you pay
the load factor penalty only on the single pointer, but you've almost
doubled your total storage).

But again, that's a more general argument. We're not storing anything of
that size here, and in fact I think we are just storing pointers
everywhere.

Yes. With pointers, its a very close call regarding space. Let's take bitmap_index.bitmaps / struct stored_bitmap as an example. I'm assuming 8 byte pointers and an average load factor of 0.5.

struct stored_bitmap is already kind of an entry structure (key + value) allocated on the heap. This is a very common szenario, all hash.[ch] -> hashmap.[ch] conversions were that way.

The average khash memory requirement per entry is (on top of the data on the heap):

  (key + value + flags) / load-factor = (8 + 8 + .25) / .5 = 32.5 bytes

For the hashmap conversion, I simply injected struct hashmap_entry into the existing structure, adding 12 bytes per entry. So the total hashmap memory per entry is:

  hashmap_entry + (entry-pointer / load-factor) = 12 + (8 / .5) = 28 bytes

quoted

Additionally, there are the obvious problems with khash's macro design
(hard to read, impossible to debug, and each named instance increases
executable size by ~4k).

Yes, those are all downsides to macros. Type safety is one of the
upsides, though.

Well, khash_sha1 maps to void *, so I guess its not that important :-) But if you care about type safety, a common core implementation with a few small wrapper macros would be hugely preferable, don't you think?
 

Besides macros, I think the major difference between the two
implementations is open-addressing versus chaining. Especially for sets,
we've had good experiences with open-addressing by keeping the load
factor low (e.g., the one in object.c). As you note, the resizing
operation pays some penalty, but in most of our workloads it's largely
irrelevant compared to lookup times.

Resizing is reasonably fast and straightforward for both open addressing and chaining. My 'copy three times' remark above was specific to the rehash-in-place stunt in kh_resize (if you haven't wondered what these 64 multi-statement-lines do, you probably don't wanna know... ;-)

But its still best if you know the target size and can prevent resizing altogether.

Chaining typically adds an extra layer of pointer-following to the
lookup, and I'd be worried about that loss of locality. It's true that
when you are storing a pointer you are already hurting locality to
follow the pointer to the key, but I don't know whether that means an
_extra_ layer doesn't still hurt more (and I really mean I don't know --
I'd be interested to see measurements).

The locality advantage of open addressing _only_ applies when storing the data directly in the table, but AFAIK we're not doing that anywhere in git. Compared to open addressing with pointers, chaining in fact has _better_ locality.

Iterating a linked list (i.e. chaining) accesses exactly one (1.0) memory location per element.

Iterating an array of pointers (i.e. open addressing with linear probing) accesses ~1.125 memory locations per element (assuming 8 byte pointers and 64 byte cache lines, array[8] will be in a different cache line than array[0], thus the +.125).

Of course, any implementation can add more pointer-following to that minimum. E.g. khash uses separate flags and keys arrays and triangular numbers as probe sequence, so its up to 3 memory locations per element.

Hashmap, on the other hand, allows you to inject it's per-entry data into the user data structure to prevent locality penalties (well, the user data structure could add more pointer-following, but that's not hashmap's fault).

In your implementation, it looks like you break even there because you
store the hash directly in the entry, and do a single-word compare (so
you avoid having to follow a pointer to the key in the common case
during lookup).

More importantly, it saves calling a function pointer with three parameters unless its a _very_ probable match.

But that also means you're paying extra to store the
hash. That probably makes sense for things like strings, where it takes
some effort to calculate the hash. But not necessarily for sha1s, where
looking at the hash is the same thing as looking at the key bytes (so
you are storing extra bytes,

True. Its 4 bytes overhead for sha1s and probably ints (but even for ints you may want to wiggle the bits for better distribution). However, its an utterly necessary optimization for e.g. strings with common prefixes. Think of a Java project where all paths start with com/mycompany/myou/productname/component/... i.e. strcmp has to compare ~40 bytes before finding a difference.

and when you do have a hit on the stored
hash, which is just the first bytes of the sha1, you end up comparing
them again as part of the hashcmp.

Not necessarily - I could skip the part that I've used as hash code...

The tradeoff is that in the
non-matching cases, you avoid an extra level of indirection).

All of these are things I could see helping or hurting, depending on the
case. I'd really love to see more numbers. I tried timing your patch
below, but there was no interesting change. Mostly because the code path
you changed is not heavily exercised (the "ext_index" is for objects
that are not in the pack, and frequent packing keeps that number low).

I'd be really interested to see if you could make the hash in object.c
faster. That one is a prominent lookup bottle-neck (e.g., for "git
rev-list --objects --all"); if you can make that faster, I would be very
convinced that your implementation is fast (note that I am not implying
the converse; if you cannot make it faster, that does not necessarily
mean your implementation sucks, but perhaps only that the existing one
has lots of type-specific optimizations which add up).

Ok, let's see...

Hash tables only compare for equality, not for sorting, so the first thing that comes to mind is to compare 4 bytes at a time.

The hashmap version cuts quite a bit of code, but uses slightly more memory (~6 bytes per entry). Still todo: get_indexed_object now only returns the list heads, so callers need to follow the chain...

Then I wrote a custom chaining version (i.e. no cached hash code, inlined hashcmp() etc.). The increased load-factor of 0.8 should fully compensate the additional next pointer in struct object. Ditto for get_indexed_object.

Finally, just for fun, the khash version...

Your move-to-front optimization seems highly specialized to lookup_object access patterns, and also breaks the assumption that concurrent lookup is thread safe. So I didn't bother to pimp hashmap and khash internals, and instead did the other measurements with and without move-to-front enabled. The hashmap move-to-front is via the existing API (remove + add), i.e. its true LRU instead of swap (same for custom-chaining).

Numbers are in seconds, best of 10 runs of 'git rev-list --all --objects >/dev/null' on the linux kernel repo.

 fast  | move  ||  next  |  hash  | custom | khash  |
 hash  |  to   ||        |  map   |        |        |
 cmp   | front || (open) |(chain) |(chain) | (open) |
=======+=======++========+========+========+========+
  no   |  no   || 45.593 | 42.924 | 41.033 | 62.974 |
  no   |  yes  || 41.017 | 43.095 | 40.478 |        |
  yes  |  no   || 43.172 | 40.965 | 39.564 |        |
  yes  |  yes  || 39.332 | 41.008 | 38.869 |        |

The fastest versions of each variant can be found here:

https://github.com/kblees/git/commits/kb/optimize-lookup-object-next
https://github.com/kblees/git/commits/kb/optimize-lookup-object-hashmap
https://github.com/kblees/git/commits/kb/optimize-lookup-object-custom-chaining
https://github.com/kblees/git/commits/kb/optimize-lookup-object-khash

Khash also has a lot of bloat (e.g., flags) that the one in object.c
does not have. If you do not care about deletion and are storing
something with a sentinel value (e.g., NULL for pointers), you can trim
quite a bit of fat.

Actually, the lack of deletion in hash.[ch] was the reason I started this...one advantage of chaining is that delete can be implemented efficiently (O(1)) without affecting lookup / insert performance.

quoted

Below is a patch that converts pack-bitmap.c to hashmap. Its not even
longer than the khash version, and the hashmap API forces you to think
about no-brainer improvements such as specifying an expected size or
skipping duplicates checks where they aren't needed. I could do the
same for pack-bitmap-write.c if you like.

If it's not too much trouble, I'd be curious to measure the performance
impact on pack-bitmap-write.

I'll see what I can do

quoted

Removes two unnecessary duplicates checks:
 - we don't expect a pack index file to contain duplicate sha1's

We don't expect them to, but it has happened (and caused bugs not too
long ago). What happens after your patch when there are duplicates?

Both entries are added, and hashmap_get returns one of them at random. Re-adding duplicates checks is simple, though:

- hashmap_add(...);
+ if (hashmap_put(...))
+   die("foo has duplicate o's");

quoted

+static struct ewah_bitmap *lookup_stored_bitmap_sha1(const unsigned char *sha1)
+{
+	struct stored_bitmap key, *st;
+	hashmap_entry_init(&key, __kh_oid_hash(sha1));
+	st = hashmap_get(&bitmap_git.bitmaps, &key, sha1);
+	if (st)
+		return lookup_stored_bitmap(st);
+	return NULL;
+}

This interface looks odd to me. You create a fake stored_bitmap for the
hashmap_entry part of it, and then fill in the "hash" field by hashing
the sha1. And then pass the same sha1 in. I guess you are trying to
avoid the hash table knowing about the hash function at all, since it
just stores the hash for each entry already.

The general case would be:

 struct stored_bitmap key;
 /* fill in hash code */
 hashmap_entry_init(&key, __kh_oid_hash(sha1));
 /* fill in key data */
 hashcpy(key.sha1, sha1);
 key.another_key_field = foobar;
 ...
 return hashmap_get(&bitmap_git.bitmaps, &key, NULL);

In this case, the sha1 is the only key data, and its larger that a word, so passing it as keydata parameter and checking for this in the cmp-function is slightly more efficient.

I guess that makes sense, but would not work for a system where you
wanted to get rid of the extra hash storage (but as I implied above, I
am not sure if it is helping or hurting for the sha1 case).

quoted

-	hash_pos = kh_put_sha1_pos(eindex->positions, object->sha1, &hash_ret);
-	if (hash_ret > 0) {
-		if (eindex->count >= eindex->alloc) {
-			eindex->alloc = (eindex->alloc + 16) * 3 / 2;
-			eindex->objects = xrealloc(eindex->objects,
-				eindex->alloc * sizeof(struct object *));
-			eindex->hashes = xrealloc(eindex->hashes,
-				eindex->alloc * sizeof(uint32_t));
-		}
-
-		bitmap_pos = eindex->count;
-		eindex->objects[eindex->count] = object;
-		eindex->hashes[eindex->count] = pack_name_hash(name);
-		kh_value(eindex->positions, hash_pos) = bitmap_pos;
-		eindex->count++;
-	} else {
-		bitmap_pos = kh_value(eindex->positions, hash_pos);
-	}
-
-	return bitmap_pos + bitmap_git.pack->num_objects;
+	struct ext_entry *e = xmalloc(sizeof(struct ext_entry));
+	hashmap_entry_init(e, __kh_oid_hash(object->sha1));
+	e->object = object;
+	e->name_hash = pack_name_hash(name);
+	e->nr = bitmap_git.ext_index.size;
+	hashmap_add(&bitmap_git.ext_index, e);
+	return e->nr + bitmap_git.pack->num_objects;

One of the side effects of the current system is that the array
effectively works as a custom allocator, and we do not pay per-entry
malloc overhead. As I mentioned above, this is not that
heavily-exercised a code path, so it may not matter (and you can convert
it by explicitly using a custom allocator, at which point you could drop
the e->nr field entirely, I'd think).

Realloc doesn't produce stable pointers, so we'd have to use a custom slab-allocator such as in alloc.c. However, I tend to think of malloc as a separate problem. There are quite efficient heap implementations with near-zero memory overhead even for small objects out there. I wouldn't be surprised if some day allocating many small objects will be faster and more space-efficient than re-allocating big blocks. Then you'd have all your code base littered with custom allocators that actually slow down the application...

quoted

@@ -584,17 +581,15 @@ static struct bitmap *find_objects(struct rev_info *revs,
 static void show_extended_objects(struct bitmap *objects,
 				  show_reachable_fn show_reach)
 {
-	struct eindex *eindex = &bitmap_git.ext_index;
-	uint32_t i;
-
-	for (i = 0; i < eindex->count; ++i) {
-		struct object *obj;
+	struct ext_entry *e;
+	struct hashmap_iter iter;
 
-		if (!bitmap_get(objects, bitmap_git.pack->num_objects + i))
+	for (e = hashmap_iter_first(&bitmap_git.ext_index, &iter); e;
+	     e = hashmap_iter_next(&iter)) {
+		if (!bitmap_get(objects, bitmap_git.pack->num_objects + e->nr))
 			continue;
 
-		obj = eindex->objects[i];
-		show_reach(obj->sha1, obj->type, 0, eindex->hashes[i], NULL, 0);
+		show_reach(e->object->sha1, e->object->type, 0, e->name_hash, NULL, 0);

Before we were iterating in eindex order. Now we are iterating in
hashmap order. That effects our traversal order, and ultimately our
output for something like "rev-list". We'd want to sort on e->nr (or
again, a custom allocator would make this go away because we would
iterate over the array).

I didn't think it would matter, as the caller emits the objects from the bitmapped pack ordered by type and pack-index...well, I'll try to think of something (probably a linked list between entries?)

quoted

-	for (i = 0; i < eindex->count; ++i) {
-		if (eindex->objects[i]->type == type &&
-			bitmap_get(objects, bitmap_git.pack->num_objects + i))
+	for (e = hashmap_iter_first(&bitmap_git.ext_index, &iter); e;
+	     e = hashmap_iter_next(&iter)) {
+		if (e->object->type == type &&
+			bitmap_get(objects, bitmap_git.pack->num_objects + e->nr))
 			count++;

Ditto here, but I do not think the order matters in this instance.

-Peff