{"thread":{"id":"46715","subject":"[PATCH v2] merge-recursive: change current file dir string_lists to hashmap","startedAt":"2017-09-06T22:30:42Z","lastAt":"2017-09-06T23:45:06Z","messageCount":2,"participants":["Kevin Willford","Junio C Hamano"],"isPatch":true,"patchVersion":2,"patchTotal":null},"messages":[{"id":"327678","messageId":"20170906222834.77116-1-kewillf@microsoft.com","threadId":"46715","inReplyTo":null,"subject":"[PATCH v2] merge-recursive: change current file dir string_lists to hashmap","fromName":"Kevin Willford","fromEmail":"kewillf@microsoft.com","sentAt":"2017-09-06T22:28:34Z","receivedAt":"2017-09-06T22:30:42Z","isPatch":true,"sender":{"key":"kewillf@microsoft.com","avatar":null},"body":"The code was using two string_lists, one for the directories and\none for the files.  The code never checks the lists independently\nso we should be able to only use one list.  The string_list also\nis a O(log n) for lookup and insertion.  Switching this to use a\nhashmap will give O(1) which will save some time when there are\nmillions of paths that will be checked.\n\nAlso cleaned up a memory leak and method where the return was not\nbeing used.\n\nSigned-off-by: Kevin Willford <kewillf@microsoft.com>\n---\n merge-recursive.c | 76 ++++++++++++++++++++++++++++++++++++++++---------------\n merge-recursive.h |  3 +--\n 2 files changed, 57 insertions(+), 22 deletions(-)\n\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 1494ffdb82..ebfe01017f 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -24,6 +24,31 @@\n #include \"dir.h\"\n #include \"submodule.h\"\n \n+struct path_hashmap_entry {\n+\tstruct hashmap_entry;\n+\tchar path[FLEX_ARRAY];\n+};\n+\n+static int path_hashmap_cmp(const void *cmp_data,\n+\t\t\t    const void *entry,\n+\t\t\t    const void *entry_or_key,\n+\t\t\t    const void *keydata)\n+{\n+\tconst struct path_hashmap_entry *a = entry;\n+\tconst struct path_hashmap_entry *b = entry_or_key;\n+\tconst char *key = keydata;\n+\n+\tif (ignore_case)\n+\t\treturn strcasecmp(a->path, key ? key : b->path);\n+\telse\n+\t\treturn strcmp(a->path, key ? key : b->path);\n+}\n+\n+static unsigned int path_hash(const char *path)\n+{\n+\treturn ignore_case ? strihash(path) : strhash(path);\n+}\n+\n static void flush_output(struct merge_options *o)\n {\n \tif (o->buffer_output < 2 && o->obuf.len) {\n@@ -314,29 +339,25 @@ static int save_files_dirs(const unsigned char *sha1,\n \t\tstruct strbuf *base, const char *path,\n \t\tunsigned int mode, int stage, void *context)\n {\n+\tstruct path_hashmap_entry *entry;\n \tint baselen = base->len;\n \tstruct merge_options *o = context;\n \n \tstrbuf_addstr(base, path);\n \n-\tif (S_ISDIR(mode))\n-\t\tstring_list_insert(&o->current_directory_set, base->buf);\n-\telse\n-\t\tstring_list_insert(&o->current_file_set, base->buf);\n+\tFLEX_ALLOC_MEM(entry, path, base->buf, base->len);\n+\thashmap_entry_init(entry, path_hash(entry->path));\n+\thashmap_add(&o->current_file_dir_set, entry);\n \n \tstrbuf_setlen(base, baselen);\n \treturn (S_ISDIR(mode) ? READ_TREE_RECURSIVE : 0);\n }\n \n-static int get_files_dirs(struct merge_options *o, struct tree *tree)\n+static void get_files_dirs(struct merge_options *o, struct tree *tree)\n {\n-\tint n;\n \tstruct pathspec match_all;\n \tmemset(&match_all, 0, sizeof(match_all));\n-\tif (read_tree_recursive(tree, \"\", 0, 0, &match_all, save_files_dirs, o))\n-\t\treturn 0;\n-\tn = o->current_file_set.nr + o->current_directory_set.nr;\n-\treturn n;\n+\tread_tree_recursive(tree, \"\", 0, 0, &match_all, save_files_dirs, o);\n }\n \n /*\n@@ -646,6 +667,7 @@ static void add_flattened_path(struct strbuf *out, const char *s)\n \n static char *unique_path(struct merge_options *o, const char *path, const char *branch)\n {\n+\tstruct path_hashmap_entry *entry;\n \tstruct strbuf newpath = STRBUF_INIT;\n \tint suffix = 0;\n \tsize_t base_len;\n@@ -654,14 +676,16 @@ static char *unique_path(struct merge_options *o, const char *path, const char *\n \tadd_flattened_path(&newpath, branch);\n \n \tbase_len = newpath.len;\n-\twhile (string_list_has_string(&o->current_file_set, newpath.buf) ||\n-\t       string_list_has_string(&o->current_directory_set, newpath.buf) ||\n+\twhile (hashmap_get_from_hash(&o->current_file_dir_set,\n+\t\t\t\t     path_hash(newpath.buf), newpath.buf) ||\n \t       (!o->call_depth && file_exists(newpath.buf))) {\n \t\tstrbuf_setlen(&newpath, base_len);\n \t\tstrbuf_addf(&newpath, \"_%d\", suffix++);\n \t}\n \n-\tstring_list_insert(&o->current_file_set, newpath.buf);\n+\tFLEX_ALLOC_MEM(entry, path, newpath.buf, newpath.len);\n+\thashmap_entry_init(entry, path_hash(entry->path));\n+\thashmap_add(&o->current_file_dir_set, entry);\n \treturn strbuf_detach(&newpath, NULL);\n }\n \n@@ -1945,8 +1969,14 @@ int merge_trees(struct merge_options *o,\n \tif (unmerged_cache()) {\n \t\tstruct string_list *entries, *re_head, *re_merge;\n \t\tint i;\n-\t\tstring_list_clear(&o->current_file_set, 1);\n-\t\tstring_list_clear(&o->current_directory_set, 1);\n+\t\t/*\n+\t\t * Only need the hashmap while processing entries, so\n+\t\t * initialize it here and free it when we are done running\n+\t\t * through the entries. Keeping it in the merge_options as\n+\t\t * opposed to decaring a local hashmap is for convenience\n+\t\t * so that we don't have to pass it to around.\n+\t\t */\n+\t\thashmap_init(&o->current_file_dir_set, path_hashmap_cmp, NULL, 512);\n \t\tget_files_dirs(o, head);\n \t\tget_files_dirs(o, merge);\n \n@@ -1956,7 +1986,7 @@ int merge_trees(struct merge_options *o,\n \t\tre_merge = get_renames(o, merge, common, head, merge, entries);\n \t\tclean = process_renames(o, re_head, re_merge);\n \t\tif (clean < 0)\n-\t\t\treturn clean;\n+\t\t\tgoto cleanup;\n \t\tfor (i = entries->nr-1; 0 <= i; i--) {\n \t\t\tconst char *path = entries->items[i].string;\n \t\t\tstruct stage_data *e = entries->items[i].util;\n@@ -1964,8 +1994,10 @@ int merge_trees(struct merge_options *o,\n \t\t\t\tint ret = process_entry(o, path, e);\n \t\t\t\tif (!ret)\n \t\t\t\t\tclean = 0;\n-\t\t\t\telse if (ret < 0)\n-\t\t\t\t\treturn ret;\n+\t\t\t\telse if (ret < 0) {\n+\t\t\t\t\tclean = ret;\n+\t\t\t\t\tgoto cleanup;\n+\t\t\t\t}\n \t\t\t}\n \t\t}\n \t\tfor (i = 0; i < entries->nr; i++) {\n@@ -1975,13 +2007,19 @@ int merge_trees(struct merge_options *o,\n \t\t\t\t    entries->items[i].string);\n \t\t}\n \n+cleanup:\n \t\tstring_list_clear(re_merge, 0);\n \t\tstring_list_clear(re_head, 0);\n \t\tstring_list_clear(entries, 1);\n \n+\t\thashmap_free(&o->current_file_dir_set, 1);\n+\n \t\tfree(re_merge);\n \t\tfree(re_head);\n \t\tfree(entries);\n+\n+\t\tif (clean < 0)\n+\t\t\treturn clean;\n \t}\n \telse\n \t\tclean = 1;\n@@ -2177,8 +2215,6 @@ void init_merge_options(struct merge_options *o)\n \tif (o->verbosity >= 5)\n \t\to->buffer_output = 0;\n \tstrbuf_init(&o->obuf, 0);\n-\tstring_list_init(&o->current_file_set, 1);\n-\tstring_list_init(&o->current_directory_set, 1);\n \tstring_list_init(&o->df_conflict_file_set, 1);\n }\n \ndiff --git a/merge-recursive.h b/merge-recursive.h\nindex 735343b413..80d69d1401 100644\n--- a/merge-recursive.h\n+++ b/merge-recursive.h\n@@ -25,8 +25,7 @@ struct merge_options {\n \tint show_rename_progress;\n \tint call_depth;\n \tstruct strbuf obuf;\n-\tstruct string_list current_file_set;\n-\tstruct string_list current_directory_set;\n+\tstruct hashmap current_file_dir_set;\n \tstruct string_list df_conflict_file_set;\n };\n \n-- \n2.14.1.327.g2b87382360.dirty\n\n"},{"id":"327681","messageId":"xmqqmv672xzb.fsf@gitster.mtv.corp.google.com","threadId":"46715","inReplyTo":"20170906222834.77116-1-kewillf@microsoft.com","subject":"Re: [PATCH v2] merge-recursive: change current file dir string_lists to hashmap","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-09-06T23:44:56Z","receivedAt":"2017-09-06T23:45:06Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kevin Willford <kewillf@microsoft.com> writes:\n\n> The code was using two string_lists, one for the directories and\n> one for the files.  The code never checks the lists independently\n> so we should be able to only use one list.  The string_list also\n> is a O(log n) for lookup and insertion.  Switching this to use a\n> hashmap will give O(1) which will save some time when there are\n> millions of paths that will be checked.\n>\n> Also cleaned up a memory leak and method where the return was not\n> being used.\n>\n> Signed-off-by: Kevin Willford <kewillf@microsoft.com>\n> ---\n>  merge-recursive.c | 76 ++++++++++++++++++++++++++++++++++++++++---------------\n>  merge-recursive.h |  3 +--\n>  2 files changed, 57 insertions(+), 22 deletions(-)\n>\n> diff --git a/merge-recursive.c b/merge-recursive.c\n> index 1494ffdb82..ebfe01017f 100644\n> --- a/merge-recursive.c\n> +++ b/merge-recursive.c\n> @@ -24,6 +24,31 @@\n>  #include \"dir.h\"\n>  #include \"submodule.h\"\n>  \n> +struct path_hashmap_entry {\n> +\tstruct hashmap_entry;\n\nYou seem to have lost the squash you privately agreed to that is\nneeded in order to make it compile?\n"}]}