[PATCH v3 11/13] Preallocate hash tables when the number of inserts are known in advance
- From
Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
- Date
- Mar 12, 2013, 13:04 UTC
- Message-ID
- <1363093500-16796-12-git-send-email-pclouds@gmail.com>
- In-Reply-To
- <1363093500-16796-1-git-send-email-pclouds@gmail.com>
This avoids unnecessary allocations and reinsertions. On webkit.git (i.e. about 100k inserts to the name hash table), this reduces about 100ms out of 3s user time.
treat_leading_path: 0.000 0.000 read_directory: 1.299 1.305 +treat_one_path: 0.599 0.599 ++is_excluded: 0.103 0.103 +++prep_exclude: 0.040 0.040 +++matching: 0.036 0.035 ++dir_exist: 0.036 0.035 ++index_name_exists: 0.291 0.292 lazy_init_name_hash: 0.257 0.155 +simplify_away: 0.082 0.083 +dir_add_name: 0.000 0.000
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com> --- diffcore-rename.c | 1 + hash.h | 7 +++++++ name-hash.c | 1 + 3 files changed, 9 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..1287a19 100644 --- a/name-hash.c +++ b/name-hash.c @@ -92,6 +92,7 @@ static void lazy_init_name_hash(struct index_state *istate) if (istate->name_hash_initialized) return; + 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.1.2.536.gf441e6d