[PATCH] Preallocate hash tables when the number of inserts are known in advance

This avoids unnecessary re-allocations and reinsertions. On webkit.git
(i.e. about 182k inserts to the name hash table), this reduces about
100ms out of 3s user time.

Signed-off-by: Nguyễn Thái Ngọc Duy <redacted>
---
 nd/read-directory-recursive-optim reduces the number of input (from
 182k to 11k on webkit) to exclude machinery that all patches in the
 exclude optimization series I posted seem insignificant. So I won't
 repost them for inclusion unless you think it has cleanup values.

 This one is worth doing though. I think keeping "untracked index"
 would help avoid looking up in name-hash, where all user-space CPU
 cycles are spent. But I have nothing to show about that.

 diffcore-rename.c | 1 +
 hash.h            | 7 +++++++
 name-hash.c       | 2 ++
 3 files changed, 10 insertions(+)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 512d0ac..8d3d9bb 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) * 2);
 	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 b875ce6..244d1fe 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 size)
+{
+	assert(table->size == 0 && table->nr == 0 && table->array == NULL);
+	table->size = size;
+	table->array = xcalloc(sizeof(struct hash_table_entry), size);
+}
+
 #endif

diff --git a/name-hash.c b/name-hash.c
index 942c459..12364d1 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 * 2);
 	for (nr = 0; nr < istate->cache_nr; nr++)
 		hash_index_entry(istate, istate->cache[nr]);
 	istate->name_hash_initialized = 1;

-- 
1.8.2.83.gc99314b

On Sun, Mar 17, 2013 at 10:28:06AM +0700, Nguyen Thai Ngoc Duy wrote:

This avoids unnecessary re-allocations and reinsertions. On webkit.git
(i.e. about 182k inserts to the name hash table), this reduces about
100ms out of 3s user time.

Good idea.

I had a similar thought when analyzing the hashing behavior of
pack-objects' "Counting objects..." phase, but it had even less impact
there. The insertions are just drowned out by the number of lookups in
that case.

-Peff