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 <pclouds@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 512d0ac5fd2bc0acfb57147a6eb77f61f92b7c7e..6c7a72fbe74e8dd6fca07d2555cdea62c16b8b1e 100644 (file)
--- 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);
        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);
 
        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 b875ce67c49eb39a8ca8ad6a688a334985db0534..1d43ac0ba0120e947e40476946360efbdee80a93 100644 (file)
--- a/hash.h
+++ b/hash.h
@@ -40,4 +40,11 @@ static inline void init_hash(struct hash_table *table)
        table->array = NULL;
 }
 
        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
 #endif

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