{"thread":{"id":"33206","subject":"[PATCH] Preallocate hash tables when the number of inserts are known in advance","startedAt":"2013-03-17T03:28:06Z","lastAt":"2013-03-17T08:51:07Z","messageCount":5,"participants":["Nguyễn Thái Ngọc Duy","Junio C Hamano","Duy Nguyen","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"211479","messageId":"1363490886-29729-1-git-send-email-pclouds@gmail.com","threadId":"33206","inReplyTo":null,"subject":"[PATCH] Preallocate hash tables when the number of inserts are known in advance","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-17T03:28:06Z","receivedAt":"2013-03-17T03:28:06Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"This avoids unnecessary re-allocations and reinsertions. On webkit.git\n(i.e. about 182k inserts to the name hash table), this reduces about\n100ms out of 3s user time.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n nd/read-directory-recursive-optim reduces the number of input (from\n 182k to 11k on webkit) to exclude machinery that all patches in the\n exclude optimization series I posted seem insignificant. So I won't\n repost them for inclusion unless you think it has cleanup values.\n\n This one is worth doing though. I think keeping \"untracked index\"\n would help avoid looking up in name-hash, where all user-space CPU\n cycles are spent. But I have nothing to show about that.\n\n diffcore-rename.c | 1 +\n hash.h | 7 +++++++\n name-hash.c | 2 ++\n 3 files changed, 10 insertions(+)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 512d0ac..8d3d9bb 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -389,6 +389,7 @@ static int find_exact_renames(struct diff_options *options)\n \tstruct hash_table file_table;\n \n \tinit_hash(&file_table);\n+\tpreallocate_hash(&file_table, (rename_src_nr + rename_dst_nr) * 2);\n \tfor (i = 0; i < rename_src_nr; i++)\n \t\tinsert_file_table(&file_table, -1, i, rename_src[i].p->one);\n \ndiff --git a/hash.h b/hash.h\nindex b875ce6..244d1fe 100644\n--- a/hash.h\n+++ b/hash.h\n@@ -40,4 +40,11 @@ static inline void init_hash(struct hash_table *table)\n \ttable->array = NULL;\n }\n \n+static inline void preallocate_hash(struct hash_table *table, unsigned int size)\n+{\n+\tassert(table->size == 0 && table->nr == 0 && table->array == NULL);\n+\ttable->size = size;\n+\ttable->array = xcalloc(sizeof(struct hash_table_entry), size);\n+}\n+\n #endif\ndiff --git a/name-hash.c b/name-hash.c\nindex 942c459..12364d1 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -92,6 +92,8 @@ static void lazy_init_name_hash(struct index_state *istate)\n \n \tif (istate->name_hash_initialized)\n \t\treturn;\n+\tif (istate->cache_nr)\n+\t\tpreallocate_hash(&istate->name_hash, istate->cache_nr * 2);\n \tfor (nr = 0; nr < istate->cache_nr; nr++)\n \t\thash_index_entry(istate, istate->cache[nr]);\n \tistate->name_hash_initialized = 1;\n-- \n1.8.2.83.gc99314b\n"},{"id":"211486","messageId":"7vzjy2si7l.fsf@alter.siamese.dyndns.org","threadId":"33206","inReplyTo":"1363490886-29729-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH] Preallocate hash tables when the number of inserts are known in advance","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-17T05:34:06Z","receivedAt":"2013-03-17T05:34:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nguyễn Thái Ngọc Duy writes:\n\n> This avoids unnecessary re-allocations and reinsertions. On webkit.git\n> (i.e. about 182k inserts to the name hash table), this reduces about\n> 100ms out of 3s user time.\n>\n> Signed-off-by: Nguyễn Thái Ngọc Duy \n\nI think this is a very good idea, but I would prefer the second\nparameter to the \"preallocate\" to be \"expected number of entries\"\nand have the preallocate, which is a part of the hash API, decide\nhow to inflate that number to adjust to the desired load factor of\nthe hash table. We shouldn't have to adjust the caller when the\ninternal implementation of the hash table changes.\n\n> ---\n> nd/read-directory-recursive-optim reduces the number of input (from\n> 182k to 11k on webkit) to exclude machinery that all patches in the\n> exclude optimization series I posted seem insignificant. So I won't\n> repost them for inclusion unless you think it has cleanup values.\n\nSorry, without a pointer, it is unclear what \"exclude optimization\nseries\" you are referring to.\n"},{"id":"211487","messageId":"CACsJy8B=KrmbsqAuvoJTVxmUVYF_fG7XNnKvu3zDVELsWcmtQg@mail.gmail.com","threadId":"33206","inReplyTo":"7vzjy2si7l.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] Preallocate hash tables when the number of inserts are known in advance","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-17T05:39:39Z","receivedAt":"2013-03-17T05:39:39Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Mar 17, 2013 at 12:34 PM, Junio C Hamano wrote:\n> Nguyễn Thái Ngọc Duy writes:\n>\n>> This avoids unnecessary re-allocations and reinsertions. On webkit.git\n>> (i.e. about 182k inserts to the name hash table), this reduces about\n>> 100ms out of 3s user time.\n>>\n>> Signed-off-by: Nguyễn Thái Ngọc Duy \n>\n> I think this is a very good idea, but I would prefer the second\n> parameter to the \"preallocate\" to be \"expected number of entries\"\n> and have the preallocate, which is a part of the hash API, decide\n> how to inflate that number to adjust to the desired load factor of\n> the hash table. We shouldn't have to adjust the caller when the\n> internal implementation of the hash table changes.\n\nOK will do.\n\n>> ---\n>> nd/read-directory-recursive-optim reduces the number of input (from\n>> 182k to 11k on webkit) to exclude machinery that all patches in the\n>> exclude optimization series I posted seem insignificant. So I won't\n>> repost them for inclusion unless you think it has cleanup values.\n>\n> Sorry, without a pointer, it is unclear what \"exclude optimization\n> series\" you are referring to.\n\nhttp://thread.gmane.org/gmane.comp.version-control.git/217697/focus=217950\n-- \nDuy\n"},{"id":"211496","messageId":"7vfvzusg65.fsf@alter.siamese.dyndns.org","threadId":"33206","inReplyTo":"CACsJy8B=KrmbsqAuvoJTVxmUVYF_fG7XNnKvu3zDVELsWcmtQg@mail.gmail.com","subject":"Re: [PATCH] Preallocate hash tables when the number of inserts are known in advance","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-17T06:18:10Z","receivedAt":"2013-03-17T06:18:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen writes:\n\n> On Sun, Mar 17, 2013 at 12:34 PM, Junio C Hamano wrote:\n>> Nguyễn Thái Ngọc Duy writes:\n>>\n>>> This avoids unnecessary re-allocations and reinsertions. On webkit.git\n>>> (i.e. about 182k inserts to the name hash table), this reduces about\n>>> 100ms out of 3s user time.\n>>>\n>>> Signed-off-by: Nguyễn Thái Ngọc Duy \n>>\n>> I think this is a very good idea, but I would prefer the second\n>> parameter to the \"preallocate\" to be \"expected number of entries\"\n>> and have the preallocate, which is a part of the hash API, decide\n>> how to inflate that number to adjust to the desired load factor of\n>> the hash table. We shouldn't have to adjust the caller when the\n>> internal implementation of the hash table changes.\n>\n> OK will do.\n\nI've squashed it in myself, so no need to resend only for this.\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 8d3d9bb..6c7a72f 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -389,7 +389,7 @@ static int find_exact_renames(struct diff_options *options)\n \tstruct hash_table file_table;\n \n \tinit_hash(&file_table);\n-\tpreallocate_hash(&file_table, (rename_src_nr + rename_dst_nr) * 2);\n+\tpreallocate_hash(&file_table, rename_src_nr + rename_dst_nr);\n \tfor (i = 0; i < rename_src_nr; i++)\n \t\tinsert_file_table(&file_table, -1, i, rename_src[i].p->one);\n \ndiff --git a/hash.h b/hash.h\nindex 244d1fe..1d43ac0 100644\n--- a/hash.h\n+++ b/hash.h\n@@ -40,11 +40,11 @@ static inline void init_hash(struct hash_table *table)\n \ttable->array = NULL;\n }\n \n-static inline void preallocate_hash(struct hash_table *table, unsigned int size)\n+static inline void preallocate_hash(struct hash_table *table, unsigned int elts)\n {\n \tassert(table->size == 0 && table->nr == 0 && table->array == NULL);\n-\ttable->size = size;\n-\ttable->array = xcalloc(sizeof(struct hash_table_entry), size);\n+\ttable->size = elts * 2;\n+\ttable->array = xcalloc(sizeof(struct hash_table_entry), table->size);\n }\n \n #endif\ndiff --git a/name-hash.c b/name-hash.c\nindex 90c7b99..2a1f108 100644\n--- a/name-hash.c\n+++ b/name-hash.c\n@@ -93,7 +93,7 @@ static void lazy_init_name_hash(struct index_state *istate)\n \tif (istate->name_hash_initialized)\n \t\treturn;\n \tif (istate->cache_nr)\n-\t\tpreallocate_hash(&istate->name_hash, istate->cache_nr * 2);\n+\t\tpreallocate_hash(&istate->name_hash, istate->cache_nr);\n \tfor (nr = 0; nr < istate->cache_nr; nr++)\n \t\thash_index_entry(istate, istate->cache[nr]);\n \tistate->name_hash_initialized = 1;\n"},{"id":"211509","messageId":"20130317085107.GB934@sigill.intra.peff.net","threadId":"33206","inReplyTo":"1363490886-29729-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH] Preallocate hash tables when the number of inserts are known in advance","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-17T08:51:07Z","receivedAt":"2013-03-17T08:51:07Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Mar 17, 2013 at 10:28:06AM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> This avoids unnecessary re-allocations and reinsertions. On webkit.git\n> (i.e. about 182k inserts to the name hash table), this reduces about\n> 100ms out of 3s user time.\n\nGood idea.\n\nI had a similar thought when analyzing the hashing behavior of\npack-objects' \"Counting objects...\" phase, but it had even less impact\nthere. The insertions are just drowned out by the number of lookups in\nthat case.\n\n-Peff\n"}]}