{"thread":{"id":"55781","subject":"[PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative","startedAt":"2021-05-27T08:37:27Z","lastAt":"2021-06-08T16:13:07Z","messageCount":39,"participants":["Elijah Newren via GitGitGadget","René Scharfe","Elijah Newren","Taylor Blau","Derrick Stolee","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"425657","messageId":"5055dfce32815c8c8ec250457df389d4cd02ee12.1622104642.git.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.git.1622104642.gitgitgadget@gmail.com","subject":"[PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-05-27T08:37:17Z","receivedAt":"2021-05-27T08:37:27Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nGathering accumulated times from trace2 output on the mega-renames\ntestcase, I saw the following timings (where I'm only showing a few\nlines to highlight the portions of interest):\n\n 10.120 : label:incore_nonrecursive\n 4.462 : ..label:process_entries\n 3.143 : ....label:process_entries setup\n 2.988 : ......label:plist special sort\n 1.305 : ....label:processing\n 2.604 : ..label:collect_merge_info\n 2.018 : ..label:merge_start\n 1.018 : ..label:renames\n\nIn the above output, note that the 4.462 seconds for process_entries was\nsplit as 3.143 seconds for \"process_entries setup\" and 1.305 seconds for\n\"processing\" (and a little time for other stuff removed from the\nhighlight). Most of the \"process_entries setup\" time was spent on\n\"plist special sort\" which corresponds to the following code:\n\n trace2_region_enter(\"merge\", \"plist special sort\", opt->repo);\n plist.cmp = string_list_df_name_compare;\n string_list_sort(&plist);\n trace2_region_leave(\"merge\", \"plist special sort\", opt->repo);\n\nIn other words, in a merge strategy that would be invoked by passing\n\"-sort\" to either rebase or merge, sorting an array takes more time than\nanything else. Serves me right for naming my merge strategy this way.\n\nRewrite the comparison function and remove as many levels of indirection\nas possible (e.g. the old code had\n cmp_items() ->\n string_list_df_name_compare() ->\n df_name_compare()\nnow we just have sort_dirs_next_to_their_children()), and tweak it to be\nas optimized as possible for our specific case. These changes reduced\nthe time spent in \"plist special sort\" by ~25% in the mega-renames case.\n\nFor the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\nperformance work; instrument with trace2_region_* calls\", 2020-10-28),\nthis change improves the performance as follows:\n\n Before After\n no-renames: 5.622 s ± 0.059 s 5.235 s ± 0.042 s\n mega-renames: 10.127 s ± 0.073 s 9.419 s ± 0.107 s\n just-one-mega: 500.3 ms ± 3.8 ms 480.1 ms ± 3.9 ms\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 64 ++++++++++++++++++++++++++++++++++-------------------\n 1 file changed, 41 insertions(+), 23 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 142d44d74d63..367aec4b7def 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2746,31 +2746,50 @@ static int detect_and_process_renames(struct merge_options *opt,\n \n /*** Function Grouping: functions related to process_entries() ***/\n \n-static int string_list_df_name_compare(const char *one, const char *two)\n+static int sort_dirs_next_to_their_children(const void *a, const void *b)\n {\n-\tint onelen = strlen(one);\n-\tint twolen = strlen(two);\n \t/*\n-\t * Here we only care that entries for D/F conflicts are\n-\t * adjacent, in particular with the file of the D/F conflict\n-\t * appearing before files below the corresponding directory.\n-\t * The order of the rest of the list is irrelevant for us.\n+\t * Here we only care that entries for directories appear adjacent\n+\t * to and before files underneath the directory. In other words,\n+\t * we do not want the natural sorting of\n+\t * foo\n+\t * foo.txt\n+\t * foo/bar\n+\t * Instead, we want \"foo\" to sort as though it were \"foo/\", so that\n+\t * we instead get\n+\t * foo.txt\n+\t * foo\n+\t * foo/bar\n+\t * To achieve this, we basically implement our own strcmp, except that\n+\t * if we get to the end of either string instead of comparing NUL to\n+\t * another character, we compare '/' to it.\n \t *\n-\t * To achieve this, we sort with df_name_compare and provide\n-\t * the mode S_IFDIR so that D/F conflicts will sort correctly.\n-\t * We use the mode S_IFDIR for everything else for simplicity,\n-\t * since in other cases any changes in their order due to\n-\t * sorting cause no problems for us.\n+\t * The reason to not use df_name_compare directly was that it was\n+\t * just too expensive, so I had to reimplement it.\n \t */\n-\tint cmp = df_name_compare(one, onelen, S_IFDIR,\n-\t\t\t\t two, twolen, S_IFDIR);\n-\t/*\n-\t * Now that 'foo' and 'foo/bar' compare equal, we have to make sure\n-\t * that 'foo' comes before 'foo/bar'.\n-\t */\n-\tif (cmp)\n-\t\treturn cmp;\n-\treturn onelen - twolen;\n+\tconst char *one = ((struct string_list_item *)a)->string;\n+\tconst char *two = ((struct string_list_item *)b)->string;\n+\tunsigned char c1, c2;\n+\n+\twhile (*one && (*one == *two)) {\n+\t\tone++;\n+\t\ttwo++;\n+\t}\n+\n+\tc1 = *one;\n+\tif (!c1)\n+\t\tc1 = '/';\n+\n+\tc2 = *two;\n+\tif (!c2)\n+\t\tc2 = '/';\n+\n+\tif (c1 == c2) {\n+\t\t/* Getting here means one is a leading directory of the other */\n+\t\treturn (*one) ? 1 : -1;\n+\t}\n+\telse\n+\t\treturn c1-c2;\n }\n \n static int read_oid_strbuf(struct merge_options *opt,\n@@ -3481,8 +3500,7 @@ static void process_entries(struct merge_options *opt,\n \ttrace2_region_leave(\"merge\", \"plist copy\", opt->repo);\n \n \ttrace2_region_enter(\"merge\", \"plist special sort\", opt->repo);\n-\tplist.cmp = string_list_df_name_compare;\n-\tstring_list_sort(&plist);\n+\tQSORT(plist.items, plist.nr, sort_dirs_next_to_their_children);\n \ttrace2_region_leave(\"merge\", \"plist special sort\", opt->repo);\n \n \ttrace2_region_leave(\"merge\", \"process_entries setup\", opt->repo);\n-- \ngitgitgadget\n\n"},{"id":"425658","messageId":"7212816c8d4734b33a874835e53d9e13b3198971.1622104642.git.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.git.1622104642.gitgitgadget@gmail.com","subject":"[PATCH 2/5] diffcore-rename: avoid unnecessary strdup'ing in break_idx","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-05-27T08:37:18Z","receivedAt":"2021-05-27T08:37:28Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThe keys of break_idx are strings from the diff_filepairs of\ndiff_queued_diff. break_idx is only used in location_rename_dst(), and\nthat usage is always before any free'ing of the pairs (and thus the\nstrings in the pairs). As such, there is no need to strdup these keys;\nwe can just reuse the existing strings as-is.\n\nThe merge logic doesn't make use of break detection, so this does not\naffect the performance of any of my testcases. It was just a minor\nunrelated optimization noted in passing while looking at the code.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 3375e24659ea..e333a6d64791 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -54,7 +54,7 @@ static void register_rename_src(struct diff_filepair *p)\n \tif (p->broken_pair) {\n \t\tif (!break_idx) {\n \t\t\tbreak_idx = xmalloc(sizeof(*break_idx));\n-\t\t\tstrintmap_init(break_idx, -1);\n+\t\t\tstrintmap_init_with_options(break_idx, -1, NULL, 0);\n \t\t}\n \t\tstrintmap_set(break_idx, p->one->path, rename_dst_nr);\n \t}\n-- \ngitgitgadget\n\n"},{"id":"425659","messageId":"pull.962.git.1622104642.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":null,"subject":"[PATCH 0/5] Optimization batch 12: miscellaneous unthemed stuff","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-05-27T08:37:16Z","receivedAt":"2021-05-27T08:37:29Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series depends on en/ort-perf-batch-11 textually, but is semantically\nindependent of it.\n\nThis short series has a few optimizations, but only one of which affects the\ntestcases of interest (namely, reducing our time spent on sorting an array).\nIt also fixes a few comments.\n\nFor the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\nperformance work; instrument with trace2_region_* calls\", 2020-10-28), the\nchanges in just this series improves the performance as follows:\n\n Before Series After Series\nno-renames: 5.622 s ± 0.059 s 5.235 s ± 0.042 s\nmega-renames: 10.127 s ± 0.073 s 9.419 s ± 0.107 s\njust-one-mega: 500.3 ms ± 3.8 ms 480.1 ms ± 3.9 ms\n\n\nAs a reminder, before any merge-ort/diffcore-rename performance work, the\nperformance results we started with were:\n\nno-renames-am: 6.940 s ± 0.485 s\nno-renames: 18.912 s ± 0.174 s\nmega-renames: 5964.031 s ± 10.459 s\njust-one-mega: 149.583 s ± 0.751 s\n\n\nElijah Newren (5):\n merge-ort: replace string_list_df_name_compare with faster alternative\n diffcore-rename: avoid unnecessary strdup'ing in break_idx\n diffcore-rename: enable limiting rename detection to relevant\n destinations\n Fix various issues found in comments\n merge-ort: miscellaneous touch-ups\n\n diffcore-rename.c | 52 ++++++++++++++++---\n diffcore.h | 2 +\n merge-ort.c | 78 +++++++++++++++++++----------\n t/t6423-merge-rename-directories.sh | 2 +-\n 4 files changed, 99 insertions(+), 35 deletions(-)\n\n\nbase-commit: 76e253793c9a1d7fdd1836d5e4db26dabd3d713a\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-962%2Fnewren%2Fort-perf-batch-12-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-962/newren/ort-perf-batch-12-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/962\n-- \ngitgitgadget\n"},{"id":"425660","messageId":"19150b5750586996383dc26f3801a9441486f9f0.1622104642.git.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.git.1622104642.gitgitgadget@gmail.com","subject":"[PATCH 3/5] diffcore-rename: enable limiting rename detection to relevant destinations","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-05-27T08:37:19Z","receivedAt":"2021-05-27T08:37:30Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nOur former optimizations focused on limiting rename detection to a\npre-specified set of relevant sources. This was because the merge logic\nonly had a way of knowing which sources were relevant. However, other\ncallers of rename detection might benefit from being able to limit\nrename detection to a known set of relevant destinations. In\nparticular, a properly implemented `git log --follow` might benefit from\nsuch an ability.\n\nSince the code to implement such limiting is very similar to what we've\nalready done, just implement it now even though we do not yet have any\ncallers making use of this ability.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 48 +++++++++++++++++++++++++++++++++++++++++------\n diffcore.h | 2 ++\n merge-ort.c | 1 +\n 3 files changed, 45 insertions(+), 6 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex e333a6d64791..8ff83a9f3b99 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -372,6 +372,7 @@ struct dir_rename_info {\n \tstruct strmap dir_rename_guess;\n \tstruct strmap *dir_rename_count;\n \tstruct strintmap *relevant_source_dirs;\n+\tstruct strset *relevant_destination_dirs;\n \tunsigned setup;\n };\n \n@@ -491,8 +492,11 @@ static void update_dir_rename_counts(struct dir_rename_info *info,\n \t\t !strintmap_contains(info->relevant_source_dirs, old_dir))\n \t\t\tbreak;\n \n-\t\t/* Get new_dir */\n+\t\t/* Get new_dir, skip if its directory isn't relevant. */\n \t\tdirname_munge(new_dir);\n+\t\tif (info->relevant_destination_dirs &&\n+\t\t !strset_contains(info->relevant_destination_dirs, new_dir))\n+\t\t\tbreak;\n \n \t\t/*\n \t\t * When renaming\n@@ -567,6 +571,7 @@ static void update_dir_rename_counts(struct dir_rename_info *info,\n \n static void initialize_dir_rename_info(struct dir_rename_info *info,\n \t\t\t\t struct strintmap *relevant_sources,\n+\t\t\t\t struct strset *relevant_destinations,\n \t\t\t\t struct strintmap *dirs_removed,\n \t\t\t\t struct strmap *dir_rename_count,\n \t\t\t\t struct strmap *cached_pairs)\n@@ -575,7 +580,7 @@ static void initialize_dir_rename_info(struct dir_rename_info *info,\n \tstruct strmap_entry *entry;\n \tint i;\n \n-\tif (!dirs_removed && !relevant_sources) {\n+\tif (!dirs_removed && !relevant_sources && !relevant_destinations) {\n \t\tinfo->setup = 0;\n \t\treturn;\n \t}\n@@ -589,6 +594,18 @@ static void initialize_dir_rename_info(struct dir_rename_info *info,\n \tstrintmap_init_with_options(&info->idx_map, -1, NULL, 0);\n \tstrmap_init_with_options(&info->dir_rename_guess, NULL, 0);\n \n+\t/* Setup info->relevant_destination_dirs */\n+\tinfo->relevant_destination_dirs = NULL;\n+\tif (relevant_destinations) {\n+\t\tinfo->relevant_destination_dirs = xmalloc(sizeof(struct strset));\n+\t\tstrset_init(info->relevant_destination_dirs);\n+\t\tstrset_for_each_entry(relevant_destinations, &iter, entry) {\n+\t\t\tchar *dirname = get_dirname(entry->key);\n+\t\t\tstrset_add(info->relevant_destination_dirs, dirname);\n+\t\t\tfree(dirname);\n+\t\t}\n+\t}\n+\n \t/* Setup info->relevant_source_dirs */\n \tinfo->relevant_source_dirs = NULL;\n \tif (dirs_removed || !relevant_sources) {\n@@ -700,6 +717,12 @@ static void cleanup_dir_rename_info(struct dir_rename_info *info,\n \t\tFREE_AND_NULL(info->relevant_source_dirs);\n \t}\n \n+\t/* relevant_destination_dirs */\n+\tif (info->relevant_destination_dirs) {\n+\t\tstrset_clear(info->relevant_destination_dirs);\n+\t\tFREE_AND_NULL(info->relevant_destination_dirs);\n+\t}\n+\n \t/* dir_rename_count */\n \tif (!keep_dir_rename_count) {\n \t\tpartial_clear_dir_rename_count(info->dir_rename_count);\n@@ -827,6 +850,7 @@ static int find_basename_matches(struct diff_options *options,\n \t\t\t\t int minimum_score,\n \t\t\t\t struct dir_rename_info *info,\n \t\t\t\t struct strintmap *relevant_sources,\n+\t\t\t\t struct strset *relevant_destinations,\n \t\t\t\t struct strintmap *dirs_removed)\n {\n \t/*\n@@ -949,9 +973,15 @@ static int find_basename_matches(struct diff_options *options,\n \t\t\tif (rename_dst[dst_index].is_rename)\n \t\t\t\tcontinue; /* already used previously */\n \n-\t\t\t/* Estimate the similarity */\n \t\t\tone = rename_src[src_index].p->one;\n \t\t\ttwo = rename_dst[dst_index].p->two;\n+\n+\t\t\t/* Skip irrelevant destinations */\n+\t\t\tif (relevant_destinations &&\n+\t\t\t !strset_contains(relevant_destinations, two->path))\n+\t\t\t\tcontinue;\n+\n+\t\t\t/* Estimate the similarity */\n \t\t\tscore = estimate_similarity(options->repo, one, two,\n \t\t\t\t\t\t minimum_score, skip_unmodified);\n \n@@ -1258,6 +1288,7 @@ static void handle_early_known_dir_renames(struct dir_rename_info *info,\n \n void diffcore_rename_extended(struct diff_options *options,\n \t\t\t struct strintmap *relevant_sources,\n+\t\t\t struct strset *relevant_destinations,\n \t\t\t struct strintmap *dirs_removed,\n \t\t\t struct strmap *dir_rename_count,\n \t\t\t struct strmap *cached_pairs)\n@@ -1376,8 +1407,8 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t/* Preparation for basename-driven matching. */\n \t\ttrace2_region_enter(\"diff\", \"dir rename setup\", options->repo);\n \t\tinitialize_dir_rename_info(&info, relevant_sources,\n-\t\t\t\t\t dirs_removed, dir_rename_count,\n-\t\t\t\t\t cached_pairs);\n+\t\t\t\t\t relevant_destinations, dirs_removed,\n+\t\t\t\t\t dir_rename_count, cached_pairs);\n \t\ttrace2_region_leave(\"diff\", \"dir rename setup\", options->repo);\n \n \t\t/* Utilize file basenames to quickly find renames. */\n@@ -1386,6 +1417,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t\t\t\t\t min_basename_score,\n \t\t\t\t\t\t &info,\n \t\t\t\t\t\t relevant_sources,\n+\t\t\t\t\t\t relevant_destinations,\n \t\t\t\t\t\t dirs_removed);\n \t\ttrace2_region_leave(\"diff\", \"basename matches\", options->repo);\n \n@@ -1441,6 +1473,10 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\tif (rename_dst[i].is_rename)\n \t\t\tcontinue; /* exact or basename match already handled */\n \n+\t\tif (relevant_destinations &&\n+\t\t !strset_contains(relevant_destinations, two->path))\n+\t\t\tcontinue;\n+\n \t\tm = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];\n \t\tfor (j = 0; j < NUM_CANDIDATE_PER_DST; j++)\n \t\t\tm[j].dst = -1;\n@@ -1574,5 +1610,5 @@ void diffcore_rename_extended(struct diff_options *options,\n \n void diffcore_rename(struct diff_options *options)\n {\n-\tdiffcore_rename_extended(options, NULL, NULL, NULL, NULL);\n+\tdiffcore_rename_extended(options, NULL, NULL, NULL, NULL, NULL);\n }\ndiff --git a/diffcore.h b/diffcore.h\nindex 533b30e21e7f..435c7094f403 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -10,6 +10,7 @@ struct diff_options;\n struct repository;\n struct strintmap;\n struct strmap;\n+struct strset;\n struct userdiff_driver;\n \n /* This header file is internal between diff.c and its diff transformers\n@@ -180,6 +181,7 @@ void diffcore_break(struct repository *, int);\n void diffcore_rename(struct diff_options *);\n void diffcore_rename_extended(struct diff_options *options,\n \t\t\t struct strintmap *relevant_sources,\n+\t\t\t struct strset *relevant_destinations,\n \t\t\t struct strintmap *dirs_removed,\n \t\t\t struct strmap *dir_rename_count,\n \t\t\t struct strmap *cached_pairs);\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 367aec4b7def..db16cbc3bd33 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2568,6 +2568,7 @@ static void detect_regular_renames(struct merge_options *opt,\n \ttrace2_region_enter(\"diff\", \"diffcore_rename\", opt->repo);\n \tdiffcore_rename_extended(&diff_opts,\n \t\t\t\t &renames->relevant_sources[side_index],\n+\t\t\t\t NULL,\n \t\t\t\t &renames->dirs_removed[side_index],\n \t\t\t\t &renames->dir_rename_count[side_index],\n \t\t\t\t &renames->cached_pairs[side_index]);\n-- \ngitgitgadget\n\n"},{"id":"425661","messageId":"98c9a419b313261a21d3794742181c27ed8cd0cb.1622104642.git.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.git.1622104642.gitgitgadget@gmail.com","subject":"[PATCH 4/5] Fix various issues found in comments","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-05-27T08:37:20Z","receivedAt":"2021-05-27T08:37:31Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nA random hodge-podge of incorrect or out-of-date comments that I found:\n\n * t6423 had a comment that has referred to the wrong test for years;\n fix it to refer to the right one.\n * diffcore-rename had a FIXME comment meant to remind myself to\n investigate if I could make another code change. I later\n investigated and removed the FIXME, but while cherry-picking the\n patch to submit upstream I missed the later update. Remove the\n comment now.\n * merge-ort had the early part of a comment for a function; I had\n meant to include the more involved description when I updated the\n function. Update the comment now.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 2 +-\n merge-ort.c | 8 +++++---\n t/t6423-merge-rename-directories.sh | 2 +-\n 3 files changed, 7 insertions(+), 5 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 8ff83a9f3b99..c9f7d59cf62b 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -1579,7 +1579,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t\t/* all the usual ones need to be kept */\n \t\t\tdiff_q(&outq, p);\n \t\telse\n-\t\t\t/* no need to keep unmodified pairs; FIXME: remove earlier? */\n+\t\t\t/* no need to keep unmodified pairs */\n \t\t\tpair_to_free = p;\n \n \t\tif (pair_to_free)\ndiff --git a/merge-ort.c b/merge-ort.c\nindex db16cbc3bd33..6cb103c8e855 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2533,7 +2533,7 @@ static int compare_pairs(const void *a_, const void *b_)\n \treturn strcmp(a->one->path, b->one->path);\n }\n \n-/* Call diffcore_rename() to compute which files have changed on given side */\n+/* Call diffcore_rename() to update deleted/added pairs into rename pairs */\n static void detect_regular_renames(struct merge_options *opt,\n \t\t\t\t unsigned side_index)\n {\n@@ -2587,8 +2587,10 @@ static void detect_regular_renames(struct merge_options *opt,\n }\n \n /*\n- * Get information of all renames which occurred in 'side_pairs', discarding\n- * non-renames.\n+ * Get information of all renames which occurred in 'side_pairs', making use\n+ * of any implicit directory renames in side_dir_renames (also making use of\n+ * implicit directory renames rename_exclusions as needed by\n+ * check_for_directory_rename()). Add all (updated) renames into result.\n */\n static int collect_renames(struct merge_options *opt,\n \t\t\t struct diff_queue_struct *result,\ndiff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh\nindex be84d22419d9..e834b7e6efe0 100755\n--- a/t/t6423-merge-rename-directories.sh\n+++ b/t/t6423-merge-rename-directories.sh\n@@ -454,7 +454,7 @@ test_expect_success '1f: Split a directory into two other directories' '\n # the directory renamed, but the files within it. (see 1b)\n #\n # If renames split a directory into two or more others, the directory\n-# with the most renames, \"wins\" (see 1c). However, see the testcases\n+# with the most renames, \"wins\" (see 1f). However, see the testcases\n # in section 2, plus testcases 3a and 4a.\n ###########################################################################\n \n-- \ngitgitgadget\n\n"},{"id":"425662","messageId":"e85dad887f95b6cee8df6a4452cb3b10198368f3.1622104642.git.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.git.1622104642.gitgitgadget@gmail.com","subject":"[PATCH 5/5] merge-ort: miscellaneous touch-ups","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-05-27T08:37:21Z","receivedAt":"2021-05-27T08:37:32Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nAdd some notes in the code about invariants with match_mask when adding\npairs. Also add a comment that seems to have been left out in my work\nof pushing these changes upstream.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 5 +++++\n 1 file changed, 5 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 6cb103c8e855..e174a8734a41 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -765,6 +765,7 @@ static void add_pair(struct merge_options *opt,\n \tint names_idx = is_add ? side : 0;\n \n \tif (is_add) {\n+\t\tassert(match_mask == 0 || match_mask == 6);\n \t\tif (strset_contains(&renames->cached_target_names[side],\n \t\t\t\t pathname))\n \t\t\treturn;\n@@ -772,6 +773,8 @@ static void add_pair(struct merge_options *opt,\n \t\tunsigned content_relevant = (match_mask == 0);\n \t\tunsigned location_relevant = (dir_rename_mask == 0x07);\n \n+\t\tassert(match_mask == 0 || match_mask == 3 || match_mask == 5);\n+\n \t\t/*\n \t\t * If pathname is found in cached_irrelevant[side] due to\n \t\t * previous pick but for this commit content is relevant,\n@@ -3470,6 +3473,8 @@ static void process_entry(struct merge_options *opt,\n \t */\n \tif (!ci->merged.clean)\n \t\tstrmap_put(&opt->priv->conflicted, path, ci);\n+\n+\t/* Record metadata for ci->merged in dir_metadata */\n \trecord_entry_for_tree(dir_metadata, path, &ci->merged);\n }\n \n-- \ngitgitgadget\n"},{"id":"425709","messageId":"e0842d32-a11c-91d8-3660-cffdb5639193@web.de","threadId":"55781","inReplyTo":"5055dfce32815c8c8ec250457df389d4cd02ee12.1622104642.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-05-27T21:00:26Z","receivedAt":"2021-05-27T21:00:41Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 27.05.21 um 10:37 schrieb Elijah Newren via GitGitGadget:\n> From: Elijah Newren \n>\n> Gathering accumulated times from trace2 output on the mega-renames\n> testcase, I saw the following timings (where I'm only showing a few\n> lines to highlight the portions of interest):\n>\n> 10.120 : label:incore_nonrecursive\n> 4.462 : ..label:process_entries\n> 3.143 : ....label:process_entries setup\n> 2.988 : ......label:plist special sort\n> 1.305 : ....label:processing\n> 2.604 : ..label:collect_merge_info\n> 2.018 : ..label:merge_start\n> 1.018 : ..label:renames\n>\n> In the above output, note that the 4.462 seconds for process_entries was\n> split as 3.143 seconds for \"process_entries setup\" and 1.305 seconds for\n> \"processing\" (and a little time for other stuff removed from the\n> highlight). Most of the \"process_entries setup\" time was spent on\n> \"plist special sort\" which corresponds to the following code:\n>\n> trace2_region_enter(\"merge\", \"plist special sort\", opt->repo);\n> plist.cmp = string_list_df_name_compare;\n> string_list_sort(&plist);\n> trace2_region_leave(\"merge\", \"plist special sort\", opt->repo);\n>\n> In other words, in a merge strategy that would be invoked by passing\n> \"-sort\" to either rebase or merge, sorting an array takes more time than\n> anything else. Serves me right for naming my merge strategy this way.\n>\n> Rewrite the comparison function and remove as many levels of indirection\n> as possible (e.g. the old code had\n> cmp_items() ->\n> string_list_df_name_compare() ->\n> df_name_compare()\n> now we just have sort_dirs_next_to_their_children()), and tweak it to be\n> as optimized as possible for our specific case. These changes reduced\n> the time spent in \"plist special sort\" by ~25% in the mega-renames case.\n>\n> For the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\n> performance work; instrument with trace2_region_* calls\", 2020-10-28),\n> this change improves the performance as follows:\n>\n> Before After\n> no-renames: 5.622 s ± 0.059 s 5.235 s ± 0.042 s\n> mega-renames: 10.127 s ± 0.073 s 9.419 s ± 0.107 s\n> just-one-mega: 500.3 ms ± 3.8 ms 480.1 ms ± 3.9 ms\n\nInteresting.\n\n>\n> Signed-off-by: Elijah Newren \n> ---\n> merge-ort.c | 64 ++++++++++++++++++++++++++++++++++-------------------\n> 1 file changed, 41 insertions(+), 23 deletions(-)\n>\n> diff --git a/merge-ort.c b/merge-ort.c\n> index 142d44d74d63..367aec4b7def 100644\n> --- a/merge-ort.c\n> +++ b/merge-ort.c\n> @@ -2746,31 +2746,50 @@ static int detect_and_process_renames(struct merge_options *opt,\n>\n> /*** Function Grouping: functions related to process_entries() ***/\n>\n> -static int string_list_df_name_compare(const char *one, const char *two)\n> +static int sort_dirs_next_to_their_children(const void *a, const void *b)\n> {\n> -\tint onelen = strlen(one);\n> -\tint twolen = strlen(two);\n\nThe old code scans both strings fully, while the new one stops when it\nreaches a difference and doesn't look at any further characters. How\nmuch does that contribute to the speedup? (I suspect a lot.)\n\n> \t/*\n> -\t * Here we only care that entries for D/F conflicts are\n> -\t * adjacent, in particular with the file of the D/F conflict\n> -\t * appearing before files below the corresponding directory.\n> -\t * The order of the rest of the list is irrelevant for us.\n> +\t * Here we only care that entries for directories appear adjacent\n> +\t * to and before files underneath the directory. In other words,\n> +\t * we do not want the natural sorting of\n> +\t * foo\n> +\t * foo.txt\n> +\t * foo/bar\n> +\t * Instead, we want \"foo\" to sort as though it were \"foo/\", so that\n> +\t * we instead get\n> +\t * foo.txt\n> +\t * foo\n> +\t * foo/bar\n> +\t * To achieve this, we basically implement our own strcmp, except that\n> +\t * if we get to the end of either string instead of comparing NUL to\n> +\t * another character, we compare '/' to it.\n> \t *\n> -\t * To achieve this, we sort with df_name_compare and provide\n> -\t * the mode S_IFDIR so that D/F conflicts will sort correctly.\n> -\t * We use the mode S_IFDIR for everything else for simplicity,\n> -\t * since in other cases any changes in their order due to\n> -\t * sorting cause no problems for us.\n> +\t * The reason to not use df_name_compare directly was that it was\n> +\t * just too expensive, so I had to reimplement it.\n> \t */\n> -\tint cmp = df_name_compare(one, onelen, S_IFDIR,\n> -\t\t\t\t two, twolen, S_IFDIR);\n> -\t/*\n> -\t * Now that 'foo' and 'foo/bar' compare equal, we have to make sure\n> -\t * that 'foo' comes before 'foo/bar'.\n> -\t */\n> -\tif (cmp)\n> -\t\treturn cmp;\n> -\treturn onelen - twolen;\n> +\tconst char *one = ((struct string_list_item *)a)->string;\n> +\tconst char *two = ((struct string_list_item *)b)->string;\n\nCasting away const, hmm. :-/ Harmless because no actual write is\nattempted, but still looks needlessly scary to me.\n\n> +\tunsigned char c1, c2;\n> +\n> +\twhile (*one && (*one == *two)) {\n> +\t\tone++;\n> +\t\ttwo++;\n> +\t}\n> +\n> +\tc1 = *one;\n> +\tif (!c1)\n> +\t\tc1 = '/';\n> +\n> +\tc2 = *two;\n> +\tif (!c2)\n> +\t\tc2 = '/';\n> +\n> +\tif (c1 == c2) {\n> +\t\t/* Getting here means one is a leading directory of the other */\n> +\t\treturn (*one) ? 1 : -1;\n> +\t}\n> +\telse\n> +\t\treturn c1-c2;\n> }\n>\n> static int read_oid_strbuf(struct merge_options *opt,\n> @@ -3481,8 +3500,7 @@ static void process_entries(struct merge_options *opt,\n> \ttrace2_region_leave(\"merge\", \"plist copy\", opt->repo);\n>\n> \ttrace2_region_enter(\"merge\", \"plist special sort\", opt->repo);\n> -\tplist.cmp = string_list_df_name_compare;\n> -\tstring_list_sort(&plist);\n> +\tQSORT(plist.items, plist.nr, sort_dirs_next_to_their_children);\n\nHow much does the direct use of QSORT instead of string_list_sort()\ncontribute to the speedup? (I suspect only a bit.)\n\n> \ttrace2_region_leave(\"merge\", \"plist special sort\", opt->repo);\n>\n> \ttrace2_region_leave(\"merge\", \"process_entries setup\", opt->repo);\n>\n\n"},{"id":"425715","messageId":"CABPp-BH_nFJ2N6Jf64jZPNKdbwm2Yt=zo6pw-9s6S+fzo7a=pg@mail.gmail.com","threadId":"55781","inReplyTo":"e0842d32-a11c-91d8-3660-cffdb5639193@web.de","subject":"Re: [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-05-27T22:47:27Z","receivedAt":"2021-05-27T22:47:45Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, May 27, 2021 at 2:00 PM René Scharfe wrote:\n>\n> Am 27.05.21 um 10:37 schrieb Elijah Newren via GitGitGadget:\n> > From: Elijah Newren \n> >\n> > Gathering accumulated times from trace2 output on the mega-renames\n> > testcase, I saw the following timings (where I'm only showing a few\n> > lines to highlight the portions of interest):\n> >\n> > 10.120 : label:incore_nonrecursive\n> > 4.462 : ..label:process_entries\n> > 3.143 : ....label:process_entries setup\n> > 2.988 : ......label:plist special sort\n> > 1.305 : ....label:processing\n> > 2.604 : ..label:collect_merge_info\n> > 2.018 : ..label:merge_start\n> > 1.018 : ..label:renames\n> >\n> > In the above output, note that the 4.462 seconds for process_entries was\n> > split as 3.143 seconds for \"process_entries setup\" and 1.305 seconds for\n> > \"processing\" (and a little time for other stuff removed from the\n> > highlight). Most of the \"process_entries setup\" time was spent on\n> > \"plist special sort\" which corresponds to the following code:\n> >\n> > trace2_region_enter(\"merge\", \"plist special sort\", opt->repo);\n> > plist.cmp = string_list_df_name_compare;\n> > string_list_sort(&plist);\n> > trace2_region_leave(\"merge\", \"plist special sort\", opt->repo);\n> >\n> > In other words, in a merge strategy that would be invoked by passing\n> > \"-sort\" to either rebase or merge, sorting an array takes more time than\n> > anything else. Serves me right for naming my merge strategy this way.\n> >\n> > Rewrite the comparison function and remove as many levels of indirection\n> > as possible (e.g. the old code had\n> > cmp_items() ->\n> > string_list_df_name_compare() ->\n> > df_name_compare()\n> > now we just have sort_dirs_next_to_their_children()), and tweak it to be\n> > as optimized as possible for our specific case. These changes reduced\n> > the time spent in \"plist special sort\" by ~25% in the mega-renames case.\n> >\n> > For the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\n> > performance work; instrument with trace2_region_* calls\", 2020-10-28),\n> > this change improves the performance as follows:\n> >\n> > Before After\n> > no-renames: 5.622 s ± 0.059 s 5.235 s ± 0.042 s\n> > mega-renames: 10.127 s ± 0.073 s 9.419 s ± 0.107 s\n> > just-one-mega: 500.3 ms ± 3.8 ms 480.1 ms ± 3.9 ms\n>\n> Interesting.\n>\n> >\n> > Signed-off-by: Elijah Newren \n> > ---\n> > merge-ort.c | 64 ++++++++++++++++++++++++++++++++++-------------------\n> > 1 file changed, 41 insertions(+), 23 deletions(-)\n> >\n> > diff --git a/merge-ort.c b/merge-ort.c\n> > index 142d44d74d63..367aec4b7def 100644\n> > --- a/merge-ort.c\n> > +++ b/merge-ort.c\n> > @@ -2746,31 +2746,50 @@ static int detect_and_process_renames(struct merge_options *opt,\n> >\n> > /*** Function Grouping: functions related to process_entries() ***/\n> >\n> > -static int string_list_df_name_compare(const char *one, const char *two)\n> > +static int sort_dirs_next_to_their_children(const void *a, const void *b)\n> > {\n> > - int onelen = strlen(one);\n> > - int twolen = strlen(two);\n>\n> The old code scans both strings fully, while the new one stops when it\n> reaches a difference and doesn't look at any further characters. How\n> much does that contribute to the speedup? (I suspect a lot.)\n\nOh, indeed, good catch. It appears to be responsible for essentially all of it.\n\n> > /*\n> > - * Here we only care that entries for D/F conflicts are\n> > - * adjacent, in particular with the file of the D/F conflict\n> > - * appearing before files below the corresponding directory.\n> > - * The order of the rest of the list is irrelevant for us.\n> > + * Here we only care that entries for directories appear adjacent\n> > + * to and before files underneath the directory. In other words,\n> > + * we do not want the natural sorting of\n> > + * foo\n> > + * foo.txt\n> > + * foo/bar\n> > + * Instead, we want \"foo\" to sort as though it were \"foo/\", so that\n> > + * we instead get\n> > + * foo.txt\n> > + * foo\n> > + * foo/bar\n> > + * To achieve this, we basically implement our own strcmp, except that\n> > + * if we get to the end of either string instead of comparing NUL to\n> > + * another character, we compare '/' to it.\n> > *\n> > - * To achieve this, we sort with df_name_compare and provide\n> > - * the mode S_IFDIR so that D/F conflicts will sort correctly.\n> > - * We use the mode S_IFDIR for everything else for simplicity,\n> > - * since in other cases any changes in their order due to\n> > - * sorting cause no problems for us.\n> > + * The reason to not use df_name_compare directly was that it was\n> > + * just too expensive, so I had to reimplement it.\n> > */\n> > - int cmp = df_name_compare(one, onelen, S_IFDIR,\n> > - two, twolen, S_IFDIR);\n> > - /*\n> > - * Now that 'foo' and 'foo/bar' compare equal, we have to make sure\n> > - * that 'foo' comes before 'foo/bar'.\n> > - */\n> > - if (cmp)\n> > - return cmp;\n> > - return onelen - twolen;\n> > + const char *one = ((struct string_list_item *)a)->string;\n> > + const char *two = ((struct string_list_item *)b)->string;\n>\n> Casting away const, hmm. :-/ Harmless because no actual write is\n> attempted, but still looks needlessly scary to me.\n\nRight, that should have been\n+ const char *one = ((const struct string_list_item *)a)->string;\n+ const char *two = ((const struct string_list_item *)b)->string;\nbut since I was just assigning to a const char * on those lines, I'm\nnot sure why it'd qualify as scary. Regardless, I'm happy to put\nthese consts back in.\n\n> > + unsigned char c1, c2;\n> > +\n> > + while (*one && (*one == *two)) {\n> > + one++;\n> > + two++;\n> > + }\n> > +\n> > + c1 = *one;\n> > + if (!c1)\n> > + c1 = '/';\n> > +\n> > + c2 = *two;\n> > + if (!c2)\n> > + c2 = '/';\n> > +\n> > + if (c1 == c2) {\n> > + /* Getting here means one is a leading directory of the other */\n> > + return (*one) ? 1 : -1;\n> > + }\n> > + else\n> > + return c1-c2;\n> > }\n> >\n> > static int read_oid_strbuf(struct merge_options *opt,\n> > @@ -3481,8 +3500,7 @@ static void process_entries(struct merge_options *opt,\n> > trace2_region_leave(\"merge\", \"plist copy\", opt->repo);\n> >\n> > trace2_region_enter(\"merge\", \"plist special sort\", opt->repo);\n> > - plist.cmp = string_list_df_name_compare;\n> > - string_list_sort(&plist);\n> > + QSORT(plist.items, plist.nr, sort_dirs_next_to_their_children);\n>\n> How much does the direct use of QSORT instead of string_list_sort()\n> contribute to the speedup? (I suspect only a bit.)\n\nYep, I'll fix up the commit message.\n"},{"id":"425725","messageId":"YLBIIL+yShDVlWo5@nand.local","threadId":"55781","inReplyTo":"5055dfce32815c8c8ec250457df389d4cd02ee12.1622104642.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2021-05-28T01:32:16Z","receivedAt":"2021-05-28T01:32:22Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, May 27, 2021 at 08:37:17AM +0000, Elijah Newren via GitGitGadget wrote:\n> -static int string_list_df_name_compare(const char *one, const char *two)\n> +static int sort_dirs_next_to_their_children(const void *a, const void *b)\n\nI looked at the new implementation of this function (and\ndf_name_compare() to double check it) and am convinced that it's\ncorrectness, with the exception of one question.\n\nSome thoughts I had while trying to make sure this was all OK:\n\n> +\tconst char *one = ((struct string_list_item *)a)->string;\n> +\tconst char *two = ((struct string_list_item *)b)->string;\n> +\tunsigned char c1, c2;\n> +\n> +\twhile (*one && (*one == *two)) {\n> +\t\tone++;\n> +\t\ttwo++;\n> +\t}\n\nAdvancing 'one' and 'two' to point at either the end of 'a' (and the\nsame position within 'b'), or the first place where the two have\ndifferent characters. If 'b' is shorter than 'a', '*one != *two' will\nterminate the loop (since '*two' will be NUL, and '*one' will not).\n\n> +\tc1 = *one;\n> +\tif (!c1)\n> +\t\tc1 = '/';\n> +\n> +\tc2 = *two;\n> +\tif (!c2)\n> +\t\tc2 = '/';\n\nStore off the last character of each, or '/' if we got to the end. Hmm,\nis this right (the guard in 'df_name_compare()' read 'if (!c1 &&\nS_ISDIR(mode1))'). Suppose both strings were \"foo\", then both c1 and c2\nwould be \"/\", and I think we would return -1.\n\nThat doesn't seem quite right to me. I think it *would* be right if we\nchecked the mode of each entry before assigning c1 or c2 to '/',\nthough. (Being generally unfamiliar with this area, I haven't looked to\nsee whether getting access to the modes of each entry at this point is\neasy or not).\n\n> +\n> +\tif (c1 == c2) {\n> +\t\t/* Getting here means one is a leading directory of the other */\n> +\t\treturn (*one) ? 1 : -1;\n> +\t}\n\n> +\telse\n\nI did find this spacing awkward (would have expected '} else' or even '}\nelse {'), but it hardly matters.\n\nThanks,\nTaylor\n"},{"id":"425731","messageId":"CABPp-BGXwC5Gtz5PVkXnw2wXzacqjUACB=sgCF5e=BwJiWsYPQ@mail.gmail.com","threadId":"55781","inReplyTo":"YLBIIL+yShDVlWo5@nand.local","subject":"Re: [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-05-28T04:10:27Z","receivedAt":"2021-05-28T04:12:20Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, May 27, 2021 at 6:32 PM Taylor Blau wrote:\n>\n> On Thu, May 27, 2021 at 08:37:17AM +0000, Elijah Newren via GitGitGadget wrote:\n> > -static int string_list_df_name_compare(const char *one, const char *two)\n> > +static int sort_dirs_next_to_their_children(const void *a, const void *b)\n>\n> I looked at the new implementation of this function (and\n> df_name_compare() to double check it) and am convinced that it's\n> correctness, with the exception of one question.\n>\n> Some thoughts I had while trying to make sure this was all OK:\n>\n> > + const char *one = ((struct string_list_item *)a)->string;\n> > + const char *two = ((struct string_list_item *)b)->string;\n> > + unsigned char c1, c2;\n> > +\n> > + while (*one && (*one == *two)) {\n> > + one++;\n> > + two++;\n> > + }\n>\n> Advancing 'one' and 'two' to point at either the end of 'a' (and the\n> same position within 'b'), or the first place where the two have\n> different characters. If 'b' is shorter than 'a', '*one != *two' will\n> terminate the loop (since '*two' will be NUL, and '*one' will not).\n>\n> > + c1 = *one;\n> > + if (!c1)\n> > + c1 = '/';\n> > +\n> > + c2 = *two;\n> > + if (!c2)\n> > + c2 = '/';\n>\n> Store off the last character of each, or '/' if we got to the end. Hmm,\n> is this right (the guard in 'df_name_compare()' read 'if (!c1 &&\n> S_ISDIR(mode1))'). Suppose both strings were \"foo\", then both c1 and c2\n> would be \"/\", and I think we would return -1.\n>\n> That doesn't seem quite right to me. I think it *would* be right if we\n> checked the mode of each entry before assigning c1 or c2 to '/',\n> though. (Being generally unfamiliar with this area, I haven't looked to\n> see whether getting access to the modes of each entry at this point is\n> easy or not).\n\nGood reasoning; I should have been clearer about one of the\nassumptions that this function operates under which precludes that\npossibility.\n\n> > +\n> > + if (c1 == c2) {\n> > + /* Getting here means one is a leading directory of the other */\n\nYour example case of both strings being \"foo\" obviously conflicts with\nthis comment; but the comment is correct. This function will never be\ngiven two equal strings because it is called to sort the keys of a\nstrmap, and strmap keys are unique by construction. (If one side of\nhistory has \"foo\" as a directory, and the other side has \"foo\" as a\npath, then there is still only one \"foo\" in opt->priv->paths. Every\nentry in opt->priv->paths records 3 hashes and modes and whatnot in\norder to know what each side of history had at the given path.)\n\nAlso, even in that case (when two strings are equal), getting the\nright return value would only matter if we cared about a stable sort.\nBut we call this function with QSORT, not STABLE_QSORT.\n\nInterestingly, this function technically doesn't even need to fully\nsort the array either. For example, if you took the output of 'git\nls-tree -rt HEAD' and permuted the order of files within the same\ndirectory, that kind of level of quasi-sorted would be good enough for\nmy purposes; I just need files underneath the same directory to be\n\"together\" and the containing directory to appear immediately before\nthose. There is a later call to write_tree() that will hande sorting\nwithin a single directory to ensure fully-sorted-ness. Unfortunately,\nI don't know of a way to take advantage of that less strict sorting\nrequirement for this point of the code to improve the performance\nfurther, so this function just implemented \"pretend that every path\nhas a '/' appended and then fully sort them\".\n\n> > + return (*one) ? 1 : -1;\n> > + }\n>\n> > + else\n>\n> I did find this spacing awkward (would have expected '} else' or even '}\n> else {'), but it hardly matters.\n\nI'll fix that up while adding some comments about the purpose of the\nfunction and the fact that it assumes there will be no duplicates in\nthe array being sorted.\n"},{"id":"425811","messageId":"106a5592-4e5e-cf06-16e4-100ca3c3fb5f@web.de","threadId":"55781","inReplyTo":"CABPp-BH_nFJ2N6Jf64jZPNKdbwm2Yt=zo6pw-9s6S+fzo7a=pg@mail.gmail.com","subject":"Re: [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-05-28T16:12:29Z","receivedAt":"2021-05-28T16:12:39Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 28.05.21 um 00:47 schrieb Elijah Newren:\n> On Thu, May 27, 2021 at 2:00 PM René Scharfe wrote:\n>>\n>> Am 27.05.21 um 10:37 schrieb Elijah Newren via GitGitGadget:\n>>> From: Elijah Newren \n>>>\n>>> Gathering accumulated times from trace2 output on the mega-renames\n>>> testcase, I saw the following timings (where I'm only showing a few\n>>> lines to highlight the portions of interest):\n>>>\n>>> 10.120 : label:incore_nonrecursive\n>>> 4.462 : ..label:process_entries\n>>> 3.143 : ....label:process_entries setup\n>>> 2.988 : ......label:plist special sort\n>>> 1.305 : ....label:processing\n>>> 2.604 : ..label:collect_merge_info\n>>> 2.018 : ..label:merge_start\n>>> 1.018 : ..label:renames\n>>>\n>>> In the above output, note that the 4.462 seconds for process_entries was\n>>> split as 3.143 seconds for \"process_entries setup\" and 1.305 seconds for\n>>> \"processing\" (and a little time for other stuff removed from the\n>>> highlight). Most of the \"process_entries setup\" time was spent on\n>>> \"plist special sort\" which corresponds to the following code:\n>>>\n>>> trace2_region_enter(\"merge\", \"plist special sort\", opt->repo);\n>>> plist.cmp = string_list_df_name_compare;\n>>> string_list_sort(&plist);\n>>> trace2_region_leave(\"merge\", \"plist special sort\", opt->repo);\n>>>\n>>> In other words, in a merge strategy that would be invoked by passing\n>>> \"-sort\" to either rebase or merge, sorting an array takes more time than\n>>> anything else. Serves me right for naming my merge strategy this way.\n>>>\n>>> Rewrite the comparison function and remove as many levels of indirection\n>>> as possible (e.g. the old code had\n>>> cmp_items() ->\n>>> string_list_df_name_compare() ->\n>>> df_name_compare()\n>>> now we just have sort_dirs_next_to_their_children()), and tweak it to be\n>>> as optimized as possible for our specific case. These changes reduced\n>>> the time spent in \"plist special sort\" by ~25% in the mega-renames case.\n>>>\n>>> For the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\n>>> performance work; instrument with trace2_region_* calls\", 2020-10-28),\n>>> this change improves the performance as follows:\n>>>\n>>> Before After\n>>> no-renames: 5.622 s ± 0.059 s 5.235 s ± 0.042 s\n>>> mega-renames: 10.127 s ± 0.073 s 9.419 s ± 0.107 s\n>>> just-one-mega: 500.3 ms ± 3.8 ms 480.1 ms ± 3.9 ms\n>>\n>> Interesting.\n>>\n>>>\n>>> Signed-off-by: Elijah Newren \n>>> ---\n>>> merge-ort.c | 64 ++++++++++++++++++++++++++++++++++-------------------\n>>> 1 file changed, 41 insertions(+), 23 deletions(-)\n>>>\n>>> diff --git a/merge-ort.c b/merge-ort.c\n>>> index 142d44d74d63..367aec4b7def 100644\n>>> --- a/merge-ort.c\n>>> +++ b/merge-ort.c\n>>> @@ -2746,31 +2746,50 @@ static int detect_and_process_renames(struct merge_options *opt,\n>>>\n>>> /*** Function Grouping: functions related to process_entries() ***/\n>>>\n>>> -static int string_list_df_name_compare(const char *one, const char *two)\n>>> +static int sort_dirs_next_to_their_children(const void *a, const void *b)\n>>> {\n>>> - int onelen = strlen(one);\n>>> - int twolen = strlen(two);\n>>\n>> The old code scans both strings fully, while the new one stops when it\n>> reaches a difference and doesn't look at any further characters. How\n>> much does that contribute to the speedup? (I suspect a lot.)\n>\n> Oh, indeed, good catch. It appears to be responsible for essentially all of it.\n\nThen you can keep the original function signature (as well as the use of\nstring_list_sort) and avoid explicit casts.\n\nThe same function exists in merge-recursive.c, by the way. I suspect we\ncould avoid sorting entirely there by taking advantage of the index\norder and a mechanism like the one in the second half of\nfsck.c::verify_ordered(). That's a bit tricky, though (for me anyway).\n\nAll tests still pass when I replace string_list_df_name_compare() with\nstrcmp() in merge-recursive.c, so the first thing needed would be tests\nthat highlight the difference between those comparison functions,\nhowever. Not sure if it's worth it -- merge-recursive is on its way\nout, right?\n\nNot sure if d/f conflicts could also be detected in merge-ort.c without\nsorting -- the original order is lost when the paths are thrown into\na strmap.\n\n>\n>>> /*\n>>> - * Here we only care that entries for D/F conflicts are\n>>> - * adjacent, in particular with the file of the D/F conflict\n>>> - * appearing before files below the corresponding directory.\n>>> - * The order of the rest of the list is irrelevant for us.\n>>> + * Here we only care that entries for directories appear adjacent\n>>> + * to and before files underneath the directory. In other words,\n>>> + * we do not want the natural sorting of\n>>> + * foo\n>>> + * foo.txt\n>>> + * foo/bar\n>>> + * Instead, we want \"foo\" to sort as though it were \"foo/\", so that\n>>> + * we instead get\n>>> + * foo.txt\n>>> + * foo\n>>> + * foo/bar\n>>> + * To achieve this, we basically implement our own strcmp, except that\n>>> + * if we get to the end of either string instead of comparing NUL to\n>>> + * another character, we compare '/' to it.\n>>> *\n>>> - * To achieve this, we sort with df_name_compare and provide\n>>> - * the mode S_IFDIR so that D/F conflicts will sort correctly.\n>>> - * We use the mode S_IFDIR for everything else for simplicity,\n>>> - * since in other cases any changes in their order due to\n>>> - * sorting cause no problems for us.\n>>> + * The reason to not use df_name_compare directly was that it was\n>>> + * just too expensive, so I had to reimplement it.\n>>> */\n>>> - int cmp = df_name_compare(one, onelen, S_IFDIR,\n>>> - two, twolen, S_IFDIR);\n>>> - /*\n>>> - * Now that 'foo' and 'foo/bar' compare equal, we have to make sure\n>>> - * that 'foo' comes before 'foo/bar'.\n>>> - */\n>>> - if (cmp)\n>>> - return cmp;\n>>> - return onelen - twolen;\n>>> + const char *one = ((struct string_list_item *)a)->string;\n>>> + const char *two = ((struct string_list_item *)b)->string;\n>>\n>> Casting away const, hmm. :-/ Harmless because no actual write is\n>> attempted, but still looks needlessly scary to me.\n>\n> Right, that should have been\n> + const char *one = ((const struct string_list_item *)a)->string;\n> + const char *two = ((const struct string_list_item *)b)->string;\n> but since I was just assigning to a const char * on those lines, I'm\n> not sure why it'd qualify as scary. Regardless, I'm happy to put\n> these consts back in.\n\nExplicit casts are a red flag already (anything could be cast to\nanything else) and if they remove const their severity increases. The\nresulting object text is fine, but the code yells \"TYPE SYSTEM\nOVERRRULED!\" And type checks in C are weak to begin with, so a casual\nreader has to wonder what kind of black magic is at work. None in\nthis case, as an implicit casts would have sufficed:\n\n\tconst struct string_list_item *item_a = a, *item_b = b;\n\tconst char *one = item_a->string, *two = item_b->string;\n\nBoring. Calming. Nice. ;) The compiler would warn us if the pieces\ndidn't fit.\n\nRené\n"},{"id":"425819","messageId":"CABPp-BHoZTFwcqZvLLdPR0deuBRjzeY9DgPVkCu4GYkt9=gc-Q@mail.gmail.com","threadId":"55781","inReplyTo":"106a5592-4e5e-cf06-16e4-100ca3c3fb5f@web.de","subject":"Re: [PATCH 1/5] merge-ort: replace string_list_df_name_compare with faster alternative","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-05-28T18:09:25Z","receivedAt":"2021-05-28T18:09:39Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, May 28, 2021 at 9:12 AM René Scharfe wrote:\n>\n> Am 28.05.21 um 00:47 schrieb Elijah Newren:\n> > On Thu, May 27, 2021 at 2:00 PM René Scharfe wrote:\n> >>\n> >> Am 27.05.21 um 10:37 schrieb Elijah Newren via GitGitGadget:\n...\n> >>> /*** Function Grouping: functions related to process_entries() ***/\n> >>>\n> >>> -static int string_list_df_name_compare(const char *one, const char *two)\n> >>> +static int sort_dirs_next_to_their_children(const void *a, const void *b)\n> >>> {\n> >>> - int onelen = strlen(one);\n> >>> - int twolen = strlen(two);\n> >>\n> >> The old code scans both strings fully, while the new one stops when it\n> >> reaches a difference and doesn't look at any further characters. How\n> >> much does that contribute to the speedup? (I suspect a lot.)\n> >\n> > Oh, indeed, good catch. It appears to be responsible for essentially all of it.\n>\n> Then you can keep the original function signature (as well as the use of\n> string_list_sort) and avoid explicit casts.\n\nFair enough; though I'll probably still apply the function rename,\neven if I keep the old signature. The function has a completely\ndifferent purpose in merge-ort.c than it does in merge-recursive.c.\n\n> The same function exists in merge-recursive.c, by the way. I suspect we\n> could avoid sorting entirely there by taking advantage of the index\n> order and a mechanism like the one in the second half of\n> fsck.c::verify_ordered(). That's a bit tricky, though (for me anyway).\n>\n> All tests still pass when I replace string_list_df_name_compare() with\n> strcmp() in merge-recursive.c, so the first thing needed would be tests\n> that highlight the difference between those comparison functions,\n> however. Not sure if it's worth it -- merge-recursive is on its way\n> out, right?\n\nInteresting idea (and interesting that the function might not matter\nanymore in merge-recursive.c and might be replaceable by strcmp), but\nyeah merge-recursive.c is on its way out. In fact, there are two\nother reasons to also not modify merge-recursive.c along these lines:\n(1) We want to keep merge-recursive stable right now as we push people\nto try out merge-ort, so that we have a good comparison point if they\nrun into problems; if we modify merge-recursive, especially in tricky\nways, then our comparison point might get invalidated. (2) This\ncodepath is relatively hot in merge-ort.c because it has optimized all\nthe other stuff, so saving approximately half a second is significant.\nIn merge-recursive.c, saving half a second is a small blip in the\noverall timing that would be lost in the run-to-run variability.\n(Saving 0.7s off of 10.127 s ± 0.073 s is huge; but removing that\nmuch time from 5964.031 s ± 10.459 is wasted effort.)\n\n> Not sure if d/f conflicts could also be detected in merge-ort.c without\n> sorting -- the original order is lost when the paths are thrown into\n> a strmap.\n\nWhile string_list_df_name_compare() in merge-recursive.c is used for\nthe purpose of detecting D/F conflicts, this function in merge-ort.c\nhad nothing to do with detecting D/F conflicts. In fact, D/F\nconflicts were already detected in collect_merge_info_callback() on\nthis line:\n\n unsigned df_conflict = (filemask != 0) && (dirmask != 0);\n\nand recorded in setup_path_info(), which was done long before it got\nto this point in the code. The point of this sorting in merge-ort.c\nis just to put paths in an order that allows us to write out trees as\nwe process them and record the resulting hash for the next directory\nup the chain as we go.\n"},{"id":"426136","messageId":"pull.962.v2.git.1622559516.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.git.1622104642.gitgitgadget@gmail.com","subject":"[PATCH v2 0/5] Optimization batch 12: miscellaneous unthemed stuff","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-01T14:58:30Z","receivedAt":"2021-06-01T14:58:41Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series depends on en/ort-perf-batch-11 textually, but is semantically\nindependent of it.\n\nChanges since v1 (all for the first patch):\n\n * Add more comments explaining the sorting function, its purpose, and how\n its expected to be called\n * Small style fixup\n * Switch back to using string_list_sort() instead of direct QSORT()\n\nThis short series has a few optimizations, but only one of which affects the\ntestcases of interest (namely, reducing our time spent on sorting an array).\nIt also fixes a few comments.\n\nFor the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\nperformance work; instrument with trace2_region_* calls\", 2020-10-28), the\nchanges in just this series improves the performance as follows:\n\n Before Series After Series\nno-renames: 5.622 s ± 0.059 s 5.235 s ± 0.042 s\nmega-renames: 10.127 s ± 0.073 s 9.419 s ± 0.107 s\njust-one-mega: 500.3 ms ± 3.8 ms 480.1 ms ± 3.9 ms\n\n\nAs a reminder, before any merge-ort/diffcore-rename performance work, the\nperformance results we started with were:\n\nno-renames-am: 6.940 s ± 0.485 s\nno-renames: 18.912 s ± 0.174 s\nmega-renames: 5964.031 s ± 10.459 s\njust-one-mega: 149.583 s ± 0.751 s\n\n\nElijah Newren (5):\n merge-ort: replace string_list_df_name_compare with faster alternative\n diffcore-rename: avoid unnecessary strdup'ing in break_idx\n diffcore-rename: enable limiting rename detection to relevant\n destinations\n Fix various issues found in comments\n merge-ort: miscellaneous touch-ups\n\n diffcore-rename.c | 52 ++++++++++++++---\n diffcore.h | 2 +\n merge-ort.c | 86 +++++++++++++++++++++--------\n t/t6423-merge-rename-directories.sh | 2 +-\n 4 files changed, 110 insertions(+), 32 deletions(-)\n\n\nbase-commit: 76e253793c9a1d7fdd1836d5e4db26dabd3d713a\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-962%2Fnewren%2Fort-perf-batch-12-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-962/newren/ort-perf-batch-12-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/962\n\nRange-diff vs v1:\n\n 1: 5055dfce3281 ! 1: c4a0f6a9510c merge-ort: replace string_list_df_name_compare with faster alternative\n @@ Commit message\n \"-sort\" to either rebase or merge, sorting an array takes more time than\n anything else. Serves me right for naming my merge strategy this way.\n \n - Rewrite the comparison function and remove as many levels of indirection\n - as possible (e.g. the old code had\n - cmp_items() ->\n - string_list_df_name_compare() ->\n - df_name_compare()\n - now we just have sort_dirs_next_to_their_children()), and tweak it to be\n - as optimized as possible for our specific case. These changes reduced\n - the time spent in \"plist special sort\" by ~25% in the mega-renames case.\n + Rewrite the comparison function in a way that does not require finding\n + out the lengths of the strings when comparing them. While at it, tweak\n + the code for our specific case -- no need to handle a variety of modes,\n + for example. The combination of these changes reduced the time spent in\n + \"plist special sort\" by ~25% in the mega-renames case.\n \n For the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\n performance work; instrument with trace2_region_* calls\", 2020-10-28),\n @@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt,\n /*** Function Grouping: functions related to process_entries() ***/\n \n -static int string_list_df_name_compare(const char *one, const char *two)\n -+static int sort_dirs_next_to_their_children(const void *a, const void *b)\n ++static int sort_dirs_next_to_their_children(const char *one, const char *two)\n {\n -\tint onelen = strlen(one);\n -\tint twolen = strlen(two);\n ++\tunsigned char c1, c2;\n ++\n \t/*\n -\t * Here we only care that entries for D/F conflicts are\n -\t * adjacent, in particular with the file of the D/F conflict\n -\t * appearing before files below the corresponding directory.\n -\t * The order of the rest of the list is irrelevant for us.\n +\t * Here we only care that entries for directories appear adjacent\n -+\t * to and before files underneath the directory. In other words,\n -+\t * we do not want the natural sorting of\n ++\t * to and before files underneath the directory. We can achieve\n ++\t * that by pretending to add a trailing slash to every file and\n ++\t * then sorting. In other words, we do not want the natural\n ++\t * sorting of\n +\t * foo\n +\t * foo.txt\n +\t * foo/bar\n @@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt,\n +\t * To achieve this, we basically implement our own strcmp, except that\n +\t * if we get to the end of either string instead of comparing NUL to\n +\t * another character, we compare '/' to it.\n ++\t *\n ++\t * If this unusual \"sort as though '/' were appended\" perplexes\n ++\t * you, perhaps it will help to note that this is not the final\n ++\t * sort. write_tree() will sort again without the trailing slash\n ++\t * magic, but just on paths immediately under a given tree.\n \t *\n -\t * To achieve this, we sort with df_name_compare and provide\n -\t * the mode S_IFDIR so that D/F conflicts will sort correctly.\n @@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt,\n -\t * since in other cases any changes in their order due to\n -\t * sorting cause no problems for us.\n +\t * The reason to not use df_name_compare directly was that it was\n -+\t * just too expensive, so I had to reimplement it.\n ++\t * just too expensive (we don't have the string lengths handy), so\n ++\t * I had to reimplement it.\n \t */\n -\tint cmp = df_name_compare(one, onelen, S_IFDIR,\n -\t\t\t\t two, twolen, S_IFDIR);\n --\t/*\n ++\n + \t/*\n -\t * Now that 'foo' and 'foo/bar' compare equal, we have to make sure\n -\t * that 'foo' comes before 'foo/bar'.\n --\t */\n ++\t * NOTE: This function will never be called with two equal strings,\n ++\t * because it is used to sort the keys of a strmap, and strmaps have\n ++\t * unique keys by construction. That simplifies our c1==c2 handling\n ++\t * below.\n + \t */\n -\tif (cmp)\n -\t\treturn cmp;\n -\treturn onelen - twolen;\n -+\tconst char *one = ((struct string_list_item *)a)->string;\n -+\tconst char *two = ((struct string_list_item *)b)->string;\n -+\tunsigned char c1, c2;\n +\n +\twhile (*one && (*one == *two)) {\n +\t\tone++;\n @@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt,\n +\tif (c1 == c2) {\n +\t\t/* Getting here means one is a leading directory of the other */\n +\t\treturn (*one) ? 1 : -1;\n -+\t}\n -+\telse\n ++\t} else\n +\t\treturn c1-c2;\n }\n \n @@ merge-ort.c: static void process_entries(struct merge_options *opt,\n \n \ttrace2_region_enter(\"merge\", \"plist special sort\", opt->repo);\n -\tplist.cmp = string_list_df_name_compare;\n --\tstring_list_sort(&plist);\n -+\tQSORT(plist.items, plist.nr, sort_dirs_next_to_their_children);\n ++\tplist.cmp = sort_dirs_next_to_their_children;\n + \tstring_list_sort(&plist);\n \ttrace2_region_leave(\"merge\", \"plist special sort\", opt->repo);\n \n - \ttrace2_region_leave(\"merge\", \"process_entries setup\", opt->repo);\n 2: 7212816c8d47 = 2: 38713ed48273 diffcore-rename: avoid unnecessary strdup'ing in break_idx\n 3: 19150b575058 = 3: 45e1de5fe780 diffcore-rename: enable limiting rename detection to relevant destinations\n 4: 98c9a419b313 = 4: 2f26d7e935c0 Fix various issues found in comments\n 5: e85dad887f95 = 5: 7156f26ab299 merge-ort: miscellaneous touch-ups\n\n-- \ngitgitgadget\n"},{"id":"426137","messageId":"c4a0f6a9510c6e57604e7b0c62b1216a4f5f5618.1622559516.git.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.v2.git.1622559516.gitgitgadget@gmail.com","subject":"[PATCH v2 1/5] merge-ort: replace string_list_df_name_compare with faster alternative","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-01T14:58:31Z","receivedAt":"2021-06-01T14:58:42Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nGathering accumulated times from trace2 output on the mega-renames\ntestcase, I saw the following timings (where I'm only showing a few\nlines to highlight the portions of interest):\n\n 10.120 : label:incore_nonrecursive\n 4.462 : ..label:process_entries\n 3.143 : ....label:process_entries setup\n 2.988 : ......label:plist special sort\n 1.305 : ....label:processing\n 2.604 : ..label:collect_merge_info\n 2.018 : ..label:merge_start\n 1.018 : ..label:renames\n\nIn the above output, note that the 4.462 seconds for process_entries was\nsplit as 3.143 seconds for \"process_entries setup\" and 1.305 seconds for\n\"processing\" (and a little time for other stuff removed from the\nhighlight). Most of the \"process_entries setup\" time was spent on\n\"plist special sort\" which corresponds to the following code:\n\n trace2_region_enter(\"merge\", \"plist special sort\", opt->repo);\n plist.cmp = string_list_df_name_compare;\n string_list_sort(&plist);\n trace2_region_leave(\"merge\", \"plist special sort\", opt->repo);\n\nIn other words, in a merge strategy that would be invoked by passing\n\"-sort\" to either rebase or merge, sorting an array takes more time than\nanything else. Serves me right for naming my merge strategy this way.\n\nRewrite the comparison function in a way that does not require finding\nout the lengths of the strings when comparing them. While at it, tweak\nthe code for our specific case -- no need to handle a variety of modes,\nfor example. The combination of these changes reduced the time spent in\n\"plist special sort\" by ~25% in the mega-renames case.\n\nFor the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\nperformance work; instrument with trace2_region_* calls\", 2020-10-28),\nthis change improves the performance as follows:\n\n Before After\n no-renames: 5.622 s ± 0.059 s 5.235 s ± 0.042 s\n mega-renames: 10.127 s ± 0.073 s 9.419 s ± 0.107 s\n just-one-mega: 500.3 ms ± 3.8 ms 480.1 ms ± 3.9 ms\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 72 ++++++++++++++++++++++++++++++++++++++---------------\n 1 file changed, 52 insertions(+), 20 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 142d44d74d63..0fe2eaf02eb2 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2746,31 +2746,63 @@ static int detect_and_process_renames(struct merge_options *opt,\n \n /*** Function Grouping: functions related to process_entries() ***/\n \n-static int string_list_df_name_compare(const char *one, const char *two)\n+static int sort_dirs_next_to_their_children(const char *one, const char *two)\n {\n-\tint onelen = strlen(one);\n-\tint twolen = strlen(two);\n+\tunsigned char c1, c2;\n+\n \t/*\n-\t * Here we only care that entries for D/F conflicts are\n-\t * adjacent, in particular with the file of the D/F conflict\n-\t * appearing before files below the corresponding directory.\n-\t * The order of the rest of the list is irrelevant for us.\n+\t * Here we only care that entries for directories appear adjacent\n+\t * to and before files underneath the directory. We can achieve\n+\t * that by pretending to add a trailing slash to every file and\n+\t * then sorting. In other words, we do not want the natural\n+\t * sorting of\n+\t * foo\n+\t * foo.txt\n+\t * foo/bar\n+\t * Instead, we want \"foo\" to sort as though it were \"foo/\", so that\n+\t * we instead get\n+\t * foo.txt\n+\t * foo\n+\t * foo/bar\n+\t * To achieve this, we basically implement our own strcmp, except that\n+\t * if we get to the end of either string instead of comparing NUL to\n+\t * another character, we compare '/' to it.\n+\t *\n+\t * If this unusual \"sort as though '/' were appended\" perplexes\n+\t * you, perhaps it will help to note that this is not the final\n+\t * sort. write_tree() will sort again without the trailing slash\n+\t * magic, but just on paths immediately under a given tree.\n \t *\n-\t * To achieve this, we sort with df_name_compare and provide\n-\t * the mode S_IFDIR so that D/F conflicts will sort correctly.\n-\t * We use the mode S_IFDIR for everything else for simplicity,\n-\t * since in other cases any changes in their order due to\n-\t * sorting cause no problems for us.\n+\t * The reason to not use df_name_compare directly was that it was\n+\t * just too expensive (we don't have the string lengths handy), so\n+\t * I had to reimplement it.\n \t */\n-\tint cmp = df_name_compare(one, onelen, S_IFDIR,\n-\t\t\t\t two, twolen, S_IFDIR);\n+\n \t/*\n-\t * Now that 'foo' and 'foo/bar' compare equal, we have to make sure\n-\t * that 'foo' comes before 'foo/bar'.\n+\t * NOTE: This function will never be called with two equal strings,\n+\t * because it is used to sort the keys of a strmap, and strmaps have\n+\t * unique keys by construction. That simplifies our c1==c2 handling\n+\t * below.\n \t */\n-\tif (cmp)\n-\t\treturn cmp;\n-\treturn onelen - twolen;\n+\n+\twhile (*one && (*one == *two)) {\n+\t\tone++;\n+\t\ttwo++;\n+\t}\n+\n+\tc1 = *one;\n+\tif (!c1)\n+\t\tc1 = '/';\n+\n+\tc2 = *two;\n+\tif (!c2)\n+\t\tc2 = '/';\n+\n+\tif (c1 == c2) {\n+\t\t/* Getting here means one is a leading directory of the other */\n+\t\treturn (*one) ? 1 : -1;\n+\t} else\n+\t\treturn c1-c2;\n }\n \n static int read_oid_strbuf(struct merge_options *opt,\n@@ -3481,7 +3513,7 @@ static void process_entries(struct merge_options *opt,\n \ttrace2_region_leave(\"merge\", \"plist copy\", opt->repo);\n \n \ttrace2_region_enter(\"merge\", \"plist special sort\", opt->repo);\n-\tplist.cmp = string_list_df_name_compare;\n+\tplist.cmp = sort_dirs_next_to_their_children;\n \tstring_list_sort(&plist);\n \ttrace2_region_leave(\"merge\", \"plist special sort\", opt->repo);\n \n-- \ngitgitgadget\n\n"},{"id":"426138","messageId":"45e1de5fe7808f5297d5e33d14c239d74de33bdc.1622559516.git.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.v2.git.1622559516.gitgitgadget@gmail.com","subject":"[PATCH v2 3/5] diffcore-rename: enable limiting rename detection to relevant destinations","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-01T14:58:33Z","receivedAt":"2021-06-01T14:58:44Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nOur former optimizations focused on limiting rename detection to a\npre-specified set of relevant sources. This was because the merge logic\nonly had a way of knowing which sources were relevant. However, other\ncallers of rename detection might benefit from being able to limit\nrename detection to a known set of relevant destinations. In\nparticular, a properly implemented `git log --follow` might benefit from\nsuch an ability.\n\nSince the code to implement such limiting is very similar to what we've\nalready done, just implement it now even though we do not yet have any\ncallers making use of this ability.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 48 +++++++++++++++++++++++++++++++++++++++++------\n diffcore.h | 2 ++\n merge-ort.c | 1 +\n 3 files changed, 45 insertions(+), 6 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex e333a6d64791..8ff83a9f3b99 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -372,6 +372,7 @@ struct dir_rename_info {\n \tstruct strmap dir_rename_guess;\n \tstruct strmap *dir_rename_count;\n \tstruct strintmap *relevant_source_dirs;\n+\tstruct strset *relevant_destination_dirs;\n \tunsigned setup;\n };\n \n@@ -491,8 +492,11 @@ static void update_dir_rename_counts(struct dir_rename_info *info,\n \t\t !strintmap_contains(info->relevant_source_dirs, old_dir))\n \t\t\tbreak;\n \n-\t\t/* Get new_dir */\n+\t\t/* Get new_dir, skip if its directory isn't relevant. */\n \t\tdirname_munge(new_dir);\n+\t\tif (info->relevant_destination_dirs &&\n+\t\t !strset_contains(info->relevant_destination_dirs, new_dir))\n+\t\t\tbreak;\n \n \t\t/*\n \t\t * When renaming\n@@ -567,6 +571,7 @@ static void update_dir_rename_counts(struct dir_rename_info *info,\n \n static void initialize_dir_rename_info(struct dir_rename_info *info,\n \t\t\t\t struct strintmap *relevant_sources,\n+\t\t\t\t struct strset *relevant_destinations,\n \t\t\t\t struct strintmap *dirs_removed,\n \t\t\t\t struct strmap *dir_rename_count,\n \t\t\t\t struct strmap *cached_pairs)\n@@ -575,7 +580,7 @@ static void initialize_dir_rename_info(struct dir_rename_info *info,\n \tstruct strmap_entry *entry;\n \tint i;\n \n-\tif (!dirs_removed && !relevant_sources) {\n+\tif (!dirs_removed && !relevant_sources && !relevant_destinations) {\n \t\tinfo->setup = 0;\n \t\treturn;\n \t}\n@@ -589,6 +594,18 @@ static void initialize_dir_rename_info(struct dir_rename_info *info,\n \tstrintmap_init_with_options(&info->idx_map, -1, NULL, 0);\n \tstrmap_init_with_options(&info->dir_rename_guess, NULL, 0);\n \n+\t/* Setup info->relevant_destination_dirs */\n+\tinfo->relevant_destination_dirs = NULL;\n+\tif (relevant_destinations) {\n+\t\tinfo->relevant_destination_dirs = xmalloc(sizeof(struct strset));\n+\t\tstrset_init(info->relevant_destination_dirs);\n+\t\tstrset_for_each_entry(relevant_destinations, &iter, entry) {\n+\t\t\tchar *dirname = get_dirname(entry->key);\n+\t\t\tstrset_add(info->relevant_destination_dirs, dirname);\n+\t\t\tfree(dirname);\n+\t\t}\n+\t}\n+\n \t/* Setup info->relevant_source_dirs */\n \tinfo->relevant_source_dirs = NULL;\n \tif (dirs_removed || !relevant_sources) {\n@@ -700,6 +717,12 @@ static void cleanup_dir_rename_info(struct dir_rename_info *info,\n \t\tFREE_AND_NULL(info->relevant_source_dirs);\n \t}\n \n+\t/* relevant_destination_dirs */\n+\tif (info->relevant_destination_dirs) {\n+\t\tstrset_clear(info->relevant_destination_dirs);\n+\t\tFREE_AND_NULL(info->relevant_destination_dirs);\n+\t}\n+\n \t/* dir_rename_count */\n \tif (!keep_dir_rename_count) {\n \t\tpartial_clear_dir_rename_count(info->dir_rename_count);\n@@ -827,6 +850,7 @@ static int find_basename_matches(struct diff_options *options,\n \t\t\t\t int minimum_score,\n \t\t\t\t struct dir_rename_info *info,\n \t\t\t\t struct strintmap *relevant_sources,\n+\t\t\t\t struct strset *relevant_destinations,\n \t\t\t\t struct strintmap *dirs_removed)\n {\n \t/*\n@@ -949,9 +973,15 @@ static int find_basename_matches(struct diff_options *options,\n \t\t\tif (rename_dst[dst_index].is_rename)\n \t\t\t\tcontinue; /* already used previously */\n \n-\t\t\t/* Estimate the similarity */\n \t\t\tone = rename_src[src_index].p->one;\n \t\t\ttwo = rename_dst[dst_index].p->two;\n+\n+\t\t\t/* Skip irrelevant destinations */\n+\t\t\tif (relevant_destinations &&\n+\t\t\t !strset_contains(relevant_destinations, two->path))\n+\t\t\t\tcontinue;\n+\n+\t\t\t/* Estimate the similarity */\n \t\t\tscore = estimate_similarity(options->repo, one, two,\n \t\t\t\t\t\t minimum_score, skip_unmodified);\n \n@@ -1258,6 +1288,7 @@ static void handle_early_known_dir_renames(struct dir_rename_info *info,\n \n void diffcore_rename_extended(struct diff_options *options,\n \t\t\t struct strintmap *relevant_sources,\n+\t\t\t struct strset *relevant_destinations,\n \t\t\t struct strintmap *dirs_removed,\n \t\t\t struct strmap *dir_rename_count,\n \t\t\t struct strmap *cached_pairs)\n@@ -1376,8 +1407,8 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t/* Preparation for basename-driven matching. */\n \t\ttrace2_region_enter(\"diff\", \"dir rename setup\", options->repo);\n \t\tinitialize_dir_rename_info(&info, relevant_sources,\n-\t\t\t\t\t dirs_removed, dir_rename_count,\n-\t\t\t\t\t cached_pairs);\n+\t\t\t\t\t relevant_destinations, dirs_removed,\n+\t\t\t\t\t dir_rename_count, cached_pairs);\n \t\ttrace2_region_leave(\"diff\", \"dir rename setup\", options->repo);\n \n \t\t/* Utilize file basenames to quickly find renames. */\n@@ -1386,6 +1417,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t\t\t\t\t min_basename_score,\n \t\t\t\t\t\t &info,\n \t\t\t\t\t\t relevant_sources,\n+\t\t\t\t\t\t relevant_destinations,\n \t\t\t\t\t\t dirs_removed);\n \t\ttrace2_region_leave(\"diff\", \"basename matches\", options->repo);\n \n@@ -1441,6 +1473,10 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\tif (rename_dst[i].is_rename)\n \t\t\tcontinue; /* exact or basename match already handled */\n \n+\t\tif (relevant_destinations &&\n+\t\t !strset_contains(relevant_destinations, two->path))\n+\t\t\tcontinue;\n+\n \t\tm = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];\n \t\tfor (j = 0; j < NUM_CANDIDATE_PER_DST; j++)\n \t\t\tm[j].dst = -1;\n@@ -1574,5 +1610,5 @@ void diffcore_rename_extended(struct diff_options *options,\n \n void diffcore_rename(struct diff_options *options)\n {\n-\tdiffcore_rename_extended(options, NULL, NULL, NULL, NULL);\n+\tdiffcore_rename_extended(options, NULL, NULL, NULL, NULL, NULL);\n }\ndiff --git a/diffcore.h b/diffcore.h\nindex 533b30e21e7f..435c7094f403 100644\n--- a/diffcore.h\n+++ b/diffcore.h\n@@ -10,6 +10,7 @@ struct diff_options;\n struct repository;\n struct strintmap;\n struct strmap;\n+struct strset;\n struct userdiff_driver;\n \n /* This header file is internal between diff.c and its diff transformers\n@@ -180,6 +181,7 @@ void diffcore_break(struct repository *, int);\n void diffcore_rename(struct diff_options *);\n void diffcore_rename_extended(struct diff_options *options,\n \t\t\t struct strintmap *relevant_sources,\n+\t\t\t struct strset *relevant_destinations,\n \t\t\t struct strintmap *dirs_removed,\n \t\t\t struct strmap *dir_rename_count,\n \t\t\t struct strmap *cached_pairs);\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 0fe2eaf02eb2..28951c35ddc2 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2568,6 +2568,7 @@ static void detect_regular_renames(struct merge_options *opt,\n \ttrace2_region_enter(\"diff\", \"diffcore_rename\", opt->repo);\n \tdiffcore_rename_extended(&diff_opts,\n \t\t\t\t &renames->relevant_sources[side_index],\n+\t\t\t\t NULL,\n \t\t\t\t &renames->dirs_removed[side_index],\n \t\t\t\t &renames->dir_rename_count[side_index],\n \t\t\t\t &renames->cached_pairs[side_index]);\n-- \ngitgitgadget\n\n"},{"id":"426139","messageId":"38713ed482736af8d1dea4d180651fd919837109.1622559516.git.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.v2.git.1622559516.gitgitgadget@gmail.com","subject":"[PATCH v2 2/5] diffcore-rename: avoid unnecessary strdup'ing in break_idx","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-01T14:58:32Z","receivedAt":"2021-06-01T14:58:45Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThe keys of break_idx are strings from the diff_filepairs of\ndiff_queued_diff. break_idx is only used in location_rename_dst(), and\nthat usage is always before any free'ing of the pairs (and thus the\nstrings in the pairs). As such, there is no need to strdup these keys;\nwe can just reuse the existing strings as-is.\n\nThe merge logic doesn't make use of break detection, so this does not\naffect the performance of any of my testcases. It was just a minor\nunrelated optimization noted in passing while looking at the code.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 3375e24659ea..e333a6d64791 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -54,7 +54,7 @@ static void register_rename_src(struct diff_filepair *p)\n \tif (p->broken_pair) {\n \t\tif (!break_idx) {\n \t\t\tbreak_idx = xmalloc(sizeof(*break_idx));\n-\t\t\tstrintmap_init(break_idx, -1);\n+\t\t\tstrintmap_init_with_options(break_idx, -1, NULL, 0);\n \t\t}\n \t\tstrintmap_set(break_idx, p->one->path, rename_dst_nr);\n \t}\n-- \ngitgitgadget\n\n"},{"id":"426141","messageId":"2f26d7e935c08ae792c5c8ae00a1f897fc5b1a5a.1622559516.git.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.v2.git.1622559516.gitgitgadget@gmail.com","subject":"[PATCH v2 4/5] Fix various issues found in comments","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-01T14:58:34Z","receivedAt":"2021-06-01T14:58:45Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nA random hodge-podge of incorrect or out-of-date comments that I found:\n\n * t6423 had a comment that has referred to the wrong test for years;\n fix it to refer to the right one.\n * diffcore-rename had a FIXME comment meant to remind myself to\n investigate if I could make another code change. I later\n investigated and removed the FIXME, but while cherry-picking the\n patch to submit upstream I missed the later update. Remove the\n comment now.\n * merge-ort had the early part of a comment for a function; I had\n meant to include the more involved description when I updated the\n function. Update the comment now.\n\nSigned-off-by: Elijah Newren \n---\n diffcore-rename.c | 2 +-\n merge-ort.c | 8 +++++---\n t/t6423-merge-rename-directories.sh | 2 +-\n 3 files changed, 7 insertions(+), 5 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 8ff83a9f3b99..c9f7d59cf62b 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -1579,7 +1579,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t\t/* all the usual ones need to be kept */\n \t\t\tdiff_q(&outq, p);\n \t\telse\n-\t\t\t/* no need to keep unmodified pairs; FIXME: remove earlier? */\n+\t\t\t/* no need to keep unmodified pairs */\n \t\t\tpair_to_free = p;\n \n \t\tif (pair_to_free)\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 28951c35ddc2..14b3e14bbe47 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2533,7 +2533,7 @@ static int compare_pairs(const void *a_, const void *b_)\n \treturn strcmp(a->one->path, b->one->path);\n }\n \n-/* Call diffcore_rename() to compute which files have changed on given side */\n+/* Call diffcore_rename() to update deleted/added pairs into rename pairs */\n static void detect_regular_renames(struct merge_options *opt,\n \t\t\t\t unsigned side_index)\n {\n@@ -2587,8 +2587,10 @@ static void detect_regular_renames(struct merge_options *opt,\n }\n \n /*\n- * Get information of all renames which occurred in 'side_pairs', discarding\n- * non-renames.\n+ * Get information of all renames which occurred in 'side_pairs', making use\n+ * of any implicit directory renames in side_dir_renames (also making use of\n+ * implicit directory renames rename_exclusions as needed by\n+ * check_for_directory_rename()). Add all (updated) renames into result.\n */\n static int collect_renames(struct merge_options *opt,\n \t\t\t struct diff_queue_struct *result,\ndiff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh\nindex be84d22419d9..e834b7e6efe0 100755\n--- a/t/t6423-merge-rename-directories.sh\n+++ b/t/t6423-merge-rename-directories.sh\n@@ -454,7 +454,7 @@ test_expect_success '1f: Split a directory into two other directories' '\n # the directory renamed, but the files within it. (see 1b)\n #\n # If renames split a directory into two or more others, the directory\n-# with the most renames, \"wins\" (see 1c). However, see the testcases\n+# with the most renames, \"wins\" (see 1f). However, see the testcases\n # in section 2, plus testcases 3a and 4a.\n ###########################################################################\n \n-- \ngitgitgadget\n\n"},{"id":"426140","messageId":"7156f26ab29919344c929be540d404dce2d5fe50.1622559516.git.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.v2.git.1622559516.gitgitgadget@gmail.com","subject":"[PATCH v2 5/5] merge-ort: miscellaneous touch-ups","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-01T14:58:35Z","receivedAt":"2021-06-01T14:58:46Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nAdd some notes in the code about invariants with match_mask when adding\npairs. Also add a comment that seems to have been left out in my work\nof pushing these changes upstream.\n\nSigned-off-by: Elijah Newren \n---\n merge-ort.c | 5 +++++\n 1 file changed, 5 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 14b3e14bbe47..d428b73dedd4 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -765,6 +765,7 @@ static void add_pair(struct merge_options *opt,\n \tint names_idx = is_add ? side : 0;\n \n \tif (is_add) {\n+\t\tassert(match_mask == 0 || match_mask == 6);\n \t\tif (strset_contains(&renames->cached_target_names[side],\n \t\t\t\t pathname))\n \t\t\treturn;\n@@ -772,6 +773,8 @@ static void add_pair(struct merge_options *opt,\n \t\tunsigned content_relevant = (match_mask == 0);\n \t\tunsigned location_relevant = (dir_rename_mask == 0x07);\n \n+\t\tassert(match_mask == 0 || match_mask == 3 || match_mask == 5);\n+\n \t\t/*\n \t\t * If pathname is found in cached_irrelevant[side] due to\n \t\t * previous pick but for this commit content is relevant,\n@@ -3483,6 +3486,8 @@ static void process_entry(struct merge_options *opt,\n \t */\n \tif (!ci->merged.clean)\n \t\tstrmap_put(&opt->priv->conflicted, path, ci);\n+\n+\t/* Record metadata for ci->merged in dir_metadata */\n \trecord_entry_for_tree(dir_metadata, path, &ci->merged);\n }\n \n-- \ngitgitgadget\n"},{"id":"426225","messageId":"11416fb2-50f1-ebf0-e2ca-cebe64aeeeed@gmail.com","threadId":"55781","inReplyTo":"c4a0f6a9510c6e57604e7b0c62b1216a4f5f5618.1622559516.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 1/5] merge-ort: replace string_list_df_name_compare with faster alternative","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-06-02T11:29:17Z","receivedAt":"2021-06-02T11:29:26Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/1/21 10:58 AM, Elijah Newren via GitGitGadget wrote:\n> From: Elijah Newren \n> \n...\n> \t/*\n> -\t * Here we only care that entries for D/F conflicts are\n> -\t * adjacent, in particular with the file of the D/F conflict\n> -\t * appearing before files below the corresponding directory.\n> -\t * The order of the rest of the list is irrelevant for us.\n> +\t * Here we only care that entries for directories appear adjacent\n> +\t * to and before files underneath the directory. We can achieve\n> +\t * that by pretending to add a trailing slash to every file and\n> +\t * then sorting. In other words, we do not want the natural\n> +\t * sorting of\n> +\t * foo\n> +\t * foo.txt\n> +\t * foo/bar\n> +\t * Instead, we want \"foo\" to sort as though it were \"foo/\", so that\n> +\t * we instead get\n> +\t * foo.txt\n> +\t * foo\n> +\t * foo/bar\n> +\t * To achieve this, we basically implement our own strcmp, except that\n> +\t * if we get to the end of either string instead of comparing NUL to\n> +\t * another character, we compare '/' to it.\n> +\t *\n> +\t * If this unusual \"sort as though '/' were appended\" perplexes\n> +\t * you, perhaps it will help to note that this is not the final\n> +\t * sort. write_tree() will sort again without the trailing slash\n> +\t * magic, but just on paths immediately under a given tree.\n\nI find this comment to be helpful.\n\n> +\t * The reason to not use df_name_compare directly was that it was\n> +\t * just too expensive (we don't have the string lengths handy), so\n> +\t * I had to reimplement it.\n\nJust a hyper-nit I think first person works great in commit\nmessages, as the author's name is clearly listed in context.\nHere, I'd prefer \"so it was reimplemented\" over \"so I had to\nreimplement it\" as the author will not be present in context.\n\n> +\n> +\twhile (*one && (*one == *two)) {\n> +\t\tone++;\n> +\t\ttwo++;\n> +\t}\n> +\n> +\tc1 = *one;\n> +\tif (!c1)\n> +\t\tc1 = '/';\n> +\n> +\tc2 = *two;\n> +\tif (!c2)\n> +\t\tc2 = '/';\n\nWhile I'm making other nits on this patch, perhaps this is\nan appropriate place for some ternary operators to compress\nthe vertical space in this method:\n\n\tc1 = *one ? *one : '/';\n\tc2 = *two ? *two : '/';\n\n> +\tif (c1 == c2) {\n> +\t\t/* Getting here means one is a leading directory of the other */\n> +\t\treturn (*one) ? 1 : -1;\n> +\t} else\n> +\t\treturn c1-c2;\n\nnit: \"c1 - c2\"\n\nThanks,\n-Stolee\n"},{"id":"426324","messageId":"1016e500-8169-7bb3-8428-b5ea35d19630@gmail.com","threadId":"55781","inReplyTo":"45e1de5fe7808f5297d5e33d14c239d74de33bdc.1622559516.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 3/5] diffcore-rename: enable limiting rename detection to relevant destinations","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-06-03T12:54:08Z","receivedAt":"2021-06-03T12:54:28Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/1/2021 10:58 AM, Elijah Newren via GitGitGadget wrote:\n> From: Elijah Newren \n> \n> Our former optimizations focused on limiting rename detection to a\n> pre-specified set of relevant sources. This was because the merge logic\n> only had a way of knowing which sources were relevant. However, other\n> callers of rename detection might benefit from being able to limit\n> rename detection to a known set of relevant destinations. In\n> particular, a properly implemented `git log --follow` might benefit from\n> such an ability.\n\nI would be interested in seeing such an improvement. It could also\nhelp the batch-download of missing blobs in a partial clone situation\nbecause it would only need the \"deletes\" portion of the diff, since we\nonly care about one \"add\" (we'd need that blob, too, of course).\n \n> Since the code to implement such limiting is very similar to what we've\n> already done, just implement it now even though we do not yet have any\n> callers making use of this ability.\n\nHowever, I'm not sure that this change is warranted without such an\nintegration. Perhaps keep this patch here on the list as a reference\nfor anyone who wants to do the `git log --follow` speedup? This person\ncan include \"you in the future\".\n\nI'm just worried that without a consumer, this code has no automated\nvalidation and can either be buggy now or become buggy in the future\nbefore someone starts trying to use the logic.\n\nThanks,\n-Stolee\n\n"},{"id":"426325","messageId":"20ec3b80-ce94-6ccf-05f1-3ee488e467ca@gmail.com","threadId":"55781","inReplyTo":"pull.962.v2.git.1622559516.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 0/5] Optimization batch 12: miscellaneous unthemed stuff","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-06-03T12:55:39Z","receivedAt":"2021-06-03T12:56:59Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/1/2021 10:58 AM, Elijah Newren via GitGitGadget wrote:\n> This series depends on en/ort-perf-batch-11 textually, but is semantically\n> independent of it.\n\nI have read this series and really only found some nits in\nPatch 1, but also think Patch 3 should be ejected until it can\nbe consumed by a full integration with a testable command.\n\nThe other patches look good to me.\n\nThanks,\n-Stolee\n"},{"id":"426327","messageId":"CABPp-BHaGEKYKCbwJxYgk7mY_mx6h9dSReRn=PXEpd0xCzqsdg@mail.gmail.com","threadId":"55781","inReplyTo":"1016e500-8169-7bb3-8428-b5ea35d19630@gmail.com","subject":"Re: [PATCH v2 3/5] diffcore-rename: enable limiting rename detection to relevant destinations","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-06-03T14:13:08Z","receivedAt":"2021-06-03T14:14:20Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Jun 3, 2021 at 5:54 AM Derrick Stolee wrote:\n>\n> On 6/1/2021 10:58 AM, Elijah Newren via GitGitGadget wrote:\n> > From: Elijah Newren \n> >\n> > Our former optimizations focused on limiting rename detection to a\n> > pre-specified set of relevant sources. This was because the merge logic\n> > only had a way of knowing which sources were relevant. However, other\n> > callers of rename detection might benefit from being able to limit\n> > rename detection to a known set of relevant destinations. In\n> > particular, a properly implemented `git log --follow` might benefit from\n> > such an ability.\n>\n> I would be interested in seeing such an improvement. It could also\n> help the batch-download of missing blobs in a partial clone situation\n> because it would only need the \"deletes\" portion of the diff, since we\n> only care about one \"add\" (we'd need that blob, too, of course).\n\nOh, good point. And in order to work well with the new prefetching\nimprovements (which will be the next series submitted), I should\nreally rename remove_unneeded_paths_from_src() to\nremove_unneeded_paths() and add a relevant_destinations parameter and\nuse it, instead of having the strset_contains() check in\ndiffcore_rename_extended.\n\n> > Since the code to implement such limiting is very similar to what we've\n> > already done, just implement it now even though we do not yet have any\n> > callers making use of this ability.\n>\n> However, I'm not sure that this change is warranted without such an\n> integration. Perhaps keep this patch here on the list as a reference\n> for anyone who wants to do the `git log --follow` speedup? This person\n> can include \"you in the future\".\n>\n> I'm just worried that without a consumer, this code has no automated\n> validation and can either be buggy now or become buggy in the future\n> before someone starts trying to use the logic.\n\nFair enough; I'll pull it out.\n"},{"id":"426389","messageId":"f63ffc2a7c22faea9ffea9abbd95595b6a1196de.1622781578.git.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.v3.git.1622781578.gitgitgadget@gmail.com","subject":"[PATCH v3 1/4] merge-ort: replace string_list_df_name_compare with faster alternative","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-04T04:39:35Z","receivedAt":"2021-06-04T04:39:57Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nGathering accumulated times from trace2 output on the mega-renames\ntestcase, I saw the following timings (where I'm only showing a few\nlines to highlight the portions of interest):\n\n 10.120 : label:incore_nonrecursive\n 4.462 : ..label:process_entries\n 3.143 : ....label:process_entries setup\n 2.988 : ......label:plist special sort\n 1.305 : ....label:processing\n 2.604 : ..label:collect_merge_info\n 2.018 : ..label:merge_start\n 1.018 : ..label:renames\n\nIn the above output, note that the 4.462 seconds for process_entries was\nsplit as 3.143 seconds for \"process_entries setup\" and 1.305 seconds for\n\"processing\" (and a little time for other stuff removed from the\nhighlight). Most of the \"process_entries setup\" time was spent on\n\"plist special sort\" which corresponds to the following code:\n\n trace2_region_enter(\"merge\", \"plist special sort\", opt->repo);\n plist.cmp = string_list_df_name_compare;\n string_list_sort(&plist);\n trace2_region_leave(\"merge\", \"plist special sort\", opt->repo);\n\nIn other words, in a merge strategy that would be invoked by passing\n\"-sort\" to either rebase or merge, sorting an array takes more time than\nanything else. Serves me right for naming my merge strategy this way.\n\nRewrite the comparison function in a way that does not require finding\nout the lengths of the strings when comparing them. While at it, tweak\nthe code for our specific case -- no need to handle a variety of modes,\nfor example. The combination of these changes reduced the time spent in\n\"plist special sort\" by ~25% in the mega-renames case.\n\nFor the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\nperformance work; instrument with trace2_region_* calls\", 2020-10-28),\nthis change improves the performance as follows:\n\n Before After\n no-renames: 5.622 s ± 0.059 s 5.235 s ± 0.042 s\n mega-renames: 10.127 s ± 0.073 s 9.419 s ± 0.107 s\n just-one-mega: 500.3 ms ± 3.8 ms 480.1 ms ± 3.9 ms\n\nSigned-off-by: Elijah Newren \nAcked-by: Derrick Stolee \n---\n merge-ort.c | 67 +++++++++++++++++++++++++++++++++++++----------------\n 1 file changed, 47 insertions(+), 20 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 142d44d74d63..061f15701359 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2746,31 +2746,58 @@ static int detect_and_process_renames(struct merge_options *opt,\n \n /*** Function Grouping: functions related to process_entries() ***/\n \n-static int string_list_df_name_compare(const char *one, const char *two)\n+static int sort_dirs_next_to_their_children(const char *one, const char *two)\n {\n-\tint onelen = strlen(one);\n-\tint twolen = strlen(two);\n+\tunsigned char c1, c2;\n+\n \t/*\n-\t * Here we only care that entries for D/F conflicts are\n-\t * adjacent, in particular with the file of the D/F conflict\n-\t * appearing before files below the corresponding directory.\n-\t * The order of the rest of the list is irrelevant for us.\n+\t * Here we only care that entries for directories appear adjacent\n+\t * to and before files underneath the directory. We can achieve\n+\t * that by pretending to add a trailing slash to every file and\n+\t * then sorting. In other words, we do not want the natural\n+\t * sorting of\n+\t * foo\n+\t * foo.txt\n+\t * foo/bar\n+\t * Instead, we want \"foo\" to sort as though it were \"foo/\", so that\n+\t * we instead get\n+\t * foo.txt\n+\t * foo\n+\t * foo/bar\n+\t * To achieve this, we basically implement our own strcmp, except that\n+\t * if we get to the end of either string instead of comparing NUL to\n+\t * another character, we compare '/' to it.\n+\t *\n+\t * If this unusual \"sort as though '/' were appended\" perplexes\n+\t * you, perhaps it will help to note that this is not the final\n+\t * sort. write_tree() will sort again without the trailing slash\n+\t * magic, but just on paths immediately under a given tree.\n \t *\n-\t * To achieve this, we sort with df_name_compare and provide\n-\t * the mode S_IFDIR so that D/F conflicts will sort correctly.\n-\t * We use the mode S_IFDIR for everything else for simplicity,\n-\t * since in other cases any changes in their order due to\n-\t * sorting cause no problems for us.\n+\t * The reason to not use df_name_compare directly was that it was\n+\t * just too expensive (we don't have the string lengths handy), so\n+\t * it was reimplemented.\n \t */\n-\tint cmp = df_name_compare(one, onelen, S_IFDIR,\n-\t\t\t\t two, twolen, S_IFDIR);\n+\n \t/*\n-\t * Now that 'foo' and 'foo/bar' compare equal, we have to make sure\n-\t * that 'foo' comes before 'foo/bar'.\n+\t * NOTE: This function will never be called with two equal strings,\n+\t * because it is used to sort the keys of a strmap, and strmaps have\n+\t * unique keys by construction. That simplifies our c1==c2 handling\n+\t * below.\n \t */\n-\tif (cmp)\n-\t\treturn cmp;\n-\treturn onelen - twolen;\n+\n+\twhile (*one && (*one == *two)) {\n+\t\tone++;\n+\t\ttwo++;\n+\t}\n+\n+\tc1 = *one ? *one : '/';\n+\tc2 = *two ? *two : '/';\n+\n+\tif (c1 == c2) {\n+\t\t/* Getting here means one is a leading directory of the other */\n+\t\treturn (*one) ? 1 : -1;\n+\t} else\n+\t\treturn c1 - c2;\n }\n \n static int read_oid_strbuf(struct merge_options *opt,\n@@ -3481,7 +3508,7 @@ static void process_entries(struct merge_options *opt,\n \ttrace2_region_leave(\"merge\", \"plist copy\", opt->repo);\n \n \ttrace2_region_enter(\"merge\", \"plist special sort\", opt->repo);\n-\tplist.cmp = string_list_df_name_compare;\n+\tplist.cmp = sort_dirs_next_to_their_children;\n \tstring_list_sort(&plist);\n \ttrace2_region_leave(\"merge\", \"plist special sort\", opt->repo);\n \n-- \ngitgitgadget\n\n"},{"id":"426390","messageId":"pull.962.v3.git.1622781578.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.v2.git.1622559516.gitgitgadget@gmail.com","subject":"[PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-04T04:39:34Z","receivedAt":"2021-06-04T04:39:59Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series depends on en/ort-perf-batch-11 textually, but is semantically\nindependent of it.\n\nChanges since v2:\n\n * Made suggested minor tweaks from Stolee on Patch 1\n * Dropped patch 3, for now\n * Added Stolee's Acked-by\n\nChanges since v1 (all for the first patch):\n\n * Add more comments explaining the sorting function, its purpose, and how\n its expected to be called\n * Small style fixup\n * Switch back to using string_list_sort() instead of direct QSORT()\n\nThis short series has a few optimizations, but only one of which affects the\ntestcases of interest (namely, reducing our time spent on sorting an array).\nIt also fixes a few comments.\n\nFor the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\nperformance work; instrument with trace2_region_* calls\", 2020-10-28), the\nchanges in just this series improves the performance as follows:\n\n Before Series After Series\nno-renames: 5.622 s ± 0.059 s 5.235 s ± 0.042 s\nmega-renames: 10.127 s ± 0.073 s 9.419 s ± 0.107 s\njust-one-mega: 500.3 ms ± 3.8 ms 480.1 ms ± 3.9 ms\n\n\nAs a reminder, before any merge-ort/diffcore-rename performance work, the\nperformance results we started with were:\n\nno-renames-am: 6.940 s ± 0.485 s\nno-renames: 18.912 s ± 0.174 s\nmega-renames: 5964.031 s ± 10.459 s\njust-one-mega: 149.583 s ± 0.751 s\n\n\nElijah Newren (4):\n merge-ort: replace string_list_df_name_compare with faster alternative\n diffcore-rename: avoid unnecessary strdup'ing in break_idx\n Fix various issues found in comments\n merge-ort: miscellaneous touch-ups\n\n diffcore-rename.c | 4 +-\n merge-ort.c | 80 ++++++++++++++++++++---------\n t/t6423-merge-rename-directories.sh | 2 +-\n 3 files changed, 60 insertions(+), 26 deletions(-)\n\n\nbase-commit: 76e253793c9a1d7fdd1836d5e4db26dabd3d713a\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-962%2Fnewren%2Fort-perf-batch-12-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-962/newren/ort-perf-batch-12-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/962\n\nRange-diff vs v2:\n\n 1: c4a0f6a9510c ! 1: f63ffc2a7c22 merge-ort: replace string_list_df_name_compare with faster alternative\n @@ Commit message\n just-one-mega: 500.3 ms ± 3.8 ms 480.1 ms ± 3.9 ms\n \n Signed-off-by: Elijah Newren \n + Acked-by: Derrick Stolee \n \n ## merge-ort.c ##\n @@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt,\n @@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt,\n -\t * sorting cause no problems for us.\n +\t * The reason to not use df_name_compare directly was that it was\n +\t * just too expensive (we don't have the string lengths handy), so\n -+\t * I had to reimplement it.\n ++\t * it was reimplemented.\n \t */\n -\tint cmp = df_name_compare(one, onelen, S_IFDIR,\n -\t\t\t\t two, twolen, S_IFDIR);\n @@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt,\n +\t\ttwo++;\n +\t}\n +\n -+\tc1 = *one;\n -+\tif (!c1)\n -+\t\tc1 = '/';\n -+\n -+\tc2 = *two;\n -+\tif (!c2)\n -+\t\tc2 = '/';\n ++\tc1 = *one ? *one : '/';\n ++\tc2 = *two ? *two : '/';\n +\n +\tif (c1 == c2) {\n +\t\t/* Getting here means one is a leading directory of the other */\n +\t\treturn (*one) ? 1 : -1;\n +\t} else\n -+\t\treturn c1-c2;\n ++\t\treturn c1 - c2;\n }\n \n static int read_oid_strbuf(struct merge_options *opt,\n 2: 38713ed48273 ! 2: cd13499a6ff5 diffcore-rename: avoid unnecessary strdup'ing in break_idx\n @@ Commit message\n unrelated optimization noted in passing while looking at the code.\n \n Signed-off-by: Elijah Newren \n + Acked-by: Derrick Stolee \n \n ## diffcore-rename.c ##\n @@ diffcore-rename.c: static void register_rename_src(struct diff_filepair *p)\n 3: 45e1de5fe780 < -: ------------ diffcore-rename: enable limiting rename detection to relevant destinations\n 4: 2f26d7e935c0 ! 3: 91c0962a7d75 Fix various issues found in comments\n @@ Commit message\n function. Update the comment now.\n \n Signed-off-by: Elijah Newren \n + Acked-by: Derrick Stolee \n \n ## diffcore-rename.c ##\n @@ diffcore-rename.c: void diffcore_rename_extended(struct diff_options *options,\n 5: 7156f26ab299 ! 4: 01352fcdf3a9 merge-ort: miscellaneous touch-ups\n @@ Commit message\n of pushing these changes upstream.\n \n Signed-off-by: Elijah Newren \n + Acked-by: Derrick Stolee \n \n ## merge-ort.c ##\n @@ merge-ort.c: static void add_pair(struct merge_options *opt,\n\n-- \ngitgitgadget\n"},{"id":"426391","messageId":"91c0962a7d75f3f56441446b022c05fc87810230.1622781578.git.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.v3.git.1622781578.gitgitgadget@gmail.com","subject":"[PATCH v3 3/4] Fix various issues found in comments","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-04T04:39:37Z","receivedAt":"2021-06-04T04:40:06Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nA random hodge-podge of incorrect or out-of-date comments that I found:\n\n * t6423 had a comment that has referred to the wrong test for years;\n fix it to refer to the right one.\n * diffcore-rename had a FIXME comment meant to remind myself to\n investigate if I could make another code change. I later\n investigated and removed the FIXME, but while cherry-picking the\n patch to submit upstream I missed the later update. Remove the\n comment now.\n * merge-ort had the early part of a comment for a function; I had\n meant to include the more involved description when I updated the\n function. Update the comment now.\n\nSigned-off-by: Elijah Newren \nAcked-by: Derrick Stolee \n---\n diffcore-rename.c | 2 +-\n merge-ort.c | 8 +++++---\n t/t6423-merge-rename-directories.sh | 2 +-\n 3 files changed, 7 insertions(+), 5 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex e333a6d64791..35378d84e8f1 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -1543,7 +1543,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t\t/* all the usual ones need to be kept */\n \t\t\tdiff_q(&outq, p);\n \t\telse\n-\t\t\t/* no need to keep unmodified pairs; FIXME: remove earlier? */\n+\t\t\t/* no need to keep unmodified pairs */\n \t\t\tpair_to_free = p;\n \n \t\tif (pair_to_free)\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 061f15701359..2ec382e292a6 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2533,7 +2533,7 @@ static int compare_pairs(const void *a_, const void *b_)\n \treturn strcmp(a->one->path, b->one->path);\n }\n \n-/* Call diffcore_rename() to compute which files have changed on given side */\n+/* Call diffcore_rename() to update deleted/added pairs into rename pairs */\n static void detect_regular_renames(struct merge_options *opt,\n \t\t\t\t unsigned side_index)\n {\n@@ -2586,8 +2586,10 @@ static void detect_regular_renames(struct merge_options *opt,\n }\n \n /*\n- * Get information of all renames which occurred in 'side_pairs', discarding\n- * non-renames.\n+ * Get information of all renames which occurred in 'side_pairs', making use\n+ * of any implicit directory renames in side_dir_renames (also making use of\n+ * implicit directory renames rename_exclusions as needed by\n+ * check_for_directory_rename()). Add all (updated) renames into result.\n */\n static int collect_renames(struct merge_options *opt,\n \t\t\t struct diff_queue_struct *result,\ndiff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh\nindex be84d22419d9..e834b7e6efe0 100755\n--- a/t/t6423-merge-rename-directories.sh\n+++ b/t/t6423-merge-rename-directories.sh\n@@ -454,7 +454,7 @@ test_expect_success '1f: Split a directory into two other directories' '\n # the directory renamed, but the files within it. (see 1b)\n #\n # If renames split a directory into two or more others, the directory\n-# with the most renames, \"wins\" (see 1c). However, see the testcases\n+# with the most renames, \"wins\" (see 1f). However, see the testcases\n # in section 2, plus testcases 3a and 4a.\n ###########################################################################\n \n-- \ngitgitgadget\n\n"},{"id":"426392","messageId":"01352fcdf3a96480ffa4e25a103a83a9e5d7f67a.1622781578.git.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.v3.git.1622781578.gitgitgadget@gmail.com","subject":"[PATCH v3 4/4] merge-ort: miscellaneous touch-ups","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-04T04:39:38Z","receivedAt":"2021-06-04T04:40:54Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nAdd some notes in the code about invariants with match_mask when adding\npairs. Also add a comment that seems to have been left out in my work\nof pushing these changes upstream.\n\nSigned-off-by: Elijah Newren \nAcked-by: Derrick Stolee \n---\n merge-ort.c | 5 +++++\n 1 file changed, 5 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 2ec382e292a6..cfa751053b01 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -765,6 +765,7 @@ static void add_pair(struct merge_options *opt,\n \tint names_idx = is_add ? side : 0;\n \n \tif (is_add) {\n+\t\tassert(match_mask == 0 || match_mask == 6);\n \t\tif (strset_contains(&renames->cached_target_names[side],\n \t\t\t\t pathname))\n \t\t\treturn;\n@@ -772,6 +773,8 @@ static void add_pair(struct merge_options *opt,\n \t\tunsigned content_relevant = (match_mask == 0);\n \t\tunsigned location_relevant = (dir_rename_mask == 0x07);\n \n+\t\tassert(match_mask == 0 || match_mask == 3 || match_mask == 5);\n+\n \t\t/*\n \t\t * If pathname is found in cached_irrelevant[side] due to\n \t\t * previous pick but for this commit content is relevant,\n@@ -3477,6 +3480,8 @@ static void process_entry(struct merge_options *opt,\n \t */\n \tif (!ci->merged.clean)\n \t\tstrmap_put(&opt->priv->conflicted, path, ci);\n+\n+\t/* Record metadata for ci->merged in dir_metadata */\n \trecord_entry_for_tree(dir_metadata, path, &ci->merged);\n }\n \n-- \ngitgitgadget\n"},{"id":"426393","messageId":"cd13499a6ff5f9ac2287d18ff00d8f7d1690bb6c.1622781578.git.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.v3.git.1622781578.gitgitgadget@gmail.com","subject":"[PATCH v3 2/4] diffcore-rename: avoid unnecessary strdup'ing in break_idx","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-04T04:39:36Z","receivedAt":"2021-06-04T04:40:59Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThe keys of break_idx are strings from the diff_filepairs of\ndiff_queued_diff. break_idx is only used in location_rename_dst(), and\nthat usage is always before any free'ing of the pairs (and thus the\nstrings in the pairs). As such, there is no need to strdup these keys;\nwe can just reuse the existing strings as-is.\n\nThe merge logic doesn't make use of break detection, so this does not\naffect the performance of any of my testcases. It was just a minor\nunrelated optimization noted in passing while looking at the code.\n\nSigned-off-by: Elijah Newren \nAcked-by: Derrick Stolee \n---\n diffcore-rename.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 3375e24659ea..e333a6d64791 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -54,7 +54,7 @@ static void register_rename_src(struct diff_filepair *p)\n \tif (p->broken_pair) {\n \t\tif (!break_idx) {\n \t\t\tbreak_idx = xmalloc(sizeof(*break_idx));\n-\t\t\tstrintmap_init(break_idx, -1);\n+\t\t\tstrintmap_init_with_options(break_idx, -1, NULL, 0);\n \t\t}\n \t\tstrintmap_set(break_idx, p->one->path, rename_dst_nr);\n \t}\n-- \ngitgitgadget\n\n"},{"id":"426415","messageId":"a5755340-c0c8-8028-7c03-3c8e7f0268d1@gmail.com","threadId":"55781","inReplyTo":"pull.962.v3.git.1622781578.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-06-04T13:11:16Z","receivedAt":"2021-06-04T13:12:36Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/4/2021 12:39 AM, Elijah Newren via GitGitGadget wrote:\n> This series depends on en/ort-perf-batch-11 textually, but is semantically\n> independent of it.\n> \n> Changes since v2:\n> \n> * Made suggested minor tweaks from Stolee on Patch 1\n> * Dropped patch 3, for now\n\nWith these changes, I think the code is good to go.\n\n> * Added Stolee's Acked-by\n...\n> 1: c4a0f6a9510c ! 1: f63ffc2a7c22 merge-ort: replace string_list_df_name_compare with faster alternative\n> @@ Commit message\n> just-one-mega: 500.3 ms ± 3.8 ms 480.1 ms ± 3.9 ms\n> \n> Signed-off-by: Elijah Newren \n> + Acked-by: Derrick Stolee \n\nI believe the sign-off should always be the last thing in\nthe message. Perhaps Junio is willing to fix this without a\nre-roll?\n\nFeel free to replace Acked-by with Reviewed-by.\n\nThanks,\n-Stolee\n"},{"id":"426420","messageId":"CABPp-BEsiw-E9_TGUDaGEkhQHNqLH48=ZTu7yXX7XqRaM2JdOQ@mail.gmail.com","threadId":"55781","inReplyTo":"a5755340-c0c8-8028-7c03-3c8e7f0268d1@gmail.com","subject":"Re: [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-06-04T15:48:21Z","receivedAt":"2021-06-04T15:49:49Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Jun 4, 2021 at 6:11 AM Derrick Stolee wrote:\n>\n> On 6/4/2021 12:39 AM, Elijah Newren via GitGitGadget wrote:\n> > This series depends on en/ort-perf-batch-11 textually, but is semantically\n> > independent of it.\n> >\n> > Changes since v2:\n> >\n> > * Made suggested minor tweaks from Stolee on Patch 1\n> > * Dropped patch 3, for now\n>\n> With these changes, I think the code is good to go.\n>\n> > * Added Stolee's Acked-by\n> ...\n> > 1: c4a0f6a9510c ! 1: f63ffc2a7c22 merge-ort: replace string_list_df_name_compare with faster alternative\n> > @@ Commit message\n> > just-one-mega: 500.3 ms ± 3.8 ms 480.1 ms ± 3.9 ms\n> >\n> > Signed-off-by: Elijah Newren \n> > + Acked-by: Derrick Stolee \n>\n> I believe the sign-off should always be the last thing in\n> the message. Perhaps Junio is willing to fix this without a\n> re-roll?\n\nInteresting, this is the first I've ever heard of such a requirement,\nand I've submitted patches this way numerous times and have seen\nothers do it. A quick search through git.git history says there are\n5133 commits that place such trailers before the author's\nSigned-off-by, and 1175 that place them after. While the former is\nclearly more common, and some of the latter could have been Junio\nadding trailers while applying the patches, there still seem like\nplenty of counter-examples suggesting that there is no rule here.\n\nDigging into Documentation/SubmittingPatches, I find three places that\nsuggest or state something about placement of trailers.\n\n'''\n[[real-name]]\nAlso notice that a real name is used in the `Signed-off-by` trailer. Please\ndon't hide your real name.\n\n[[commit-trailers]]\nIf you like, you can put extra tags at the end:\n'''\n\nWhich isn't definitive but seems like it could be easy to accidentally\nconstrue as a rule that says the opposite, namely that other trailers\ncome after the Signed-off-by. Another part of the document states:\n\n'''\nyou add a \"Signed-off-by\" trailer to your commit, that looks like\nthis:\n\n....\n Signed-off-by: Random J Developer \n....\n'''\n\nwhich possibly suggests that the relative location compared to other\ntrailers does not matter. The wording in that document that comes\nclosest to your interpretation is\n\n'''\nAt the beginning of the\npatch should come your commit message, ending with the\n`Signed-off-by` trailers'''\n'''\n\nbut if it had really meant to convey the rule you suggest here, it\nshould have said \"ending with your Signed-off-by trailer\"; the\n\"trailers\" here to me suggest the phrasing here has a totally\ndifferent meaning than your rule.\n\nSo, if \"Signed-off-by should come last\" is a rule, then neither\nexisting practice nor our documentation seem to cover it. I'll assume\nit's not a rule for now.\n\n> Feel free to replace Acked-by with Reviewed-by.\n\nThanks.\n"},{"id":"426421","messageId":"CABPp-BHbDY+y6mJb3QgYeLaqbPM8qphOGmoZXsO31094ZWgwrA@mail.gmail.com","threadId":"55781","inReplyTo":"CABPp-BEsiw-E9_TGUDaGEkhQHNqLH48=ZTu7yXX7XqRaM2JdOQ@mail.gmail.com","subject":"Re: [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-06-04T16:30:15Z","receivedAt":"2021-06-04T16:30:43Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Jun 4, 2021 at 8:48 AM Elijah Newren wrote:\n>\n> On Fri, Jun 4, 2021 at 6:11 AM Derrick Stolee wrote:\n> >\n> > On 6/4/2021 12:39 AM, Elijah Newren via GitGitGadget wrote:\n\n> > > * Added Stolee's Acked-by\n> > ...\n> > > 1: c4a0f6a9510c ! 1: f63ffc2a7c22 merge-ort: replace string_list_df_name_compare with faster alternative\n> > > @@ Commit message\n> > > just-one-mega: 500.3 ms ± 3.8 ms 480.1 ms ± 3.9 ms\n> > >\n> > > Signed-off-by: Elijah Newren \n> > > + Acked-by: Derrick Stolee \n> >\n> > I believe the sign-off should always be the last thing in\n> > the message. Perhaps Junio is willing to fix this without a\n> > re-roll?\n>\n> Interesting, this is the first I've ever heard of such a requirement,\n> and I've submitted patches this way numerous times and have seen\n> others do it. A quick search through git.git history says there are\n> 5133 commits that place such trailers before the author's\n> Signed-off-by, and 1175 that place them after. While the former is\n\nSorry, there was a bug in my script, found while running it on the\nlinux kernel (where the Signed-off-by stuff came from) to see if it\nwas different. The corrected numbers are:\n\nAuthor Signed-off-by comes after all non-Signed-off-by trailers: 2990\nnon-Signed-off-by trailers follow the Author's Signed-off-by line: 3069\n\nSo, this suggests it's even less of a rule. For those curious, the\nLinux kernel has these numbers:\n\nAuthor Signed-off-by comes after all non-Signed-off-by trailers: 83530\nnon-Signed-off-by trailers follow the Author's Signed-off-by line: 199778\n\n> ...\n> So, if \"Signed-off-by should come last\" is a rule, then neither\n> existing practice nor our documentation seem to cover it. I'll assume\n> it's not a rule for now.\n"},{"id":"426422","messageId":"YLpWbLkaqVYqTrGL@coredump.intra.peff.net","threadId":"55781","inReplyTo":"CABPp-BEsiw-E9_TGUDaGEkhQHNqLH48=ZTu7yXX7XqRaM2JdOQ@mail.gmail.com","subject":"Re: [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-06-04T16:35:56Z","receivedAt":"2021-06-04T16:35:58Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jun 04, 2021 at 08:48:21AM -0700, Elijah Newren wrote:\n\n> > > Signed-off-by: Elijah Newren \n> > > + Acked-by: Derrick Stolee \n> >\n> > I believe the sign-off should always be the last thing in\n> > the message. Perhaps Junio is willing to fix this without a\n> > re-roll?\n> \n> Interesting, this is the first I've ever heard of such a requirement,\n> and I've submitted patches this way numerous times and have seen\n> others do it. A quick search through git.git history says there are\n> 5133 commits that place such trailers before the author's\n> Signed-off-by, and 1175 that place them after. While the former is\n> clearly more common, and some of the latter could have been Junio\n> adding trailers while applying the patches, there still seem like\n> plenty of counter-examples suggesting that there is no rule here.\n\nI don't think there's a hard rule here. The usual advice (which I also\ndidn't find documented from a quick grep, but hopefully is kind of\nintuitive) is that trailers should be chronological.\n\nSo if you picked up a patch from person X who signed off, then you\nmodified and signed off the result, then Junio signed off after\napplying, we'd expect that chain of custody to be represented by reading\ntop to bottom. And that's what happens if you use \"am -s\", \"commit -s\",\netc.\n\nWhether \"Acked-by\" happens after the author signs off or not is\ndebatable. Obviously it happens after the version of the patch that is\nsent out. But if you re-send with an Acked-by, is the signoff your one\nfrom before that happened first, or a new one that happened as you sent\nout the patch? Perhaps a question for the philosophers. ;)\n\nAnyway, I think it is perfectly fine either way (as your numbers\nindicate).\n\n-Peff\n"},{"id":"426431","messageId":"c9d596f3-cfc9-4bb7-1008-4873dafd8270@gmail.com","threadId":"55781","inReplyTo":"YLpWbLkaqVYqTrGL@coredump.intra.peff.net","subject":"Re: [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-06-04T18:42:03Z","receivedAt":"2021-06-04T18:42:08Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/4/2021 12:35 PM, Jeff King wrote:\n> On Fri, Jun 04, 2021 at 08:48:21AM -0700, Elijah Newren wrote:\n> \n>>>> Signed-off-by: Elijah Newren \n>>>> + Acked-by: Derrick Stolee \n>>>\n>>> I believe the sign-off should always be the last thing in\n>>> the message. Perhaps Junio is willing to fix this without a\n>>> re-roll?\n>>\n>> Interesting, this is the first I've ever heard of such a requirement,\n>> and I've submitted patches this way numerous times and have seen\n>> others do it. A quick search through git.git history says there are\n>> 5133 commits that place such trailers before the author's\n>> Signed-off-by, and 1175 that place them after. While the former is\n>> clearly more common, and some of the latter could have been Junio\n>> adding trailers while applying the patches, there still seem like\n>> plenty of counter-examples suggesting that there is no rule here.\n> \n> I don't think there's a hard rule here. The usual advice (which I also\n> didn't find documented from a quick grep, but hopefully is kind of\n> intuitive) is that trailers should be chronological.\n> \n> So if you picked up a patch from person X who signed off, then you\n> modified and signed off the result, then Junio signed off after\n> applying, we'd expect that chain of custody to be represented by reading\n> top to bottom. And that's what happens if you use \"am -s\", \"commit -s\",\n> etc.\n> \n> Whether \"Acked-by\" happens after the author signs off or not is\n> debatable. Obviously it happens after the version of the patch that is\n> sent out. But if you re-send with an Acked-by, is the signoff your one\n> from before that happened first, or a new one that happened as you sent\n> out the patch? Perhaps a question for the philosophers. ;)\n\nI guess I was just interpreting that the \"Acked-by\" was part of\nthe content you created, and hence it should be covered by the\nsign-off. I can imagine that if Junio added it, then it would be\nafter your sign-off but before his.\n \n> Anyway, I think it is perfectly fine either way (as your numbers\n> indicate).\n\nI agree. I didn't mean to make a big deal of it.\n\nThanks,\n-Stolee\n"},{"id":"426433","messageId":"CABPp-BH=UVvEyBpVG+8+V-7wNjXS1hsQoZoqYs-xnPKRg3SPBA@mail.gmail.com","threadId":"55781","inReplyTo":"c9d596f3-cfc9-4bb7-1008-4873dafd8270@gmail.com","subject":"Re: [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2021-06-04T19:43:10Z","receivedAt":"2021-06-04T19:44:23Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Jun 4, 2021 at 11:42 AM Derrick Stolee wrote:\n>\n> On 6/4/2021 12:35 PM, Jeff King wrote:\n> > On Fri, Jun 04, 2021 at 08:48:21AM -0700, Elijah Newren wrote:\n> >\n> >>>> Signed-off-by: Elijah Newren \n> >>>> + Acked-by: Derrick Stolee \n> >>>\n> >>> I believe the sign-off should always be the last thing in\n> >>> the message. Perhaps Junio is willing to fix this without a\n> >>> re-roll?\n> >>\n> >> Interesting, this is the first I've ever heard of such a requirement,\n> >> and I've submitted patches this way numerous times and have seen\n> >> others do it. A quick search through git.git history says there are\n> >> 5133 commits that place such trailers before the author's\n> >> Signed-off-by, and 1175 that place them after. While the former is\n> >> clearly more common, and some of the latter could have been Junio\n> >> adding trailers while applying the patches, there still seem like\n> >> plenty of counter-examples suggesting that there is no rule here.\n> >\n> > I don't think there's a hard rule here. The usual advice (which I also\n> > didn't find documented from a quick grep, but hopefully is kind of\n> > intuitive) is that trailers should be chronological.\n> >\n> > So if you picked up a patch from person X who signed off, then you\n> > modified and signed off the result, then Junio signed off after\n> > applying, we'd expect that chain of custody to be represented by reading\n> > top to bottom. And that's what happens if you use \"am -s\", \"commit -s\",\n> > etc.\n> >\n> > Whether \"Acked-by\" happens after the author signs off or not is\n> > debatable. Obviously it happens after the version of the patch that is\n> > sent out. But if you re-send with an Acked-by, is the signoff your one\n> > from before that happened first, or a new one that happened as you sent\n> > out the patch? Perhaps a question for the philosophers. ;)\n>\n> I guess I was just interpreting that the \"Acked-by\" was part of\n> the content you created, and hence it should be covered by the\n> sign-off. I can imagine that if Junio added it, then it would be\n> after your sign-off but before his.\n>\n> > Anyway, I think it is perfectly fine either way (as your numbers\n> > indicate).\n>\n> I agree. I didn't mean to make a big deal of it.\n\nSorry, it was me who made a big deal out of it. I was just really\nsurprised that I had missed another rule (you correctly caught one I\ndid miss on a recent other series I submitted), and so I thought it\nwas prudent to go digging and see how I had _also_ missed this rule\nand refresh myself on the rules in general. And once I did that,\nalthough I felt this one probably didn't qualify, I thought it was\nuseful to share what I found and highlight what I thought needed\nclarification if I was wrong.\n"},{"id":"426435","messageId":"YLqEnEJgQANm1SCD@coredump.intra.peff.net","threadId":"55781","inReplyTo":"c9d596f3-cfc9-4bb7-1008-4873dafd8270@gmail.com","subject":"Re: [PATCH v3 0/4] Optimization batch 12: miscellaneous unthemed stuff","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-06-04T19:53:00Z","receivedAt":"2021-06-04T19:53:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jun 04, 2021 at 02:42:03PM -0400, Derrick Stolee wrote:\n\n> > Whether \"Acked-by\" happens after the author signs off or not is\n> > debatable. Obviously it happens after the version of the patch that is\n> > sent out. But if you re-send with an Acked-by, is the signoff your one\n> > from before that happened first, or a new one that happened as you sent\n> > out the patch? Perhaps a question for the philosophers. ;)\n> \n> I guess I was just interpreting that the \"Acked-by\" was part of\n> the content you created, and hence it should be covered by the\n> sign-off. I can imagine that if Junio added it, then it would be\n> after your sign-off but before his.\n\nFWIW, that's how I interpret it, too. I was curious how it looks for my\nown patches, which is easy-ish to dig up with:\n\n git log --author=peff --grep=Acked-by --format='%H%n%(trailers)'\n\nThey're mostly after my signoff there, but I think that's because I very\nrarely add in the Ack, and mostly Junio does it (likewise for\nReviewed-by).\n\nMy workflow is maybe a little different than others, too, in that I very\nrarely signoff patches in my repo, but add it via \"format-patch -s\" when\nsending them out (so naturally it would come after anything I had\ntyped).\n\n> > Anyway, I think it is perfectly fine either way (as your numbers\n> > indicate).\n> \n> I agree. I didn't mean to make a big deal of it.\n\nIt was a little bit of an interesting diversion, though. :)\n\n-Peff\n"},{"id":"426784","messageId":"be858c46cfe76e59b526f6d7af497ef70280765e.1623168703.git.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.v4.git.1623168703.gitgitgadget@gmail.com","subject":"[PATCH v4 2/4] diffcore-rename: avoid unnecessary strdup'ing in break_idx","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-08T16:11:40Z","receivedAt":"2021-06-08T16:12:09Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nThe keys of break_idx are strings from the diff_filepairs of\ndiff_queued_diff. break_idx is only used in location_rename_dst(), and\nthat usage is always before any free'ing of the pairs (and thus the\nstrings in the pairs). As such, there is no need to strdup these keys;\nwe can just reuse the existing strings as-is.\n\nThe merge logic doesn't make use of break detection, so this does not\naffect the performance of any of my testcases. It was just a minor\nunrelated optimization noted in passing while looking at the code.\n\nSigned-off-by: Elijah Newren \nReviewed-by: Derrick Stolee \n---\n diffcore-rename.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex 3375e24659ea..e333a6d64791 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -54,7 +54,7 @@ static void register_rename_src(struct diff_filepair *p)\n \tif (p->broken_pair) {\n \t\tif (!break_idx) {\n \t\t\tbreak_idx = xmalloc(sizeof(*break_idx));\n-\t\t\tstrintmap_init(break_idx, -1);\n+\t\t\tstrintmap_init_with_options(break_idx, -1, NULL, 0);\n \t\t}\n \t\tstrintmap_set(break_idx, p->one->path, rename_dst_nr);\n \t}\n-- \ngitgitgadget\n\n"},{"id":"426785","messageId":"pull.962.v4.git.1623168703.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.v3.git.1622781578.gitgitgadget@gmail.com","subject":"[PATCH v4 0/4] Optimization batch 12: miscellaneous unthemed stuff","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-08T16:11:38Z","receivedAt":"2021-06-08T16:12:12Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"This series depends on en/ort-perf-batch-11 textually, but is semantically\nindependent of it.\n\nChanges since v3:\n\n * Changed Acked-by from Stolee to Reviewed-by.\n\nChanges since v2:\n\n * Made suggested minor tweaks from Stolee on Patch 1\n * Dropped patch 3, for now\n * Added Stolee's Acked-by\n\nChanges since v1 (all for the first patch):\n\n * Add more comments explaining the sorting function, its purpose, and how\n its expected to be called\n * Small style fixup\n * Switch back to using string_list_sort() instead of direct QSORT()\n\nThis short series has a few optimizations, but only one of which affects the\ntestcases of interest (namely, reducing our time spent on sorting an array).\nIt also fixes a few comments.\n\nFor the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\nperformance work; instrument with trace2_region_* calls\", 2020-10-28), the\nchanges in just this series improves the performance as follows:\n\n Before Series After Series\nno-renames: 5.622 s ± 0.059 s 5.235 s ± 0.042 s\nmega-renames: 10.127 s ± 0.073 s 9.419 s ± 0.107 s\njust-one-mega: 500.3 ms ± 3.8 ms 480.1 ms ± 3.9 ms\n\n\nAs a reminder, before any merge-ort/diffcore-rename performance work, the\nperformance results we started with were:\n\nno-renames-am: 6.940 s ± 0.485 s\nno-renames: 18.912 s ± 0.174 s\nmega-renames: 5964.031 s ± 10.459 s\njust-one-mega: 149.583 s ± 0.751 s\n\n\nElijah Newren (4):\n merge-ort: replace string_list_df_name_compare with faster alternative\n diffcore-rename: avoid unnecessary strdup'ing in break_idx\n Fix various issues found in comments\n merge-ort: miscellaneous touch-ups\n\n diffcore-rename.c | 4 +-\n merge-ort.c | 80 ++++++++++++++++++++---------\n t/t6423-merge-rename-directories.sh | 2 +-\n 3 files changed, 60 insertions(+), 26 deletions(-)\n\n\nbase-commit: 76e253793c9a1d7fdd1836d5e4db26dabd3d713a\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-962%2Fnewren%2Fort-perf-batch-12-v4\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-962/newren/ort-perf-batch-12-v4\nPull-Request: https://github.com/gitgitgadget/git/pull/962\n\nRange-diff vs v3:\n\n 1: f63ffc2a7c22 ! 1: 140c1e89e0ec merge-ort: replace string_list_df_name_compare with faster alternative\n @@ Commit message\n just-one-mega: 500.3 ms ± 3.8 ms 480.1 ms ± 3.9 ms\n \n Signed-off-by: Elijah Newren \n - Acked-by: Derrick Stolee \n + Reviewed-by: Derrick Stolee \n \n ## merge-ort.c ##\n @@ merge-ort.c: static int detect_and_process_renames(struct merge_options *opt,\n 2: cd13499a6ff5 ! 2: be858c46cfe7 diffcore-rename: avoid unnecessary strdup'ing in break_idx\n @@ Commit message\n unrelated optimization noted in passing while looking at the code.\n \n Signed-off-by: Elijah Newren \n - Acked-by: Derrick Stolee \n + Reviewed-by: Derrick Stolee \n \n ## diffcore-rename.c ##\n @@ diffcore-rename.c: static void register_rename_src(struct diff_filepair *p)\n 3: 91c0962a7d75 ! 3: 55c0f2c4560a Fix various issues found in comments\n @@ Commit message\n function. Update the comment now.\n \n Signed-off-by: Elijah Newren \n - Acked-by: Derrick Stolee \n + Reviewed-by: Derrick Stolee \n \n ## diffcore-rename.c ##\n @@ diffcore-rename.c: void diffcore_rename_extended(struct diff_options *options,\n 4: 01352fcdf3a9 ! 4: 6de569e6ac49 merge-ort: miscellaneous touch-ups\n @@ Commit message\n of pushing these changes upstream.\n \n Signed-off-by: Elijah Newren \n - Acked-by: Derrick Stolee \n + Reviewed-by: Derrick Stolee \n \n ## merge-ort.c ##\n @@ merge-ort.c: static void add_pair(struct merge_options *opt,\n\n-- \ngitgitgadget\n"},{"id":"426786","messageId":"140c1e89e0ec69c5c5e8a99b632c1cf25c2325d4.1623168703.git.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.v4.git.1623168703.gitgitgadget@gmail.com","subject":"[PATCH v4 1/4] merge-ort: replace string_list_df_name_compare with faster alternative","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-08T16:11:39Z","receivedAt":"2021-06-08T16:12:47Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nGathering accumulated times from trace2 output on the mega-renames\ntestcase, I saw the following timings (where I'm only showing a few\nlines to highlight the portions of interest):\n\n 10.120 : label:incore_nonrecursive\n 4.462 : ..label:process_entries\n 3.143 : ....label:process_entries setup\n 2.988 : ......label:plist special sort\n 1.305 : ....label:processing\n 2.604 : ..label:collect_merge_info\n 2.018 : ..label:merge_start\n 1.018 : ..label:renames\n\nIn the above output, note that the 4.462 seconds for process_entries was\nsplit as 3.143 seconds for \"process_entries setup\" and 1.305 seconds for\n\"processing\" (and a little time for other stuff removed from the\nhighlight). Most of the \"process_entries setup\" time was spent on\n\"plist special sort\" which corresponds to the following code:\n\n trace2_region_enter(\"merge\", \"plist special sort\", opt->repo);\n plist.cmp = string_list_df_name_compare;\n string_list_sort(&plist);\n trace2_region_leave(\"merge\", \"plist special sort\", opt->repo);\n\nIn other words, in a merge strategy that would be invoked by passing\n\"-sort\" to either rebase or merge, sorting an array takes more time than\nanything else. Serves me right for naming my merge strategy this way.\n\nRewrite the comparison function in a way that does not require finding\nout the lengths of the strings when comparing them. While at it, tweak\nthe code for our specific case -- no need to handle a variety of modes,\nfor example. The combination of these changes reduced the time spent in\n\"plist special sort\" by ~25% in the mega-renames case.\n\nFor the testcases mentioned in commit 557ac0350d (\"merge-ort: begin\nperformance work; instrument with trace2_region_* calls\", 2020-10-28),\nthis change improves the performance as follows:\n\n Before After\n no-renames: 5.622 s ± 0.059 s 5.235 s ± 0.042 s\n mega-renames: 10.127 s ± 0.073 s 9.419 s ± 0.107 s\n just-one-mega: 500.3 ms ± 3.8 ms 480.1 ms ± 3.9 ms\n\nSigned-off-by: Elijah Newren \nReviewed-by: Derrick Stolee \n---\n merge-ort.c | 67 +++++++++++++++++++++++++++++++++++++----------------\n 1 file changed, 47 insertions(+), 20 deletions(-)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 142d44d74d63..061f15701359 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2746,31 +2746,58 @@ static int detect_and_process_renames(struct merge_options *opt,\n \n /*** Function Grouping: functions related to process_entries() ***/\n \n-static int string_list_df_name_compare(const char *one, const char *two)\n+static int sort_dirs_next_to_their_children(const char *one, const char *two)\n {\n-\tint onelen = strlen(one);\n-\tint twolen = strlen(two);\n+\tunsigned char c1, c2;\n+\n \t/*\n-\t * Here we only care that entries for D/F conflicts are\n-\t * adjacent, in particular with the file of the D/F conflict\n-\t * appearing before files below the corresponding directory.\n-\t * The order of the rest of the list is irrelevant for us.\n+\t * Here we only care that entries for directories appear adjacent\n+\t * to and before files underneath the directory. We can achieve\n+\t * that by pretending to add a trailing slash to every file and\n+\t * then sorting. In other words, we do not want the natural\n+\t * sorting of\n+\t * foo\n+\t * foo.txt\n+\t * foo/bar\n+\t * Instead, we want \"foo\" to sort as though it were \"foo/\", so that\n+\t * we instead get\n+\t * foo.txt\n+\t * foo\n+\t * foo/bar\n+\t * To achieve this, we basically implement our own strcmp, except that\n+\t * if we get to the end of either string instead of comparing NUL to\n+\t * another character, we compare '/' to it.\n+\t *\n+\t * If this unusual \"sort as though '/' were appended\" perplexes\n+\t * you, perhaps it will help to note that this is not the final\n+\t * sort. write_tree() will sort again without the trailing slash\n+\t * magic, but just on paths immediately under a given tree.\n \t *\n-\t * To achieve this, we sort with df_name_compare and provide\n-\t * the mode S_IFDIR so that D/F conflicts will sort correctly.\n-\t * We use the mode S_IFDIR for everything else for simplicity,\n-\t * since in other cases any changes in their order due to\n-\t * sorting cause no problems for us.\n+\t * The reason to not use df_name_compare directly was that it was\n+\t * just too expensive (we don't have the string lengths handy), so\n+\t * it was reimplemented.\n \t */\n-\tint cmp = df_name_compare(one, onelen, S_IFDIR,\n-\t\t\t\t two, twolen, S_IFDIR);\n+\n \t/*\n-\t * Now that 'foo' and 'foo/bar' compare equal, we have to make sure\n-\t * that 'foo' comes before 'foo/bar'.\n+\t * NOTE: This function will never be called with two equal strings,\n+\t * because it is used to sort the keys of a strmap, and strmaps have\n+\t * unique keys by construction. That simplifies our c1==c2 handling\n+\t * below.\n \t */\n-\tif (cmp)\n-\t\treturn cmp;\n-\treturn onelen - twolen;\n+\n+\twhile (*one && (*one == *two)) {\n+\t\tone++;\n+\t\ttwo++;\n+\t}\n+\n+\tc1 = *one ? *one : '/';\n+\tc2 = *two ? *two : '/';\n+\n+\tif (c1 == c2) {\n+\t\t/* Getting here means one is a leading directory of the other */\n+\t\treturn (*one) ? 1 : -1;\n+\t} else\n+\t\treturn c1 - c2;\n }\n \n static int read_oid_strbuf(struct merge_options *opt,\n@@ -3481,7 +3508,7 @@ static void process_entries(struct merge_options *opt,\n \ttrace2_region_leave(\"merge\", \"plist copy\", opt->repo);\n \n \ttrace2_region_enter(\"merge\", \"plist special sort\", opt->repo);\n-\tplist.cmp = string_list_df_name_compare;\n+\tplist.cmp = sort_dirs_next_to_their_children;\n \tstring_list_sort(&plist);\n \ttrace2_region_leave(\"merge\", \"plist special sort\", opt->repo);\n \n-- \ngitgitgadget\n\n"},{"id":"426787","messageId":"55c0f2c4560a5361979f3fac52e19b720036fe79.1623168703.git.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.v4.git.1623168703.gitgitgadget@gmail.com","subject":"[PATCH v4 3/4] Fix various issues found in comments","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-08T16:11:41Z","receivedAt":"2021-06-08T16:13:01Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nA random hodge-podge of incorrect or out-of-date comments that I found:\n\n * t6423 had a comment that has referred to the wrong test for years;\n fix it to refer to the right one.\n * diffcore-rename had a FIXME comment meant to remind myself to\n investigate if I could make another code change. I later\n investigated and removed the FIXME, but while cherry-picking the\n patch to submit upstream I missed the later update. Remove the\n comment now.\n * merge-ort had the early part of a comment for a function; I had\n meant to include the more involved description when I updated the\n function. Update the comment now.\n\nSigned-off-by: Elijah Newren \nReviewed-by: Derrick Stolee \n---\n diffcore-rename.c | 2 +-\n merge-ort.c | 8 +++++---\n t/t6423-merge-rename-directories.sh | 2 +-\n 3 files changed, 7 insertions(+), 5 deletions(-)\n\ndiff --git a/diffcore-rename.c b/diffcore-rename.c\nindex e333a6d64791..35378d84e8f1 100644\n--- a/diffcore-rename.c\n+++ b/diffcore-rename.c\n@@ -1543,7 +1543,7 @@ void diffcore_rename_extended(struct diff_options *options,\n \t\t\t/* all the usual ones need to be kept */\n \t\t\tdiff_q(&outq, p);\n \t\telse\n-\t\t\t/* no need to keep unmodified pairs; FIXME: remove earlier? */\n+\t\t\t/* no need to keep unmodified pairs */\n \t\t\tpair_to_free = p;\n \n \t\tif (pair_to_free)\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 061f15701359..2ec382e292a6 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -2533,7 +2533,7 @@ static int compare_pairs(const void *a_, const void *b_)\n \treturn strcmp(a->one->path, b->one->path);\n }\n \n-/* Call diffcore_rename() to compute which files have changed on given side */\n+/* Call diffcore_rename() to update deleted/added pairs into rename pairs */\n static void detect_regular_renames(struct merge_options *opt,\n \t\t\t\t unsigned side_index)\n {\n@@ -2586,8 +2586,10 @@ static void detect_regular_renames(struct merge_options *opt,\n }\n \n /*\n- * Get information of all renames which occurred in 'side_pairs', discarding\n- * non-renames.\n+ * Get information of all renames which occurred in 'side_pairs', making use\n+ * of any implicit directory renames in side_dir_renames (also making use of\n+ * implicit directory renames rename_exclusions as needed by\n+ * check_for_directory_rename()). Add all (updated) renames into result.\n */\n static int collect_renames(struct merge_options *opt,\n \t\t\t struct diff_queue_struct *result,\ndiff --git a/t/t6423-merge-rename-directories.sh b/t/t6423-merge-rename-directories.sh\nindex be84d22419d9..e834b7e6efe0 100755\n--- a/t/t6423-merge-rename-directories.sh\n+++ b/t/t6423-merge-rename-directories.sh\n@@ -454,7 +454,7 @@ test_expect_success '1f: Split a directory into two other directories' '\n # the directory renamed, but the files within it. (see 1b)\n #\n # If renames split a directory into two or more others, the directory\n-# with the most renames, \"wins\" (see 1c). However, see the testcases\n+# with the most renames, \"wins\" (see 1f). However, see the testcases\n # in section 2, plus testcases 3a and 4a.\n ###########################################################################\n \n-- \ngitgitgadget\n\n"},{"id":"426788","messageId":"6de569e6ac492213e81321ca35f1f1b365ba31e3.1623168703.git.gitgitgadget@gmail.com","threadId":"55781","inReplyTo":"pull.962.v4.git.1623168703.gitgitgadget@gmail.com","subject":"[PATCH v4 4/4] merge-ort: miscellaneous touch-ups","fromName":"Elijah Newren via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2021-06-08T16:11:42Z","receivedAt":"2021-06-08T16:13:07Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"From: Elijah Newren \n\nAdd some notes in the code about invariants with match_mask when adding\npairs. Also add a comment that seems to have been left out in my work\nof pushing these changes upstream.\n\nSigned-off-by: Elijah Newren \nReviewed-by: Derrick Stolee \n---\n merge-ort.c | 5 +++++\n 1 file changed, 5 insertions(+)\n\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 2ec382e292a6..cfa751053b01 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -765,6 +765,7 @@ static void add_pair(struct merge_options *opt,\n \tint names_idx = is_add ? side : 0;\n \n \tif (is_add) {\n+\t\tassert(match_mask == 0 || match_mask == 6);\n \t\tif (strset_contains(&renames->cached_target_names[side],\n \t\t\t\t pathname))\n \t\t\treturn;\n@@ -772,6 +773,8 @@ static void add_pair(struct merge_options *opt,\n \t\tunsigned content_relevant = (match_mask == 0);\n \t\tunsigned location_relevant = (dir_rename_mask == 0x07);\n \n+\t\tassert(match_mask == 0 || match_mask == 3 || match_mask == 5);\n+\n \t\t/*\n \t\t * If pathname is found in cached_irrelevant[side] due to\n \t\t * previous pick but for this commit content is relevant,\n@@ -3477,6 +3480,8 @@ static void process_entry(struct merge_options *opt,\n \t */\n \tif (!ci->merged.clean)\n \t\tstrmap_put(&opt->priv->conflicted, path, ci);\n+\n+\t/* Record metadata for ci->merged in dir_metadata */\n \trecord_entry_for_tree(dir_metadata, path, &ci->merged);\n }\n \n-- \ngitgitgadget\n"}]}