summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJunio C Hamano <gitster@pobox.com>2013-03-21 14:02:19 -0700
committerJunio C Hamano <gitster@pobox.com>2013-03-21 14:02:19 -0700
commitc241e285e53bc84def85682eeaa265c1cd99cceb (patch)
tree149c957fa2d297c1a2ddb07e5b459f855eb831d5
parent09386fff3370c1833cc8c3ba8bbf70e460fecf17 (diff)
parentc73592812d36ccc7eccfd0489177970d246fa522 (diff)
downloadgit-c241e285e53bc84def85682eeaa265c1cd99cceb.tar.gz
Merge branch 'nd/preallocate-hash'
When we know approximately how many entries we will have in the hash-table, it makes sense to size the hash table to that number from the beginning to avoid unnecessary rehashing. * nd/preallocate-hash: Preallocate hash tables when the number of inserts are known in advance
-rw-r--r--diffcore-rename.c1
-rw-r--r--hash.h7
-rw-r--r--name-hash.c2
3 files changed, 10 insertions, 0 deletions
diff --git a/diffcore-rename.c b/diffcore-rename.c
index 512d0ac5fd..6c7a72fbe7 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -389,6 +389,7 @@ static int find_exact_renames(struct diff_options *options)
struct hash_table file_table;
init_hash(&file_table);
+ preallocate_hash(&file_table, rename_src_nr + rename_dst_nr);
for (i = 0; i < rename_src_nr; i++)
insert_file_table(&file_table, -1, i, rename_src[i].p->one);
diff --git a/hash.h b/hash.h
index b875ce67c4..1d43ac0ba0 100644
--- a/hash.h
+++ b/hash.h
@@ -40,4 +40,11 @@ static inline void init_hash(struct hash_table *table)
table->array = NULL;
}
+static inline void preallocate_hash(struct hash_table *table, unsigned int elts)
+{
+ assert(table->size == 0 && table->nr == 0 && table->array == NULL);
+ table->size = elts * 2;
+ table->array = xcalloc(sizeof(struct hash_table_entry), table->size);
+}
+
#endif
diff --git a/name-hash.c b/name-hash.c
index 942c459622..9bac31a6ab 100644
--- a/name-hash.c
+++ b/name-hash.c
@@ -92,6 +92,8 @@ static void lazy_init_name_hash(struct index_state *istate)
if (istate->name_hash_initialized)
return;
+ if (istate->cache_nr)
+ preallocate_hash(&istate->name_hash, istate->cache_nr);
for (nr = 0; nr < istate->cache_nr; nr++)
hash_index_entry(istate, istate->cache[nr]);
istate->name_hash_initialized = 1;