Skip to contentSkip to conversation

New hash table implementation

PATCH Superseded Karsten Blees 5 participants 24 messages Jun 15, 2016 Kbuild

v1 of 5 Superseded Latest is v5 →

lore
Share & tools
lore

Karsten Blees

author
#0 lore raw

cover New hash table implementation

Also here: https://github.com/kblees/git/tree/kb/hashmap

Hi,

this is a spin-off of my (very slowly progressing) msysgit fscache project. I needed to remove things from the hash table, which cannot be implemented efficiently in hash.[ch].

So I wrote hasmap.[ch], with these features:
- O(1) remove
- builtin entry chaining
- ready-to-use FNV-1 hash functions
- unit test
- additions are ~twice as fast
- uses less memory

Patches 2 and 5 convert existing uses of hash.[ch] to hashmap.[ch]. Patches 3 and 4 are useful optimizations of their own.

I haven't found the time to tackle name-hash.c yet, this is where remove() could come into play (to replace the CE_UNHASHED flag).

Karsten

Karsten Blees (5):
add a hashtable implementation that supports O(1) removal buitin/describe.c: use new hash map implementation diffcore-rename.c: move code around to prepare for the next patch diffcore-rename.c: simplify finding exact renames diffcore-rename.c: use new hash map implementation

 Makefile           |   3 +
 builtin/describe.c |  53 +++++------
 diffcore-rename.c  | 185 +++++++++++++-------------------------
 hashmap.c          | 210 +++++++++++++++++++++++++++++++++++++++++++
 hashmap.h          | 200 +++++++++++++++++++++++++++++++++++++++++
 t/t0011-hashmap.sh | 236 ++++++++++++++++++++++++++++++++++++++++++++++++
 test-hashmap.c     | 258 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 995 insertions(+), 150 deletions(-)
 create mode 100644 hashmap.c
 create mode 100644 hashmap.h
 create mode 100755 t/t0011-hashmap.sh
 create mode 100644 test-hashmap.c
Signature · 1 line
1.8.4.8243.gbcbdefd
author
#1 lore raw

PATCH 1/5 add a hashtable implementation that supports O(1) removal

The existing hashtable implementation (in hash.[ch]) uses open addressing (i.e. resolve hash collisions by distributing entries across the table). Thus, removal is difficult to implement with less than O(n) complexity. Resolving collisions of entries with identical hashes (e.g. via chaining) is left to the client code.

Add a hashtable implementation that supports O(1) removal and is slightly easier to use due to builtin entry chaining.

Supports all basic operations init, free, get, add, remove and iteration.

Also includes ready-to-use hash functions based on the public domain FNV-1 algorithm (http://www.isthe.com/chongo/tech/comp/fnv).

The per-entry data structure (hashmap_entry) is meant to be piggybacked in front of the client's data structure to save memory. See test-hashmap.c for usage examples.

The hashtable is resized by a factor of four when 80% full. With these settings, average memory consumption is about 2/3 of hash.[ch], and insertion is about twice as fast due to less frequent resizing.

Signed-off-by Karsten Blees <[email protected]>
---
 Makefile           |   3 +
 hashmap.c          | 210 +++++++++++++++++++++++++++++++++++++++++++
 hashmap.h          | 200 +++++++++++++++++++++++++++++++++++++++++
 t/t0011-hashmap.sh | 236 ++++++++++++++++++++++++++++++++++++++++++++++++
 test-hashmap.c     | 258 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 907 insertions(+)
 create mode 100644 hashmap.c
 create mode 100644 hashmap.h
 create mode 100755 t/t0011-hashmap.sh
 create mode 100644 test-hashmap.c
Makefile +3 -0
index 3588ca1..e6ad011 100644
@@ -562,6 +562,7 @@ TEST_PROGRAMS_NEED_X += test-date
 TEST_PROGRAMS_NEED_X += test-delta
 TEST_PROGRAMS_NEED_X += test-dump-cache-tree
 TEST_PROGRAMS_NEED_X += test-genrandom
+TEST_PROGRAMS_NEED_X += test-hashmap
 TEST_PROGRAMS_NEED_X += test-index-version
 TEST_PROGRAMS_NEED_X += test-line-buffer
 TEST_PROGRAMS_NEED_X += test-match-trees

@@ -681,6 +682,7 @@ LIB_H += gpg-interface.h
 LIB_H += graph.h
 LIB_H += grep.h
 LIB_H += hash.h
+LIB_H += hashmap.h
 LIB_H += help.h
 LIB_H += http.h
 LIB_H += kwset.h

@@ -811,6 +813,7 @@ LIB_OBJS += gpg-interface.o
 LIB_OBJS += graph.o
 LIB_OBJS += grep.o
 LIB_OBJS += hash.o
+LIB_OBJS += hashmap.o
 LIB_OBJS += help.o
 LIB_OBJS += hex.o
 LIB_OBJS += ident.o
hashmap.c new file +210 -0

210 lines not on this page · raw message

hashmap.h new file +200 -0

200 lines not on this page · raw message

t/t0011-hashmap.sh new file +236 -0

236 lines not on this page · raw message

test-hashmap.c new file +258 -0

258 lines not on this page · raw message

Signature · 1 line
1.8.4.8243.gbcbdefd
#2 lore raw

Re: [PATCH/RFC 1/5] add a hashtable implementation that supports O(1) removal

Quoted 3 lines · Karsten Blees

+/*
+ * Hashmap entry data structure, intended to be used as first member of user
+ * data structures. Consists of a pointer and an int. Ideally it should be

It is technically correct to say this is "intended to be" used, but to those who are using this API, it would be more helpful to say "a user data structure that uses this API *must* have this as its first member field".

hashmap.h line 74

Quoted 13 lines

+ * followed by an int-sized member to prevent unused memory on 64-bit systems
+ * due to alignment.
+ */

hashmap.h new file +10 -0
+typedef struct hashmap_entry {
+	struct hashmap_entry *next;
+	unsigned int hash;
+} hashmap_entry;
+ ...
+typedef struct hashmap {
+	hashmap_entry **table;
+	hashmap_cmp_fn cmpfn;
+	unsigned int size, tablesize;
+} hashmap;

I forgot to mention in my previous message, but we find that the code tends to be easier to read if we avoid using typedef'ed struct like these. E.g. in 2/5 we see something like this:

     static int abbrev = -1; /* unspecified */
     static int max_candidates = 10;
    -static struct hash_table names;
    +static hashmap names;
     static int have_util;
     static const char *pattern;
     static int always;
    @@ -38,7 +38,7 @@ static const char *diff_index_args[] = {


     struct commit_name {
    -	struct commit_name *next;
    +	hashmap_entry entry;
            unsigned char peeled[20];

The version before the patch is preferrable.

Thanks.

author
#3 lore raw

Re: [PATCH/RFC 1/5] add a hashtable implementation that supports O(1) removal

Am 12.09.2013 06:10, schrieb Junio C Hamano:

Quoted 11 lines
Quoted 3 lines · Karsten Blees

+/*
+ * Hashmap entry data structure, intended to be used as first member of user
+ * data structures. Consists of a pointer and an int. Ideally it should be

It is technically correct to say this is "intended to be" used, but to those who are using this API, it would be more helpful to say "a user data structure that uses this API *must* have this as its first member field".

Right. I considered making the position in the user struct configurable via some offsetof() magic, but this would have just complicated things unnecessarily.

Quoted 33 lines

hashmap.h line 74

Quoted 13 lines

+ * followed by an int-sized member to prevent unused memory on 64-bit systems
+ * due to alignment.
+ */

hashmap.h new file +10 -0
+typedef struct hashmap_entry {
+	struct hashmap_entry *next;
+	unsigned int hash;
+} hashmap_entry;
+ ...
+typedef struct hashmap {
+	hashmap_entry **table;
+	hashmap_cmp_fn cmpfn;
+	unsigned int size, tablesize;
+} hashmap;

I forgot to mention in my previous message, but we find that the code tends to be easier to read if we avoid using typedef'ed struct like these. E.g. in 2/5 we see something like this:

     static int abbrev = -1; /* unspecified */
     static int max_candidates = 10;
    -static struct hash_table names;
    +static hashmap names;
     static int have_util;
     static const char *pattern;
     static int always;
    @@ -38,7 +38,7 @@ static const char *diff_index_args[] = {


     struct commit_name {
    -	struct commit_name *next;
    +	hashmap_entry entry;
            unsigned char peeled[20];
Quoted 2 lines

The version before the patch is preferrable.

OK

#4 lore raw

Re: [PATCH/RFC 1/5] add a hashtable implementation that supports O(1) removal

In reply to Karsten Blees

hashmap.c line 70

Quoted 7 lines · Karsten Blees
hashmap.c new file +7 -0
+#define FNV32_BASE ((unsigned int) 0x811c9dc5)
+#define FNV32_PRIME ((unsigned int) 0x01000193)
+ ...
+static inline unsigned int bucket(const hashmap *map, const hashmap_entry *key)
+{
+	return key->hash & (map->tablesize - 1);
+}

As tablesize would hopefully be reasonably small, not worrying about platforms' "unsigned int" being 64-bit (in which case it would be more appropriate to compute with FNV64_PRIME) should be fine.

hashmap.c line 99

Quoted 8 lines
hashmap.c new file +8 -0
+static inline hashmap_entry **find_entry(const hashmap *map,
+		const hashmap_entry *key)
+{
+	hashmap_entry **e = &map->table[bucket(map, key)];
+	while (*e && !entry_equals(map, *e, key))
+		e = &(*e)->next;
+	return e;
+}

(mental note) This finds the location the pointer to the entry is stored, not the entry itself.

hashmap.c line 137

Quoted 4 lines
hashmap.c new file +4 -0
+void *hashmap_get(const hashmap *map, const void *key)
+{
+	return *find_entry(map, key);
+}

... which is consistent with this, and more importantly, it is crucial for hashmap_remove()'s implementation, because...

hashmap.c line 171

Quoted 10 lines
hashmap.c new file +10 -0
+void *hashmap_remove(hashmap *map, const void *key)
+{
+	hashmap_entry *old;
+	hashmap_entry **e = find_entry(map, key);
+	if (!*e)
+		return NULL;
+
+	/* remove existing entry */
+	old = *e;
+	*e = old->next;

... this wants to update the linked list in place.

Looking good.

I however wonder if the singly linked linear chain is a really good alternative for the access pattern of the hashes we use, though. Do we really want to trigger growth on the bucket load factor, not the length of the longest chain, for example?

hashmap.c line 178

Quoted 7 lines
hashmap.c new file +7 -0
+	old->next = NULL;
+
+	/* fix size and rehash if appropriate */
+	map->size--;
+	if (map->tablesize > HASHMAP_INITIAL_SIZE &&
+		map->size * HASHMAP_SHRINK_AT < map->tablesize)
+		rehash(map, map->tablesize >> HASHMAP_GROW);

Please align the first two lines so that the first non-whitespace on the second line of the condition part of the "if" statement (i.e. 'm') aligns with the first non-whitespace inside the '(' open parenthesis (i.e. 'm').

author
#5 lore raw

Re: [PATCH/RFC 1/5] add a hashtable implementation that supports O(1) removal

Sorry for the delay, I've been on vacation...

Am 12.09.2013 01:56, schrieb Junio C Hamano:

Quoted 14 lines

hashmap.c line 70

Quoted 7 lines · Karsten Blees
hashmap.c new file +7 -0
+#define FNV32_BASE ((unsigned int) 0x811c9dc5)
+#define FNV32_PRIME ((unsigned int) 0x01000193)
+ ...
+static inline unsigned int bucket(const hashmap *map, const hashmap_entry *key)
+{
+	return key->hash & (map->tablesize - 1);
+}

As tablesize would hopefully be reasonably small, not worrying about platforms' "unsigned int" being 64-bit (in which case it would be more appropriate to compute with FNV64_PRIME) should be fine.

Quoted 12 lines

hashmap.c line 99

Quoted 8 lines
hashmap.c new file +8 -0
+static inline hashmap_entry **find_entry(const hashmap *map,
+		const hashmap_entry *key)
+{
+	hashmap_entry **e = &map->table[bucket(map, key)];
+	while (*e && !entry_equals(map, *e, key))
+		e = &(*e)->next;
+	return e;
+}

(mental note) This finds the location the pointer to the entry is stored, not the entry itself.

Will rename to find_entry_ptr to make this clear

Quoted 21 lines

hashmap.c line 137

Quoted 4 lines
hashmap.c new file +4 -0
+void *hashmap_get(const hashmap *map, const void *key)
+{
+	return *find_entry(map, key);
+}

... which is consistent with this, and more importantly, it is crucial for hashmap_remove()'s implementation, because...

hashmap.c line 171

Quoted 10 lines
hashmap.c new file +10 -0
+void *hashmap_remove(hashmap *map, const void *key)
+{
+	hashmap_entry *old;
+	hashmap_entry **e = find_entry(map, key);
+	if (!*e)
+		return NULL;
+
+	/* remove existing entry */
+	old = *e;
+	*e = old->next;

... this wants to update the linked list in place.

Quoted 4 lines

Looking good.

I however wonder if the singly linked linear chain is a really good alternative for the access pattern of the hashes we use, though.

I don't think it will make a big difference in lookup performance, especially with good hash codes (such as the first bytes of a sha1). In theory, chaining should be slightly faster, because entries are strictly confined to their buckets (i.e. no extraneous entries need to be traversed when looking up an entry). With uniform hash distribution, chaining should require (1 + loadfactor) comparisons to find an entry, while open addressing requires (1/(1 - loadfactor)) [1]. I'll add a performance test for lookups, though.

[1] http://en.wikipedia.org/wiki/Hash_table#Performance_analysis

Quoted 3 lines

Do we really want to trigger growth on the bucket load factor, not the length of the longest chain, for example?

With good hashes and a load factor < 1, the longest 'chain' is 1. We only get chains in case of collisions, which however cannot necessarily be resolved by resizing. E.g. in the worst case, all entries have the same hash code, which deforms the hash table into a long linked list in a single bucket. Resizing won't change that.

An alternative would be to resize on the number of used buckets instead of total entries. I.e. with exceptionally bad hash codes and lots of collisions, we at least don't waste memory by making the table unnecessarily large. However, I don't think this is worth the extra effort.

Quoted 4 lines
Quoted 4 lines
hashmap.c new file +4 -0
+	old->next = NULL;
+
+	/* fix size and rehash if appropriate */
+	map->size--;
Quoted 9 lines

hashmap.c line 178

Quoted 3 lines
hashmap.c new file +3 -0
+	if (map->tablesize > HASHMAP_INITIAL_SIZE &&
+		map->size * HASHMAP_SHRINK_AT < map->tablesize)
+		rehash(map, map->tablesize >> HASHMAP_GROW);

Please align the first two lines so that the first non-whitespace on the second line of the condition part of the "if" statement (i.e. 'm') aligns with the first non-whitespace inside the '(' open parenthesis (i.e. 'm').

Will do.

author
#6 lore raw

PATCH 2/5 buitin/describe.c: use new hash map implementation

In reply to Karsten Blees
Signed-off-by Karsten Blees <[email protected]>
---
 builtin/describe.c | 53 ++++++++++++++++++++++++-----------------------------
 1 file changed, 24 insertions(+), 29 deletions(-)
builtin/describe.c +24 -29
index 7d73722..bbc7159 100644
@@ -6,7 +6,7 @@
 #include "exec_cmd.h"
 #include "parse-options.h"
 #include "diff.h"
-#include "hash.h"
+#include "hashmap.h"
 #include "argv-array.h"
 
 #define SEEN		(1u<<0)

@@ -25,7 +25,7 @@ static int longformat;
 static int first_parent;
 static int abbrev = -1; /* unspecified */
 static int max_candidates = 10;
-static struct hash_table names;
+static hashmap names;
 static int have_util;
 static const char *pattern;
 static int always;

@@ -38,7 +38,7 @@ static const char *diff_index_args[] = {
 
 
 struct commit_name {
-	struct commit_name *next;
+	hashmap_entry entry;
 	unsigned char peeled[20];
 	struct tag *tag;
 	unsigned prio:2; /* annotated tag = 2, tag = 1, head = 0 */

@@ -50,6 +50,11 @@ static const char *prio_names[] = {
 	"head", "lightweight", "annotated",
 };
 
+static int commit_name_cmp(struct commit_name *cn1, struct commit_name *cn2)
+{
+	return hashcmp(cn1->peeled, cn2->peeled);
+}
+
 static inline unsigned int hash_sha1(const unsigned char *sha1)
 {
 	unsigned int hash;

@@ -59,21 +64,10 @@ static inline unsigned int hash_sha1(const unsigned char *sha1)
 
 static inline struct commit_name *find_commit_name(const unsigned char *peeled)
 {
-	struct commit_name *n = lookup_hash(hash_sha1(peeled), &names);
-	while (n && !!hashcmp(peeled, n->peeled))
-		n = n->next;
-	return n;
-}
-
-static int set_util(void *chain, void *data)
-{
-	struct commit_name *n;
-	for (n = chain; n; n = n->next) {
-		struct commit *c = lookup_commit_reference_gently(n->peeled, 1);
-		if (c)
-			c->util = n;
-	}
-	return 0;
+	struct commit_name key;
+	hashmap_entry_init(&key, hash_sha1(peeled), 0);
+	hashcpy(key.peeled, peeled);
+	return hashmap_get(&names, &key);
 }
 
 static int replace_name(struct commit_name *e,

@@ -118,16 +112,10 @@ static void add_to_known_names(const char *path,
 	struct tag *tag = NULL;
 	if (replace_name(e, prio, sha1, &tag)) {
 		if (!e) {
-			void **pos;
 			e = xmalloc(sizeof(struct commit_name));
 			hashcpy(e->peeled, peeled);
-			pos = insert_hash(hash_sha1(peeled), e, &names);
-			if (pos) {
-				e->next = *pos;
-				*pos = e;
-			} else {
-				e->next = NULL;
-			}
+			hashmap_entry_init(e, hash_sha1(peeled), 0);
+			hashmap_add(&names, e);
 			e->path = NULL;
 		}
 		e->tag = tag;

@@ -292,7 +280,14 @@ static void describe(const char *arg, int last_one)
 		fprintf(stderr, _("searching to describe %s\n"), arg);
 
 	if (!have_util) {
-		for_each_hash(&names, set_util, NULL);
+		hashmap_iter iter;
+		struct commit *c;
+		struct commit_name *n = hashmap_iter_first(&names, &iter);
+		for (; n; n = hashmap_iter_next(&iter)) {
+			c = lookup_commit_reference_gently(n->peeled, 1);
+			if (c)
+				c->util = n;
+		}
 		have_util = 1;
 	}
 

@@ -463,9 +458,9 @@ int cmd_describe(int argc, const char **argv, const char *prefix)
 		return cmd_name_rev(args.argc, args.argv, prefix);
 	}
 
-	init_hash(&names);
+	hashmap_init(&names, (hashmap_cmp_fn) commit_name_cmp, 0);
 	for_each_rawref(get_name, NULL);
-	if (!names.nr && !always)
+	if (!names.size && !always)
 		die(_("No names found, cannot describe anything."));
 
 	if (argc == 0) {
Signature · 1 line
1.8.4.8243.gbcbdefd
author
#7 lore raw

PATCH 3/5 diffcore-rename.c: move code around to prepare for the next patch

In reply to Karsten Blees

No actual code changes, just move hash_filespec up and outdent part of find_identical_files.

Signed-off-by Karsten Blees <[email protected]>
---
 diffcore-rename.c | 98 +++++++++++++++++++++++++++----------------------------
 1 file changed, 49 insertions(+), 49 deletions(-)
diffcore-rename.c +49 -49
index 6c7a72f..008a60c 100644
@@ -248,6 +248,18 @@ struct file_similarity {
 	struct file_similarity *next;
 };
 
+static unsigned int hash_filespec(struct diff_filespec *filespec)
+{
+	unsigned int hash;
+	if (!filespec->sha1_valid) {
+		if (diff_populate_filespec(filespec, 0))
+			return 0;
+		hash_sha1_file(filespec->data, filespec->size, "blob", filespec->sha1);
+	}
+	memcpy(&hash, filespec->sha1, sizeof(hash));
+	return hash;
+}
+
 static int find_identical_files(struct file_similarity *src,
 				struct file_similarity *dst,
 				struct diff_options *options)

@@ -258,46 +270,46 @@ static int find_identical_files(struct file_similarity *src,
 	 * Walk over all the destinations ...
 	 */
 	do {
-		struct diff_filespec *target = dst->filespec;
-		struct file_similarity *p, *best;
-		int i = 100, best_score = -1;
-
-		/*
-		 * .. to find the best source match
-		 */
-		best = NULL;
-		for (p = src; p; p = p->next) {
-			int score;
-			struct diff_filespec *source = p->filespec;
-
-			/* False hash collision? */
-			if (hashcmp(source->sha1, target->sha1))
-				continue;
-			/* Non-regular files? If so, the modes must match! */
-			if (!S_ISREG(source->mode) || !S_ISREG(target->mode)) {
-				if (source->mode != target->mode)
-					continue;
-			}
-			/* Give higher scores to sources that haven't been used already */
-			score = !source->rename_used;
-			if (source->rename_used && options->detect_rename != DIFF_DETECT_COPY)
-				continue;
-			score += basename_same(source, target);
-			if (score > best_score) {
-				best = p;
-				best_score = score;
-				if (score == 2)
-					break;
-			}
+	struct diff_filespec *target = dst->filespec;
+	struct file_similarity *p, *best;
+	int i = 100, best_score = -1;
 
-			/* Too many identical alternatives? Pick one */
-			if (!--i)
-				break;
+	/*
+	 * .. to find the best source match
+	 */
+	best = NULL;
+	for (p = src; p; p = p->next) {
+		int score;
+		struct diff_filespec *source = p->filespec;
+
+		/* False hash collision? */
+		if (hashcmp(source->sha1, target->sha1))
+			continue;
+		/* Non-regular files? If so, the modes must match! */
+		if (!S_ISREG(source->mode) || !S_ISREG(target->mode)) {
+			if (source->mode != target->mode)
+				continue;
 		}
-		if (best) {
-			record_rename_pair(dst->index, best->index, MAX_SCORE);
-			renames++;
+		/* Give higher scores to sources that haven't been used already */
+		score = !source->rename_used;
+		if (source->rename_used && options->detect_rename != DIFF_DETECT_COPY)
+			continue;
+		score += basename_same(source, target);
+		if (score > best_score) {
+			best = p;
+			best_score = score;
+			if (score == 2)
+				break;
 		}
+
+		/* Too many identical alternatives? Pick one */
+		if (!--i)
+			break;
+	}
+	if (best) {
+		record_rename_pair(dst->index, best->index, MAX_SCORE);
+		renames++;
+	}
 	} while ((dst = dst->next) != NULL);
 	return renames;
 }

@@ -343,18 +355,6 @@ static int find_same_files(void *ptr, void *data)
 	return ret;
 }
 
-static unsigned int hash_filespec(struct diff_filespec *filespec)
-{
-	unsigned int hash;
-	if (!filespec->sha1_valid) {
-		if (diff_populate_filespec(filespec, 0))
-			return 0;
-		hash_sha1_file(filespec->data, filespec->size, "blob", filespec->sha1);
-	}
-	memcpy(&hash, filespec->sha1, sizeof(hash));
-	return hash;
-}
-
 static void insert_file_table(struct hash_table *table, int src_dst, int index, struct diff_filespec *filespec)
 {
 	void **pos;
Signature · 1 line
1.8.4.8243.gbcbdefd
author
#8 lore raw

PATCH 4/5 diffcore-rename.c: simplify finding exact renames

In reply to Karsten Blees

The find_exact_renames function currently only uses the hash table for grouping, i.e.:

1. add sources
2. add destinations
3. iterate all buckets, per bucket:
4. split sources from destinations
5. iterate destinations, per destination:
6. iterate sources to find best match

This can be simplified by utilizing the lookup functionality of the hash table, i.e.:

1. add sources
2. iterate destinations, per destination:
3. lookup sources matching the current destination
4. iterate sources to find best match

This saves several iterations and file_similarity allocations for the destinations.

Signed-off-by Karsten Blees <[email protected]>
---
 diffcore-rename.c | 75 +++++++++++++++----------------------------------------
 1 file changed, 20 insertions(+), 55 deletions(-)
diffcore-rename.c +20 -55
index 008a60c..82b7975 100644
@@ -243,7 +243,7 @@ static int score_compare(const void *a_, const void *b_)
 }
 
 struct file_similarity {
-	int src_dst, index;
+	int index;
 	struct diff_filespec *filespec;
 	struct file_similarity *next;
 };

@@ -260,25 +260,21 @@ static unsigned int hash_filespec(struct diff_filespec *filespec)
 	return hash;
 }
 
-static int find_identical_files(struct file_similarity *src,
-				struct file_similarity *dst,
+static int find_identical_files(struct hash_table *srcs,
+				int dst_index,
 				struct diff_options *options)
 {
 	int renames = 0;
 
-	/*
-	 * Walk over all the destinations ...
-	 */
-	do {
-	struct diff_filespec *target = dst->filespec;
+	struct diff_filespec *target = rename_dst[dst_index].two;
 	struct file_similarity *p, *best;
 	int i = 100, best_score = -1;
 
 	/*
-	 * .. to find the best source match
+	 * Find the best source match for specified destination.
 	 */
 	best = NULL;
-	for (p = src; p; p = p->next) {
+	for (p = lookup_hash(hash_filespec(target), srcs); p; p = p->next) {
 		int score;
 		struct diff_filespec *source = p->filespec;
 

@@ -307,61 +303,28 @@ static int find_identical_files(struct file_similarity *src,
 			break;
 	}
 	if (best) {
-		record_rename_pair(dst->index, best->index, MAX_SCORE);
+		record_rename_pair(dst_index, best->index, MAX_SCORE);
 		renames++;
 	}
-	} while ((dst = dst->next) != NULL);
 	return renames;
 }
 
-static void free_similarity_list(struct file_similarity *p)
+static int free_similarity_list(void *p, void *unused)
 {
 	while (p) {
 		struct file_similarity *entry = p;
-		p = p->next;
+		p = entry->next;
 		free(entry);
 	}
+	return 0;
 }
 
-static int find_same_files(void *ptr, void *data)
-{
-	int ret;
-	struct file_similarity *p = ptr;
-	struct file_similarity *src = NULL, *dst = NULL;
-	struct diff_options *options = data;
-
-	/* Split the hash list up into sources and destinations */
-	do {
-		struct file_similarity *entry = p;
-		p = p->next;
-		if (entry->src_dst < 0) {
-			entry->next = src;
-			src = entry;
-		} else {
-			entry->next = dst;
-			dst = entry;
-		}
-	} while (p);
-
-	/*
-	 * If we have both sources *and* destinations, see if
-	 * we can match them up
-	 */
-	ret = (src && dst) ? find_identical_files(src, dst, options) : 0;
-
-	/* Free the hashes and return the number of renames found */
-	free_similarity_list(src);
-	free_similarity_list(dst);
-	return ret;
-}
-
-static void insert_file_table(struct hash_table *table, int src_dst, int index, struct diff_filespec *filespec)
+static void insert_file_table(struct hash_table *table, int index, struct diff_filespec *filespec)
 {
 	void **pos;
 	unsigned int hash;
 	struct file_similarity *entry = xmalloc(sizeof(*entry));
 
-	entry->src_dst = src_dst;
 	entry->index = index;
 	entry->filespec = filespec;
 	entry->next = NULL;

@@ -385,24 +348,26 @@ static void insert_file_table(struct hash_table *table, int src_dst, int index,
  */
 static int find_exact_renames(struct diff_options *options)
 {
-	int i;
+	int i, renames;
 	struct hash_table file_table;
 
+	/* Add all sources to the hash table */
 	init_hash(&file_table);
-	preallocate_hash(&file_table, rename_src_nr + rename_dst_nr);
+	preallocate_hash(&file_table, rename_src_nr);
 	for (i = 0; i < rename_src_nr; i++)
-		insert_file_table(&file_table, -1, i, rename_src[i].p->one);
+		insert_file_table(&file_table, i, rename_src[i].p->one);
 
+	/* Walk the destinations and find best source match */
 	for (i = 0; i < rename_dst_nr; i++)
-		insert_file_table(&file_table, 1, i, rename_dst[i].two);
+		renames += find_identical_files(&file_table, i, options);
 
-	/* Find the renames */
-	i = for_each_hash(&file_table, find_same_files, options);
+	/* Free source file_similarity chains */
+	for_each_hash(&file_table, free_similarity_list, options);
 
 	/* .. and free the hash data structure */
 	free_hash(&file_table);
 
-	return i;
+	return renames;
 }
 
 #define NUM_CANDIDATE_PER_DST 4
Signature · 1 line
1.8.4.8243.gbcbdefd
author
#9 lore raw

PATCH 5/5 diffcore-rename.c: use new hash map implementation

In reply to Karsten Blees
Signed-off-by Karsten Blees <[email protected]>
---
 diffcore-rename.c | 48 +++++++++++++-----------------------------------
 1 file changed, 13 insertions(+), 35 deletions(-)
diffcore-rename.c +13 -35
index 82b7975..6271af9 100644
@@ -4,7 +4,7 @@
 #include "cache.h"
 #include "diff.h"
 #include "diffcore.h"
-#include "hash.h"
+#include "hashmap.h"
 #include "progress.h"
 
 /* Table of rename/copy destinations */

@@ -243,9 +243,9 @@ static int score_compare(const void *a_, const void *b_)
 }
 
 struct file_similarity {
+	hashmap_entry entry;
 	int index;
 	struct diff_filespec *filespec;
-	struct file_similarity *next;
 };
 
 static unsigned int hash_filespec(struct diff_filespec *filespec)

@@ -260,21 +260,22 @@ static unsigned int hash_filespec(struct diff_filespec *filespec)
 	return hash;
 }
 
-static int find_identical_files(struct hash_table *srcs,
+static int find_identical_files(hashmap *srcs,
 				int dst_index,
 				struct diff_options *options)
 {
 	int renames = 0;
 
 	struct diff_filespec *target = rename_dst[dst_index].two;
-	struct file_similarity *p, *best;
+	struct file_similarity *p, *best, dst;
 	int i = 100, best_score = -1;
 
 	/*
 	 * Find the best source match for specified destination.
 	 */
 	best = NULL;
-	for (p = lookup_hash(hash_filespec(target), srcs); p; p = p->next) {
+	hashmap_entry_init(&dst, hash_filespec(target), 0);
+	for (p = hashmap_get(srcs, &dst); p; p = hashmap_get_next(srcs, p)) {
 		int score;
 		struct diff_filespec *source = p->filespec;
 

@@ -309,34 +310,15 @@ static int find_identical_files(struct hash_table *srcs,
 	return renames;
 }
 
-static int free_similarity_list(void *p, void *unused)
+static void insert_file_table(hashmap *table, int index, struct diff_filespec *filespec)
 {
-	while (p) {
-		struct file_similarity *entry = p;
-		p = entry->next;
-		free(entry);
-	}
-	return 0;
-}
-
-static void insert_file_table(struct hash_table *table, int index, struct diff_filespec *filespec)
-{
-	void **pos;
-	unsigned int hash;
 	struct file_similarity *entry = xmalloc(sizeof(*entry));
 
 	entry->index = index;
 	entry->filespec = filespec;
-	entry->next = NULL;
-
-	hash = hash_filespec(filespec);
-	pos = insert_hash(hash, entry, table);
 
-	/* We already had an entry there? */
-	if (pos) {
-		entry->next = *pos;
-		*pos = entry;
-	}
+	hashmap_entry_init(entry, hash_filespec(filespec), 0);
+	hashmap_add(table, entry);
 }
 
 /*

@@ -349,11 +331,10 @@ static void insert_file_table(struct hash_table *table, int index, struct diff_f
 static int find_exact_renames(struct diff_options *options)
 {
 	int i, renames;
-	struct hash_table file_table;
+	hashmap file_table;
 
 	/* Add all sources to the hash table */
-	init_hash(&file_table);
-	preallocate_hash(&file_table, rename_src_nr);
+	hashmap_init(&file_table, NULL, rename_src_nr);
 	for (i = 0; i < rename_src_nr; i++)
 		insert_file_table(&file_table, i, rename_src[i].p->one);
 

@@ -361,11 +342,8 @@ static int find_exact_renames(struct diff_options *options)
 	for (i = 0; i < rename_dst_nr; i++)
 		renames += find_identical_files(&file_table, i, options);
 
-	/* Free source file_similarity chains */
-	for_each_hash(&file_table, free_similarity_list, options);
-
-	/* .. and free the hash data structure */
-	free_hash(&file_table);
+	/* Free the hash data structure and entries */
+	hashmap_free(&file_table, free);
 
 	return renames;
 }
Signature · 1 line
1.8.4.8243.gbcbdefd
author
#10 lore raw

v2 cover New hash table implementation

In reply to Karsten Blees

Also here: https://github.com/kblees/git/tree/kb/hashmap-v2

Changes since initial version:
- removed struct typedefs
- clarified documentation of hashmap_entry
- renamed find_entry -> find_entry_ptr
- added performance tests for lookup

I've also tried to resize the table based on the number of used buckets (instead of total entries). However, this doesn't work with hash functions that produce 'gaps'. E.g. a hash function that returns only even numbers would fill only every second bucket (i.e. max. 50% buckets used), and the 80% resize threshold is never reached.

Regarding performance, I have to admit that the difference between the two implementations is far greater than I had anticipated. The following times (in seconds) are from Linux x64 (Debian Sarge) on a Core i7 860 @2.8GHz. All tests have been run with 1,000 rounds of 100,000 entries each.

The 'get 10% hits' test does 100,000 lookups on a table with 10,000 entries (i.e. 90% unsuccessful lookups).

The rows denote different hash functions with different qualities:
- FNV: FNV-1 hash on stringified loop counter (i.e. fnv1(itoa(i))), as an example of a high quality / low collision hash
- i: just the loop counter (i.e. 0, 1, 2,...), guaranteed collision free
- i/10: every 10 entries share the same hash code, lots of collisions

The i and i/10 tests show that open addressing suffers badly from clustering, i.e. with adjacent hash codes, it degrades to linear search. The *2 versions provide for some space between used buckets to better compare it to the chaining version.

        |       add        |  get 100% hits  |    get 10% hits
        |  hash  | hashmap | hash  | hashmap |  hash   | hashmap
--------+--------+---------+-------+---------+---------+--------
FNV     | 14.815 |   2.345 | 3.059 |   1.642 |   4.085 |   0.976
FNV  x2 | 14.409 |   2.706 | 2.888 |   1.959 |   3.905 |   1.393
i       |  7.432 |   1.593 | 1.364 |   1.142 | 413.023 |   0.589
i    x2 |  9.169 |   1.866 | 1.427 |   1.163 |   0.757 |   0.670
i/10    |  1.800 |   1.555 | 5.365 |   6.465 |  32.918 |   1.052
i/10 x2 |  1.892 |   1.555 | 5.386 |   6.474 |   1.123 |   1.206

Tests can be reproduced with 'time echo "perfhash[map] <method> 1000" | ./test-hashmap', see test-hashmap.c for definition of method flags.

Karsten Blees (5):
add a hashtable implementation that supports O(1) removal buitin/describe.c: use new hash map implementation diffcore-rename.c: move code around to prepare for the next patch diffcore-rename.c: simplify finding exact renames diffcore-rename.c: use new hash map implementation

 Makefile           |   3 +
 builtin/describe.c |  53 ++++----
 diffcore-rename.c  | 185 ++++++++++------------------
 hashmap.c          | 211 +++++++++++++++++++++++++++++++
 hashmap.h          | 200 ++++++++++++++++++++++++++++++
 t/t0011-hashmap.sh | 236 +++++++++++++++++++++++++++++++++++
 test-hashmap.c     | 354 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 1092 insertions(+), 150 deletions(-)
 create mode 100644 hashmap.c
 create mode 100644 hashmap.h
 create mode 100755 t/t0011-hashmap.sh
 create mode 100644 test-hashmap.c

---
git diff kb/hashmap..kb/hashmap-v2:

builtin/describe.c +3 -3
index bbc7159..5db5d89 100644
@@ -25,7 +25,7 @@ static int longformat;
 static int first_parent;
 static int abbrev = -1; /* unspecified */
 static int max_candidates = 10;
-static hashmap names;
+static struct hashmap names;
 static int have_util;
 static const char *pattern;
 static int always;

@@ -38,7 +38,7 @@ static const char *diff_index_args[] = {
 
 
 struct commit_name {
-	hashmap_entry entry;
+	struct hashmap_entry entry;
 	unsigned char peeled[20];
 	struct tag *tag;
 	unsigned prio:2; /* annotated tag = 2, tag = 1, head = 0 */

@@ -280,7 +280,7 @@ static void describe(const char *arg, int last_one)
 		fprintf(stderr, _("searching to describe %s\n"), arg);
 
 	if (!have_util) {
-		hashmap_iter iter;
+		struct hashmap_iter iter;
 		struct commit *c;
 		struct commit_name *n = hashmap_iter_first(&names, &iter);
 		for (; n; n = hashmap_iter_next(&iter)) {
diffcore-rename.c +4 -4
index 6271af9..2e70d31 100644
@@ -243,7 +243,7 @@ static int score_compare(const void *a_, const void *b_)
 }
 
 struct file_similarity {
-	hashmap_entry entry;
+	struct hashmap_entry entry;
 	int index;
 	struct diff_filespec *filespec;
 };

@@ -260,7 +260,7 @@ static unsigned int hash_filespec(struct diff_filespec *filespec)
 	return hash;
 }
 
-static int find_identical_files(hashmap *srcs,
+static int find_identical_files(struct hashmap *srcs,
 				int dst_index,
 				struct diff_options *options)
 {

@@ -310,7 +310,7 @@ static int find_identical_files(hashmap *srcs,
 	return renames;
 }
 
-static void insert_file_table(hashmap *table, int index, struct diff_filespec *filespec)
+static void insert_file_table(struct hashmap *table, int index, struct diff_filespec *filespec)
 {
 	struct file_similarity *entry = xmalloc(sizeof(*entry));
 

@@ -331,7 +331,7 @@ static void insert_file_table(hashmap *table, int index, struct diff_filespec *f
 static int find_exact_renames(struct diff_options *options)
 {
 	int i, renames;
-	hashmap file_table;
+	struct hashmap file_table;
 
 	/* Add all sources to the hash table */
 	hashmap_init(&file_table, NULL, rename_src_nr);
hashmap.c +32 -31

157 lines not on this page · raw message

hashmap.h +28 -28

151 lines not on this page · raw message

test-hashmap.c +145 -49

315 lines not on this page · raw message

#11 lore raw
Quoted 23 lines · Karsten Blees

Regarding performance, I have to admit that the difference between the two implementations is far greater than I had anticipated. The following times (in seconds) are from Linux x64 (Debian Sarge) on a Core i7 860 @2.8GHz. All tests have been run with 1,000 rounds of 100,000 entries each.

The 'get 10% hits' test does 100,000 lookups on a table with 10,000 entries (i.e. 90% unsuccessful lookups).

The rows denote different hash functions with different qualities:
- FNV: FNV-1 hash on stringified loop counter (i.e. fnv1(itoa(i))), as an example of a high quality / low collision hash
- i: just the loop counter (i.e. 0, 1, 2,...), guaranteed collision free
- i/10: every 10 entries share the same hash code, lots of collisions

The i and i/10 tests show that open addressing suffers badly from clustering, i.e. with adjacent hash codes, it degrades to linear search. The *2 versions provide for some space between used buckets to better compare it to the chaining version.

        |       add        |  get 100% hits  |    get 10% hits
        |  hash  | hashmap | hash  | hashmap |  hash   | hashmap
--------+--------+---------+-------+---------+---------+--------
FNV     | 14.815 |   2.345 | 3.059 |   1.642 |   4.085 |   0.976
FNV  x2 | 14.409 |   2.706 | 2.888 |   1.959 |   3.905 |   1.393
i       |  7.432 |   1.593 | 1.364 |   1.142 | 413.023 |   0.589
i    x2 |  9.169 |   1.866 | 1.427 |   1.163 |   0.757 |   0.670
i/10    |  1.800 |   1.555 | 5.365 |   6.465 |  32.918 |   1.052
i/10 x2 |  1.892 |   1.555 | 5.386 |   6.474 |   1.123 |   1.206
Quoted 2 lines

Tests can be reproduced with 'time echo "perfhash[map] <method> 1000" | ./test-hashmap', see test-hashmap.c for definition of method flags.

So I did this improved hash implementation a few months back. Although I could do a test like this and see an improvement, I failed to see an improvement in actual git usage.

Hopefully it was just me doing something wrong, but I abandonned the idea of a better hashmap since I couldn't see any major performance boost using git and the current implementation is really simple and easy to maintain.

So my question to you is, does your hashmap speed up git? And does it speed it up enough to justify that your implementation is the double amount of code than the current?

Signature · 5 lines
Med vänliga hälsningar
Fredrik Gustafsson

tel: 0733-608274
e-post: [email protected]
author
#12 lore raw

PATCH v2 1/5 add a hashtable implementation that supports O(1) removal

In reply to Karsten Blees

The existing hashtable implementation (in hash.[ch]) uses open addressing (i.e. resolve hash collisions by distributing entries across the table). Thus, removal is difficult to implement with less than O(n) complexity. Resolving collisions of entries with identical hashes (e.g. via chaining) is left to the client code.

Add a hashtable implementation that supports O(1) removal and is slightly easier to use due to builtin entry chaining.

Supports all basic operations init, free, get, add, remove and iteration.

Also includes ready-to-use hash functions based on the public domain FNV-1 algorithm (http://www.isthe.com/chongo/tech/comp/fnv).

The per-entry data structure (hashmap_entry) is piggybacked in front of the client's data structure to save memory. See test-hashmap.c for usage examples.

The hashtable is resized by a factor of four when 80% full. With these settings, average memory consumption is about 2/3 of hash.[ch], and insertion is about twice as fast due to less frequent resizing.

Lookups are also slightly faster, because entries are strictly confined to their bucket (i.e. no data of other buckets needs to be traversed).

Signed-off-by Karsten Blees <[email protected]>
---
 Makefile           |   3 +
 hashmap.c          | 211 +++++++++++++++++++++++++++++++
 hashmap.h          | 200 ++++++++++++++++++++++++++++++
 t/t0011-hashmap.sh | 236 +++++++++++++++++++++++++++++++++++
 test-hashmap.c     | 354 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 1004 insertions(+)
 create mode 100644 hashmap.c
 create mode 100644 hashmap.h
 create mode 100755 t/t0011-hashmap.sh
 create mode 100644 test-hashmap.c
Makefile +3 -0
index 3588ca1..e6ad011 100644
@@ -562,6 +562,7 @@ TEST_PROGRAMS_NEED_X += test-date
 TEST_PROGRAMS_NEED_X += test-delta
 TEST_PROGRAMS_NEED_X += test-dump-cache-tree
 TEST_PROGRAMS_NEED_X += test-genrandom
+TEST_PROGRAMS_NEED_X += test-hashmap
 TEST_PROGRAMS_NEED_X += test-index-version
 TEST_PROGRAMS_NEED_X += test-line-buffer
 TEST_PROGRAMS_NEED_X += test-match-trees

@@ -681,6 +682,7 @@ LIB_H += gpg-interface.h
 LIB_H += graph.h
 LIB_H += grep.h
 LIB_H += hash.h
+LIB_H += hashmap.h
 LIB_H += help.h
 LIB_H += http.h
 LIB_H += kwset.h

@@ -811,6 +813,7 @@ LIB_OBJS += gpg-interface.o
 LIB_OBJS += graph.o
 LIB_OBJS += grep.o
 LIB_OBJS += hash.o
+LIB_OBJS += hashmap.o
 LIB_OBJS += help.o
 LIB_OBJS += hex.o
 LIB_OBJS += ident.o
hashmap.c new file +211 -0

211 lines not on this page · raw message

hashmap.h new file +200 -0

200 lines not on this page · raw message

t/t0011-hashmap.sh new file +236 -0

236 lines not on this page · raw message

test-hashmap.c new file +354 -0

354 lines not on this page · raw message

Signature · 1 line
1.8.4.5.gef01589.dirty
author
#13 lore raw

PATCH v2 2/5 buitin/describe.c: use new hash map implementation

In reply to Karsten Blees
Signed-off-by Karsten Blees <[email protected]>
---
 builtin/describe.c | 53 ++++++++++++++++++++++++-----------------------------
 1 file changed, 24 insertions(+), 29 deletions(-)
builtin/describe.c +24 -29
index 7d73722..5db5d89 100644
@@ -6,7 +6,7 @@
 #include "exec_cmd.h"
 #include "parse-options.h"
 #include "diff.h"
-#include "hash.h"
+#include "hashmap.h"
 #include "argv-array.h"
 
 #define SEEN		(1u<<0)

@@ -25,7 +25,7 @@ static int longformat;
 static int first_parent;
 static int abbrev = -1; /* unspecified */
 static int max_candidates = 10;
-static struct hash_table names;
+static struct hashmap names;
 static int have_util;
 static const char *pattern;
 static int always;

@@ -38,7 +38,7 @@ static const char *diff_index_args[] = {
 
 
 struct commit_name {
-	struct commit_name *next;
+	struct hashmap_entry entry;
 	unsigned char peeled[20];
 	struct tag *tag;
 	unsigned prio:2; /* annotated tag = 2, tag = 1, head = 0 */

@@ -50,6 +50,11 @@ static const char *prio_names[] = {
 	"head", "lightweight", "annotated",
 };
 
+static int commit_name_cmp(struct commit_name *cn1, struct commit_name *cn2)
+{
+	return hashcmp(cn1->peeled, cn2->peeled);
+}
+
 static inline unsigned int hash_sha1(const unsigned char *sha1)
 {
 	unsigned int hash;

@@ -59,21 +64,10 @@ static inline unsigned int hash_sha1(const unsigned char *sha1)
 
 static inline struct commit_name *find_commit_name(const unsigned char *peeled)
 {
-	struct commit_name *n = lookup_hash(hash_sha1(peeled), &names);
-	while (n && !!hashcmp(peeled, n->peeled))
-		n = n->next;
-	return n;
-}
-
-static int set_util(void *chain, void *data)
-{
-	struct commit_name *n;
-	for (n = chain; n; n = n->next) {
-		struct commit *c = lookup_commit_reference_gently(n->peeled, 1);
-		if (c)
-			c->util = n;
-	}
-	return 0;
+	struct commit_name key;
+	hashmap_entry_init(&key, hash_sha1(peeled), 0);
+	hashcpy(key.peeled, peeled);
+	return hashmap_get(&names, &key);
 }
 
 static int replace_name(struct commit_name *e,

@@ -118,16 +112,10 @@ static void add_to_known_names(const char *path,
 	struct tag *tag = NULL;
 	if (replace_name(e, prio, sha1, &tag)) {
 		if (!e) {
-			void **pos;
 			e = xmalloc(sizeof(struct commit_name));
 			hashcpy(e->peeled, peeled);
-			pos = insert_hash(hash_sha1(peeled), e, &names);
-			if (pos) {
-				e->next = *pos;
-				*pos = e;
-			} else {
-				e->next = NULL;
-			}
+			hashmap_entry_init(e, hash_sha1(peeled), 0);
+			hashmap_add(&names, e);
 			e->path = NULL;
 		}
 		e->tag = tag;

@@ -292,7 +280,14 @@ static void describe(const char *arg, int last_one)
 		fprintf(stderr, _("searching to describe %s\n"), arg);
 
 	if (!have_util) {
-		for_each_hash(&names, set_util, NULL);
+		struct hashmap_iter iter;
+		struct commit *c;
+		struct commit_name *n = hashmap_iter_first(&names, &iter);
+		for (; n; n = hashmap_iter_next(&iter)) {
+			c = lookup_commit_reference_gently(n->peeled, 1);
+			if (c)
+				c->util = n;
+		}
 		have_util = 1;
 	}
 

@@ -463,9 +458,9 @@ int cmd_describe(int argc, const char **argv, const char *prefix)
 		return cmd_name_rev(args.argc, args.argv, prefix);
 	}
 
-	init_hash(&names);
+	hashmap_init(&names, (hashmap_cmp_fn) commit_name_cmp, 0);
 	for_each_rawref(get_name, NULL);
-	if (!names.nr && !always)
+	if (!names.size && !always)
 		die(_("No names found, cannot describe anything."));
 
 	if (argc == 0) {
Signature · 1 line
1.8.4.5.gef01589.dirty
author
#14 lore raw

PATCH v2 3/5 diffcore-rename.c: move code around to prepare for the next patch

In reply to Karsten Blees

No actual code changes, just move hash_filespec up and outdent part of find_identical_files.

Signed-off-by Karsten Blees <[email protected]>
---
 diffcore-rename.c | 98 +++++++++++++++++++++++++++----------------------------
 1 file changed, 49 insertions(+), 49 deletions(-)
diffcore-rename.c +49 -49
index 6c7a72f..008a60c 100644
@@ -248,6 +248,18 @@ struct file_similarity {
 	struct file_similarity *next;
 };
 
+static unsigned int hash_filespec(struct diff_filespec *filespec)
+{
+	unsigned int hash;
+	if (!filespec->sha1_valid) {
+		if (diff_populate_filespec(filespec, 0))
+			return 0;
+		hash_sha1_file(filespec->data, filespec->size, "blob", filespec->sha1);
+	}
+	memcpy(&hash, filespec->sha1, sizeof(hash));
+	return hash;
+}
+
 static int find_identical_files(struct file_similarity *src,
 				struct file_similarity *dst,
 				struct diff_options *options)

@@ -258,46 +270,46 @@ static int find_identical_files(struct file_similarity *src,
 	 * Walk over all the destinations ...
 	 */
 	do {
-		struct diff_filespec *target = dst->filespec;
-		struct file_similarity *p, *best;
-		int i = 100, best_score = -1;
-
-		/*
-		 * .. to find the best source match
-		 */
-		best = NULL;
-		for (p = src; p; p = p->next) {
-			int score;
-			struct diff_filespec *source = p->filespec;
-
-			/* False hash collision? */
-			if (hashcmp(source->sha1, target->sha1))
-				continue;
-			/* Non-regular files? If so, the modes must match! */
-			if (!S_ISREG(source->mode) || !S_ISREG(target->mode)) {
-				if (source->mode != target->mode)
-					continue;
-			}
-			/* Give higher scores to sources that haven't been used already */
-			score = !source->rename_used;
-			if (source->rename_used && options->detect_rename != DIFF_DETECT_COPY)
-				continue;
-			score += basename_same(source, target);
-			if (score > best_score) {
-				best = p;
-				best_score = score;
-				if (score == 2)
-					break;
-			}
+	struct diff_filespec *target = dst->filespec;
+	struct file_similarity *p, *best;
+	int i = 100, best_score = -1;
 
-			/* Too many identical alternatives? Pick one */
-			if (!--i)
-				break;
+	/*
+	 * .. to find the best source match
+	 */
+	best = NULL;
+	for (p = src; p; p = p->next) {
+		int score;
+		struct diff_filespec *source = p->filespec;
+
+		/* False hash collision? */
+		if (hashcmp(source->sha1, target->sha1))
+			continue;
+		/* Non-regular files? If so, the modes must match! */
+		if (!S_ISREG(source->mode) || !S_ISREG(target->mode)) {
+			if (source->mode != target->mode)
+				continue;
 		}
-		if (best) {
-			record_rename_pair(dst->index, best->index, MAX_SCORE);
-			renames++;
+		/* Give higher scores to sources that haven't been used already */
+		score = !source->rename_used;
+		if (source->rename_used && options->detect_rename != DIFF_DETECT_COPY)
+			continue;
+		score += basename_same(source, target);
+		if (score > best_score) {
+			best = p;
+			best_score = score;
+			if (score == 2)
+				break;
 		}
+
+		/* Too many identical alternatives? Pick one */
+		if (!--i)
+			break;
+	}
+	if (best) {
+		record_rename_pair(dst->index, best->index, MAX_SCORE);
+		renames++;
+	}
 	} while ((dst = dst->next) != NULL);
 	return renames;
 }

@@ -343,18 +355,6 @@ static int find_same_files(void *ptr, void *data)
 	return ret;
 }
 
-static unsigned int hash_filespec(struct diff_filespec *filespec)
-{
-	unsigned int hash;
-	if (!filespec->sha1_valid) {
-		if (diff_populate_filespec(filespec, 0))
-			return 0;
-		hash_sha1_file(filespec->data, filespec->size, "blob", filespec->sha1);
-	}
-	memcpy(&hash, filespec->sha1, sizeof(hash));
-	return hash;
-}
-
 static void insert_file_table(struct hash_table *table, int src_dst, int index, struct diff_filespec *filespec)
 {
 	void **pos;
Signature · 1 line
1.8.4.5.gef01589.dirty
author
#15 lore raw

PATCH v2 4/5 diffcore-rename.c: simplify finding exact renames

In reply to Karsten Blees

The find_exact_renames function currently only uses the hash table for grouping, i.e.:

1. add sources
2. add destinations
3. iterate all buckets, per bucket:
4. split sources from destinations
5. iterate destinations, per destination:
6. iterate sources to find best match

This can be simplified by utilizing the lookup functionality of the hash table, i.e.:

1. add sources
2. iterate destinations, per destination:
3. lookup sources matching the current destination
4. iterate sources to find best match

This saves several iterations and file_similarity allocations for the destinations.

Signed-off-by Karsten Blees <[email protected]>
---
 diffcore-rename.c | 75 +++++++++++++++----------------------------------------
 1 file changed, 20 insertions(+), 55 deletions(-)
diffcore-rename.c +20 -55
index 008a60c..82b7975 100644
@@ -243,7 +243,7 @@ static int score_compare(const void *a_, const void *b_)
 }
 
 struct file_similarity {
-	int src_dst, index;
+	int index;
 	struct diff_filespec *filespec;
 	struct file_similarity *next;
 };

@@ -260,25 +260,21 @@ static unsigned int hash_filespec(struct diff_filespec *filespec)
 	return hash;
 }
 
-static int find_identical_files(struct file_similarity *src,
-				struct file_similarity *dst,
+static int find_identical_files(struct hash_table *srcs,
+				int dst_index,
 				struct diff_options *options)
 {
 	int renames = 0;
 
-	/*
-	 * Walk over all the destinations ...
-	 */
-	do {
-	struct diff_filespec *target = dst->filespec;
+	struct diff_filespec *target = rename_dst[dst_index].two;
 	struct file_similarity *p, *best;
 	int i = 100, best_score = -1;
 
 	/*
-	 * .. to find the best source match
+	 * Find the best source match for specified destination.
 	 */
 	best = NULL;
-	for (p = src; p; p = p->next) {
+	for (p = lookup_hash(hash_filespec(target), srcs); p; p = p->next) {
 		int score;
 		struct diff_filespec *source = p->filespec;
 

@@ -307,61 +303,28 @@ static int find_identical_files(struct file_similarity *src,
 			break;
 	}
 	if (best) {
-		record_rename_pair(dst->index, best->index, MAX_SCORE);
+		record_rename_pair(dst_index, best->index, MAX_SCORE);
 		renames++;
 	}
-	} while ((dst = dst->next) != NULL);
 	return renames;
 }
 
-static void free_similarity_list(struct file_similarity *p)
+static int free_similarity_list(void *p, void *unused)
 {
 	while (p) {
 		struct file_similarity *entry = p;
-		p = p->next;
+		p = entry->next;
 		free(entry);
 	}
+	return 0;
 }
 
-static int find_same_files(void *ptr, void *data)
-{
-	int ret;
-	struct file_similarity *p = ptr;
-	struct file_similarity *src = NULL, *dst = NULL;
-	struct diff_options *options = data;
-
-	/* Split the hash list up into sources and destinations */
-	do {
-		struct file_similarity *entry = p;
-		p = p->next;
-		if (entry->src_dst < 0) {
-			entry->next = src;
-			src = entry;
-		} else {
-			entry->next = dst;
-			dst = entry;
-		}
-	} while (p);
-
-	/*
-	 * If we have both sources *and* destinations, see if
-	 * we can match them up
-	 */
-	ret = (src && dst) ? find_identical_files(src, dst, options) : 0;
-
-	/* Free the hashes and return the number of renames found */
-	free_similarity_list(src);
-	free_similarity_list(dst);
-	return ret;
-}
-
-static void insert_file_table(struct hash_table *table, int src_dst, int index, struct diff_filespec *filespec)
+static void insert_file_table(struct hash_table *table, int index, struct diff_filespec *filespec)
 {
 	void **pos;
 	unsigned int hash;
 	struct file_similarity *entry = xmalloc(sizeof(*entry));
 
-	entry->src_dst = src_dst;
 	entry->index = index;
 	entry->filespec = filespec;
 	entry->next = NULL;

@@ -385,24 +348,26 @@ static void insert_file_table(struct hash_table *table, int src_dst, int index,
  */
 static int find_exact_renames(struct diff_options *options)
 {
-	int i;
+	int i, renames;
 	struct hash_table file_table;
 
+	/* Add all sources to the hash table */
 	init_hash(&file_table);
-	preallocate_hash(&file_table, rename_src_nr + rename_dst_nr);
+	preallocate_hash(&file_table, rename_src_nr);
 	for (i = 0; i < rename_src_nr; i++)
-		insert_file_table(&file_table, -1, i, rename_src[i].p->one);
+		insert_file_table(&file_table, i, rename_src[i].p->one);
 
+	/* Walk the destinations and find best source match */
 	for (i = 0; i < rename_dst_nr; i++)
-		insert_file_table(&file_table, 1, i, rename_dst[i].two);
+		renames += find_identical_files(&file_table, i, options);
 
-	/* Find the renames */
-	i = for_each_hash(&file_table, find_same_files, options);
+	/* Free source file_similarity chains */
+	for_each_hash(&file_table, free_similarity_list, options);
 
 	/* .. and free the hash data structure */
 	free_hash(&file_table);
 
-	return i;
+	return renames;
 }
 
 #define NUM_CANDIDATE_PER_DST 4
Signature · 1 line
1.8.4.5.gef01589.dirty
author
#16 lore raw

PATCH v2 5/5 diffcore-rename.c: use new hash map implementation

In reply to Karsten Blees
Signed-off-by Karsten Blees <[email protected]>
---
 diffcore-rename.c | 48 +++++++++++++-----------------------------------
 1 file changed, 13 insertions(+), 35 deletions(-)
diffcore-rename.c +13 -35
index 82b7975..2e70d31 100644
@@ -4,7 +4,7 @@
 #include "cache.h"
 #include "diff.h"
 #include "diffcore.h"
-#include "hash.h"
+#include "hashmap.h"
 #include "progress.h"
 
 /* Table of rename/copy destinations */

@@ -243,9 +243,9 @@ static int score_compare(const void *a_, const void *b_)
 }
 
 struct file_similarity {
+	struct hashmap_entry entry;
 	int index;
 	struct diff_filespec *filespec;
-	struct file_similarity *next;
 };
 
 static unsigned int hash_filespec(struct diff_filespec *filespec)

@@ -260,21 +260,22 @@ static unsigned int hash_filespec(struct diff_filespec *filespec)
 	return hash;
 }
 
-static int find_identical_files(struct hash_table *srcs,
+static int find_identical_files(struct hashmap *srcs,
 				int dst_index,
 				struct diff_options *options)
 {
 	int renames = 0;
 
 	struct diff_filespec *target = rename_dst[dst_index].two;
-	struct file_similarity *p, *best;
+	struct file_similarity *p, *best, dst;
 	int i = 100, best_score = -1;
 
 	/*
 	 * Find the best source match for specified destination.
 	 */
 	best = NULL;
-	for (p = lookup_hash(hash_filespec(target), srcs); p; p = p->next) {
+	hashmap_entry_init(&dst, hash_filespec(target), 0);
+	for (p = hashmap_get(srcs, &dst); p; p = hashmap_get_next(srcs, p)) {
 		int score;
 		struct diff_filespec *source = p->filespec;
 

@@ -309,34 +310,15 @@ static int find_identical_files(struct hash_table *srcs,
 	return renames;
 }
 
-static int free_similarity_list(void *p, void *unused)
+static void insert_file_table(struct hashmap *table, int index, struct diff_filespec *filespec)
 {
-	while (p) {
-		struct file_similarity *entry = p;
-		p = entry->next;
-		free(entry);
-	}
-	return 0;
-}
-
-static void insert_file_table(struct hash_table *table, int index, struct diff_filespec *filespec)
-{
-	void **pos;
-	unsigned int hash;
 	struct file_similarity *entry = xmalloc(sizeof(*entry));
 
 	entry->index = index;
 	entry->filespec = filespec;
-	entry->next = NULL;
-
-	hash = hash_filespec(filespec);
-	pos = insert_hash(hash, entry, table);
 
-	/* We already had an entry there? */
-	if (pos) {
-		entry->next = *pos;
-		*pos = entry;
-	}
+	hashmap_entry_init(entry, hash_filespec(filespec), 0);
+	hashmap_add(table, entry);
 }
 
 /*

@@ -349,11 +331,10 @@ static void insert_file_table(struct hash_table *table, int index, struct diff_f
 static int find_exact_renames(struct diff_options *options)
 {
 	int i, renames;
-	struct hash_table file_table;
+	struct hashmap file_table;
 
 	/* Add all sources to the hash table */
-	init_hash(&file_table);
-	preallocate_hash(&file_table, rename_src_nr);
+	hashmap_init(&file_table, NULL, rename_src_nr);
 	for (i = 0; i < rename_src_nr; i++)
 		insert_file_table(&file_table, i, rename_src[i].p->one);
 

@@ -361,11 +342,8 @@ static int find_exact_renames(struct diff_options *options)
 	for (i = 0; i < rename_dst_nr; i++)
 		renames += find_identical_files(&file_table, i, options);
 
-	/* Free source file_similarity chains */
-	for_each_hash(&file_table, free_similarity_list, options);
-
-	/* .. and free the hash data structure */
-	free_hash(&file_table);
+	/* Free the hash data structure and entries */
+	hashmap_free(&file_table, free);
 
 	return renames;
 }
Signature · 1 line
1.8.4.5.gef01589.dirty
#17 lore raw
In reply to Karsten Blees

Hi Karsten,

Quoted 11 lines · Karsten Blees
        |       add        |  get 100% hits  |    get 10% hits
        |  hash  | hashmap | hash  | hashmap |  hash   | hashmap
--------+--------+---------+-------+---------+---------+--------
FNV     | 14.815 |   2.345 | 3.059 |   1.642 |   4.085 |   0.976
FNV  x2 | 14.409 |   2.706 | 2.888 |   1.959 |   3.905 |   1.393
i       |  7.432 |   1.593 | 1.364 |   1.142 | 413.023 |   0.589
i    x2 |  9.169 |   1.866 | 1.427 |   1.163 |   0.757 |   0.670
i/10    |  1.800 |   1.555 | 5.365 |   6.465 |  32.918 |   1.052
i/10 x2 |  1.892 |   1.555 | 5.386 |   6.474 |   1.123 |   1.206
Quoted 1 line

Tests can be reproduced with 'time echo "perfhash[map] <method> 1000" | ./test-hashmap', see test-hashmap.c for definition of method flags.

I'm not sure if I'm reading the numbers right, but they look impressive!

If it's not too much trouble, could you put together an API document, along the lines of Documentation/technical/api-hash.txt? I could give a stab at replacing patience and histogram diff's hash implementation with yours.

Signature · 2 lines
Cheers,
Ray Chuan
author
#18 lore raw

Am 24.09.2013 13:16, schrieb Tay Ray Chuan:

Quoted 14 lines

Hi Karsten,

Quoted 11 lines · Karsten Blees
        |       add        |  get 100% hits  |    get 10% hits
        |  hash  | hashmap | hash  | hashmap |  hash   | hashmap
--------+--------+---------+-------+---------+---------+--------
FNV     | 14.815 |   2.345 | 3.059 |   1.642 |   4.085 |   0.976
FNV  x2 | 14.409 |   2.706 | 2.888 |   1.959 |   3.905 |   1.393
i       |  7.432 |   1.593 | 1.364 |   1.142 | 413.023 |   0.589
i    x2 |  9.169 |   1.866 | 1.427 |   1.163 |   0.757 |   0.670
i/10    |  1.800 |   1.555 | 5.365 |   6.465 |  32.918 |   1.052
i/10 x2 |  1.892 |   1.555 | 5.386 |   6.474 |   1.123 |   1.206
Quoted 4 lines
Quoted 1 line

Tests can be reproduced with 'time echo "perfhash[map] <method> 1000" | ./test-hashmap', see test-hashmap.c for definition of method flags.

I'm not sure if I'm reading the numbers right, but they look impressive!

The numbers are for 100 million additions / lookups (1,000 rounds á 100,000 entries). Considering everything else that happens in git, the hash table performance should be insignificant, though.

Quoted 2 lines

If it's not too much trouble, could you put together an API document, along the lines of Documentation/technical/api-hash.txt?

Yes, I had already planned to port the documentation to asciidoc. Although in my experience, API documentation in the header file tends to better stay in sync with code changes (but this only makes real sense with extraction tools such as doxygen).

Quoted 4 lines

I could give
a stab at replacing patience and histogram diff's hash implementation with yours.

Open addressing (i.e. distributing conflicting entries to other buckes) *may* be faster *if* all data fits into the table (i.e. no pointers to the data are used). Scanning such a table (without following pointers) has very high locality and thus may benefit from accessing fewer CPU cache lines. The patience implementation seems to fall into this category (although the entry struct is fairly large, and it also uses the *2 trick to defeat bad hash codes (which wouldn't be necessary with chaining)).

Both patience and histogram use preallocated, fixed-size hash tables, and thus won't benefit from faster inserts (the 'add' performance numbers are for dynamically resized hash tables).

So, converting patience/histogram is probably not worth the trouble for performance reasons alone. If it also simplifies the algorithms and/or reduces memory usage - fine.

Ciao,
Karsten

#19 lore raw
In reply to Karsten Blees
Quoted 1 line · Karsten Blees

Tests can be reproduced with 'time echo "perfhash[map] <method> 1000" | ./test-hashmap', see test-hashmap.c for definition of method flags.

So I'm still curious about the actual performance improvements for git. I runned git describe on the linux kernel with both the old hashmap and this new one:

With old hashmap
================

iveqy@minilla:/srv/slask/linux$ time ../git/git describe
v3.12-rc2-83-g4b97280
real    0m0.236s
user    0m0.216s
sys     0m0.020s
iveqy@minilla:/srv/slask/linux$ time ../git/git describe
v3.12-rc2-83-g4b97280
real    0m0.236s
user    0m0.220s
sys     0m0.016s
iveqy@minilla:/srv/slask/linux$ time ../git/git describe
v3.12-rc2-83-g4b97280
real    0m0.236s
user    0m0.212s
sys     0m0.024s

With new hashmap
================

iveqy@minilla:/srv/slask/linux$ time ../git/git describe
v3.12-rc2-83-g4b97280
real    0m0.236s
user    0m0.216s
sys     0m0.020s
iveqy@minilla:/srv/slask/linux$ time ../git/git describe
v3.12-rc2-83-g4b97280
real    0m0.235s
user    0m0.216s
sys     0m0.020s
iveqy@minilla:/srv/slask/linux$ time ../git/git describe
v3.12-rc2-83-g4b97280
real    0m0.235s
user    0m0.208s
sys     0m0.028s

I can't see any improvements at all here. What do I miss? Am I running git describe in the wrong way? Does linux.git have too few tags to be important?

Signature · 5 lines
Med vänliga hälsningar
Fredrik Gustafsson

tel: 0733-608274
e-post: [email protected]
author
#20 lore raw

Am 26.09.2013 12:16, schrieb Fredrik Gustafsson:

Quoted 7 lines · Karsten Blees
Quoted 1 line

Tests can be reproduced with 'time echo "perfhash[map] <method> 1000" | ./test-hashmap', see test-hashmap.c for definition of method flags.

So I'm still curious about the actual performance improvements for git. I runned git describe on the linux kernel with both the old hashmap and this new one:

Performance was never the primary issue, the intention of the performance tests was to ensure that the new implementation doesn't *slow down* git.

Quoted 1 line

From the original PATCH/RFC:

- O(1) remove
- builtin entry chaining
- ready-to-use FNV-1 hash functions
- unit test
- additions are ~twice as fast
- uses less memory

So, the new implementation allows us to get rid of workarounds such as the CE_UNHASHED flag, duplicate entry chaining code and hash_name() implementations. It also addresses the memory usage FIXME in hash.h.

The simplified API may help prevent bugs such as the broken entry chaining in name-hash.c (see commits 2548183, 395c735, 2092678).

Maybe we can also replace some of the custom hash table implementations in attr.c, decorate.c, fast-import.c and object.c (to name just a few...).

#21 lore raw
In reply to Fredrik Gustafsson
Quoted 7 lines · Fredrik Gustafsson
Quoted 1 line · Karsten Blees

Tests can be reproduced with 'time echo "perfhash[map] <method> 1000" | ./test-hashmap', see test-hashmap.c for definition of method flags.

So I'm still curious about the actual performance improvements for git. I runned git describe on the linux kernel with both the old hashmap and this new one:

Quoted 5 lines

...

I can't see any improvements at all here. What do I miss? Am I running git describe in the wrong way? Does linux.git have too few tags to be important?

I wonder if it makes any difference if there are a lot more refs. I hear gerrit creates a lot but don't know how many. linux-2.6 has ~350 refs. How about increasing the number of refs to 3500 refs?

Signature · 1 line
Duy
#22 lore raw
Quoted 10 lines · Duy Nguyen
Quoted 9 lines · Fredrik Gustafsson
Quoted 1 line · Karsten Blees

Tests can be reproduced with 'time echo "perfhash[map] <method> 1000" | ./test-hashmap', see test-hashmap.c for definition of method flags.

So I'm still curious about the actual performance improvements for git. I runned git describe on the linux kernel with both the old hashmap and this new one:

...

Quoted 7 lines
Quoted 3 lines

I can't see any improvements at all here. What do I miss? Am I running git describe in the wrong way? Does linux.git have too few tags to be important?

I wonder if it makes any difference if there are a lot more refs. I hear gerrit creates a lot but don't know how many. linux-2.6 has ~350 refs. How about increasing the number of refs to 3500 refs?

So I runned:
for i in $(git rev-list HEAD ); do git tag "tag$i" $i ; done

in my linux repo and aborted it after a while:

iveqy@minilla:/srv/slask/linux$ git tag | wc -l
9323

So it's a few at least. Not sure how those artificial tagnames would hurt or improve the performance.

Old hashtable
=============

iveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD 
v3.12-rc2-83-g4b97280
real    0m0.384s
user    0m0.288s
sys     0m0.092s
iveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD 
v3.12-rc2-83-g4b97280
real    0m0.383s
user    0m0.284s
sys     0m0.100s
iveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD 
v3.12-rc2-83-g4b97280
real    0m0.386s
user    0m0.312s
sys     0m0.072s

New hashtable
=============

iveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD 
v3.12-rc2-83-g4b97280
real    0m0.382s
user    0m0.300s
sys     0m0.084s
iveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD 
v3.12-rc2-83-g4b97280
real    0m0.382s
user    0m0.288s
sys     0m0.092s
iveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD 
v3.12-rc2-83-g4b97280
real    0m0.384s
user    0m0.296s
sys     0m0.088s
Signature · 5 lines
Med vänliga hälsningar
Fredrik Gustafsson

tel: 0733-608274
e-post: [email protected]
#23 lore raw
Quoted 68 lines · Fredrik Gustafsson
Quoted 10 lines · Duy Nguyen
Quoted 9 lines · Fredrik Gustafsson
Quoted 1 line · Karsten Blees

Tests can be reproduced with 'time echo "perfhash[map] <method> 1000" | ./test-hashmap', see test-hashmap.c for definition of method flags.

So I'm still curious about the actual performance improvements for git. I runned git describe on the linux kernel with both the old hashmap and this new one:

...

Quoted 7 lines
Quoted 3 lines

I can't see any improvements at all here. What do I miss? Am I running git describe in the wrong way? Does linux.git have too few tags to be important?

I wonder if it makes any difference if there are a lot more refs. I hear gerrit creates a lot but don't know how many. linux-2.6 has ~350 refs. How about increasing the number of refs to 3500 refs?

So I runned:
for i in $(git rev-list HEAD ); do git tag "tag$i" $i ; done

in my linux repo and aborted it after a while:

iveqy@minilla:/srv/slask/linux$ git tag | wc -l
9323

So it's a few at least. Not sure how those artificial tagnames would hurt or improve the performance.

Old hashtable
=============

iveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD
v3.12-rc2-83-g4b97280
real    0m0.384s
user    0m0.288s
sys     0m0.092s
iveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD
v3.12-rc2-83-g4b97280
real    0m0.383s
user    0m0.284s
sys     0m0.100s
iveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD
v3.12-rc2-83-g4b97280
real    0m0.386s
user    0m0.312s
sys     0m0.072s

New hashtable
=============

iveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD
v3.12-rc2-83-g4b97280
real    0m0.382s
user    0m0.300s
sys     0m0.084s
iveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD
v3.12-rc2-83-g4b97280
real    0m0.382s
user    0m0.288s
sys     0m0.092s
iveqy@minilla:/srv/slask/linux$ time ../git/git describe HEAD
v3.12-rc2-83-g4b97280
Quoted 3 lines
real    0m0.384s
user    0m0.296s
sys     0m0.088s

OK I have to say I don't see any justification for more code then.

Signature · 1 line
Duy